Questions tagged [na.numerical-analysis]
Numerical algorithms for problems in analysis and algebra, scientific computation
77
questions
34
votes
5
answers
4k
views
Should computer code be included within publications that present numerical results?
Many research papers include numerical results obtained through computation. Most of the time such computations are performed using software that is used by many mathematicians, i.e., Maple, ...
6
votes
3
answers
430
views
Non-polynomial splines, a non-linear problem
I'm looking for references on how to construct spline-like functions from a basis that does not include piecewise polynomials.
To be specific, given a class of functions such as "decaying ...
2
votes
1
answer
157
views
Boundary condition for elliptic problems and domain decomposition
This question is motivated by one that has been previously asked on this website: Elliptic problem on a domain split in two subdomains
Consider an open domain $U$ split in two non-overlapping ...
46
votes
7
answers
12k
views
What is the time complexity of computing sin(x) to t bits of precision?
Short version of the question: Presumably, it's poly$(t)$. But what polynomial, and could you provide a reference?
Long version of the question:
I'm sort of surprised to be asking this, because ...
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 ...
14
votes
2
answers
2k
views
Rigorous numerical integration
I need to evaluate some (one-variable) integrals that neither SAGE nor Mathematica can do symbolically. As far as I can tell, I have two options:
(a) Use GSL (via SAGE), Maxima or Mathematica to do ...
7
votes
2
answers
7k
views
Computational complexity of calculating the nth root of a real number
Several sources state that the computational or time complexity of square rooting is the same as that of multiplication (or division). See for example:
Jean-Michel Muller, "Elementary Functions: ...
7
votes
3
answers
822
views
Books and resources on PDEs that use Mathematica and Matlab
Can you recommend some reference books that use software like MATLAB and Mathematica to deal with the basic topics in
analysis of PDE (the ones you can find in Strauss' book Partial Differential ...
3
votes
2
answers
2k
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 ...
1
vote
0
answers
418
views
Multivariate solution to Lambert W / product-log function
Consider solving the following system for $x$
\begin{align*}
a - b e^{\theta x} - cx = 0
\end{align*}
According to your favorite computer algebra program, one possible (and the simplest) is
\begin{...
127
votes
2
answers
16k
views
What are the shapes of rational functions?
I would like to understand and compute the shapes of rational functions, that is, holomorphic maps of the Riemann sphere to itself, or equivalently, ratios of two polynomials, up to Moebius ...
37
votes
11
answers
8k
views
"Must read" papers in numerical analysis
In 1993, Prof. L.N. Trefethen published a NA-net posting with a list of thirteen paper he used for teaching the seminar Classic Papers in Numerical Analysis.
In Trefethen's words, ... this course ...
28
votes
4
answers
3k
views
Can Gröbner bases be used to compute solutions to large, real-world problems?
In particular, suppose I have an affine algebraic variety over $\mathbb{R}^n$ described by generators of a radical ideal $I$ and I want to find (perhaps not all of the) points in the variety. Several ...
20
votes
9
answers
18k
views
What is the best algorithm to find the smallest nonzero Eigenvalue of a symmetric matrix?
see title.
An algorithm is 'good' if it is able to distinguish between zero Eigenvalues and nonzero Eigenvalues.
16
votes
3
answers
2k
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 ...
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-...
14
votes
2
answers
1k
views
Computing Gauss Legendre quadrature for large $N$
I've been scanning across the web, and haven't found a good method to compute the Gauss Legendre abscissas and weights $\{ x_j, w^j \} _{j=1}^N$ for large $N\in\mathbb{N}$. My question is how to do it,...
13
votes
2
answers
912
views
Computing a large permanent
Is there a practical way to compute the permanent of a large ($91 \times 91$) $(0,1)$ matrix?
I have tried to use the matlab function written by Luke Winslow which works great for smaller matrices ...
13
votes
1
answer
792
views
“Taylor series” is to “Volterra series” as “Padé approximant” is to _________?
Padé approximants are often better than Taylor series at representing a function. Given a Taylor series, one can use Wynn's epsilon algorithm to easily produce the Padé approximants to it.
Volterra ...
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 ...
11
votes
1
answer
2k
views
Best way to find a closest vector in a lattice
Let $v_1,\dotsc,v_n$ be linearly independent vectors in $\mathbb{R}^n$, and let $\Lambda=\bigoplus_{i=1}^n \mathbb{Z}v_i$. The question is, given a vector $w$ in $\mathbb R^n$, find the element $v$ ...
10
votes
2
answers
950
views
Machin-like formulas for logarithms
I found this math puzzle blog post
http://fredrikj.net/blog/2013/03/machin-like-formulas-for-logarithms/
which I'm reposting here with permission. I'm setting this to community wiki to minimize the ...
10
votes
1
answer
288
views
Confusion with practically implementing rational approximations
Writing a program visualizing Ford circles I've encountered a seemingly purely programmatic puzzle but then gradually realized there are some mathematical aspects of it which I don't understand. Let ...
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 ...
9
votes
3
answers
649
views
Degree necessary of a polynomial?
Given $-1<a<b<0$, I want to find a polynomial $f(x)\in\Bbb R[x]$ such that $f(x)\in[a,b]$ at every $x\in[b^2,a^2]$ and $f(0)=0$. What is minimum degree that is needed and maximum degree that ...
8
votes
2
answers
712
views
Is there a systematic theory for Gibbs measures (better if on Hilbert spaces)?
During these first months in my PhD, I realized how my computational problems can be drastically reduced to one single problem:
Find an efficient way to sample from a Gibbs measure.
Let me ...
8
votes
5
answers
14k
views
Eigenvalues of A+B where A is symmetric positive definite and B is diagonal
If I have a symmetric positive definite matrix A and a diagonal matrix B, and I know the eigenvalues of both A and B (by iterative numerical computation in A's case and trivially for B), is there any ...
8
votes
2
answers
2k
views
error estimates for multi-dimensional Riemann sums
Suppose that $f$ is a continuous function of bounded variation from $R^2$ to $R$ that's negative outside of some bounded set, and let $F=\max(f,0)$. Let $S_n$ be the Riemann sum for the integral of $F$...
7
votes
2
answers
3k
views
Factorizing a block symmetric matrix
Let $X,Y\in\mathbb{R}^{n\times n}$ be symmetric matrices. You may assume that $X$ is positive semidefinite and $Y$ negative semidefinite, if needed, but not that they are invertible.
I would like to ...
7
votes
1
answer
491
views
Numerical linear algebra: how to compute $b^TA^{-1}b$ efficiently
What is the most efficient way to compute $b^TA^{-1}b$ for a given $A$ and $b$?
Do we have to calculate $A^{-1}b$, or is this not necessary?
edit: I forgot to mention that A is symmetric and ...
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 ...
7
votes
4
answers
2k
views
Is there a name for the matrix equation A X B + B X A + C X C = D?
I happen to be working on a problem that reduces to solving the following equation:
$$\mathbf{A X B} + \mathbf{B X A} + \mathbf{C X C} = \mathbf{D}$$
where A through D are known matrices ( A, B, D ...
6
votes
3
answers
1k
views
Dependence of error on mesh for Riemann sums
Suppose $f$ is continuous on $[a,b]$ with $I = \int_a^b f(x)\: dx$,
and for every $\epsilon > 0$ let $\delta(\epsilon)$ be the largest
$\delta > 0$ such that every Riemann sum arising from a ...
6
votes
1
answer
602
views
On a fast high precision numerical analysis C library
This is probably a $y=f(x)$ question, but I searched several times on the MathOverflow without success so I decided to explicitly ask for the help of other members: please feel free to ask me to ...
6
votes
1
answer
720
views
Rank of the absolute-value matrix $|M|$ vs. rank of $M$
Let $M$ be a real matrix of rank $r$ (and let us set $M=UV^T$, with $U,V^T\in\mathbb{R}^{n\times r}$, to fix the notation).
Let $|M|$ be the matrix obtained by taking the absolute value of each entry ...
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 ...
5
votes
2
answers
286
views
Euler–Maclaurin formula in $\mathbb{Z}^d$
I was wondering whether there is a Euler–Maclaurin formula of sorts for expressions such as
$$
\sum_{x \in [a,b]^d\cap \mathbb{Z}^d} f(x) - \int_{[a,b]^d}f(x)
$$
where $d\ge 2$ is an integer, $a,b \...
5
votes
1
answer
2k
views
Are piecewise linear functions dense in $W^{1,\infty}$?
Are piecewise linear functions dense in $W^{1,\infty}$ ?
5
votes
6
answers
3k
views
The maximum of a real trigonometric polynomial
Given the coefficients $a_0,\ldots,a_N$, $b_1,\ldots,b_N$ of a real trigonometric polynomial:
$ f(x) = a_0 + \sum_{n=1}^N a_n \cos(nx) + \sum_{n=1}^N b_n \sin(nx) $
is there any efficient way to ...
5
votes
0
answers
224
views
Validity of $\ln z=\frac{\pi}{\operatorname{AGP}(\theta_2^2(1/z),\theta_3^2(1/z))}$
Definitions
For the definitions of $\operatorname{AGP}$ and $\operatorname{AGO}$, see here or here. $\theta_2(z)$ and $\theta_3(z)$ are defined as follows:
$$\theta_2(z)=\sum_{n=-\infty}^\infty z^{(n+...
5
votes
0
answers
141
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)$?
...
4
votes
1
answer
618
views
Singular value decomposition of truncated discrete Fourier transform matrix
Let $\mathbf{F}$ be a discrete Fourier transform (DFT) matrix such that
\begin{align}
F_{m,n}=e^{-j2\pi(m-1)(n-1)/N},\quad m,n=1,\ldots,N.
\end{align}
What we can say about the singular value ...
4
votes
2
answers
1k
views
Optimizing over matrices with spectral radius <1?
Suppose $F(x)$ is a convex objective function on $n\times n$ matrices, and I need to numerically optimize $F$ with the condition that $x$ has spectral radius less than $1$. This might be too hard, so ...
4
votes
1
answer
206
views
The link and equivalence between variant definition of computation model and computational complexity over reals
To unify the numerical computation and classic computability theory, or to pave a foundation for the numerical computation, mathematicians present variant computation model and computational ...
4
votes
2
answers
1k
views
Calculating the infinite product from the Hardy-Littlewood Conjecture F
The Hardy-Littlewood Conjecture F [1] involves the infinite product
$$\prod\left(1-\frac{1}{\varpi-1}\left(\frac D\varpi\right)\right)$$
where $\varpi$ ranges over the odd primes and $\left(\frac D\...
4
votes
1
answer
682
views
Calculating the constant in the Bateman-Horn-Stemmler conjecture
Bateman & Horn [1], building on Bateman & Stemmler [2], give a conjectured formula for the density of numbers that produce simultaneous primes in a number of fixed polynomials.
The constant ...
4
votes
0
answers
176
views
Computing the density of a set of multiples
Erdős and his coauthors often wrote about problems relating to the densities of sets of multiples. I have a computational question about the same topic. I have a finite* set $A=a_1<\cdots<a_r$ ...
4
votes
1
answer
982
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+...
4
votes
1
answer
410
views
Exponential map/ Lie derivative in variation for constant formula for ODE
In short: The question is how to go from the first equation on page 8, of this paper to the second equation.
Some background
I'm working in optimization and I am currently reading a paper
see page ...
4
votes
1
answer
1k
views
How to deduce the recursive derivative formula of B-spline basis?
Description
Let $\vec{U}=\{u_0,u_1,\ldots,u_m\}$ denote a non-decreasing sequence of real numbers, i.e, $u_i\leq u_{i+1} \quad i=0,1,2\ldots m-1$,
and the $i$-th B-spline basis function of $p$-degree, ...