Numerical algorithms for problems in analysis and algebra, scientific computation

**12**

votes

**0**answers

336 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

106 views

### Interval arithmetic with different definitions of intervals

Interval arithmetic normally deals with intervals defined as $[a,b]$ with rules like $$[a,b]+[c,d]=[a+c,b+d]$$ I am interested in interval arithmetic with different interval definitions such as ...

**11**

votes

**0**answers

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

**11**

votes

**0**answers

782 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

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

**9**

votes

**0**answers

386 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

64 views

### numerical methods to compute approximated Stiefel-Whitney class

Let $0<\epsilon<1$, $k\geq 4$ be an integer, $S^2$ be the unit sphere in $\mathbb{R}^3$, $d$ the Euclidean distance in $\mathbb{R}^3$ and
$$
...

**8**

votes

**0**answers

446 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

332 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

184 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

654 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

149 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

397 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

91 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

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

**5**

votes

**0**answers

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

**5**

votes

**0**answers

104 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

274 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

437 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

135 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

329 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

100 views

### Compensated compactness for system of conservation laws?

As far as I knew, the method of compensated compactness can be used only for one-dimensional scalar and $2\times 2$ systems of conservation laws, i.e. $u_t+f(u)_x=0$. But if I understood correctly ...

**4**

votes

**0**answers

75 views

### Numerical integration error bounds on the unit sphere

A sequence of points $x_1,x_2,\dots$ on the unit sphere $S^{D-1}$ is said to be uniformly distributed if
\begin{align}
\lim_{N \rightarrow \infty} \frac{1}{N} \sum_{j=1}^N f(x_j) = \int_{x \in ...

**4**

votes

**0**answers

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

**4**

votes

**0**answers

628 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

146 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

175 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

169 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

138 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

218 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

53 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

345 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

297 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

376 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

87 views

### Determining Nullspace Basis such that only one column is deleted or added as row is added or deleted, and remaining columns of basis stay the same

I would like to compute, in MATLAB, the basis Z for the nullspace of an m by n matrix A, such that if one row of A is added (resulting in A_a), the basis for A_a is n-m-1 of the n-m columns of Z, ...

**3**

votes

**0**answers

32 views

### Solving a Certain Constrained Isoperimetric Approximation-Problem

This question is related to my question Differential Geometric Aspects of Rubber Bands, where I asked for a mathematical model of contracting rubber bands.
In contrast to my former question, the ...

**3**

votes

**0**answers

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

**3**

votes

**0**answers

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

**3**

votes

**0**answers

87 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

79 views

### Application and relevance of Sobolev gradients

The Sobolev gradient concept has been developed in the 1970s, with a first publication in 1985, and an introduction can be found at: Ranka
I would like to learn how strong the impact of Sobolev ...

**3**

votes

**0**answers

163 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

121 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

178 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

186 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

420 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

883 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

325 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

240 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

98 views

### An alternative to the Euler--Maclaurin formula: Approximating sums by integrals only

The Euler--MacLaurin summation formula can be written as
$$ \sum_{i=0}^{n-1} f(k)\approx \int^{n-1}_0f(x)\,dx
+ \frac{f(n-1) + f(0)}2
+
\sum_{j=1}^m\frac{B_{2j}}{(2j)!}[f^{(2j - ...

**2**

votes

**0**answers

58 views

### Natural neighbor interpolation

Recently I am interested in Natural neighbor interpolation, that is :
Given a function $P(x)$ and some interpolation points $\{x_i,P(x_i)\}_{i=1}^N$, we have the interpolation function ...