Numerical algorithms for problems in analysis and algebra, scientific computation

**9**

votes

**3**answers

703 views

### Best known bounds on tensor rank of matrix multiplication of 3×3 matrices

Years ago I attended a conference where they taught us that matrix multiplication can be represented by a tensor. The rank of the tensor is important, because putting it into minimal rank form ...

**1**

vote

**1**answer

71 views

### Augmenting orthonormal system into complete orthonormal system in a numerically stable way

Let us suppose we have a, say, 10 dimensional real space with 3 orthogonal unit vectors given. How do I complete this orthonormal system with 7 additional vectors into a complete ONS in a way that is ...

**1**

vote

**0**answers

83 views

### How to solve a divergent linear system using iterative methods?

I have a matrix A which is symmetric and non-diagonal dominant. I tried to use Jacobi/Gauss-Seidel/SOR to solve it but it diverges. Is there any mechanism to condition the matrix for convergence using ...

**1**

vote

**0**answers

218 views

### Simplify this expression with modified Bessel functions of the second kind

I'm interested in the function
$$\frac{K^{(0,2)}(0,x)}{K(0,x)}$$
where the numerator is the modified Bessel function of the second kind twice differentiated with respect to $\alpha$ and taken at ...

**1**

vote

**0**answers

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

**0**

votes

**1**answer

219 views

### Does this algorithm terminate in all scenarios?

Let $x \in \mathbb{R}^p$ denote a $p$-dimensional data point (a vector). I have two sets $A = \{x_1, \dots, x_n\}$ and $B = \{x_{n+1}, \dots, x_{n+m}\}$, so $|A| = n$, and $|B| = m$. Given $k \in ...

**2**

votes

**1**answer

208 views

### Literature on root finding of convex Functions

I am interested in using a result about Newton's method, which basically states that if f is convex on $[a,b]$ and it holds $f(a)<0$ and $f(b)>0$, then the Newton iteration converges to ...

**1**

vote

**1**answer

89 views

### Fast numerical approximation of Lauricella series of the fourth kind for real variables and real parameters

I'm looking for a method to efficiently compute a numerical approximation of
$$F^n_D(x_1,\ldots,x_n) = \sum_{m=0}^{\infty} \sum_{i_1 +\ldots+i_n=m}\frac{(a)_{m}(b_1)_{i_1}\ldots ...

**1**

vote

**1**answer

87 views

### Quadrature rules exact for given functions

Many quadrature schemes are defined by the degree of polynomials for which they are exact. For example, we say that the rule SUM_i a_i f(x_i) is order n when SUM_i a_i p(x_i) = INT p(x) dx for all ...

**2**

votes

**1**answer

291 views

### Convergence of fixed point iteration algorithm

It is obvious that for any given $f(x)$ there exists $g(x)$ such that $f(x)=0 \Leftrightarrow g(x)=x$. We could use this fact to solve any root finding problem using fixed point iteration method, only ...

**1**

vote

**1**answer

153 views

### Eigenvalue problem with quadratic constraints

$\circ$ Consider the following eigenvalue problem : $$Ax=\lambda x \hspace{0.5cm} (1)$$
where matrice $A \in \mathbb{R}_{n \times n}$ is a positive semi-definite with eigenvectors $x = ...

**2**

votes

**1**answer

125 views

### Updating $LU$ decomposition after adding a sparse matrix

How many elements of $LU$ decomposition of a symmetric matrix change after adding a sparse symmetric matrix? Is it more efficient to recompute $LU$ decomposition after adding a sparse matrix comparing ...

**2**

votes

**0**answers

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

**4**

votes

**1**answer

132 views

### Do interpolation nodes have to be dense?

Let $f(x) = \exp(x)$ and $(\xi_i)_{i=0}^\infty, \, \xi_i \in (0,1)$ be a sequence of points from the unit interval.
For $n \in \mathbb{N}$ let $P_n$ be a polynomial of degree $n$ that interpolates ...

**0**

votes

**0**answers

73 views

### Looking for tighter bounds

I have to solve an equation which is $$\sum_{i=1}^N x_i = \sum_{i=1}^N y_i,$$ where
$$x_i = \frac{z_i}{1 + (K_i - 1) w}$$ and $$y_i = \frac{K_i z_i}{1 + (K_i - 1) w}.$$
The $z_i$ are all positive ...

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

**1**

vote

**2**answers

340 views

### Eigenvalue computation using inverse iteration

I have a positive definite matrix $A$. I need to compute the max eigen value of $A$ using inverse iteration. The problem is that there are duplicate maximum eigen values and so inverse iteration ...

**1**

vote

**0**answers

96 views

### Solutions of Fredholm integral equation of the fisrt kind with asymmetric kernel

Given the integral equation:
$$\int_0^{\lambda_0}K(\lambda,T)S(\lambda)d\lambda=f(T)$$
with $S(\lambda)$ unknown function and the kernel:
$$K(\lambda,T)=\frac{1}{\lambda^5(\exp(k/\lambda T )-1)}$$
...

**2**

votes

**0**answers

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

**11**

votes

**2**answers

718 views

### How to project a vector onto a very large, non-orthogonal subspace

I have a difficult problem.
I have a very large, non-orthogonal matrix $A$ and need to project the vector $y$ onto the subspace spanning the columns of $A$. If this were a small matrix, I would use ...

**1**

vote

**3**answers

274 views

### What are the basis functions for a product space?

Let $X=L^1\left([0,1]^3\right)$,
for numerical purpose, what are the possible basis function for $X$?
In finite element method, the basis functions are tooth functions, or polynomial functions.
Is ...

**5**

votes

**1**answer

276 views

### Is this inverted integral transform valid?

I have the following transform:
$$F(y) = \int_{0}^{\infty} y\exp{\left[-\frac{1}{2}(y^2 + x^2)\right]} I_0\left(xy\right)f(x)\;\mathrm{d}x$$
with the following conditions:
$f(x)$ and $F(y)$ must ...

**11**

votes

**2**answers

508 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

166 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

257 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

253 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

36 views

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

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

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

**2**

votes

**1**answer

158 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

227 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

555 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

456 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

247 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

28 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

357 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

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

**3**

votes

**1**answer

808 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

177 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

138 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

880 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

384 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

425 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

314 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

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

**1**answer

668 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

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