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


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

Place Your Bets: Tim Chartier Develops FIFA Foe Fun to Predict World Cup Outcomes

Tim ChartierTim Chartier, author of Math Bytes: Google Bombs, Chocolate-Covered Pi, and Other Cool Bits in Computing has turned some mathematical tricks to help better predict the outcome of this year’s World Cup in Brazil.

Along with the help of fellow Davidson professor Michael Mossinghoff and Whittier professor Mark Kozek, Chartier developed FIFA Foe Fun, a program that enables us ordinary, algorithmically untalented folk to generate a slew of possible match outcomes. The tool weighs factors like penalty shoot-outs and the number of years of matches considered, all with the click of a couple buttons. Chartier used a similar strategy in his March Mathness project, which allowed students and basketball fans alike to create mathematically-produced brackets – many of which were overwhelmingly successful in their predictions.

Although the system usually places the most highly considered teams, like Brazil, Germany, and Argentina at the top, the gadget is still worth a look. Tinker around a bit, and let us know in the comments section how your results pan out over the course of the competition.

In the meantime, check out the video below to hear Chartier briefly spell out the logic of the formula.

Happy calculating!

New Mathematics Catalog!

Be among the first to check out our new mathematics catalog!

Of particular interest are Alexander J. Hahn’s eye-opening Mathematical Excursions to the World’s Great Buildings, Glen Van Brummelen’s rich Heavenly Mathematics: The Forgotten Art of Spherical Trigonometry, and Dana Mackenzie’s lucid The Universe in Zero Words: The Story of Mathematics as Told through Equations. Also be sure to check out our textbooks, including Anne Greenbaum and Timothy P. Chartier’s Numerical Methods: Design, Analysis, and Computer Implementation of Algorithms, a clear and concise exploration of standard numerical analysis topics, as well as nontraditional ones, including mathematical modeling, Monte Carlo methods, Markov chains, and fractals.

The selection of critical, cutting-edge titles abounds, so if you’re interested in learning more about our other mathematics books, browse our catalog. You may also sign up to stay current on our publishing endeavors with ease here: Your email address will remain confidential!

We’ll also see you at the Joint Mathematics Meeting January 9-12 in San Diego, CA at booth 311! The following book signings will be held at our booth:

Wednesday, January 9
2:00 p.m.-3:00 p.m., Glen Van Brummelen, Heavenly Mathematics: The Forgotten Art of Spherical Trigonometry

Thursday, January 10
1:30 p.m.-2:30 p.m., Alexander J. Hahn, Mathematical Excursions to the World’s Great Buildings
3:00 p.m.-4:00 p.m., Michael Starbird, The 5 Elements of Effective Thinking

Friday, January 11
11:00 a.m.-12:00 p.m., Persi Diaconis and Ron Graham, Magical Mathematics: The Mathematical Ideas That Animate Great Magic Tricks
1:00 p.m.-2:00 p.m., Dana Mackenzie, The Universe in Zero Words: The Story of Mathematics as Told through Equations
3:00 p.m.-4:00 p.m., Siobhan Roberts, Wind Wizard: Alan G. Davenport and the Art of Wind Engineering

Also, stop booth 311 to chat about March Mathness! We’re aiming to double last year’s six participating schools with a goal of twelve in 2013, providing entertainment for math and basketball aficionados alike! Find out more here in the meantime: