Questions tagged [na.numerical-analysis]

Numerical algorithms for problems in analysis and algebra, scientific computation

Filter by
Sorted by
Tagged with
0 votes
0 answers
27 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
  • 676
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-...
Felix Goldberg's user avatar
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}^{\...
poeaqnwgo's user avatar
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$. ...
Ma Joad's user avatar
  • 1,591
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 ...
gmvh's user avatar
  • 2,758
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 ...
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
  • 199
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 ...
AChem's user avatar
  • 803
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 ...
Rule's user avatar
  • 1
-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 ...
ironmanaudi's user avatar
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 ...
ironmanaudi's user avatar
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 ...
NancyBoy's user avatar
  • 175
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 ...
Redsbefall's user avatar
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. ...
Paul R's user avatar
  • 39
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 ...
Bogdan's user avatar
  • 1,330
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(...
Spencer Kraisler's user avatar
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 ...
knuth's user avatar
  • 29
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 ...
poeaqnwgo's user avatar
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 ...
poeaqnwgo's user avatar
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\...
0xbadf00d's user avatar
  • 161
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}{\...
David G.'s user avatar
  • 111
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 ...
Nate River's user avatar
  • 4,802
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{...
Aaron Hendrickson's user avatar
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 ...
Paul R's user avatar
  • 39
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$ $$ ...
leo monsaingeon's user avatar
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 ...
Ma Joad's user avatar
  • 1,591
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 ...
Ziamor's user avatar
  • 133
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^...
Alex Joe's user avatar
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 ...
amilton moreira's user avatar
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 ...
Hao Yu's user avatar
  • 771
0 votes
0 answers
69 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-...
Hao Yu's user avatar
  • 771
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{ ...
tommy1996q's user avatar
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}...
Yi_Feng's user avatar
  • 47
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}~(\...
qmww987's user avatar
  • 49
1 vote
1 answer
110 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
  • 2,758
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 ...
AChem's user avatar
  • 803
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}...
noon's user avatar
  • 11
6 votes
0 answers
176 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 ...
mtheorylord's user avatar
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: #######...
Phasefieldlover's user avatar
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 ...
gmvh's user avatar
  • 2,758
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 ...
Enea Olati's user avatar
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 ...
Mauro Giliberti's user avatar
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}$, ...
user918212's user avatar
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. ...
Redsbefall's user avatar
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 ...
eepperly16's user avatar
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 ...
roignoirewg's user avatar
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}...
yaoxiao's user avatar
  • 1,654
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 ...
muddy's user avatar
  • 69
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 ...
Daniele Tampieri's user avatar
1 vote
0 answers
87 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 ...
Ganymed_'s user avatar

1
2 3 4 5
25