Questions tagged [na.numerical-analysis]
Numerical algorithms for problems in analysis and algebra, scientific computation
1,224
questions
16
votes
2
answers
746
views
Numerical integration using interval arithmetic, nowadays
This is an update to my question Rigorous numerical integration from three years ago.
Is there now a package for rigorous numerical integration that uses interval arithmetic and has access to a well-...
0
votes
1
answer
47
views
$C^\infty$ Periodic Pole-free Rational Interpolation
let $\quad-1=x_0 < x_1 <\ ...\ < x_n<1\quad$ be a set of abscissas
and $\quad(y_0, y_1,\ ...\,y_n)\quad$ a sequence of the corresponding ordinates.
Question:
what can be said ...
3
votes
1
answer
111
views
Numerically decomposing a function as a sum of non-integer powers
Let $f(x)$ be a function of $x\in(0,1)$ that I can compute numerically. I expect that there exists a convergent decomposition of the type
$$
f(x) = \sum_{n=0}^\infty a_n x^{\Delta_n}
$$
for some real ...
3
votes
2
answers
481
views
Unknown bias in a distribution related to prime numbers
If $n$ is composite then $\phi(n) < n-1$, hence there is at least one divisor $d$ of $n-1$ which does not divide $\phi(n)$. We call $d$ as the totient divisor of $n$. Trvially, if $n$ is prime then ...
2
votes
0
answers
258
views
Difficult integral - speed up numerical integration using a trick?
I have the following integral that I need to solve (with high precision) millions of times in my simulations. This is time consuming and is prohibiting me from proceeding from proceeding forward.
I ...
2
votes
2
answers
740
views
Approximation rate of $L^2$ function by piecewise constant functions
Let $\{x_i\mid i\in \mathbb{Z}\}$ be a partition of $\mathbb{R}$ with equal distance $h>0$, and a given function $f\in L^2(\mathbb{R})$. I approximate $f$ by $P_hf$, the $L^2$ projection of $f$ on ...
3
votes
1
answer
285
views
Fluctuating constants
Let $p_k$ be the $k$-th prime number, $\gamma$ be the Euler-Mascheroni constant and $M$ be the Meissel–Mertens and let $m$ be the integer part of $\log p_n$. We can show that
$$
\sum_{r=1}^{m} \frac{...
5
votes
2
answers
851
views
Pade approximation of gaussian distribution to given precision
Apologies if the question is too elementary here.
For a certain computational application I need to approximate Gaussian distribution $e^{-x^2}$ with specific absolute precision (within $10^{-7}$ ...
4
votes
2
answers
626
views
Difference between Chebyshev first and second degree iterative methods
Consider linear equation $Au = f$.
We want to solve it with iterative method (assuming $A$ is good).
First order iterative method is:
$$
u^{k+1} = u^k - \alpha_{k+1}(Au^k - f),
$$
The second degree ...
2
votes
1
answer
233
views
Computing 3-term connection coefficients for wavelets
I am trying to calculate the three-term connection coefficients
$$
Λ_{l,m}^{d_1,d_2,d_3} = \int_{-\infty}^\infty \varphi^{(d_1)}(x) \varphi^{(d_2)}_l(x) \varphi^{(d_3)}_m(x) dx
$$
for Daubechies ...
2
votes
0
answers
58
views
Similar matrix for numerical computations [closed]
I compute numerically a symmetric matrix $W$ from the flow of a ode. I have to check numerically if this matrix is definite-positive.
Two cases:
either I use the Cholesky algorithm :ok
or I compute ...
1
vote
0
answers
70
views
The jump set of $SBV$ function for different value of parameter in image denoising problem
The classical Mumford-Shah image denoisng problem study the minimizer of the following functional, for each $\alpha>0$ where $\Omega\subset \mathbb R^2$ is open bounded with sommth boundary,
$$
u_\...
1
vote
0
answers
171
views
Negative eigenvalue of Toeplitz Hermitian matrix?
I am working on estimation of a covariance matrix and I know that the matrix is Toeplitz. The desired matrix should not produce negative eigenvalues at all. However, sometime my estimation leads to a ...
3
votes
0
answers
82
views
Eigenvalues of approximations to product-convolution operators
Consider an operator $T: L^2 \mapsto L^2$ of the form $TA = g (h \ast A)$ where $g$ is and $h$ are bounded $C^\infty$ functions.
This operator $T$ can be shown to be Hilbert-Schmidt, hence compact. ...
4
votes
0
answers
146
views
Connection between cardiac equations and untangling knots?
I was surprised to learn that there is (conjecturally) a connection between a cardiac muscle model known as the FitzHugh-Nagumo equations, and untangling knots:
Maucher, Fabian, and Paul Sutcliffe. ...
7
votes
1
answer
286
views
A centralised website for computational attempts in graph theory and metric geometry?
The set of questions below stems from this question.
1) does a website exist that contains (at least links to) code and data files, with the aim to centralise computational results in graph theory ...
6
votes
2
answers
756
views
Symmetric matrix formula for Gauss-Legendre quadrature
While searching the web, I came across the following algorithm for the Gauss-Legendre quadrature. I wasn't able to find a reference or a proof of my own as to why it works. I'll present it, and the ...
8
votes
1
answer
203
views
Fast Fourier Transforms for non-trigonometric bases
The fast Fourier transform allows decomposition into a sin/cos basis in $N \log(N)$ complexity. Can one generalize the algorithm (or the ideas used) to other bases, e.g. orthogonal polynomial bases ...
3
votes
0
answers
163
views
Deriving Milne's predictor of order four from extrapolation polynomial [closed]
I am trying to derive the following Milne's predictor formula of order four for the differential equation $\frac{dy}{dx}=f(x,y)$ from an extrapolation polynomial of degree four. $$y_{n+1} = y_{n-3}+\...
0
votes
1
answer
453
views
Efficient computation of matrix exponential of trace zero matrix [closed]
I am looking for identities that may help with numerical computation of the matrix exponential ${\rm exp}(A)$ where ${\rm tr}(A)=0$. I am already aware of general-purpose algorithms for computing the ...
1
vote
0
answers
2k
views
How to rotate a covariance matrix which contains quaternion elements? [closed]
I am implementing a paper which recovers full-3d body pose from images.
It represents individual body parts as 7D vectors containing first the absolute 3D location [x y z] and then the unit ...
10
votes
1
answer
443
views
How to compute $\sum_{x \in \mathbb{Z}^n} e^{-x^TMx}$ efficiently
Let $M$ be a real symmetric integer valued positive definite matrix with $\det(M) \geq 1$. I would like write code to compute
$$S_M= \sum_{x \in \mathbb{Z}^n} e^{-x^TMx}.$$
One option is to simply ...
1
vote
1
answer
82
views
Subquadratic multiplication of probability mass functions (with log-convolution?)
We are currently looking for a fast, i.e. subquadratic, algorithm for the following equation:
$z_m = \sum_{i,j :\, (i \cdot j) = m} x_i \cdot y_j$.
That is, we are given two finite input vectors $x$ ...
1
vote
0
answers
90
views
Separable Least squares - is there a notion of conjugate directions?
I have a general question.
Suppose I have the following to optimize
$$\|Y-A(\mathbf{x})B(\mathbf{y})\|^2$$
where $Y$ is a vector, $A(\mathbf{x})$ is a matrix that depends on a vector $\mathbf{x}$ in a ...
4
votes
0
answers
468
views
Efficiently calculate the trace of the product of two large but symmetric matrices, one of which is an inverse
Sorry about the long title. I need to calculate the trace of $M(M+D)^{-1}$, where $M$ is a dense symmetric matrix, and $D$ is a diagonal matrix. The main issue is the dimension could be large (usually ...
4
votes
0
answers
688
views
What does the Von Neumann's stability analysis tell us about non-linear finite difference equations?
I've asked this question on computation science stackexchange, but it did not receive any answers so I have decided to ask it here as well.
I am reading a paper [1] where they solve the following non-...
7
votes
3
answers
2k
views
Euler Schemes in Stochastic Differential Equations
So i am trying to understand what happens in Implicit (backward) and Explicit (forward) Euler in Stochastic Differential Equations
I'll start with explicit. Say I have the following SDE known as ...
7
votes
1
answer
231
views
Add a multiple of $I$ to a matrix to minimize its operator norm
Given $A\in\mathbb{C}^{n\times n}$, what is $s_* = \arg\min \|A-sI\|$?
Here $\|A\|$ is the operator norm, $\|A\|=\rho(A^*A)^{1/2}$, and $I$ is the identity.
The corresponding problem for the ...
57
votes
2
answers
5k
views
Recent observation of gravitational waves
It was exciting to hear that LIGO detected the merging of two black
holes one billion light-years away. One of the black holes had 36
times the mass of the sun, and the other 29. After the merging the
...
1
vote
0
answers
223
views
Find optimal value for a regularization parameter in generalized eigenvalue problem
Consider the generalized eigenvalue problem :
$ \Sigma_{XY} \Sigma_{YX} {W} = \lambda \Sigma_{XX} {W} $
where $\Sigma_{XX} $ and $\Sigma_{XY}$ are sample covariance matrices are of the matrices $X$...
2
votes
0
answers
360
views
What's the advantage of majorization-minimization (MM) algorithm [closed]
The majorization-minimization (MM) algorithm is a framework for convex and nonconvex optimization. When applied to nonconvex optimization, the MM algorithm solves a sequence of convex problems to ...
7
votes
0
answers
311
views
An inequality which involves a sum of integrals
Please help me to prove
$$
\sum\limits_{j=2}^n \frac{1}{j^\alpha (j-1)^\alpha} \int\limits_{j-1}^j \frac{dx}{x^{1-\alpha}(n-x)^\alpha} \leq \int\limits_0^1 \frac{dx}{x^{1-\alpha}(n-x)^\alpha},\quad \...
1
vote
1
answer
852
views
Uniqueness and invariance of the LDLT decomposition
A real symmetric positive semi-definite matrix $A$ can be decomposed in the form
$A = P^TLDL^TP$,
where $P$ is a permutation matrix, $L$ is a lower unit triangular matrix and $D$ is a diagonal ...
1
vote
0
answers
110
views
Evaluate a Function to Full Machine Precision [closed]
If we want to evaluate $$f(x)=\frac{e^x-1-x}{x^2}$$ then we have to observe its large relative error as $x\to 0$.
My question is that how can we find a method so that we can compute $f(x)$ to full ...
3
votes
1
answer
120
views
Injectivity of vector functions: Numerical Verification
Problem Setup
Let $f:A\rightarrow B$, be a continuous function, $A\subset\Re^{n}$,$B\subset\Re^{m}$, $m\geq n$ and $A, B$ compact.
The function $f(\cdot)$ can only be evaluated numerically.
...
2
votes
1
answer
151
views
Reference Request: Variational Problem
I want to solve approximately the following variational problem:
Given a function $c:[-1,1]^2\rightarrow [0,1]$, constants $p_1...p_n\in \mathbb{R}^+$, $\alpha_1...\alpha_n\in \mathbb{R}$, and $\...
2
votes
1
answer
1k
views
Solving a simple Schrödinger equation with Fast Fourier Transforms
While trying to solve a stochastic Gross-Pitaevskii equation I have found a problem that can be tracked down to something buggy occurring in the simplest Schrodinger equation possible:
$$\partial_t \...
1
vote
0
answers
26
views
How can I filter the effects of a variable from a correlation matrix?
I have a correlation matrix (it contains 500 columns and 500 rows) and I would like to make an other correlation matrix in which one variable (and its influences) is filtered from the initial matrix. ...
1
vote
0
answers
64
views
Maximization of the difference of a monotone submodular function and a linear function with a cardinality constraint
Maximizing a monotone submodular function with a cardinality constraint can be solved by using a simple greedy heuristic. However, if the submodular function is non-monotone, the greedy heuristic can ...
7
votes
2
answers
369
views
Alternating binomial Dirichlet series
I have come across the following deceptively simple expression:
$$ H_n^s=\sum_{j=1}^n(-1)^{j-1}\left(\begin{array}{c}n\\j\end{array}\right)j^{-s} $$
We have (using eg mathematica, though probably ...
12
votes
2
answers
4k
views
Why Householder reflection is better than Givens rotation in dense linear algebra?
It’s obvious that Givens rotation works better with sparse matrices. But I don’t know why Householder reflection is better for dense matrices. Does it require less computations? Or it’s numerically ...
5
votes
2
answers
1k
views
Roots of the Chebyshev polynomials of the second kind
It is known that the roots of Chebyshev polynomials of the second kind, denote it by $U_n(x)$, are in the interval $(-1,1)$. I have noticed that, by looking at the low values of $n$, the roots of $(...
3
votes
1
answer
609
views
Claimed Quadrature Results seem Impossible
We've been preparing a preprint that shows that the convergence bounds proved for tanh-sinh quadrature for numerical integration, cannot possibly hold, and an error must exist - since they imply a P ...
4
votes
0
answers
175
views
numerical stability of root identification via Newton-Raphson iteration of Stieltjes residue sums
I have asked several questions on math.SE in order to compute numerically the poles of high-degree Padé approximations for $e^{-x}$, because a computation directly from the polynomial ...
0
votes
1
answer
312
views
Is spectral properties a general term for condition number?
I am reading an article about solving large sparse linear systems, in this paper it’s said that most of the iterative methods to solve $Ax = b$ are very much influenced by the spectral properties of ...
5
votes
0
answers
2k
views
Find the axis of symmetry in a point cloud
I have some dataset which describes a spherical cloud of points in 4D space. Actually, the coordinates of the points are the coefficients of unit quaternions, so you get the idea on what the data is ...
35
votes
9
answers
14k
views
What is... a grossone?
Y. Sergeyev developed a positional system for representing infinite numbers using a basic unit called a "grossone", as well as what he calls an "infinity computer". The ...
3
votes
0
answers
240
views
Numerical inversion involved confluent hypergeometric (1F1) (or Kummer function)
Edit: The question is solved !! The code is actually correct. There is not error in the codes. I miss-used it. Thank you for your attention : )
This problem arises when I tried to compute the valua ...
2
votes
0
answers
94
views
Numerical techniques for nonlinear, coupled integro-differential equations
The gist of the problem I have is I want to be able to find a numerical solution to these three coupled, rather unpleasant looking integro-differential equations
(1):
$$ \frac{d^2 x(t)}{dt^2} = \frac{...
19
votes
2
answers
760
views
"Fractally self-similar" numbers
This is another question about visualization of Ford circles, the previous one being Confusion with practically implementing rational approximations. Here is an output of zooming into Ford circles at $...