Numerical algorithms for problems in analysis and algebra, scientific computation

**4**

votes

**1**answer

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

**8**

votes

**0**answers

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

**9**

votes

**3**answers

424 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

129 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

397 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

**0**answers

61 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

307 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

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

**2**

votes

**0**answers

60 views

### Approximating solutions to minima of the discrete Lagrangian

I have been stuck on this problem for a week and I'm not sure whether or not it is hard or I'm just missing something obvious.
General gist of the problem
I have a variational problem on a ...

**1**

vote

**1**answer

412 views

### Software to numerically solve partial differential equation

When we use software to numerically solve differential equation, for example, using finite difference, finite element or finite volume methods, etc., is it possible that people input differential ...

**21**

votes

**3**answers

876 views

### “Wild” solutions of the heat equation: how to graph them?

It has long been known that the Cauchy initial-value problem for the
classical heat equation on $\mathbb{R}$ (or $\mathbb{R}^n$) doesn't
have unique solutions, without additional assumptions. In ...

**2**

votes

**2**answers

222 views

### Computing hypergeometric function of matrix argument

In the context of the Bingham probability distribution the ${ }_1F_1$ hypergeometric function of matrix argument naturally arises as a normalization constant of the probability distribution function. ...

**6**

votes

**2**answers

260 views

### Rigorous numerics for maxima and minima (one variable)

Let $f:\mathbb{R}_0^+\to \mathbb{R}$ be defined by some combination of the four basic operations and square roots. (The argument of square-roots is assumed is to be non-negative, and the value of ...

**1**

vote

**1**answer

148 views

### integral basis of orthogonal complement

Suppose there are $r$ linearly independent vectors $v_1,\dots,v_r\in \mathbb{R}^n$, all of them have integer-valued entries and $\|v_i\|_\infty\leq m$ for some integer $m$.
My goal is to find an ...

**2**

votes

**0**answers

192 views

### eigenvalues of the sum of a stochastic matrix and a diagonal matrix

Let $D$ be a real diagonal matrix $D=diag(a_1,a_2,\ldots,a_n)$ with $a_1\le a_2\le\ldots\le a_n$. Assume that at least one of the $a_i$ is positive. Let $P$ be an irreducible, real, row-stochastic ...

**3**

votes

**2**answers

230 views

### Questions on Discrete Exterior Calculus in numerial computing

I have several questions about the Discrete Exterior Calculus (DEC) in the numerical method for solving partial differential equation in physics:
(Discrete Exterious Calculus is the newly developed ...

**1**

vote

**1**answer

126 views

### For what values of the parameter does this function have an elementary anti-derivative?

I am a grad student working on some independent research trying to derive some exact formulas for a particular class of power series. During my study I came across the following integral which would ...

**2**

votes

**1**answer

158 views

### Reducing the error of Algorithms by assigning variables formulas instead of values

Let me first give the intuition for my question: Suppose that you want to use a ruler to mark $n$ points in a line on a page, with 1 cm distance between neighbor points. There are two ways:
1- Mark ...

**4**

votes

**1**answer

372 views

### Hilbert Matrix and Approximation Theory

I was reading about the Hilbert matrix and Cauchy determinants:
\[ \det \left[ \frac{1}{i+j-1} \right]_{i,j} \]
By guessing where this determinant is $0$ or $\infty$ we can guess the right formula. ...

**5**

votes

**0**answers

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

**2**

votes

**1**answer

125 views

### Optimization problem

I'm trying to solve a very practical optimization problem and I think I hit a dead-end.
There are $N$ products ($N \sim 50$). Each product can have a price $p_i$ in range between 1 and 40 dollars. ...

**0**

votes

**1**answer

76 views

### Avoiding epsilon in mixed integer linear and quadratically constrained programs

I would like to represent the following constraint as MILP constraint where $x \in [a, b]$ with fixed $a, b \in \mathbb{R}$ and $y \in \lbrace 0, 1 \rbrace$.
$(x = 0 \wedge y = 1) \vee (x \neq 0 ...

**1**

vote

**0**answers

62 views

### Orthogonal projection of discontinuous piecewise polynomial space in energy scalar product

Let $I = [0,1]$ be the unit interval Let $I$ be partioned into $n$ closed subintervals $(I_j)_J$, each of length $1/n$.
Let $X_{DC} = \{ v \in L^2[0,1] | 1 \leq j \leq n : v_{|I_j} \in \mathcal P_1( ...

**9**

votes

**2**answers

618 views

### Rigorous numerical integration

I need to evaluate some (one-variable) integrals that neither SAGE nor Mathematica can do symbolically. As far as I can tell, I have two options:
(a) Use GSL (via SAGE), Maxima or Mathematica to do ...

**0**

votes

**2**answers

190 views

### Proof that polynomial evaluated at roots of unity is DFT [closed]

Hello All,
I hope I am not abusing the forum here.
I am just trying to understand the efficient implementations of the fast fourier transform. My reading and searching has led me to understand that ...

**12**

votes

**1**answer

1k views

### The unreasonable effectiveness of Pade approximation

I am trying to get an intuitive feel for why the Pade approximation works so well. Given a truncated Taylor/Maclaurin series it "extrapolates" it beyond the radius of convergence. But what I can't ...

**4**

votes

**1**answer

210 views

### best rank r approximation for non-Frobenius norm

The best rank $r$ approximation to a given matrix $M$ in Frobenius norm, according to Eckart-Young theorem, is truncated SVD - just keep $r$ largest singular values. What if I need to construct best ...

**2**

votes

**2**answers

942 views

### Finding the formula for Bezier curve ratios (hull/point : point/baseline)

Given a cubic Bezier curve defined by points p₁, p₂, p₃, and p₄, a point B on that curve at some t value (where 0 ≤ t ≤ 1), a point A on the line (p₂ — p₃) at distance ratio t from p₂, and a point C ...

**1**

vote

**1**answer

111 views

### Recommendations for binomial system solver

I am interested in solving binomial systems of the form
$$
\begin{cases}
a_1 x_1^{d_{11}} x_2^{d_{12}} \cdots x_n^{d_{1n}} +
b_1 x_1^{d_{11}} x_2^{d_{12}} \cdots x_n^{d_{1n}} &= 0 \\\\
...

**3**

votes

**1**answer

115 views

### approximation methods in integral equations

Recently I was reading about integral equations and I am a beginner in it. There was a constant reference to the non-availability of methods to find the exact solutions and hence lot of approximation ...

**1**

vote

**1**answer

195 views

### How are real-analytic functions encoded in computer algebra?

I would like to know how are encoded the real-analytic functions on the interval by the computers. When I think in a real-analytic function I just think in a composition of the ''typical'' analytic ...

**4**

votes

**1**answer

490 views

### Matrix perturbation theory

I am having matrix $M_0$ with coresponding eigenvectors and 4 eigenvalues {0,0,a,-a}. Eigenvalue $\lambda=0$ is double degenerated. Now I am appliing small perturbation $\epsilon M_1$ and want to get ...

**2**

votes

**0**answers

179 views

### Convergence rate of iterated nonlinear equations?

For $i=1, \dots, n$ ($n$ could be large) we have variables $x_i$ and $y_i$ relating to probability bounds s.t. $x_i, y_i \geq 0, x_i+y_i \leq 1 \; \forall i$. Each $i$ has a constant $\theta_i$, and ...

**2**

votes

**0**answers

155 views

### Heat transfer coefficients - correlation equations for Nusselt number - vertical pipe

I need a heat transfer coefficient applicable to free convection of water INSIDE a vertical pipe. I have the correlation equation from Churchill and Chu, but it is only valid for D/L>=35/Gr^(1/4), ...

**3**

votes

**1**answer

89 views

### Kronecker-structured matrix kernel

Let $A,B\in\mathbb{C}^{n\times 3n}$ be two matrices, and denote the Kronecker matrix product by $\otimes$. The matrix
$$
M=
\begin{bmatrix} A \otimes I_n \\\\ I_n \otimes B\end{bmatrix}
$$
has size ...

**2**

votes

**1**answer

212 views

### Approximation theory under $L_1$-error

Is there a reference for results in approximation theory of bounded functions of one (and multiple) variables under $L_1$-error?
Formal definitions for functions of one variable are below.
Let $C$ ...

**2**

votes

**0**answers

127 views

### Radius of convergence to be proved more precisely (differential equation)

There is a differential equation in polar coordinates:
$r'^2+r^2=(kt)^2$, $r(t=0)=0$, k- Const.
It is possible to get a solution which is a power series (see below). However, I am looking for an ...

**3**

votes

**1**answer

258 views

### Lebesgue constant as condition number of polynomial interpolation

Let $T = \{ x_0,\ldots,x_n \}$ be a set of $n+1$ different points in the real interval $[a,b]$. Let $X_T$ be the associated interpolation operator on $C[a,b]$: it takes a function $f \in C[a,b]$ into ...

**4**

votes

**1**answer

694 views

### Smoothing L1 norm, Huber vs Conjugate

I'm trying to minimize a convex (not necessarily strictly convex) function involving an L1 norm (similar to lasso), which makes it non-differentiable at some points. So I'd like to smooth it and treat ...

**4**

votes

**0**answers

45 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)} ...

**6**

votes

**2**answers

649 views

### Approximating erf by tanh

It appears to be well-known that $\tanh(x)\le \mathrm{erf}(x)$ on $[0,\infty)$. It's off-handedly mentioned here, for example. Where can I find a formal proof? On the one hand, it's hard to imagine ...

**2**

votes

**0**answers

114 views

### integrate square of bessel 1st and 2nd kind

Has anyone ever solved the integral of square of Bessel and Neumann functions? This is for standing wave analysis on a cylindrical object.
I need to integrate $(AJ(kr) + BY(kr))^2$ from $r=a$ to ...

**1**

vote

**0**answers

75 views

### Integrating B-Spline composed with log

If $f$ is a real B-Spline and $a, b$ are real numbers, then is there a numerically stable way to evaluate the following expression?
$\int_a^b f (\log x) \mathrm{d}x$

**16**

votes

**3**answers

831 views

### Easy functions ?

Let $f$ be an analytic function, and suppose that we want to compute
$f(x)$. The input consists of the digits of $x$ and the output of
a rational number approximating $f(x)$. A function $f$ is called ...

**5**

votes

**0**answers

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

**13**

votes

**2**answers

287 views

### Condition number of matrix after partial orthogonalization

I'm wondering about which bounds one can put on the condition number of
a $n\times n$ square matrix which is obtained from another $n\times n$
square matrix by orthogonalizing the first $m < n$ ...

**3**

votes

**0**answers

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

**5**

votes

**0**answers

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

**7**

votes

**2**answers

285 views

### How to solve a system of linear equations without storing the matrix?

I have a procedurally defined Hermitian matrix $M$, i.e. I can get any matrix element by calling a black box function (e.g. a library function), and a vector $Y$. And I have to solve a system of ...

**4**

votes

**4**answers

723 views

### When we use Bernstein polynomials in application

When it is preferable to use Bernstein polynomials to approximate a continuous function instead of using the only following preliminary Numerical Analysis methods: "Lagrange Polynomials", "Simple ...