Skip to main content

All Questions

Filter by
Sorted by
Tagged with
0 votes
0 answers
98 views

Interpolation polynomials with constraints

Lets consider a collection of $n$ points $\{Z_i\}_{i=1}^n\subseteq \mathbb{D}^k(1)=\{(z_1,\ldots,z_k)\in\mathbb{C}^k:\forall j\leq k, |z_j|\leq 1\}$. Let $h: \{Z_i\}_{i=1}^n \to \mathbb{D}^1(1)$ be a ...
JustSomeGuy's user avatar
4 votes
0 answers
46 views

Implementation of Friedman's algorithm of reconstructing simple polytopes

In Finding a Simple Polytope from Its Graph in Polynomial Time, Friedman gave a polynomial time algorithm on reconstructing a simple polytope from its graph. Has this algorithm been actually ...
mashedcarrots's user avatar
1 vote
0 answers
60 views

Galerkin’s Method for hyperbolic PDEs: proving convergence without using compactness

Lawrence Evan's PDE book prove the existence of solution to the following problem where $L$ is an elliptic operator: $$ \begin{cases} u_{tt} = -Lu+f,\\ u|_{t=0} = u_0,\\ u|_{\partial U} = 0 \end{cases}...
Ma Joad's user avatar
  • 1,755
2 votes
1 answer
158 views

Are the coefficients in the stationary phase approximation computed explicitly somewhere

In Stein's "Harmonic analysis" book, page 334, one can find the asymptotic expansion An instructive proof is given for the case $k=2$. It is clear enough to generalize to the cases $k\geq ...
Medo's user avatar
  • 852
0 votes
0 answers
67 views

Concentration of bilinear forms

This is a bit vague so I'll begin by indicating the motivation. I am looking for ways to [do something interesting or useful] with the self-attention in transformer models. Ultimately the self-...
Felix Goldberg's user avatar
0 votes
0 answers
39 views

Max-flow modeling with unified vehicle and commodity variables

I am working on a network flow problem that involves routing through a time-space network. The network consists of: A single source node and a single demand node. A fleet of vehicles with specified ...
graphtheory123's user avatar
0 votes
1 answer
58 views

Integration algorithm and analytic property

This question is the continuation of the previous one. In the article about the integration of analytical polynomial - time computable function $f(x)$ with the Taylor series $$f(x) = \sum_{n=0}^{\...
poeaqnwgo's user avatar
1 vote
0 answers
92 views

Computing smallest singular value of a matrix with explicit error control?

Many good algorithms are out there computing truncated SVD: What is the time complexity of truncated SVD?. I am trying to implement some codes to find the smallest singular value of a big matrix $A$. ...
Ma Joad's user avatar
  • 1,755
1 vote
0 answers
44 views

Error bounds for a Romberg-style improvement of a non-linear approximation

I have a (possibly non-linear) functional $F$, which I want to numerically approximate by a (typically non-linear) $\widehat{F}_h$. For a suitable class of functions, I have asymptotic error behaviour ...
gmvh's user avatar
  • 3,065
1 vote
0 answers
126 views

Integration in polynomial time

The work of Friedman and Ko and Müller guarantee the polynomial time computability of the integrals of analytic functions inside the circle of convergence. But do algorithms have practical value? Is ...
poeaqnwgo's user avatar
14 votes
3 answers
2k views

Guaranteed correct digits of elementary expressions

Let $E$ be the set of elementary expressions, defined as the smallest set of mathematical expressions such that $1 \in E$, and if $a,b \in E$ then $a + b$, $a - b$, $ab$, $a/b$, $\exp(a)$, $\log(a)$ ...
rosan98's user avatar
  • 361
0 votes
0 answers
30 views

Application of greedy approach for optimization

I want to maximize an objective given by $$\max_{\{q_n,p_n\}} \sum_{n=0}^\infty (\alpha_1 - \beta_1 n) p_n + (\alpha_2 - \beta_2 n) q_n$$ where $\alpha_1 > \beta_1 >0$ and $\alpha_2 > \beta_2 ...
Prakirt Raj's user avatar
1 vote
1 answer
309 views

Numerical estimation of partial derivatives of convolved functions when closed forms do not exist

Summary: Some peak functions are convolutions which may not have a closed form solution. A classical example can that of a Voigt which is a convolution of a Lorentzian and a Gaussian, followed by ...
ACR's user avatar
  • 879
0 votes
0 answers
34 views

Ensuring symmetry in mixed derivatives using RBF-FD method

I'm working on a numerical problem where I have the first-order partial derivatives $\frac{\partial f}{\partial x}$ and $\frac{\partial f}{\partial y}$ of a bivariate function $f(x, y)$ at a set of ...
Rule's user avatar
  • 1
-1 votes
1 answer
214 views

Best approximation of the modulus function

While there is extensive study regarding the best approximation of function with polynomial functions in the real domain, the study of approximation of complex variables becomes much sparse. See this ...
ironmanaudi's user avatar
4 votes
3 answers
682 views

Approximation for complex variables

Approximation theory, which aims to provide the optimal polynomial function approximating the target function in a given domain such as $x\in[-1,1]$, has been well-developed for real variables. In ...
ironmanaudi's user avatar
2 votes
1 answer
213 views

Is matrix B obtained from matrix A?

Assuming a matrix $\mathbf{A} \in \mathbb{R}^{4096 \times 4096}$ sampled from a standard normal distribution $N(0, 1)$, and another matrix $\mathbf{B} \in \mathbb{R}^{4096 \times 4096}$ either sampled ...
eternity's user avatar
0 votes
0 answers
36 views

Convergence of numerical scheme for HJB equation

Convergence of numerical scheme for HJB equation has been widely studied, the key paper is the Barles's one. Essentially, the convergence is guarenteed if the scheme is: Consistent Stable Monotony ...
NancyBoy's user avatar
  • 393
0 votes
0 answers
56 views

Godunov splitting convergence research

The approximation of Godunov splitting on certain differential equations is known to be first order accurate. In 2011, a paper has also shown that it is first order accurate for nonlinear ordinary ...
Redsbefall's user avatar
2 votes
2 answers
272 views

Numerical integration method that doesn't involve derivative in the error bound

Consider the integral $\int_a^b f(t)dt$. There are many numerical integration methods, like trapezoidal rule, Simpson's rule, Gaussian quadrature, but all they involve derivative in the error bound. ...
Paul R's user avatar
  • 49
0 votes
0 answers
36 views

ILPs with square constraint matrix

Given the Integer Linear Programming ($\text{ILP}$) problem \begin{array}{ll} \text{minimize} & c^T x \\ \text{subject to}& \mathbf{A}^T x \ge b \\ \text{where}&c,x,b\in\mathbb{N}_0^n,\\ &...
Manfred Weis's user avatar
  • 13.2k
0 votes
0 answers
87 views

How to solve with FEM a semilinear elliptic equation?

I searched in many books regarding FEM how to solve semilinear elliptic equation, but I did not find too many things. They mostly treat linear and simple problems. For example in P.Ciarlet-The finite ...
Bogdan's user avatar
  • 1,759
1 vote
0 answers
49 views

Computing geodesic length of Euclidean lines in the manifold of positive definite matrices

I am working with the manifold of positive definite matrices $PD(n)$ equipped with the affine-invariant Riemannian metric (AIRM) $g_P(V,W):=tr(P^{-1}VP^{-1}W)$, where $P \in PD(n)$ and $V,W \in T_P PD(...
Spencer Kraisler's user avatar
0 votes
0 answers
26 views

Monotony of enforced subtour merging

Is it true that for a symmetric TSP instance in the sequence of edges generated by successively: calculating the optimal 2-factor adding cardinality constraints on the edgesets of the 2-factor's ...
Manfred Weis's user avatar
  • 13.2k
1 vote
0 answers
183 views

Connection of eigenspace of finite Hilbert matrix and its continuous operator counterpart

I am trying to understand the connection between the eigenspace of the continuous operator $$ H(x,y) = \frac{1}{x+y} $$ which is nothing but the square of the Laplace operator, and its discrete ...
knuth's user avatar
  • 33
0 votes
0 answers
171 views

Solve NP-hard type problems with linear programming

I would like to know if there is any way to solve an NP-hard type problem, for example, the TSP, sum of subsets or knapsack problem, by using linear programming and not by brute force. I ask this ...
Juan Carlos's user avatar
3 votes
1 answer
308 views

Root finding algorithm for an analytic function

Given an analytic function $f(x)$. What is the best algorithm to find roots on the interval $[a,b]$ inside the radius of convergence> What is its complexity with respect to the length of input of ...
poeaqnwgo's user avatar
0 votes
0 answers
64 views

Alternatives to McCormick Envelope

I have an optimization problem for which I have the optimal solution obtained by the ILP. However, when I introduced the McCormick Envelope to replace the product of a bi-linear term in its LP ...
LyLa's user avatar
  • 3
2 votes
0 answers
119 views

Seeking insights on bounded set positive solutions for a set of linear systems in $\mathbb{R}^n$

Before delving into my query, I'd like to provide some context. Consider a continuous function $f:\mathbb{R}^{k}\rightarrow\mathbb{R}^{m}$ and a compact set $\mathcal{B}\subset \mathbb{R}^{k}$ (...
Diego Fonseca's user avatar
4 votes
0 answers
214 views

Computational complexity of zeros of an analytic function

The work of Friedman and Ko, page 342, Corollary 4.3.1 states that all zeros of analytic polynomial time computable function are polynomial time computable, but for me that is not clear how it could ...
poeaqnwgo's user avatar
0 votes
1 answer
169 views

How to integrate an indicator function/constraint into the cost function of a linear program?

I have a mathematical model $P$ for which I optimize two cost functions say $F_1$ and $F_2$ subject to a set of constraints $C1$–$C10$. In $F_2$, I want it to be included only when its expression ...
LyLa's user avatar
  • 3
2 votes
0 answers
68 views

Are there spectral Galerkin methods for PDE of the form $\partial_tu=\nabla\cdot f(\nabla u)\nabla u$?

Question is in the title. The nonlinearity due to the term $f(\nabla u)$ makes it difficult to directly apply the spectral Galerkin method as it can be done for PDE of the form $\partial_tu=\nabla\...
0xbadf00d's user avatar
  • 167
0 votes
1 answer
40 views

How to handle the evaluation of functions on staggered ghost nodes?

I have a convection-diffusion-reaction steady state PDE in the form $$ \frac{\partial C}{\partial x} = \frac{1}{u_0(x)}\left(\frac{\partial}{\partial z} \left( \mathcal{D}(z) \frac{\partial C}{\...
David G.'s user avatar
  • 111
1 vote
1 answer
184 views

Average distance between points of lower dimensional simplices in $\mathbb R^n$

Notation: By a simplex, we mean the convex hull of a finite set of distinct points in $\mathbb R^n$, which are called the vertices of the simplex. $\mathcal H^n$ will denote the $n$-dimensional ...
Nate River's user avatar
  • 6,155
3 votes
0 answers
130 views

Series acceleration for $\sum_{k=0}^\infty\left(\frac{H^k}{k!}\right)^\beta$, $\beta\ll 1$

The probability mass of the Conway-Maxwell-Poisson variable $K$ is given by $$ \mathsf P(K=k)=\frac{1}{Z(H,\beta)}\left(\frac{H^k}{k!}\right)^\beta $$ where $$ Z(H,\beta)=\sum_{k=0}^\infty\left(\frac{...
Aaron Hendrickson's user avatar
0 votes
1 answer
166 views

Matrices and vectors of intervals

I'm working on a project and think that matrices and vectors of intervals will be useful. I'm aware about interval arithmetic, but there is little information on the internet, regarding matrices and ...
Paul R's user avatar
  • 49
0 votes
0 answers
164 views

Inf-convolution of norm 1 and norm 2 square

The inf-convolution of the functions $f$ and $g$ defined on $\mathbb{R}^n$ is $$ h(x)=\inf _{y \in \mathbb{R}^n} f(y)+g(x-y) . $$ We can prove that if $f,g$ are convex functions, then $h$ is convex. ...
Pipnap's user avatar
  • 129
1 vote
0 answers
61 views

Discrete-to-continuum convergence of principal Fokker-Planck eigenvalues

I am looking for a reference justifying the following statement. Let $L^n$ be any "reasonably consistent" finite-difference approximation of the Fokker-Planck operator in dimension $d=1$ $$ ...
leo monsaingeon's user avatar
0 votes
1 answer
28 views

Calculating vertex potentials from optimal matchings

Question: can the solution to the dual of a Linear Program be calculated directly from the solution of the primal Linear Program? If yes, what are known algorithms and their bounds on complexity. As ...
Manfred Weis's user avatar
  • 13.2k
3 votes
1 answer
273 views

Inflection point calculation for cubic Bézier curve encounters division by zero

I've been working on finding the inflection points of a cubic Bezier curve using the method described in a paper Hain, Venkat, Racherla, and Langan - Fast, Precise Flattening of Cubic Bézier Segment ...
Ziamor's user avatar
  • 133
2 votes
1 answer
217 views

How to do LU factorization efficiently based on the factorized result added with a low-rank matrix?

Suppose a square $n\times n$, dense matrix $A^{\text{old}}$ has been factorized into $L^{\text{old}}$ and $U^{\text{old}}$ components by performing a LU decomposition $A^{\text{old}} = L^{\text{old}}U^...
Alex Joe's user avatar
2 votes
0 answers
79 views

Proof of the convergence of the Rayleigh-Ritz Method?

In this article The convergence of the Rayleigh-Ritz Method in quantum chemistry by Bruno Klahn & Werner A. Bingel they have at page 11 Let $H_B$ be that Hilbert space which can be obtained as the ...
amilton moreira's user avatar
4 votes
1 answer
210 views

Is Stokes equation a saddle point problem or a minimum problem?

Consider $\Omega \subset \mathbb{R}^2 $ (or $\mathbb{R}^3$). The well known stationary Stokes equations in the incompressible case are \begin{equation} \begin{cases} - \Delta u + \nabla p = f \text{ ...
tommy1996q's user avatar
1 vote
0 answers
41 views

The boundedness of dynamical systems discretized from Hamiltonian systems

Let $H(p,q) = T(q) + U(p)$ be a Hamiltonian function that defines a Hamiltonian system, i.e., \begin{align} &\frac{dp}{dt} = \frac{\partial H}{\partial q}(p,q) = \frac{dT}{dq},\\ &\frac{dq}{dt}...
Yi_Feng's user avatar
  • 47
1 vote
0 answers
145 views

Complexity of calculating the expectation of $\operatorname{Tr} h(A)$, $A$ is a random matrix

$A$ is a $d_1\times d_1$ random matrix. Given $\{g_i\}~(1\leq i\leq n)$ iid Gaussian variables, $f_{ij}(g_1,g_2,...,g_n)~(1\leq i,j\leq d_1)$ are degree-$d_2$ polynomials. And $f_{ij}\equiv f_{ji}~(\...
qmww987's user avatar
  • 91
1 vote
0 answers
94 views

Linear Program Optimal Value

If $f(A,b,c)$ is the optimal value of a linear program $\min c.x$ subject to $A.x \leq b ; x \geq 0.$ Does $f(A,b,c)$ have a piecewise polynomial/rational upper bound in $(A,b,c)$ on the domain of ...
Pathikrit Basu's user avatar
0 votes
1 answer
114 views

Mixed integer program and continuous Diophantine approximation

Let $n\in\mathbb{N}$ such that $n\geq 2$ and let $0<r<1$ be a real number. We wish to solve the following problem. $$\min_{(t,(z_j)_{j=2}^n) \in \mathbb{R}\times \mathbb{Z}^{n-1}} t$$ subject to ...
Pathikrit Basu's user avatar
1 vote
1 answer
186 views

Practical calculation of Canterbury approximants

I'm looking for references on how to compute Canterbury approximants numerically from a practical point of view. The references on Canterbury approximants that I am aware of all appear rather abstract ...
gmvh's user avatar
  • 3,065
0 votes
2 answers
131 views

Reshaping data vector into a matrix for deconvolution using a circulant matrix

Suppose we have a circulant matrix S made from pseudorandom binary sequence of length $N$ consisting of $0$'s or/and $1$'s. $1$ means that we can inject something for chemical analysis and $0$ means ...
ACR's user avatar
  • 879
1 vote
0 answers
128 views

Resolving singularities in numerical integration

I am now trying to compute numerically the following integral. $$ \begin{split} L_1^s(\hat{\phi}_s)(r,\zeta,\theta_\zeta) &=\frac{1}{\sqrt{2}\pi} \int\limits_{0}^{2\pi} d\varphi \int\limits_0^{\pi}...
noon's user avatar
  • 11

1
2
3 4 5
35