Numerical algorithms for problems in analysis and algebra, scientific computation

**1**

vote

**1**answer

209 views

### Decompositions of sparse symmetric matrices and methods for solving large linear equations

I am writing code for solving linear equations of the form
$$A_{n\times n}\cdot x=1_n$$
where $n$ is on the order of $10^6$ and $A$ is a symmetric matrix with approx $10^3$ nonzero entries in each ...

**2**

votes

**1**answer

75 views

### An algebraic equation question [closed]

My question is this:
If $\frac{\sqrt[n]{\prod_{i=1}^n(p_i + 1)}}{\sqrt[n]{\prod_{i=1}^n(m_i + 1)}} = e ^\beta$
can I find an expression (either exact or approximate) for ...

**2**

votes

**1**answer

157 views

### Polynomial upper and lower bounds

Consider approximating smooth function $f(x): \mathbb{R} \to \mathbb{R}$ over the interval $[a,b]$ with a bounded $k$th derivative over the interval. I would like to find degree $d$ polynomials ...

**3**

votes

**1**answer

210 views

### Numerical Evaluation of Some Triple Integral involving Negative Powers

Let $\beta_i\in (-1/2,0)$, $i=1,2,3,4$. I'm interested in obtaining numerical value of the following integrals:
$$
\int_{0<u_1<u_2<u_3<1} (1-u_1)^{\beta_1}(1-u_2)^{\beta_2} ...

**2**

votes

**0**answers

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

**9**

votes

**1**answer

416 views

### Fast checking that overdetermined polynomial system does not have a solution

As a result of some inductive procedure for each $n$ I have a system of about $n^2$ polynomial equations with $n$ variables with integer coefficients, which can be precisely computed. As the system is ...

**-1**

votes

**1**answer

112 views

### Convergence for symmetric, positive semi-definite operator

Assume $u$ is a vector in the Euclidean space $\mathbb{R}^N$, $\|u\|=\sqrt{\langle u, u\rangle}$, where $\langle u, v\rangle = \sum_{i=1}^N u_i v_i$.
I have that $\|u^{k+1}-u\|\leq \|I - c ...

**8**

votes

**1**answer

276 views

### Sharpest bound on the zero free region of $\zeta^{\prime}$?

I'm interested in calculating all of the zeroes of the first derivative of the Riemann $\zeta$ function up to an arbitrary height. I know that (on the RH), all of these zeroes will have real part $\ge ...

**3**

votes

**1**answer

158 views

### Approximate the square root of (1-X) efficiently through (nested) products

Currently, I encountered a problem of approximating the following
series:
$$
(I-X)^{-\frac{1}{2}}=I+\frac{1}{2}X+\frac{1\cdot3}{2\cdot4}X^{2}+\frac{1\cdot3\cdot5}{2\cdot4\cdot6}X^{3}+\ldots
$$
where ...

**8**

votes

**1**answer

245 views

### is there any such result about Bernstein polynomials?

It is well known that for any lipschitz function $f:[0,1]\rightarrow [0,1]$, we can approximate it
by $\sum_{i=1}^n f(i/n) {n\choose i} x^i (1-x)^{n-i}$, and the $L_\infty$ error is $O(1/\sqrt{n})$. ...

**1**

vote

**1**answer

391 views

### Is there an example where the error of Gauss-Laguerre quadrature does not vanish?

The $n$th Gauss-Laguerre quadrature aims to approximate integral $$\int_{\mathbb{R}_+} f(x) \exp(-x)$$ by the sum
$$\sum_{i=1}^n f(x_i) w_i$$
where $x_1,...,x_n$ are the roots of the $n$th Laguerre ...

**2**

votes

**0**answers

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

**3**

votes

**1**answer

130 views

### Trace of multiplied positive definite matrices

I have to compute $Tr(K^{-1}\Sigma)$ where both $K$ and $\Sigma$ are symmetric positive definite matrices.
Question is considering that I have computed the Cholesky, $L_1$ of $K$ previously, is there ...

**1**

vote

**2**answers

153 views

### Numerical calculation of Fourier transform with a nice error bound

I'd like to have an algorithm for a numerical calculation of Fourier transform with a nice error bound. To be precise, if $f$ is a function from $L_1(R)$, $F[f]$ is it's exact Fourier transform and ...

**3**

votes

**0**answers

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

**2**

votes

**0**answers

174 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

**2**answers

139 views

### Seeking a class of functions for which sums approximate integrals well

Is there a "natural" class of integrable functions $f: {\mathbb R} \rightarrow {\mathbb R}$ for which it is true (and, preferably, not too hard to prove!) that $\sup_{0 \leq a < h} |h S(a,h) - I|$ ...

**5**

votes

**0**answers

107 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)$?
...

**3**

votes

**1**answer

220 views

### Error of midpoint method for functions that are not twice-differentiable

All of the bounds I've seen for the error of the midpoint method of integration are expressed in terms of the second derivative of the function. What bounds are available when the function is not ...

**1**

vote

**1**answer

241 views

### Is there any geometric and intuitive interpretation of Newton-like iterative steps in numerical optimization?

Are the iterative steps in optimization affected by the intrinsic and extrinsic curvatures of the objective functions ? and How?
Is there any geometric and intuitive demo show illustrating the ...

**0**

votes

**1**answer

837 views

### How to determine the distance between two matrices under the meaning of a matrix function? [closed]

Suppose a nonlinear infinitely continous differentiable function $f:\mathbb{D}\mapsto \mathbb{R^+}$, where $\mathbb{D}\subset\left\{X|\text{rank}{X}=2,X\in\mathbb{R}^{3\times 3}\right\}$ is a ...

**4**

votes

**1**answer

459 views

### Delay Differential Equations Numerical methods

I have a general question about delay differential equations. I know that even simple ones hardly have analytic solutions and mine clearly doesn't have any as it is a system of non-linear delay ...

**0**

votes

**0**answers

133 views

### unique positive real root fast computation

What is the fastest way to compute the value of the unique positive real root corresponding to the following polynom:
:p(x) = a*x^5 + b*x^4 + c*x^3 + d*x^2 + e*x - f = 0
where a, b, c, d, e, f are ...

**4**

votes

**0**answers

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

**5**

votes

**2**answers

323 views

### Local positivity of solutions to linear differential inequalities (Chaplygin's theorem)

According to the entry "Differential inequality" of the Encyclopedia of Mathematics
http://www.encyclopediaofmath.org/index.php/Differential_inequality
the following result is due to Chaplygin ...

**0**

votes

**1**answer

155 views

### Estimating the vector potential

My question is, that given a vector field only numerically discrete in space, is there a way to estimate its vector potential?
Theoretically, I see this which requires the vector field over all of ...

**6**

votes

**2**answers

1k views

### Mathematical study of Mpemba effect?

It has been known since the days of Aristotle and Descartes that under certain circumstances warm water freezes faster than cold water. This effect is now commonly known as the Mpemba effect, named ...

**6**

votes

**1**answer

194 views

### Approximating an iteratively defined function

Let $f_0,f_1,\ldots$ be a sequence of functions $f_n : [0,1] \rightarrow R$ defined as follows:
$$f_0(x) =1+2x$$
$$f_{n}(x) := \left\{\frac{5+t}{2} : \text{ where t solves } ...

**1**

vote

**1**answer

369 views

### Approximation of the sum involving binary entropy function

Given the following sum:
$S(n) = \sum_{i=1}^{n} \frac{1}{(1-\operatorname{H}(p))^i}$
where $H$ is the binary entropy function defined as:
$\operatorname{H}(p) = -p\log p - (1-p)\log (1-p) $.
Let ...

**2**

votes

**2**answers

153 views

### dense lattices in high dimensions

I want a collection of points $\{ x_1, \dots, x_m\}$ to sample a unit cube $[0,1]^n$ with $n >>1 $ in high dimensions so that summing over these points is approximate the integral over that ...

**10**

votes

**1**answer

370 views

### The geometric-mean factorial

Think of the factorial as $f(n) = n \odot (n-1) \odot \cdots \odot 2 \odot 1$,
where $\odot$ is the binary operator for multiplication, $\cdot$. This suggests exploring replacing
$\odot$ with other ...

**-1**

votes

**2**answers

224 views

### Does an implicit Runge Kutta scheme applied on a nonlinear ODE give a nonlinear set of equations to solve in each step?

We want to approximately solve an ODE
$$\frac{dy}{dt} = f(y,t)$$
with the Runge Kutta method
$$y_{n+1} = y_n + h \sum_{i=1}^s b_i k_i$$
$$k_i = f\left(y_n + h \sum_{j=1}^s a_{ij} k_j,\,t_n + c_i ...

**1**

vote

**1**answer

278 views

### Accurate bounds for derivatives of Legendre polynomials

Let $P_n(x)$ denote the $n$th Legendre polynomial. What bounds can one give for $d_{n,m}(x) = |\frac{d^m}{dt^m}P_n(t)|_{t=x}$ assuming that $|x| \le 1$? Clearly
$$d_{n,m}(x) \le d_{n,m}(1) = ...

**10**

votes

**3**answers

839 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

72 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

90 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

242 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

70 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

220 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

238 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

98 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

91 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

343 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

166 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

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

**3**

votes

**0**answers

404 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

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

**1**

vote

**1**answer

117 views

### Looking for tighter bounds on a certain solution of a nonlinear equation

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

152 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

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