Numerical algorithms for problems in analysis and algebra, scientific computation

learn more… | top users | synonyms

93
votes
1answer
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
19answers
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
5answers
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
2answers
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
7answers
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
11answers
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
4answers
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
3answers
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
3answers
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
6answers
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
3answers
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
1answer
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
8answers
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
2answers
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
1answer
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
9answers
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
2answers
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
2answers
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
1answer
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
3answers
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
1answer
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
1answer
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
0answers
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
8answers
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
3answers
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
2answers
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
1answer
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
2answers
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
3answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
2answers
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
2answers
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
4answers
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
6answers
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
2answers
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
3answers
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
2answers
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
3answers
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
3answers
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
4answers
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
4answers
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
7answers
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
1answer
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
2answers
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
2answers
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 ...