Questions tagged [na.numerical-analysis]

Numerical algorithms for problems in analysis and algebra, scientific computation

394 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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 ...
Malkoun's user avatar
  • 4,991
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 ...
Mikhail Skopenkov's user avatar
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 ...
Christopher A. Wong's user avatar
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 - \...
Suvrit's user avatar
  • 28.4k
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 ...
gondolier's user avatar
  • 1,829
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 ...
Maritza Sirvent's user avatar
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)}$$ ...
user3628's user avatar
  • 265
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 ...
Yuval Filmus's user avatar
  • 1,886
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 ...
arbitUser1401's user avatar
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 \...
Mikhail_K's user avatar
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 ...
Manuel Schmidt's user avatar
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 ...
mtheorylord's user avatar
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 ...
BabaUtah's user avatar
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}|\...
H A Helfgott's user avatar
  • 19.3k
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 ...
gmvh's user avatar
  • 2,758
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 ...
Chilote's user avatar
  • 586
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 ...
Turbo's user avatar
  • 13.7k
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 ...
Sergio Almada's user avatar
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 - ...
user17119's user avatar
  • 179
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 ...
lcv's user avatar
  • 496
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+...
Wane's user avatar
  • 73
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 ...
Zinkin's user avatar
  • 491
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 ...
noncom's user avatar
  • 151
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 ...
Turbo's user avatar
  • 13.7k
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(\...
Kiran Parkhe's user avatar
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)$? ...
James Propp's user avatar
  • 19.4k
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$ ...
Andrei MF's user avatar
  • 692
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 -...
Jeff's user avatar
  • 500
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 \...
H. Arponen's user avatar
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 ...
Michael Hardy's user avatar
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$ ...
Navin Goyal's user avatar
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 ...
H A Helfgott's user avatar
  • 19.3k
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). $$ ...
AatG's user avatar
  • 922
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 ...
Nilima Nigam's user avatar
  • 1,161
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_{\...
eepperly16's user avatar
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 ...
poeaqnwgo's user avatar
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)$, ...
skdys's user avatar
  • 141
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)}^...
Drew Brady's user avatar
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 ...
Aidan Backus's user avatar
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 ...
Foivos's user avatar
  • 345
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 $\...
Aidan Rocke's user avatar
  • 3,827
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 ...
Austen's user avatar
  • 1,038
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}{...
Salvatore Baldino's user avatar
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, ...
Wrzlprmft's user avatar
  • 202
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 ...
DCM's user avatar
  • 778
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 ...
cfp's user avatar
  • 183
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. ...
Joseph O'Rourke's user avatar
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 ...
aenima's user avatar
  • 41
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-...
Hunter's user avatar
  • 215

1
2 3 4 5
8