Questions tagged [na.numerical-analysis]
Numerical algorithms for problems in analysis and algebra, scientific computation
394
questions with no upvoted or accepted answers
19
votes
0
answers
830
views
I found a (probably new) family of real analytic closed Bezier-like curves; is it publishable?
Given $n$ distinct points $\mathbf{x} = (\mathbf{x}_1, \ldots, \mathbf{x}_n)$ in the plane $\mathbb{R}^2$, I associate a real analytic map:
$f_{\mathbf{x}}: S^1 \to \mathbb{R}^2$
with the following ...
15
votes
0
answers
385
views
References on Discrete field theory vs Discrete differential geometry vs Combinatorial topology
Let me ask several related questions on discretization of classical field theory:
In topological folklore, it is known that cochains are "discrete analogues" of differential forms, and coboundary ...
13
votes
0
answers
566
views
What are the difficulties in proving almost-everywhere stability of Gaussian elimination?
It is well known that Gaussian elimination without pivoting is numerically unstable, and in practice Gaussian elimination is done with row pivoting (partial pivoting). A theorem of Wilkinson states ...
13
votes
0
answers
455
views
Descartes rule of signs for a noncommutative polynomial in matrix variables
Recently, while studying certain notions of "averaging" a set of input matrices, I obtained a nonlinear polynomial in matrix variables. A simple example is
\begin{equation*}
\mathcal{G}(X) := X^n - \...
13
votes
0
answers
1k
views
Constructive aspects of Caratheodory's theorem in convex analysis
Let me paraphrase Caratheodory's theorem in a probabilistic setup:
Let $X$ be a real-valued random variable. For $k = 1, \ldots, m$, let $f_k: \mathbb{R} \to \mathbb{R}$ be a continuous function such ...
12
votes
0
answers
595
views
Once differentiable, piecewise degree three polynomials on triangulated planar domains
Here is an easily described, but very difficult, problem that I
(and a number of other people) really would like to see solved during
our life times. The basic problem is to compute the dimension of ...
10
votes
0
answers
436
views
Evaluating Shintani cone zeta functions
Hi everyone
I am trying the evaluate sums of the form
$$ \sum_{n_1>0,n_2>0,\ldots,n_m>0} \frac{1}{\big((a_{1,1}n_1 +\ldots +a_{1,m}n_m)^k \ldots (a_{m,1}n_1+ \ldots +a_{m,m}n_m)^k\big)}$$
...
9
votes
0
answers
546
views
Padé approximations of $e$
The following question came up in the analysis of some algorithm.
Let $R_{s,t}(z)$ be the Padé approximants of $e^z$, and define $r_{s,t} = R_{s,t}(1)$. Using the explicit expression for the error ...
8
votes
0
answers
450
views
Problems where Conjugate gradient works much better than GMRES
I am interested in cases where Conjugate gradient works much better than GMRES method.
In general, CG is preferable choice in many cases of SPD because it requires less storage and theoretical bound ...
7
votes
0
answers
311
views
An inequality which involves a sum of integrals
Please help me to prove
$$
\sum\limits_{j=2}^n \frac{1}{j^\alpha (j-1)^\alpha} \int\limits_{j-1}^j \frac{dx}{x^{1-\alpha}(n-x)^\alpha} \leq \int\limits_0^1 \frac{dx}{x^{1-\alpha}(n-x)^\alpha},\quad \...
7
votes
0
answers
208
views
Numerical linear algebra: how to compute $B^TC^{−1}B$ efficiently
Hi,
my question is similar to this one. I have to compute $B^TC^{−1}B$, where $C$ is a strictly positive definite $n\times n$ matrix and $B$ is $n\times m$.
The matrix $C$ is huge ($n$ up to a ...
6
votes
0
answers
188
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 ...
6
votes
0
answers
123
views
Why wavelet methods are not popular anymore in nonparametric statistics?
Back in my master years, I took a nonparametric statistics class. In this class, a few nonparametric methods were presented, but I remember spending a lot of times on methods based on wavelet ...
6
votes
0
answers
196
views
Where to cut off a double sum?
I have to compute a double infinite sum to within a given accuracy $\epsilon$. Let us say the sum is of the form
$$\sum_{m\geq 1} \sum_{n\geq 1} \frac{a_{m,n}}{m^2 n^2 \max(m,n)},$$
where $|a_{m,n}|\...
6
votes
0
answers
374
views
Numerical analysis with p-adic numbers
How should one go about doing numerical analysis with $p$-adic numbers?
By that I mean, how should one go about implementing numerical integration (using analogues of Newton-Cotes or perhaps Gaussian ...
6
votes
0
answers
306
views
Can we approximate any eigenvalue of an infinite matrix via eigenvalues of some sequence of submatrices which approximates the matrix?
Let $T:\ell^2\to\ell^2$ be a compact linear operator. Let $[T]=(a_{i,j})_{i,j=1}^{\infty}$ be the representing infinite matrix of $T$ with respect to the canonical base. Let $T_n$ be the finite rank ...
6
votes
0
answers
206
views
Degree of Chebyshev polynomial necessary
In general, given $0<a<1$, I want to find a polynomial $f(x)\in\Bbb R[x]$ such that $f(x)\in[1-\frac{a}2,1+\frac{a}2]$ at every $x\in[1-a,1+a]$ and $f(0)=0$. What is minimum degree that is ...
6
votes
0
answers
377
views
Numerical Methods for stochastic PDE, from rough paths to backward equations
this question is about some literary references regarding the state of the art in terms of numerical methods for SPDE's. In particular,
Have the numerical implications, if any, of the results in ...
6
votes
0
answers
549
views
What are the eigenvectors of the Lagrange interpolation matrix?
Let $F$ be a field.
Let $x_1,\ldots,x_k,y_1,\ldots,y_k\in F$ be distinct elements in the field.
Consider the $k\times k$ matrix that in position $i$, $j$ has the element
$\frac{\prod_{l\neq i}(y_i - ...
5
votes
0
answers
168
views
Numerical analytic continuation/asymptotics
I posted this question, quite a while ago, on math.stackexchange.com, here. I received an interesting answer but not sufficiently accurate for my purposes, so I'm trying here.
I have a class of ...
5
votes
0
answers
224
views
Validity of $\ln z=\frac{\pi}{\operatorname{AGP}(\theta_2^2(1/z),\theta_3^2(1/z))}$
Definitions
For the definitions of $\operatorname{AGP}$ and $\operatorname{AGO}$, see here or here. $\theta_2(z)$ and $\theta_3(z)$ are defined as follows:
$$\theta_2(z)=\sum_{n=-\infty}^\infty z^{(n+...
5
votes
0
answers
77
views
Numerical and computational approaches to limit cycle theory
I am searching for a big list of papers or researches devoted to limit cycles of planar polynomial vector fields based on a computational and numerical approach.
I would like to ask ...
5
votes
0
answers
121
views
How to solve this operator equation numerically?
I would like to know how one solves Sturm-Liouville problems on $(0,\infty)$ NUMERICALLY for the eigenvalues that are of the form
$$-f''(x)+\frac{1}{\sinh(x)^2}f(x)=\lambda f(x).$$
So even if there ...
5
votes
0
answers
2k
views
Find the axis of symmetry in a point cloud
I have some dataset which describes a spherical cloud of points in 4D space. Actually, the coordinates of the points are the coefficients of unit quaternions, so you get the idea on what the data is ...
5
votes
0
answers
130
views
On existence of rapid Arithmetic geometric procedure?
We know that $\pi$ can be computed by Arithmetic Geometric mean using Gauss-Legendre procedure which does provide fastest convergence rate as well with a guarantee of $2^n$ bits of $\pi$ at $n$th ...
5
votes
0
answers
156
views
Hyperbolic toral automorphisms, and maximizing over orbits the minimum along an orbit of a function
Setup:
Let $\phi\colon T^2 \to T^2$ be a hyperbolic toral automorphism. Let $f\colon T^2 \to \mathbb{R}$ be a continuous function.
For $x \in T^2$, let $\underline{f}(x) = \inf_{n \in \mathbb{Z}} f(\...
5
votes
0
answers
141
views
Error of midpoint method for differentiable functions
Is it the case that for every differentiable function $f$ on $[0,1]$ (with finite one-sided derivatives at the endpoints), the midpoint method of estimating $\int_0^1 f(x) \: dx$ has error $o(1/n)$?
...
5
votes
0
answers
1k
views
Computing a 2D Fourier transform on a disk
I am looking for a reliable and fast way of evaluating an integral like
$$
F(r, \phi)= \int_0^1 \int_0^{2\pi} f(\rho, \theta) e^{2\pi i \rho r \cos(\theta - \phi)}\rho\, d\theta\,d\rho,
$$
where $f$ ...
5
votes
0
answers
380
views
Preconditioner for finding the smallest eigenpairs of a large, but structured, matrix
I'm trying to find the eigenvector corresponding to the second smallest eigenvalue of a large $(4,000,000 \times 4,000,000)$ matrix $L$. $L$ is a graph Laplacian, with the following structure: $L = D -...
5
votes
0
answers
184
views
Pair of two-variable polynomial equations of high order
I have the following pair of equations to be solved for two variables $\rho$ and $D$ resulting from a certain Maximum Likelihood Estimation for a time series $X_n > 0$, $n=0, \ldots, N+1$ with $N \...
5
votes
0
answers
300
views
Inadmissibility of Simpson's rule
(An earlier version of this at stackexchange got no answers.)
Bayesianism says that all uncertainties, or at least all uncertainties about the truth or falsity of propositions, can be expressed by ...
5
votes
0
answers
321
views
Approximation by polynomials
The following is a well-known theorem (see e.g. The Chebyshev Polynomial by Rivlin):
If $p(x) = x^n + a_{n_1} x^{n-1} + \ldots + a_0$, then $\max_{-1\leq x \leq 1} |p(x)| \geq 2^{1-n}$ for $n \geq 1$ ...
5
votes
0
answers
494
views
Parabolic cylinder functions - explicit estimates?
I need estimates for the parabolic cylinder functions $U(a,z)$ (first studied by Whittaker).
Most work in the literature focuses on $a$ real. As it happens, I am interested in $U(a,z)$ on a strip in ...
5
votes
0
answers
158
views
reference for perturbation of projection result
Let $A$ and $B$ have the same rank and dimensions. If $P_A$ denotes the projection onto the range space of $A$, then
$$
\|P_A - P_B\|_2 \leq \|A - B\| \cdot \min (\|A^\dagger\|_2, \|B^\dagger\|_2).
$$
...
5
votes
0
answers
400
views
Approximations of negative Sobolev norms
Consider the standard Cahn-Hilliard free energy, augmented by a nonlocal interaction term which measures the $H^{-1}$ norm of a zero-mean function. Could someone point me to a reference where this ...
5
votes
1
answer
119
views
Is Sun's spectral variation bound for normal matrices optimal?
In On the variation of the spectrum of a normal matrix, Sun proves the following result (Corollary 1.2):
Let $A$ be an $n$-square normal matrix and $B$ an arbitrary $n$-square matrix. Then $$ \min_{\...
4
votes
0
answers
192
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 ...
4
votes
0
answers
431
views
What is the computational complexity of Arnoldi algorithm for diagonalization?
What is the space and time computational complexity of finding $k$ eigenvalues of an $N\times N$ matrix using the iterative Arnoldi algorithm?
I know that exact diagonalization scales like $O(N^3)$, ...
4
votes
0
answers
98
views
Interpolation on Sobolev space on $[0, 1]^d$ over finite meshes
Let $\Omega = [0, 1]^d$ and suppose that $f \colon \Omega \to \mathbb{R}$ lies in order $m > d/2$ Sobolev space; i.e.,
$$
\|f\|_{H^m(\Omega)}^2 = \sum_{|\alpha| \leq m} \|D^\alpha f\|_{L^2(\Omega)}^...
4
votes
0
answers
108
views
How can I numerically solve the Laplace equation with cohomological data?
Consider the problem of solving for $u$ where $-\Delta u = f$, $[u] = [g]$ where $[\cdot]$ denotes cohomology class and $u, f, g$ are $p$-forms on a Riemannian manifold $M$. If $g$ instead was ...
4
votes
0
answers
382
views
Intrinsic numerical methods on Riemannian manifolds
I am interested in numerical methods for ordinary differential equations on a Riemannian manifold $M$. The general form of such an equation is $\dot x(t)=V(x(t)), x(0)=x_0 \in M$, where $V$ is a ...
4
votes
0
answers
479
views
analytic approximations of the min and max operators
Question:
What is the state of the art on analytic approximations of $\min$ and $\max$? My hunch is that numerical analysts probably have a better solution than the one I propose here.
For any $\...
4
votes
0
answers
436
views
Numerical evaluation of KL divergence for SDE
Consider the SDE
$$
dX_t = v(X_t)dt + dW_t
$$
where $W_t$ is a standard Brownian motion. Girsanov's theorem tells us that the Radon-Nikodym derivative of the measure $\mathbb{P}_v$ of $X_t$ with ...
4
votes
0
answers
92
views
Convergence acceleration of successions with logarithms
I have a numerical question regarding acceleration of a succession.
A preliminary: suppose that I have a succession $a_g$ that, for high $g$, asymptotically goes as
$$
a_g=s_0+\frac{s_1}g+\frac{s_2}{...
4
votes
0
answers
266
views
For noisy or fine-structured data, are there better quadratures than the midpoint rule?
Only the first two sections of this long question are essential. The others are just for illustration.
Background
Advanced quadratures such as higher-degree composite Newton–Cotes, Gauß–Legendre, ...
4
votes
0
answers
227
views
Optimisation over $SO(3)$: is it safe to use a global parametrisation?
I am a functional analyst by training, but I am doing some numerical experiments which require me to minimise continuous functions $f:SO(3)\longrightarrow [0,+\infty)$ using a computer (I know that ...
4
votes
0
answers
282
views
When (if ever) are the weights from Smolyak (sparse grid) cubature positive?
Are there any $1$-dimensional quadrature rules of arbitrary accuracy, on either $[0,1]$ or $\mathbb{R}$, with any non-trivial weight function, such that the associated $N$-dimensional cubature rule ...
4
votes
0
answers
146
views
Connection between cardiac equations and untangling knots?
I was surprised to learn that there is (conjecturally) a connection between a cardiac muscle model known as the FitzHugh-Nagumo equations, and untangling knots:
Maucher, Fabian, and Paul Sutcliffe. ...
4
votes
0
answers
468
views
Efficiently calculate the trace of the product of two large but symmetric matrices, one of which is an inverse
Sorry about the long title. I need to calculate the trace of $M(M+D)^{-1}$, where $M$ is a dense symmetric matrix, and $D$ is a diagonal matrix. The main issue is the dimension could be large (usually ...
4
votes
0
answers
688
views
What does the Von Neumann's stability analysis tell us about non-linear finite difference equations?
I've asked this question on computation science stackexchange, but it did not receive any answers so I have decided to ask it here as well.
I am reading a paper [1] where they solve the following non-...