Numerical algorithms for problems in analysis and algebra, scientific computation

**11**

votes

**2**answers

484 views

### Who is Petrov of the Petrov-Galerkin method?

I was not able to find the origin of the name Petrov in the Petrov-Galerkin method for the numerical approximation of PDEs.
Wikipedia refers to a certain Alexander G. Petrov, but it is still not ...

**1**

vote

**0**answers

160 views

### The rationale of QR algorithm for computing eigenvectors

For a symmetric matrix $A$, the rationale for the success of applying QR to compute the spectral decomposition of $A = UDU^T$ is, for large $k$, the QR factorization of $A^k = Q_kR_k$ obeys,
...

**1**

vote

**0**answers

255 views

### Reference request for parallel transport

I am learning about parallel transport on a Riemannian manifold equipped with an affine connexion. It seems (if I understand it well) that, in general, we might not be able to compute the parallel ...

**1**

vote

**1**answer

239 views

### How to examine the convexity of a complex function numerically?

I have a function which does not have a closed form . Large numerical effort should be done to evaluate the function for even a single point. How can I examine the convexity of my function over the ...

**1**

vote

**0**answers

88 views

### Distribute Monte Carlo samples among dimensions

Simplified problem: Given a $d$-times nested convolution of an input function $g(x):\mathbb{R}\mapsto \mathbb{R}$ with the same band-limited smooth function $f(x):\mathbb{R}\mapsto \mathbb{R}$. I am ...

**0**

votes

**1**answer

35 views

### Computing a particular expection for a family of distribution

Consider the family of distributions having the form $$f = ...

**4**

votes

**0**answers

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

**2**

votes

**1**answer

152 views

### elliptic integral with singularities

I need to calculate elliptic integrals with singularities, up to a huge number of digits (250-1000). The problem is that Wolfram Mathematica can't do so many digits, and Pari intnum doesn't handle ...

**1**

vote

**1**answer

225 views

### What are the advantage of using operational calculus for numerically solving pde compared to FE or FD?

For numerically solving a partial differential equation (PDE) what advantage does operational calculus (OC) has over common methods like finite difference (FD), and finite element (FE)?
I mean OC in ...

**3**

votes

**4**answers

2k views

### Solving a System of Quadratic Equations

I have many polynomial equations in many variables which I want to jointly minimize (in a mean square sense, but you could pick a different reasonable measure which favors anything where all ...

**3**

votes

**2**answers

1k views

### Sparse approximation of the inverse of a sparse matrix

Is it possible to approximate an inverse of a sparse matrix with a sparse matrix?
The problem comes up in numerical non-linear quasi-Newton optimization: given a sparse Hessian a good starting point ...

**4**

votes

**2**answers

523 views

### Numerical solution to diffusion-like equation with negative diffusion coefficient region?

I am trying to numerically solve the initial value problem (see later discussion for ICs)
$$ x \frac{\partial f}{\partial t} = \frac{\partial}{\partial x} (1-x^2) \frac{\partial f}{\partial x} - f$$
...

**1**

vote

**1**answer

427 views

### Is there a quick way to find all roots of a real polynomial with multiple variables?

If I am asked to find the roots of a polynomial of one variable, I will use a computer to estimate the eigenvalues of its companion matrix. Now suppose I'm given a real polynomial of multiple ...

**4**

votes

**1**answer

244 views

### How to get an expression for this integral(Numerically/Analytically)

I have the following problem:
I need to evaluate the integral $$\int_{\cos(\alpha)}^{1} P_l(t)P_{l'}(t) dt $$ for $\alpha \in [0,\pi]$ and each combination of $l$ and $l'$, where $P_l$ is the l-th ...

**2**

votes

**0**answers

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

**3**

votes

**1**answer

333 views

### Practical error-estimates for (adaptive) Newton-Cotes Quadrature

I am looking for practical error estimates for Newton-Cotes Quadrature rules.
Most books on numerical methods I have found mainly deal with theoretical error bounds/estimates for the respective ...

**7**

votes

**2**answers

203 views

### Finding a low-degree polynomial vanishing on half the zeroes of a polynomial system

Let $f(x)$ be a real polynomial of degree $2d$ without real roots. Let the complex roots be $z_1$, $\bar{z_1}$, $z_2$, $\bar{z_2}$, ..., $z_d$, $\bar{z_d}$ with $z_i$ in the upper half plane. Let ...

**4**

votes

**0**answers

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

**3**

votes

**1**answer

750 views

### Parameter estimation for stochastic differential equation from discrete observations

Suppose we have a time-series $x(t_i)$ at discrete times $t_i$ and we want to estimate the parameters of an underlying SDE corresponding to this time-series:
$$dx_t = f(x_t,\theta)dt + ...

**2**

votes

**1**answer

173 views

### Possible pathological properties of positive definite matrix

Suppose $A$ is a positive definite matrix such that
$$I \preceq A \preceq 1.01I.$$
Is it possible that
$$\sum_{i=1}^n A_{1i}$$
can be arbitrarily large?
Thanks,
Jack

**2**

votes

**0**answers

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

**6**

votes

**3**answers

857 views

### Square Root Algorithm

I would like an efficient algorithm for square root of a positive integer. Is there a reference that compares various square root algorithms?

**7**

votes

**3**answers

380 views

### accelerating convergence of a class of sequences

Do any of the standard methods of acceleration convergence of series, when applied to
the series $1 - 1 + 1/2 - 1/2 + 1/3 - 1/3 + ...$, give convergence to 0 with error $o(1/n)$?
I tried applying ...

**2**

votes

**2**answers

396 views

### What is the definition of an antilimit?

I've seen some references to antilimits in the numerical analysis literature, but no definition of the term. The impression I get is that in specific contexts where every sequence $x_0,x_1,x_2,\dots$ ...

**1**

vote

**1**answer

273 views

### Understanding the rationale behind “batch means” estimation

Hello all,
I am implementing an MCMC algorithm for my work, and I've come upon something in the literature which I just can't understand.
Specifically, I am attempting to estimate the amount of ...

**4**

votes

**0**answers

137 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

**1**answer

600 views

### Numerical multivariate definite integration

I need to compute a set of multivariate definite integrals with infinite integration domain
$$\displaystyle \int_{-\infty}^{\infty} \cdots \int_{-\infty}^{\infty} f(x_1,x_2, \ldots , x_n)\;\;dx_1 ...

**2**

votes

**0**answers

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

**2**

votes

**1**answer

99 views

### non convex quadratic optimization

Hi
I would like to optimize the following system:
$$\min_{q,\|q\|=1} \sum_i^n |q^T M_i q|$$
More details:
the size of the unknown vector q is $4\times 1$,
M_i is a matrix of size $4\times 4$. It is ...

**4**

votes

**3**answers

427 views

### Lower bound for sum of square root of the degrees of a connected graph

By Cauchy-Schwartz and the handshake lemma, it is easy to see that $\left( \sum_{i=1}^n \sqrt d_i \right)^2 \leq n \sum_{i=1}^n d_i =2mn$, with equality iff the graph is regular (constant degree).
...

**1**

vote

**1**answer

192 views

### Discretizing a cosine function?

I'd like to start by noting that for some fixed natural $N$ basis functions for my system will be generated by $f(k,x)$ as defined and explained here or in numerous other sources:
$$f(k,x) = \sqrt2 ...

**0**

votes

**1**answer

136 views

### How to handle a scalar product in an integral?

I am having a problem with a certain inequality I try to understand. I think it's just a basic idia (/trick) I'm missing, but I can't seem to find it.
Here's a simplification of the problem:
$ ...

**0**

votes

**0**answers

73 views

### Approximate closed-form solution for a recurrence

Find an (approximate) closed-form solution for $S(m, b)$.
$$S(m,b)=\sum_{i=0}^{\lfloor (e-1)/2\rfloor}{e \choose i}S(m-1, b-i) \quad +
\sum_{i=\lfloor (e-1)/2\rfloor+1}^{\min(b,e)}{e\choose ...

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

**3**

votes

**1**answer

80 views

### Conjugate gradient algorithm where first search direction is not equal to residual

In usual formulation of conjugate gradient algorithm initial search direction is taken to be the residual (so residual and search direction spans Krylov subspace). However, in cases where inexact ...

**33**

votes

**2**answers

1k views

### Recent fundamental new directions in PDEs

My main interests are in modern geometry/topology, algebra and mathematical physics. I observe that there is a raising communication, language and social barrier between this community and the ...

**7**

votes

**0**answers

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

**11**

votes

**2**answers

488 views

### Computing a large permanent

Is there a practical way to compute the permanent of a large ($91 \times 91$) $(0,1)$ matrix?
I have tried to use the matlab function written by Luke Winslow which works great for smaller matrices ...

**3**

votes

**1**answer

133 views

### The discrete theory of compressible fluids dynamics

I am working on the discrete theory of compressible fluids dynamics, i.e., numerically solving and simulating the compressible fluids , we are interested in the way using discrete exterior calculus, ...

**7**

votes

**1**answer

170 views

### Who first observed that Conjugate Gradient for Symmetric Positive Definite linear systems is a Krylov method?

Conjugate gradient was originally presented in the 50's before the modern understanding of Krylov subspaces (and the resulting iterative methods) was fully realized. As such, the method was derived ...

**3**

votes

**1**answer

528 views

### Stability in algebraic geometry

Suppose I have a collection of polynomials with multiple variables (more polynomials than variables, say), and I'm given noisy versions the values of these polynomials at a certain unknown point. I ...

**10**

votes

**0**answers

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

**5**

votes

**1**answer

854 views

### Efficient computation of Markov chain transition probability matrix

Consider a continuous Markov chain $X = (X_t)$ on a finite state space and let $Q$ be the (given) transition rate matrix. This matrix is very sparse, with non-zero values on 3 diagonals only (so from ...

**7**

votes

**0**answers

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

**10**

votes

**3**answers

669 views

### Rapid evaluation of multivariate normal integral

I'm implementing a model that requires me to numerically evaluate a multivariate normal integral of the following form
$$\int_{-\infty}^\infty \phi(z)\displaystyle\prod_{i=1}^N \Phi(a_iz+b_i) \, ...

**3**

votes

**1**answer

156 views

### Using Fourier Transform to speed up calculation of forces following an inverse square law

Suppose I have $n$ electric point charges in, say, two dimensions. Is there any algorithm (and I have a hunch that it might be related to the Fourier transform) to compute the net forces that act on ...

**15**

votes

**1**answer

535 views

### The Chow & Robbins game ≈ 0.79295350640: improvements could come from simple statistics, or from a continuous version of the game

This question seeks help with improving a numerical estimate of the value of the Chow and Robbins game. Much about this game is unknown, such as whether its value is rational, but there are two routes ...

**1**

vote

**1**answer

191 views

### Dragilev method

What are the advantages and disadvantages of the Dragilev ( http://www.mathnet.ru/php/person.phtml?&personid=32359&option_lang=eng
and ...

**8**

votes

**1**answer

407 views

### Machin-like formulas for logarithms

I found this math puzzle blog post
http://fredrikj.net/blog/2013/03/machin-like-formulas-for-logarithms/
which I'm reposting here with permission. I'm setting this to community wiki to minimize the ...

**2**

votes

**0**answers

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