Questions tagged [na.numerical-analysis]
Numerical algorithms for problems in analysis and algebra, scientific computation
1,218
questions
0
votes
0
answers
33
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 ...
0
votes
0
answers
43
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-...
0
votes
1
answer
52
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}^{\...
1
vote
0
answers
41
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$. ...
1
vote
0
answers
28
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
...
1
vote
0
answers
110
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 ...
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)$ ...
1
vote
1
answer
255
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 ...
0
votes
0
answers
29
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 ...
-1
votes
1
answer
159
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 ...
3
votes
2
answers
473
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 ...
0
votes
0
answers
30
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
...
0
votes
0
answers
40
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 ...
1
vote
2
answers
181
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.
...
0
votes
0
answers
47
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 ...
1
vote
0
answers
47
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(...
1
vote
0
answers
174
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 ...
3
votes
1
answer
265
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 ...
4
votes
0
answers
188
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 ...
2
votes
0
answers
63
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\...
0
votes
1
answer
32
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}{\...
1
vote
1
answer
173
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 ...
2
votes
0
answers
121
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{...
0
votes
1
answer
124
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 ...
1
vote
0
answers
49
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$
$$
...
0
votes
0
answers
49
views
Is polynomial interpolation with RKHS in some way more advantageous than simple Lagrange interpolation?
[Question originally posted here but maybe it is more suitable for this site.]
The reproducing kernel Hilbert space associated with the polynomial kernel $K(x,z)=(1+xz)^{d-1}$ (or other similar ...
3
votes
1
answer
172
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 ...
2
votes
1
answer
130
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^...
2
votes
0
answers
67
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 ...
0
votes
0
answers
26
views
Convergence bound for zero-order optimization method
I would like to understand the error bound for a particular zero-order optimization method: (stochastic) difference method.
To solve an nonsmooth optimization problem $min_x G(x)$ where $G$ is only a ...
0
votes
0
answers
70
views
Error bound for stochastic gradient descent method
To solve an optimization problem $\min_x G(x)$ using standard stochastic gradient descent method, we let $x_0$ be the initial point and $x_k$ be the $k$-th point such that
\begin{equation}
x_k = x_{k-...
3
votes
0
answers
111
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{ ...
1
vote
0
answers
39
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}...
1
vote
0
answers
135
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}~(\...
1
vote
1
answer
111
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 ...
0
votes
2
answers
115
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 ...
1
vote
0
answers
100
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}...
6
votes
0
answers
178
views
Newton type method for finite fields?
I have a polynomial $p(x)$ in $\mathbb{Z}/q\mathbb{Z}$ that is easy to compute for any $x$ but has an absurdly large degree $d > 2^{256}$. I know for a fact that it has a zero and I would like to ...
0
votes
0
answers
32
views
Quadrature error estimates for $n$-rectangular finite elements in the context of elliptic second order problems
In Ciarlet's book "Finite Element Methods for Elliptic Problems" from 1978, in Chapter 4.1 "The Effect of Numerical Integration", the following Theorem is stated and proved:
#######...
8
votes
2
answers
1k
views
Is quadrature still considered part of numerical analysis?
This question may admittedly sound strange, but having received several desk-rejects (all of them being based on being "out of scope" for the journal in question) from numerical analysis ...
2
votes
1
answer
149
views
Product of a vector by an inverse of Toeplitz matrix
It is well known that using fast Fourier transform it's possible to multiply a vector by a Toeplitz matrix $A \cdot v = w$ in $n\cdot\log(n)$ operations.
I read somewhere that also the product of a ...
0
votes
0
answers
19
views
Numerical solution to partially-free boundary optimization problem
Background
First of all, I'm a PhD physicist working in numerical analysis, so I apologize for possible easy-to-spot mistakes (they're most likely not that easy for me).
The problem I'm trying to ...
1
vote
1
answer
82
views
The distance between a collection of points and a sequence of sets
Fix $m \geq 2$, and consider a sequence of sets
$$
J_m^{(n)} = \left\{ \frac{2}{mn}+\frac{i-1}{n}\right\}_{i=1}^n.
$$
For any collection of $m-1$ points $x_1,...,x_{m-1} \in (0, 1)\cap \mathbb{Q}$, ...
0
votes
1
answer
133
views
Where can I find the paper by Tappert and Hardin on split-step Fourier transform method?
The split-step method is a numerical method that can be used to solve a nonlinear PDE (https://en.wikipedia.org/wiki/Split-step_method). Even Wikipedia does not refer to the original authors (F.D. ...
1
vote
0
answers
57
views
Backward stability of the SVD
I am interested in the backward stability of numerical algorithms for computation of the singular value decomposition (SVD). Specifically, I am interested in the following result:
Backward stabile ...
2
votes
0
answers
118
views
Extensions of Euler–Maclaurin formula
There are ways to approximate a sum through integration like the Euler–Maclaurin formula, which requires the function $f(x)$ to be continuous, but there are several ways to extend the formula to ...
0
votes
0
answers
77
views
Non-triviality of the sum of simple rational functions
Recently, in the study of unicity problems in complex analysis, I met a problem that can be stated in the following way,
Let $\{m_i\}_{i=0}^{3}$ and $\{n_i\}_{i=0}^{3}$ be eight integers in $\mathbb{Z}...
1
vote
0
answers
40
views
Computational comparison in solving two optimization problems
Can I get some inputs on whether the following two optimization problems are computationally the same, or one of the problems is easier to solve computationally than the other, such as, finding their ...
6
votes
1
answer
599
views
On a fast high precision numerical analysis C library
This is probably a $y=f(x)$ question, but I searched several times on the MathOverflow without success so I decided to explicitly ask for the help of other members: please feel free to ask me to ...
1
vote
0
answers
88
views
Numerical strategies for evaluating a modular invariant infinite sum
I'm working on a problem that involves the numerical evaluation of the following infinite sum:
$$
\sum_{m=-\infty}^{\infty} \ln \left|1\pm e^{-2\pi \tau_1 \sqrt{m^2+x^2/(4\pi^2\tau_1)}-2 \pi i \tau_0 ...