Numerical algorithms for problems in analysis and algebra, scientific computation

**112**

votes

**2**answers

11k 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 ...

**60**

votes

**19**answers

23k views

### Why were matrix determinants once such a big deal?

I have been told that the study of matrix determinants once comprised the bulk of linear algebra. Today, few textbooks spend more than a few pages to define it and use it to compute a matrix inverse. ...

**50**

votes

**2**answers

3k 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
...

**46**

votes

**8**answers

8k views

### There must be a good introductory numerical analysis course out there!

Background As a numerical analyst, I've frequently taught the 'Introductory Numerical Analysis' class. Such courses are found in many major universities; the audience typically consists of reluctant ...

**34**

votes

**7**answers

3k 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 ...

**33**

votes

**2**answers

2k views

### Recent fundamental new directions in PDEs

My main interests are in modern geometry/topology, algebra and mathematical physics. I observe that there is a raising communication, language and social barrier between this community and the ...

**32**

votes

**11**answers

6k 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 ...

**24**

votes

**3**answers

1k views

### “Wild” solutions of the heat equation: how to graph them?

It has long been known that the Cauchy initial-value problem for the
classical heat equation on $\mathbb{R}$ (or $\mathbb{R}^n$) doesn't
have unique solutions, without additional assumptions. In ...

**23**

votes

**9**answers

3k 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 mathematical value of this ...

**23**

votes

**4**answers

2k 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 ...

**22**

votes

**2**answers

5k views

### The unreasonable effectiveness of Pade approximation

I am trying to get an intuitive feel for why the Pade approximation works so well. Given a truncated Taylor/Maclaurin series it "extrapolates" it beyond the radius of convergence. But what I can't ...

**20**

votes

**2**answers

656 views

### Distribution of the Error term in GH Hardy's “curious result” $\sum_{\nu \leq n } \{ \nu \theta \}^2 = \tfrac{1}{12} n + O(1)$

In an early paper, GH Hardy talks about the distribution of "curious" sum:
$$ \sum_{\nu \leq n } \{ \nu \theta \}^2 = \tfrac{1}{12} n + O(1)$$
where $\{x\}:=x-\left \lfloor x \right \rfloor -1/2$. ...

**19**

votes

**6**answers

3k views

### Why not evaluate integrals using ODE-solvers?

Hello!
I have a question about the relationship between numerical integration and the solution of ordinary differential equations (ODE). Suppose I want to evaluate the integral
$I(x) = \int_{0}^{x} f(...

**19**

votes

**3**answers

2k views

### Convergence of finite element method: counterexamples

There are many known results proving convergence of finite element method for elliptic problems under certain assumptions on underlying mesh [e.g., Braess,2007]. Which of these common assumptions are ...

**16**

votes

**9**answers

10k 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

**1**answer

1k views

### Why is there a $\sqrt{5}$ in Hurwitz's Theorem?

Hurwitz's theorem is an extension of Minkowski's Theorem and deals with rational approximations to irrational numbers. The theorem states:
For every irrational number $\alpha$, there are infinitely ...

**16**

votes

**1**answer

932 views

### Who introduced the notion of “stability” in numerical analysis?

I am preparing a lecture course on the applications of operator theory where I intended to make some numerical analysis application. I was wondering about this question while browsing the literature I ...

**16**

votes

**2**answers

436 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 $...

**16**

votes

**3**answers

873 views

### Easy functions ?

Let $f$ be an analytic function, and suppose that we want to compute
$f(x)$. The input consists of the digits of $x$ and the output of
a rational number approximating $f(x)$. A function $f$ is called ...

**15**

votes

**1**answer

580 views

### The Chow & Robbins game ≈ 0.79295350640: improvements could come from simple statistics, or from a continuous version of the game

This question seeks help with improving a numerical estimate of the value of the Chow and Robbins game. Much about this game is unknown, such as whether its value is rational, but there are two routes ...

**14**

votes

**3**answers

1k views

### Current Research in Numeric Mathematics

To me, as an non-expert in the field, it seems as if numeric mathematics should have lost its importance because nowadays symbolic calculations or calculations with unlimited precision are generally ...

**14**

votes

**2**answers

996 views

### Minimal polynomial with a given maximum in the unit interval

Find the lowest degree polynomial that satisfies the following constraints:
i) $F(0)=0$
ii) $F(1)=0$
iii)The maximum of $F$ on the interval $(0,1)$ occurs at point $c$
iv) $F(x)$ is positive ...

**14**

votes

**2**answers

365 views

### Condition number of matrix after partial orthogonalization

I'm wondering about which bounds one can put on the condition number of
a $n\times n$ square matrix which is obtained from another $n\times n$
square matrix by orthogonalizing the first $m < n$ ...

**14**

votes

**1**answer

1k views

### A mass spring model for hair simulation

A strand of hair is represented by a set of particles connected by springs.
The velocity for a particular particle is calculated implicitly using the following formula:
$\boldsymbol{v}^{n+1/2}=\...

**13**

votes

**8**answers

4k views

### Exponential of large matrices

I want to make a diffusion kernel, which involves $e^{\beta A}$, where A is a large matrix (25k by 25k). It is an adjacency matrix, so it's symmetric and very sparse.
Does anyone have a ...

**13**

votes

**1**answer

1k views

### On the non-rigorous calculations of the trajectories in the moon landings

In a paragraph written by a person emphasizing that rigour is not everything in mathematics (I wish I had written down the details), it was stated that the moon landings would have been impossible ...

**13**

votes

**2**answers

974 views

### Seeking proof for linear algebra constraint problem.

Given a symmetric real matrix with a zero diagonal $M$, I am trying to find a diagonal matrix $D$, such that the matrix $M + D$ is positive definite, and $(M+D)^{-1}$ has a diagonal consisting of all ...

**12**

votes

**14**answers

4k views

### Basic software libraries for numerical analysis using modern programming languages?

I'm looking for a software library with a scope similar to "numerical recipes", but implemented in a modern programming language. "Modern" in this context means to me: object oriented (not C or ...

**12**

votes

**3**answers

1k views

### How should I approximate real numbers by algebraic ones?

Given a high precision real number, how should I go about guessing an algebraic integer that it's close to?
Of course, this is extremely poorly defined -- every real number is close to a rational ...

**12**

votes

**1**answer

5k views

### Meaning of $\Subset$ notation

The symbol $\Subset$ (occurring in places where $\subseteq$ could occur syntactically) comes up frequently in a paper I'm reading. The paper lives at the intersection of a few areas of math, and I ...

**12**

votes

**3**answers

3k views

### Analytical formula for numerical derivative of the matrix pseudo-inverse?

Is there a simple numerical procedure for obtaining the derivative (with respect to $x$) of the pseudo-inverse of a matrix $A(x)$, without approximations (except for the usual floating-point ...

**12**

votes

**3**answers

2k views

### Counting roots: multidimensional Sturm's theorem

Sturm's theorem gives a way to compute the number of roots of a one-variable polynomial in an interval [a,b]. Is there a generalization to boxes in higher dimensions? Namely, let $P_1,\dotsc,P_n\in \...

**12**

votes

**7**answers

4k views

### Numerical integration over 2D disk

I have a real-valued function $f$ on the unit disk $D$ that is fairly well behaved (real-analytic everywhere) and would like to find the integral $\int_D f(x,y)dxdy$ numerically. After much searching, ...

**12**

votes

**1**answer

724 views

### Regge calculus: Questions of consistency resolved?

Hello,
Regge calculus is an approximation scheme for General Relativity, which has been introduced in early-sixties and has been adopted both in numerical relativity and numerical quantum relativity. ...

**12**

votes

**1**answer

164 views

### Interval arithmetic with different definitions of intervals

Interval arithmetic normally deals with intervals defined as $[a,b]$ with rules like $$[a,b]+[c,d]=[a+c,b+d]$$ I am interested in interval arithmetic with different interval definitions such as $$\{a\}...

**12**

votes

**0**answers

349 views

### Descartes rule of signs for a noncommutative polynomial in matrix variables

Recently, while studying certain notions of "averaging" a set of input matrices, I obtained a nonlinear polynomial in matrix variables. A simple example is
\begin{equation*}
\mathcal{G}(X) := X^n - \...

**11**

votes

**8**answers

1k views

### Why does randomness work in numerical algorithms?

There are successful numerical algorithms that involves a sequence of random numbers, like Monte Carlo methods or simulated annealing. I can follow the lines of proofs of their convergence, and ...

**11**

votes

**3**answers

854 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 ...

**11**

votes

**2**answers

934 views

### Are there any known quantum algorithms that clearly fall outside a few narrow classes?

I'm trying to refresh myself on quantum algorithms and have been skimming Childs and van Dam's 2008 RMP paper among other things. From my preliminary surfing it looks like the known quantum algorithms ...

**11**

votes

**2**answers

597 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 ...

**11**

votes

**2**answers

404 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,...

**11**

votes

**2**answers

904 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 ...

**11**

votes

**2**answers

550 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 ...

**11**

votes

**1**answer

360 views

### The complexity of the leading fractional bit of a power of a rational number

On a mailing list (math-fun) that I subscribe to Dan Asimov asked what's the most efficient way to calculate the leading decimal digits (say 10 of them) of $(p/q)^n \bmod 1$ where $p$ and $q$ are ...

**11**

votes

**0**answers

219 views

### What are the difficulties in proving almost-everywhere stability of Gaussian elimination?

It is well known that Gaussian elimination without pivoting is numerically unstable, and in practice Gaussian elimination is done with row pivoting (partial pivoting). A theorem of Wilkinson states ...

**11**

votes

**0**answers

817 views

### Constructive aspects of Caratheodory's theorem in convex analysis

Let me paraphrase Caratheodory's theorem in a probabilistic setup:
Let $X$ be a real-valued random variable. For $k = 1, \ldots, m$, let $f_k: \mathbb{R} \to \mathbb{R}$ be a continuous function such ...

**10**

votes

**4**answers

627 views

### Rounding errors in images of Julia sets

One typically computes Julia sets by iterating a complex function, such as a polynomial or rational function.
How do rounding errors affect the results?
I'm looking for references on this issue, ...

**10**

votes

**1**answer

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 ...

**10**

votes

**2**answers

283 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 ...

**10**

votes

**2**answers

3k views

### What is the constant of the Coppersmith-Winograd matrix multiplication algorithm

Or at least it's order of magnitude.
I've only ever heard it described as "huge", and a google search turned up nothing.
Also, given that the Strassen algorithm has a significantly greater constant ...