ITLApplied  Computational Mathematics Division
MCSD Highlights
Attractive Image NIST

NBS-Developed Method Named `Algorithm of the Century'

February 2000

A mathematical algorithm developed at NBS during the 1950s has been identified as one of the "Top 10 Algorithms of the Century" by Computing in Science & Engineering (CS&E) magazine. The algorithm, actually a class of methods, known today as Krylov subspace iteration, saw its genesis in work done by Magnus Hestenes, Eduard Stiefel, and Cornelius Lanczos of the Institute for Numerical Analysis operated by NBS at UCLA in the late 1940s and early 1950s. Hestenes and Lanczos were NBS staff members, while Stiefel was a visitor from the ETH in Zurich. Krylov methods can be used to solve very large systems of linear equations. Early Krylov methods were proposed by Lanczos and then by Hestenes and Stiefel, who called their technique the conjugate gradient method. These methods have the advantage of not requiring an array of matrix elements to be stored, and hence are of great interest in solving very large, sparse systems. The first reports on these methods were published in the NBS Journal of Research in 1952. Since then, many thousands of papers have been published on this topic, and Kyrlov methods remain the most popular and effective techniques for solving such problems today.

The January/February 2000 issue of CS&E in which this algorithm was cited set out to identify the "10 algorithms with the greatest influence on the development and practice of science and engineering in the 20th century". The 10 algorithms they identified (in chronological order) are: Metropolis Algorithm for Monte Carlo, Simplex Method for Linear Programming, Kyrlov Subspace Iteration, 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, and the Fast Multipole Method. CS&E is a joint publication of the IEEE Computer Society and the American Institute of Physics.

Several NIST staff members contributed to this issue of CS&E by writing articles describing the selected algorithms. Isabel Beichl of ITL's Mathematical and Computational Sciences Division co-authored the article on the Metropolis algorithm. Francis Sullivan (guest researcher, 891) of the IDA Center for Computing Sciences was Beichl's co-author, and was also co-editor of the special section on the top 10 algorithms. Two ITL faculty appointees from the University of Maryland also contributed. G. W. Stewart (891) wrote about matrix decompositions, and Joseph JaJa (895) described Quicksort.

(bullet) Ronald F. Boisvert (NIST/MCSD)
See also:
(bullet) CS&E magazine

Privacy Policy | Disclaimer | FOIA
NIST is an agency of the U.S. Commerce Department.
Last updated: 2011-01-12.