Numerical algorithms for problems in analysis and algebra, scientific computation

**93**

votes

**1**answer

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

**52**

votes

**19**answers

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

**32**

votes

**5**answers

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

**32**

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

**30**

votes

**7**answers

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

**28**

votes

**11**answers

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

**22**

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

**3**answers

878 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

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

**6**answers

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

831 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

397 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

**8**answers

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

**14**

votes

**2**answers

951 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

919 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

**9**answers

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

**13**

votes

**2**answers

907 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

287 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

**1**answer

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

**12**

votes

**3**answers

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

**1**answer

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

**12**

votes

**1**answer

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

**12**

votes

**0**answers

254 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

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

398 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

**1**answer

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

**10**

votes

**2**answers

828 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

240 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

286 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

566 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

**0**answers

133 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

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

**10**

votes

**0**answers

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

**9**

votes

**2**answers

929 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

**2**answers

618 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

691 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

**6**answers

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

**9**

votes

**2**answers

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

**9**

votes

**3**answers

425 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) \, ...

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

**8**

votes

**3**answers

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

**8**

votes

**4**answers

632 views

### What is the theoretical interest of finding closed-form sols. of infinite series?

Hi,
I was reading this when I came across Gourevitch's conjecture.
My understanding is that solutions to these series are of practical interest. If one encounters such a series, being able to solve ...

**8**

votes

**4**answers

1k views

### When Have Numerology and Computational Experimentation Been Successful?

When has numerology been successfully used in math and science? The Monstrous Moonshine conjecture led to a Fields medal for Borcherds. Balmer's formula for hydrogen spectra led to the Bohr model of ...

**8**

votes

**7**answers

1k views

### Any good books on numerical methods for ordinary differential equations?

I need to find some masters-level exercises about numerical methods for solving ODEs. Are there any good references?

**8**

votes

**1**answer

148 views

### Sharpest bound on the zero free region of $\zeta^{\prime}$?

I'm interested in calculating all of the zeroes of the first derivative of the Riemann $\zeta$ function up to an arbitrary height. I know that (on the RH), all of these zeroes will have real part $\ge ...

**8**

votes

**2**answers

251 views

### Computational methods for dealing with geometrically complicated solid boundaries in fluid-air interface problems

Hello,
I am a PhD student who does not have extensive computational experience seeking advice from those experienced with computational modelling as to which method would be most appropriate for ...

**8**

votes

**2**answers

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