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