Nicholas J. Higham: The Top 10 Algorithms in Applied Mathematics

pcam-p346-newton.jpg

From “Computational Science” by David E. Keyes in Princeton Companion to Applied Mathematics

In the January/February 2000 issue of Computing in Science and Engineering, Jack Dongarra and Francis Sullivan chose the “10
algorithms with the greatest influence on the development and practice of science and engineering in the 20th century” and presented a group of articles on them that they had commissioned and edited. (A SIAM News article by Barry Cipra gives a summary for anyone who does not have access to the original articles). This top ten list has attracted a lot of interest.

Sixteen years later, I though it would be interesting to produce such a list in a different way and see how it compares with the original top ten. My unscientific—but well defined— way of doing so is to determine which algorithms have the most page locators in the index of The Princeton Companion to Applied Mathematics (PCAM). This is a flawed measure for several reasons. First, the book focuses on applied mathematics, so some algorithms included in the original list may be outside its scope, though the book takes a broad view of the subject and includes many articles about applications and about topics on the interface with other areas. Second, the content is selective and the book does not attempt to cover all of applied mathematics. Third, the number of page locators is not necessarily a good measure of importance. However, the index was prepared by a professional indexer, so it should reflect the content of the book fairly objectively.

A problem facing anyone who compiles such a list is to define what is meant by “algorithm”. Where does one draw the line between an algorithm and a technique? For a simple example, is putting a rational function in partial fraction form an algorithm? In compiling the following list I have erred on the side of inclusion. This top ten list is in decreasing order of the number of page locators.

  1. Newton and quasi-Newton methods
  2. Matrix factorizations (LU, Cholesky, QR)
  3. Singular value decomposition, QR and QZ algorithms
  4. Monte-Carlo methods
  5. Fast Fourier transform
  6. Krylov subspace methods (conjugate gradients, Lanczos, GMRES,
    minres)
  7. JPEG
  8. PageRank
  9. Simplex algorithm
  10. Kalman filter

Note that JPEG (1992) and PageRank (1998) were youngsters in 2000, but all the other algorithms date back at least to the 1960s.

By comparison, the 2000 list is, in chronological order (no other ordering was given)

  • Metropolis algorithm for Monte Carlo
  • Simplex method for linear programming
  • Krylov subspace iteration methods
  • The decompositional approach to matrix computations
  • The Fortran optimizing compiler
  • QR algorithm for computing eigenvalues
  • Quicksort algorithm for sorting
  • Fast Fourier transform
  • Integer relation detection
  • Fast multipole method

The two lists agree in 7 of their entries. The differences are:

PCAM list 2000 list
Newton and quasi-Newton methods The Fortran Optimizing Compiler
Jpeg Quicksort algorithm for sorting
PageRank Integer relation detection
Kalman filter Fast multipole method

Of those in the right-hand column, Fortran is in the index of PCAM and would have made the list, but so would C, MATLAB, etc., and I draw the line at including languages and compilers; the fast multipole method nearly made the PCAM table; and quicksort and integer relation detection both have one page locator in the PCAM index.

There is a remarkable agreement between the two lists! Dongarra and Sullivan say they knew that “whatever we came up with in the end, it would be controversial”. Their top ten has certainly stimulated some debate, but I don’t think it has been too controversial. This comparison suggests that Dongarra and Sullivan did a pretty good job, and one that has stood the test of time well.

Finally, I point readers to a talk Who invented the great numerical algorithms? by Nick Trefethen for a historical perspective on algorithms, including most of those mentioned above.

This post originally appeared on Higham’s popular website.

Higham jacketNicholas J. Higham is the Richardson Professor of Applied Mathematics at The University of Manchester. He most recently edited The Princeton Companion to Applied Mathematics.

Wobbly table? Applied math can fix that

We are excited to be running a series of posts on applied mathematics by Nicholas Higham over the next few weeks. Higham is editor of The Princeton Companion to Applied Mathematics, new this month. Read his popular first post on color in mathematics here.

In The Princeton Companion to Applied Mathematics (page 50) I mention that a four-legged table provides an example of an ill-posed problem. If we take a table having four legs of equal length lying on a flat surface and shorten one leg by an arbitrarily small amount then the weight supported by that leg will jump from one quarter of the total weight to zero.

150912-1434-19-6791.jpg

A table with one leg shorter than the others wobbles, as may one sitting on an uneven floor, and how to cure wobbly tables has been the subject of a number of papers over the years. The tongue-in cheek article

Hanspeter Kraft, The Wobbly Garden Table, Journal of Biological Physics and Chemistry 1, 95-96, 2001

describes how an engineer, a physicist, and a mathematician would go about solving the problem. The engineer would invent an adjustable leg. The physicist would submit a research proposal to tackle the more general problem of “the stability of multiply-legged objects on rough surfaces”. The mathematician would construct an argument based on the intermediate value theorem to show that stability can be restored with a suitable rotation of no more than 90 degrees. This argument has been discussed by several authors, but turning it into a mathematically precise statement with appropriate assumptions on the table and the ground on which it rests is not easy.

The two most recent contributions to this topic that I am aware of are:

A. Martin, On the Stability of Four-Legged Tables, Physics Letters A, 360, 495-500, 2007

Bill Baritompa, Rainer Löwen, Burkard Polster, and Marty Ross, Mathematical Table Turning Revisited, arXiv:math/0511490v1, 17 pp., 2008

In the latter paper it is shown that if the ground on which a rectangular table rests slopes by less than 35.36 degrees and the legs of the table are at least half as long as its diagonals then the rotation trick works.

For more insight into this problem you may like to watch the video below in which Matthias Kreck explains the problem with the aid of some excellent animations.

Introducing the new video trailer for The Princeton Companion to Applied Mathematics

We are pleased to present the new video trailer for The Princeton Companion to Applied Mathematics. Modeled on the popular Princeton Companion to Mathematics, this is an indispensable resource for undergraduate and graduate students, researchers, and practitioners in other disciplines seeking a user-friendly reference book. Check out the video in which editor Nicholas Higham, Richardson Professor of Applied Mathematics at The University of Manchester, talks about the major ideas covered in this expansive project, which includes nearly 200 entries organized thematically and written by an international team of distinguished contributors.