Numerical algorithms for problems in analysis and algebra, scientific computation

**104**

votes

**2**answers

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

**57**

votes

**19**answers

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

**34**

votes

**5**answers

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

**33**

votes

**2**answers

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

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

**30**

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

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

**23**

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

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

**18**

votes

**1**answer

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

**17**

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

**16**

votes

**3**answers

856 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

**9**answers

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

**15**

votes

**1**answer

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

**15**

votes

**1**answer

527 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

**2**answers

982 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

**1**answer

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

**14**

votes

**1**answer

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

**13**

votes

**8**answers

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

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

**13**

votes

**2**answers

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

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

**0**answers

316 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

**13**answers

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

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

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

**11**

votes

**2**answers

637 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

471 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

350 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

763 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

**2**answers

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

**10**

votes

**3**answers

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

**10**

votes

**1**answer

326 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

**1**answer

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

**10**

votes

**1**answer

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

**10**

votes

**6**answers

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

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

**10**

votes

**3**answers

628 views

### Rapid evaluation of multivariate normal integral

I'm implementing a model that requires me to numerically evaluate a multivariate normal integral of the following form
$$\int_{-\infty}^\infty \phi(z)\displaystyle\prod_{i=1}^N \Phi(a_iz+b_i) \, ...

**10**

votes

**0**answers

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

**10**

votes

**0**answers

503 views

### Once differentiable, piecewise degree three polynomials on triangulated planar domains

Here is an easily described, but very difficult, problem that I
(and a number of other people) really would like to see solved during
our life times. The basic problem is to compute the dimension of ...

**9**

votes

**3**answers

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

**9**

votes

**2**answers

1k views

### Am I allowed to do non-rigorous numerical analysis?

I have a paper where I am trying to show that the growth of a certain function is exponential of the order $a^n$. I would like to compute $a$, at least approximately. The base $a$ satisfies a very ...

**9**

votes

**4**answers

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

**9**

votes

**4**answers

282 views

### Software tools for medium-scale systems of polynomial equations

I am attempting to find all real solutions of a system of 12 polynomial equations in 12 unknowns. The equations each have total degree 6 and contain up to 1700 terms. I am only interested in real ...

**9**

votes

**2**answers

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

**9**

votes

**4**answers

980 views

### Is Gauss-Seidel guaranteed to converge on *semi* positive definite matrices?

I know that the Gauss-Seidel method is guaranteed to converge given that the matrix you want to solve is positive definite. I've looked at the proofs of convergence, and it appears that one cannot ...

**9**

votes

**2**answers

226 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 abscisas and weights $\{ x_j, w^j \} _j$ for large N. My question is how to do it, and why should it ...

**9**

votes

**2**answers

2k views

### An optimization problem for points on the sphere (master's dissertation)

First, by means of a disclaimer, some background. I am entering the fourth and final year of an undergraduate master's degree in maths, and a quarter of the maximum credit for this year will be for a ...

**9**

votes

**3**answers

1k views

### Is there a stable algorithm for polynomial division (in several variables)?

Suppose you have a homogeneous ideal $I$ inside the algebra $\mathbb{C}[x_1,...,x_d]$ of complex polynomials in $d$-variables. Can one find a basis for $I$, say $\{f_1,...,f_k\}$, such that every $h ...