Numerical algorithms for problems in analysis and algebra, scientific computation

**12**

votes

**0**answers

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

**11**

votes

**0**answers

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

**10**

votes

**0**answers

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

**10**

votes

**0**answers

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

**8**

votes

**0**answers

356 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

409 views

### How to evaluate binomial coefficients efficiently and as correctly as possible?

This question is more precisely about evaluation with a computer, of a binomial coefficient of the form $ \binom{x}{m}$ where $x$ is a real number and $m$ a rational integer.
The reason why I ask is ...

**8**

votes

**0**answers

315 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)}$$
...

**7**

votes

**0**answers

505 views

### American put option pricing by “binomial trees”

Dear MO World,
I'm teaching a financial mathematics course and have found a fascinating (to me) numerical phenomenon and wonder if anyone has studied it, or knows anything similar.
I'll try and give ...

**6**

votes

**0**answers

375 views

### Weakest condition for an integrable, almost-symplectic manifold?

I was recently speaking with someone who works in Computational Chemistry and they mentioned that in a lot of the computational simulations they do, they have systems that are not symplectic but still ...

**5**

votes

**0**answers

97 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

253 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

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

**5**

votes

**0**answers

426 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

130 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

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

**4**

votes

**0**answers

344 views

### Linearizing and solving a nonlinear PDE numerically

Im trying to solve the following (transport & diffusion) nonlinear PDE numerically (via finite volume on a cuboid region. Some Material gets cooled down, s.t. in some areas the material becomes ...

**4**

votes

**0**answers

129 views

### About arithmetic-geometric mean

It's well known that if we set $a_0=x \geq 0, \ g_0=y \geq 0$, and
$$ a_{n+1}=\dfrac{1}{2}(a_n+g_n), \ g_{n+1}=\sqrt{a_n g_n} ,$$
then both $\{a_n\}$ and $\{g_n\}$ will converge to $AGM(x,y)$. ...

**4**

votes

**0**answers

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

**4**

votes

**0**answers

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

**4**

votes

**0**answers

136 views

### Are there some numerical test to check if a map is a contraction?

Let's say I have a multivariate function
$$
f:D \to D, D \subset \mathbb R ^n, D \text{ compact},
$$
for which there is no closed form.
That is the only way to evaluate the function is to do it ...

**4**

votes

**0**answers

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

**4**

votes

**0**answers

47 views

### Recovering Shared Eigenvector Set

Suppose we are given a set of $M$ pairs $\{(\vec{x}^{(i)},\vec{y}^{(i)})\}$, with
$\vec{x}^{(i)}\in\mathbb{R}^N$,
$\vec{y}^{(i)}\in\mathbb{R}^N$,
$M\gg N$ such that
$\vec{y}^{(i)} = Q^{(i)} ...

**4**

votes

**0**answers

294 views

### Extreme eigenvalues of real symmetric matrix with main diagonal variance twice non-diagonal

Main question
Suppose there exists a random real symmetric $N \times N$ matrix $A$ with the main diagonal elements distributed according to $\mathcal N(\mu = 0, \sigma^2 = 4N)$, while all ...

**4**

votes

**0**answers

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

**4**

votes

**0**answers

363 views

### The order of the Jacobi method for Hermitian matrices

Let $H$ be an $n\times n$ Hermitian matrix. The Jacobi method is an iterative method for finding the spectrum of $H$. It is described in every book on numerical linear algebra.
Principle: At step ...

**3**

votes

**0**answers

80 views

### What do we know about the generalized eigenvalue problem involving a projector?

Consider a matrix $A\in\mathbb{R}^{n\times n}$ and a projector $P\in\mathbb{R}^{n\times n}$.
Are there results regarding the generalized eigenpairs $(v,\lambda)$ of the generalized eigenproblem
...

**3**

votes

**0**answers

144 views

### Upper bound on integrals of Legendre polynomials

Hi,
If $P_n(x) $ is unnormalized shifted Legendre polynomial, and $g_{n,m}(x) = \int_0^x P_n(x_1)x_1^m dx_1, n>m $ then what is the upper bound $ |g_{n,m} (x)|_{max} , x\in (0,1) $ as a function ...

**3**

votes

**0**answers

118 views

### Computing the norm of the columns of an implicitly defined matrix

I have an $n \times n$ matrix $M = \Sigma W$ where $\Sigma$ is diagonal and $W$ orthogonal. $W$ is implicitly defined, i.e. I can only perform matrix-vector products (but I also have access to $W^T$).
...

**3**

votes

**0**answers

170 views

### Pseudoinverse of column submatrix, from pseudoinverse of entire matrix.

Hello,
I am working on a numerical method for the least-squares solution of a linear system. I know that I can approximate the solution to $Ax=b$ with $x=A^+b$, where $A^+$ is the Moore-Penrose ...

**3**

votes

**0**answers

177 views

### Numerical solution

Last time, I asked this question
but after discussing with some friends, I have given up finding closed-form solutions. Now I have a simpler question.Let $g_i: i=1,2$ be $C^2 =C^{2}(-\infty,\infty)$ ...

**3**

votes

**0**answers

395 views

### Convergence of the relaxation method for every parameter in the relevant disk

For large size matrices, the resolution of linear systems $Ax=b$ is often done iteratively. The matrix $A$ is split as $A=M-N$, with $M$ invertible, and one performs
$$x^{k+1}=M^{-1}(Nx^k+b).$$
The ...

**3**

votes

**0**answers

791 views

### Eigenvalue Problems with Linear Constraints

The motivation for this problem comes from trying to develop a simple way to decompose domains into non-overlapping subdomains to solve for the eigenvalues of some differential operator. The idea is ...

**3**

votes

**0**answers

318 views

### Convergence to a (unique?) fixed point?

Consider a given $N\times P$ matrix $X$ (full rank with columns ${\bf x}_p$, $p=1,\ldots,P$), a given vector ${\bf y}\in R^N$ and a thresholding function $\eta_\lambda(|x|)=(|x|-\lambda)_+$ with ...

**3**

votes

**0**answers

235 views

### Nonlinear conjugate gradient update strategy by Dai and Yuan

In Nocedal and Wright book "Numerical Optimization", they describe on
page 123 (formula 5.49) an update strategy for the beta parameter in
the nonlinear conjugate gradient optimization, which was ...

**2**

votes

**0**answers

97 views

### error estimate of linear interpolation in high dimension

Consider convex functions $f,g$ on $[0,1]^d$. Let $x_1,\cdots,x_n$ be $n\geq d+1$ fixed point in $[0,1]^d$ that is equally 'distributed' in the sense that
$$c_1\leq ...

**2**

votes

**0**answers

44 views

### Estimating polynomial approximation error in high dimension

Question
Let $x \in [-1, 1]^d \subset \mathbb{R}^d$ be a $d$-dimensional variable and assume that -- given $n$ -- I have a way of computing a polynomial $p_n(x)$ of degree $n$ that approximates a ...

**2**

votes

**0**answers

63 views

### What is the computational complexity to compute the integral numerically?

Given $$\int_{\Delta}\frac{P_1(x_1,x_2,\dots,x_n)}{P_2(x_1,x_2,\dots,x_n)}$$ where $P_i$ is polynomial(that is $P_1(x_1,x_2,\dots,x_n), P_2(x_1,x_2,\dots,x_n)$ are polynomial) whose coefficients are ...

**2**

votes

**0**answers

35 views

### Conditions for convergence of Euler's method

It is know that a sufficient and necessary condition for
$$\dot y(t) = f(y(t), t), \quad t > 0, \quad y(0) = y_0$$
assumes a unique solution of $f$ is Lipschitz in $y$ and continuous in $t$. ...

**2**

votes

**0**answers

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

**2**

votes

**0**answers

127 views

### numerical method (implicit , backward difference or forward difference) for nonlinear pde

$\newcommand{\lbar}{\underline{\lambda}}$
In this linear PDE:
\begin{cases}
B_t+b^Q(r,t)B_r+\frac{1}{2}d^2(r,t)B_{rr}+(\mu(\lambda,t)+\alpha \sigma (t))(\lambda -\lbar)B_{\lambda} \\ ...

**2**

votes

**0**answers

129 views

### Are there workable numerical approaches for the pentagon equation?

Warning: this post is the "numerical" analog of
Are there workable algebraic geometry approaches for the pentagon equation?
I've replaced "algebraic geometry" by "numerical" in its content,
...

**2**

votes

**0**answers

74 views

### Lanczos algorithm with thick restart on a dynamic matrix

currently, I'm working on a way to compute the 2 biggest eigenvalues of a real, symmetric, huge and sparse matrix that changes a few entries from time to time. The problem should be solved using an ...

**2**

votes

**0**answers

95 views

### Stationary Distribution for Markov-like system?

Let
\begin{equation}
A=
\begin{pmatrix}
0 & a_{1,2} & a_{1,3} \\
a_{2,1} & 0 & a_{2,3} \\
a_{3,1} & a_{3,2} & 0
\end{pmatrix},
\end{equation}
\begin{equation}
B=
...

**2**

votes

**0**answers

141 views

### Algorithms to compute largest gap between smallest nonzero eigenvalues of sparse symmetric matrix

I am looking mainly for implementations but also for theoretical algorithms to compute gaps between smallest positive eigenvalues of symmetric, singular matrix or real numbers.
To be precise, I want ...

**2**

votes

**0**answers

64 views

### Variational problem for optimal weight function leading to shorter intervals with many primes

The motivation for the following problem stems from the recent preprint by James Maynard, see also Proposition 5 of the recent blogpost by Terrence Tao. The solution of this problem could give better ...

**2**

votes

**0**answers

204 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$ ...

**2**

votes

**0**answers

133 views

### When is it possible to split a non-linear operator into a composition of a linear and local one?

Let $A: L^2(R^n)\to L^2(R^n)$ be a non-linear operator. Is it known when it's possible to split $A$ into a composition of a linear operator $B: L^2(R^n)\to (L^2(R^n))^k$ and a local operator $C: ...

**2**

votes

**0**answers

26 views

### In what paper was the shrinkage parameter introduced to the nelder-mead simplex direct search algorithm?

I have read lots of papers referencing a 4th shrinkage parameter when talking about the Nelder Mead Simplex method. However, I cannot see any shrinkage parameter in the flow chart of the original ...

**2**

votes

**0**answers

127 views

### A question on discrete numerical simulation on fluids mechanics

I read the paper "Stable, circulation-preseving simplicial fuids" by Elcott, et al: http://www.cs.jhu.edu/~misha/Fall09/Elcott07.pdf. It gives a structure preseving discretization of fluids. I have ...

**2**

votes

**0**answers

202 views

### minimize a cost function with matrix traces

Hi, I have a cost function of the form
$$F(X) = \operatorname{tr}(X'AX)+\operatorname{tr}(X'B),\quad\textrm{ s.t. }X'X=I.$$
$X$ is a $m\times n$ matrix, ($m>n$), with orthonormal columns. $A$ is ...