Questions tagged [na.numerical-analysis]

Numerical algorithms for problems in analysis and algebra, scientific computation

Filter by
Sorted by
Tagged with
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 ...
gmvh's user avatar
  • 2,758
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 ...
user avatar
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 ...
Ryan O'Donnell's user avatar
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 ...
Mikhail Katz's user avatar
  • 15.1k
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 ...
H A Helfgott's user avatar
  • 19.3k
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: ...
aslan's user avatar
  • 385
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 ...
user avatar
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 ...
gondolier's user avatar
  • 1,829
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{...
Tom Chen's user avatar
  • 229
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 ...
Bill Thurston's user avatar
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 ...
TerronaBell's user avatar
  • 3,039
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.
Philipp's user avatar
  • 969
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 ...
Brian Rushton's user avatar
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-...
H A Helfgott's user avatar
  • 19.3k
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,...
Amir Sagiv's user avatar
  • 3,544
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 ...
Felix Goldberg's user avatar
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 ...
Mike Battaglia's user avatar
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 ...
lino's user avatar
  • 253
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$ ...
David Cardon's user avatar
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 ...
მამუკა ჯიბლაძე's user avatar
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 ...
Simd's user avatar
  • 3,195
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 ...
Turbo's user avatar
  • 13.7k
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 ...
duccio's user avatar
  • 201
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 ...
Fumiyo Eda's user avatar
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$...
James Propp's user avatar
  • 19.4k
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 ...
Federico Poloni's user avatar
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 ...
Jules's user avatar
  • 463
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 ...
Federico Poloni's user avatar
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 ...
Jiahao Chen's user avatar
  • 1,870
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 ...
James Propp's user avatar
  • 19.4k
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 ...
Daniele Tampieri's user avatar
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 ...
Federico Poloni's user avatar
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 ...
Amir Sagiv's user avatar
  • 3,544
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 \...
Kernel's user avatar
  • 456
5 votes
1 answer
2k views

Are piecewise linear functions dense in $W^{1,\infty}$?

Are piecewise linear functions dense in $W^{1,\infty}$ ?
Buyang LI's user avatar
  • 393
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 ...
Vincenzo's user avatar
  • 501
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+...
Wane's user avatar
  • 73
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)$? ...
James Propp's user avatar
  • 19.4k
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 ...
Math_Y's user avatar
  • 311
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 ...
Yaroslav Bulatov's user avatar
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 ...
XL _At_Here_There's user avatar
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\...
Charles's user avatar
  • 8,974
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 ...
Charles's user avatar
  • 8,974
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$ ...
Charles's user avatar
  • 8,974
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+...
Fredrik Johansson's user avatar
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 ...
user avatar
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, ...
xyz's user avatar
  • 45