Numerical algorithms for problems in analysis and algebra, scientific computation

learn more… | top users | synonyms

12
votes
0answers
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
0answers
690 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
0answers
168 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
0answers
485 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
0answers
350 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
0answers
403 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
0answers
314 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
0answers
485 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
0answers
372 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
0answers
95 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
0answers
252 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
0answers
141 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
0answers
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
0answers
128 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
0answers
300 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
0answers
118 views

Rank 1 Approximation of Elementwise Inverse Matrix

I'm wondering whether there is a good way to solve the following optimisation problem. Given a strictly positive quadratic matrix $A$, find two diagonal matrices $D_1$ and $D_2$ so that $$ \| D_1 A ...
4
votes
0answers
305 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
0answers
127 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
0answers
116 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
0answers
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
0answers
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
0answers
195 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
0answers
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
0answers
291 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
0answers
273 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
0answers
361 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
0answers
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
0answers
140 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
0answers
117 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
0answers
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
0answers
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
0answers
394 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
0answers
773 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
0answers
313 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
0answers
233 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
0answers
39 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
0answers
57 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
0answers
33 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
0answers
55 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
0answers
119 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
0answers
128 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
0answers
71 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
0answers
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
0answers
134 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
0answers
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
0answers
194 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
0answers
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
0answers
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
0answers
126 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
0answers
186 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 ...