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

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 ...
Perelman's user avatar
  • 143
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 ...
knuth's user avatar
  • 33
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$ ...
Joe Shipman's user avatar
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}...
wsz_fantasy's user avatar
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{\...
Breno's user avatar
  • 111
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) = ...
Joe's user avatar
  • 31
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 ...
JustSomeGuy's user avatar
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}...
Ma Joad's user avatar
  • 1,641
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 ...
Medo's user avatar
  • 744
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-...
Felix Goldberg's user avatar
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}^{\...
poeaqnwgo's user avatar
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$. ...
Ma Joad's user avatar
  • 1,641
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 ...
gmvh's user avatar
  • 2,758
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 ...
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
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 ...
AChem's user avatar
  • 803
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 ...
Rule's user avatar
  • 1
-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 ...
ironmanaudi's user avatar
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 ...
ironmanaudi's user avatar
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 ...
NancyBoy's user avatar
  • 175
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 ...
Redsbefall's user avatar
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. ...
Paul R's user avatar
  • 39
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 ...
Bogdan's user avatar
  • 1,330
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(...
Spencer Kraisler's user avatar
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 ...
knuth's user avatar
  • 33
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 ...
poeaqnwgo's user avatar
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 ...
poeaqnwgo's user avatar
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\...
0xbadf00d's user avatar
  • 161
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}{\...
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,832
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{...
Aaron Hendrickson's user avatar
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 ...
Paul R's user avatar
  • 39
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$ $$ ...
leo monsaingeon's user avatar
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 ...
Ma Joad's user avatar
  • 1,641
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 ...
Ziamor's user avatar
  • 133
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^...
Alex Joe's user avatar
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 ...
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
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-...
Hao Yu's user avatar
  • 771
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{ ...
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
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 ...
gmvh's user avatar
  • 2,758
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 ...
AChem's user avatar
  • 803
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}...
noon's user avatar
  • 11
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 ...
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
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 ...
Enea Olati's user avatar
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 ...
Mauro Giliberti's user avatar

1
2 3 4 5
25