×

The SIAM 100-digit challenge. A study in high-accuracy numerical computing. With a foreword by David H. Bailey. (English) Zbl 1060.65002

Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 0-89871-561-X/pbk; 978-0-89871-796-9/ebook). xi, 306 p. (2004).
The 100-digit challenge was officially launched in the January/February 2002 issue of SIAM News. It went back to an idea of Nick Trefethen who used to give his graduate students in numerical analysis at Oxford University problems that can be stated in a few sentences and whose answer is a single real number. The mission was to compute that number to as many digits of precision as they could.
For the SIAM contest Nick Trefethen choose 10 challenging problems. Scoring was very simple: the contestants would get one point for each correct digit, up to ten for each problem, so the maximum score was 100 points. Nick announced that he would be impressed if anyone got 50 digits in total. The deadline was May 20, 2002.
A common feature of these problems is that they are in a sense ‘classical’. They can all be formulated easily and they originate from subjects that have traditionally received attention in mathematical curricula. At the deadline, entries had been submitted by 94 teams from 25 countries. The results were amazing: 20 teams had perfect scores of 100 and five more teams had scores of 99. A detailed report was published in the July/August issue of SIAM News.
Proving the correctness of the computed digits was not part of the challenge and not discussed in the report. The authors of the present book, members of teams that have solved all 10 problems, have addressed this issue by providing proofs for most of the problems and by providing evidence for the others, evidence that removes any doubt but is still short of proof. In most cases they discuss and compare several lines of attack.
Problem 1 ‘A twisted tail’: compute a nasty definite integral over a bounded real interval. The integrand is unbounded in a neighborhood of the left endpoint and oscillates infinitely often inside the interval of integration.
Problem 2 ‘Reliability amid chaos’: compute the endpoint of an orbit of a bouncing photon that moves in a two-dimensional space in which circular mirrors are erected around every integer lattice point.
Problem 3 ‘How far away is infinity?’: compute the spectral norm of an infinite matrix.
Problem 4 ‘Think globally, act locally’: compute the global minimum of a fast oscillating function of two variables in a bounded domain.
Problem 5 ‘A complex optimization’: compute the infinity norm of the distance between a function and its best approximation by a cubic polynomial with respect to the infinity norm.
Problem 6 ‘Biasing for a fair return’: compute a parameter in such a way that in a random walk the probability of return is \(1/2\).
Problem 7 ‘Too large to be easy, too small to be hard’: compute the \((1,1)\) entry of \(A^{-1}\) where \(A\) is an explicitly given sparse \(20000 \times 20000\) matrix.
Problem 8 ‘In the moment of heat’: compute the time when the temperature in the center of a square plate will reach a given value, given initial conditions at time zero and boundary conditions along the sides of the plane.
Problem 9 ‘Gradus at Parnassum’: compute the value of a parameter for which a parameter-dependent integral achieves its maximum.
Problem 10 ‘Hitting the ends’: a particle at the center of a \(10 \times 1\) rectangle undergoes Brownian motion until it hits the boundary. What is the probability that it hits at one of the short sides?
As one might expect, the discussion of these problems leads the authors to consider an amazing diversity of mathematical techniques. Some of the more obvious are high precision computations in Maple, Mathematica and some freely available software packages. Interval arithmetic is sometimes used to validate the digits. Maple, Mathematica and Matlab sessions are given explicitly. Symbolic computations also play a role. Among the numerical methods used we mention Newton’s method, numerical differentiation and extrapolation methods.
Among the analytic tools we cite Fourier analysis, analytical Fourier series, Fourier integrals, conformal mappings, elliptic functions, the Gamma Function, Lambert’s \(W\) function, divergent series, contour integrals, separatation of variables and singular moduli.
This is an excellent book for readers who wish to develop their problem - solving skills. It can also be recommended for teachers of numerical analysis searching for inspiration.

MSC:

65-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to numerical analysis
65Dxx Numerical approximation and computational geometry (primarily algorithms)
65Fxx Numerical linear algebra
68W30 Symbolic computation and algebraic computation
65C50 Other computational problems in probability (MSC2010)
65T40 Numerical methods for trigonometric approximation and interpolation
PDF BibTeX XML Cite
Full Text: DOI