Numerical algorithms for problems in analysis and algebra, scientific computation

learn more… | top users | synonyms

10
votes
1answer
286 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
141 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
153 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
471 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
63 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
67 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
0answers
147 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 ...
2
votes
0answers
64 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 ...
1
vote
1answer
209 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 ...
1
vote
1answer
154 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 ...
2
votes
1answer
61 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
0answers
53 views

Approximate Laplace (forward) transforms

Given f(t) let's write Lf(s) = INT_0^inf f(t) exp(-ts)dt for its Laplace transform. I lately find myself looking at expansions of the form SUM_i a_i exp(-t_i s) that converge to Lf of some given ...
1
vote
1answer
74 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 ...
1
vote
0answers
45 views

Nontrivial Matrix-estimate

I try to proof the following estimate: \begin{align} h' W^{-1} H W^{-1} h \geq c h' H h \qquad c>0, \qquad\qquad (1) \end{align} where $h\in\mathbb{R}^{K-1}$ and ...
2
votes
1answer
176 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
137 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
94 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
204 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
120 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
129 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
212 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
71 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
133 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
492 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
265 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
266 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
334 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
132 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
215 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
198 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
85 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
33 views

Computing a particular expection for a family of distribution

Consider the family of distributions having the form $$f = ...
4
votes
0answers
119 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
130 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
185 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
854 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
362 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
332 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
233 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
26 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
230 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
194 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
0answers
164 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 ...
2
votes
1answer
503 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
1answer
166 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
0answers
127 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
3answers
673 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
3answers
366 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 ...