The Top Ten Algorithms of the Century

Jack Dongarra and Francis Sullivan published a list of "The Top Ten Algorithms of the Century." Their list included:

1. the Monte Carlo method or Metropolis algorithm, devised by John von Neumann, Stanislaw Ulam, and Nicholas Metropolis;
2. the simplex method of linear programming, developed by George Dantzig;
3. the Krylov Subspace Iteration method, developed by Magnus Hestenes, Eduard Stiefel, and Cornelius Lanczos;
4. the Householder matrix decomposition, developed by Alston Householder;
5. the Fortran compiler, developed by a team lead by John Backus;
6. the QR algorithm for eigenvalue calculation, developed by J Francis;
7. the Quicksort algorithm, developed by Anthony Hoare;
8. the Fast Fourier Transform, developed by James Cooley and John Tukey;
9. the Integer Relation Detection Algorithm, developed by Helaman Ferguson and Rodney Forcade; (given N real values X_I, is there a nontrivial set of integer coefficients A_I so that sum ( 1 <= I <= N ) A_I * X_I = 0?
10. the fast Multipole algorithm, developed by Leslie Greengard and Vladimir Rokhlin; (to calculate gravitational forces in an N-body problem normally requires N^2 calculations. The fast multipole method uses order N calculations, by approximating the effects of groups of distant particles using multipole expansions)

Reference 1:

Dongarra and Sullivan,
Top Ten Algorithms of the Century,
Computing in Science and Engineering,
January/February 2000.

Reference 2:

Barry Cipra,
The Best of the 20th Century: Editors Name Top 10 Algorithms
SIAM News,
Volume 33, Number 4, May 2000, page 1.

Back to the home page.