# Questions tagged [na.numerical-analysis]

Numerical algorithms for problems in analysis and algebra, scientific computation

1,226
questions

0
votes

0
answers

27
views

### Galerkin scheme in $H^s_0(G)\subset L^2(G)\subset H^{-s}(G)$ ($s>0$)

What basis functions are usually choosen if one attempts to conduct a Galerkin finite element method given an evolution triplet $H^s_0(G)\subset L^2(G)\subset H^{-s}(G)$. Where $G$ is a sufficiently ...

1
vote

0
answers

55
views

### Discretization of oscillating integral

Suppose I am interested in computing
$$
I \equiv \int_0^B dx \, g(x) f(x)
$$
where $B$ is a known upper bound for the integral,
$g(x)$ is a known oscillating function and
$f(x)$ is a smooth function ...

0
votes

0
answers

126
views

### Antiderivatives via Taylor series and the FT of Calculus

If $f$ is a real function on an interval $[a,b]$ such that
$f$ is computationally tractable on $[a,b]$: you can calculate $f(x)$ to $n$ bits of precision using an algorithm which is polynomial in $n$ ...

1
vote

0
answers

84
views

### Vandermonde-type factorization of moment matrix?

Consider $n,d \in \mathbb{N}_{>0}$, there are many functions $y:\mathbb{N}^{n} \to \mathbb{R}$. Now for simplicity, we denote $y(\alpha)$ to be $y_{\alpha}$. Let $|\alpha| = \sum_{i=1}^{n}\alpha_{i}...

1
vote

0
answers

17
views

### Formulation of multipoint constraints using Lagrange multipliers for a time dependent problem (with the Finite Element Method)

Intro
Suppose we have the following static linear equations (e.g. of an elastostatic problem):
$$\mathbf{K}\boldsymbol{u}=\boldsymbol{f}$$
We want a multipoint constraint of the type
$$\boldsymbol{\...

3
votes

1
answer

112
views

### Converting an algebraic equation into a ODE

I'm working on a method to solve algebraic equations by converting them into ordinary differential equations (ODEs) and then integrating these ODEs over time.
Given an algebraic equation $f(x(t), t) = ...

0
votes

0
answers

73
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 ...

1
vote

0
answers

47
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}...

2
votes

1
answer

136
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

49
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

54
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

44
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

32
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

113
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

277
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

30
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

163
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 ...

4
votes

3
answers

579
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

31
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

45
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

186
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

50
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

48
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

175
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

270
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

193
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

64
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

33
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 ...

3
votes

0
answers

125
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

126
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

52
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

55
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

177
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

139
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

68
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

72
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

118
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

121
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

117
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

103
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

190
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

183
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

20
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 ...