Numerical algorithms for problems in analysis and algebra, scientific computation

learn more… | top users | synonyms

1
vote
0answers
73 views

Global Approximation via Convex Combination of Local Approximations

I recently faced the problem of efficiently approximating a very large set of data points and, neither having a model of the empiric function, nor of the error distribution, my method of choice would ...
4
votes
1answer
220 views

Rank 1 Approximation of Elementwise Inverse Matrix

I'm wondering whether there is a good way to solve the following optimisation problem. Given a strictly positive quadratic matrix $A$, find two diagonal matrices $D_1$ and $D_2$ so that $$ \| D_1 A ...
0
votes
0answers
220 views

Solving a parabolic PDE with boundary conditions given over ranges

How can one solve a Parabolic PDE (like the wave or diffusion equations) if the boundary conditions were given over ranges? Here is an example: How to solve the equation $u_{xx}+u_{yy}-\alpha^{2}u_{t}...
1
vote
0answers
358 views

Bounds for the infinity norm of the inverse for certain diagonaly dominant matrices

I m trying to analyse the stability against perturbations for a specific system of linear equations $Ax=b$. For this, i use the standard condition number $||A||_{\infty}||A^{-1}||_{\infty}$. Here ...
1
vote
0answers
59 views

Using FFT to aproximate a fuction [closed]

I am trying to use the FFT to approximate a given function. So i have 10 points xk that are given for example, if i use the FFT that will give me Xk. So now using the inverse FFT we can get the ...
2
votes
3answers
271 views

What are some good sanity checks for simulating BNLS?

After doing some googling, I failed to find any explicit solution for the Biharmonic Nonlinear Schrodinger Equation, which states: $$ i\psi (x,t) _t - \Delta ^2 \psi (x,t) + |\psi (x,t) | ^{2 \sigma} \...
4
votes
3answers
237 views

Quadrature formula max accuracy

I'm looking for a maximum accuracy quadrature formula: $$ \int_{-1} ^{1} \sqrt{\frac {1-x}{1+x}} f(x)dx = A_1f(x_1)+A_2f(x_2)+R(f) $$ I don't know exactly if it's Trapezoidal rule which has the ...
1
vote
1answer
213 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
1answer
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 $\frac{\sqrt[n]{\prod_{i=1}^...
2
votes
1answer
159 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 $u(x)$...
3
votes
1answer
212 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} (u_3-u_1)^{\...
2
votes
0answers
94 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
1answer
419 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
1answer
114 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 A\|\|u^k-u\|...
8
votes
1answer
288 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
1answer
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
1answer
249 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
1answer
405 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
0answers
105 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= \begin{...
3
votes
1answer
133 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
2answers
156 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
0answers
100 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
0answers
177 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
2answers
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
0answers
108 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
1answer
221 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
1answer
245 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
1answer
872 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 ...
5
votes
1answer
486 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
0answers
138 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
764 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
332 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 (1919)...
0
votes
1answer
164 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 $\...
7
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
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 } f_{n-1}\left(\frac{x}{t}...
1
vote
1answer
378 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
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
1answer
379 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
231 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 h\...
1
vote
1answer
289 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) = \frac{(m+...
11
votes
3answers
867 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
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
0answers
92 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
245 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
71 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
222 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
241 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 $x^*\in[...
1
vote
1answer
99 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 (b_n)_{i_n}}{(c)_{m}...
1
vote
1answer
92 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
349 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 ...