Numerical algorithms for problems in analysis and algebra, scientific computation

learn more… | top users | synonyms

0
votes
0answers
88 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
0answers
535 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
2answers
260 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
1answer
102 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
2answers
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
1answer
192 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
1answer
256 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
2answers
151 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
1answer
326 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
2answers
175 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
1answer
195 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) = ...
9
votes
3answers
653 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
1answer
66 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
0answers
81 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 ...
0
votes
0answers
193 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
0answers
68 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
1answer
216 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
1answer
189 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
1answer
79 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
1answer
83 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
1answer
238 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
1answer
147 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
1answer
117 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
0answers
291 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
1answer
128 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
0answers
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
0answers
139 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
2answers
281 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
0answers
92 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
0answers
135 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
2answers
639 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
3answers
271 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
1answer
271 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 ...
10
votes
1answer
387 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
0answers
157 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
0answers
246 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
1answer
234 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
0answers
87 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
1answer
35 views

Computing a particular expection for a family of distribution

Consider the family of distributions having the form $$f = ...
4
votes
0answers
152 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
1answer
144 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
1answer
215 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
4answers
1k 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
2answers
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
2answers
496 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
1answer
407 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
1answer
241 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
0answers
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
1answer
326 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
2answers
202 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 ...