from SIAM News,Volume 33,Number 4 The Best of the 20th Century:Editors Name Top 10 Algorithms By Barry A.Cipra e or the ver 2000 Jniversity of Tennessee and Oak Ridge National Laboratory and Fran-cis Sullivan of the Center for Comput-ing Sciences at the Institute for put togeth-er alist they cll the tand practi e and in the 20th century."Don aand Sullivan write As with any top-10 list,their selection and non-selection are bound to be acknow edge. s to picking th rithms: as first-order approxmations.Mosta besaleorithoudberead time 1946: euma etropolis,all at the Los Alamos Scientific Laboratory,cook up the Metropolis The metronolis algorithm aims toobtain an oximate solutions to numerical problems with unmanageably many degrees of freedom and to .Given the digital computer 1947:George Dantzig,at the RAND Corporation,creates the simplex method for linear programming In terms ntzig's algorithm is one of th e most s of linear programming is sometimes dictated by the comp utational bu nature of enes,Eduard Stiefeland Co the These algo urse. tha 1 s a huge刀xnm so tha t the alge oraic answer b/A is not easy to comput ier method known as the coni radient method for sustems thatar Bi-CGS ered es Ic ne s respectively.) 5iiAkctptioerofOakRadecNaionalLaboaionyfomalzsthcdkcompositioalaproach tations The ability to factor matrices into triangular,diagonal,orthogonal,and other special forms has tured out to The decompos software developers to produc bugbears ofn decomposition of a matrix as a product of lower and uppe Alston Householde mputer pro ammingFinally,scientists
from SIAM News, Volume 33, Number 4 By Barry A. Cipra Algos is the Greek word for pain. Algor is Latin, to be cold. Neither is the root for algorithm, which stems instead from al￾Khwarizmi, the name of the ninth-century Arab scholar whose book al-jabr wa’l muqabalah devolved into today’s high school algebra textbooks. Al-Khwarizmi stressed the importance of methodical procedures for solving problems. Were he around today, he’d no doubt be impressed by the advances in his eponymous approach. Some of the very best algorithms of the computer age are highlighted in the January/February 2000 issue of Computing in Science & Engineering, a joint publication of the American Institute of Physics and the IEEE Computer Society. Guest editors Jack Don-garra of the University of Tennessee and Oak Ridge National Laboratory and Fran-cis Sullivan of the Center for Comput-ing Sciences at the Institute for Defense Analyses put togeth-er a list they call the “Top Ten Algorithms of the Century.” “We tried to assemble the 10 al-gorithms with the greatest influence on the development and practice of science and engineering in the 20th century,” Dongarra and Sullivan write. As with any top-10 list, their selections—and non-selections—are bound to be controversial, they acknowledge. When it comes to picking the algorithmic best, there seems to be no best algorithm. Without further ado, here’s the CiSE top-10 list, in chronological order. (Dates and names associated with the algorithms should be read as first-order approximations. Most algorithms take shape over time, with many contributors.) 1946: John von Neumann, Stan Ulam, and Nick Metropolis, all at the Los Alamos Scientific Laboratory, cook up the Metropolis algorithm, also known as the Monte Carlo method. The Metropolis algorithm aims to obtain approximate solutions to numerical problems with unmanageably many degrees of freedom and to combinatorial problems of factorial size, by mimicking a random process. Given the digital computer’s reputation for deterministic calculation, it’s fitting that one of its earliest applications was the generation of random numbers. 1947: George Dantzig, at the RAND Corporation, creates the simplex method for linear programming. In terms of widespread application, Dantzig’s algorithm is one of the most successful of all time: Linear programming dominates the world of industry, where economic survival depends on the ability to optimize within budgetary and other constraints. (Of course, the “real” problems of industry are often nonlinear; the use of linear programming is sometimes dictated by the computational budget.) The simplex method is an elegant way of arriving at optimal answers. Although theoretically susceptible to exponential delays, the algorithm in practice is highly efficient—which in itself says something interesting about the nature of computation. 1950: Magnus Hestenes, Eduard Stiefel, and Cornelius Lanczos, all from the Institute for Numerical Analysis at the National Bureau of Standards, initiate the development of Krylov subspace iteration methods. These algorithms address the seemingly simple task of solving equations of the form Ax = b. The catch, of course, is that A is a huge n
n matrix, so that the algebraic answer x = b/A is not so easy to compute. (Indeed, matrix “division” is not a particularly useful concept.) Iterative methods—such as solving equations of the form Kxi + 1 = Kxi + b – Axi with a simpler matrix K that’s ideally “close” to A—lead to the study of Krylov subspaces. Named for the Russian mathematician Nikolai Krylov, Krylov subspaces are spanned by powers of a matrix applied to an initial “remainder” vector r0 = b – Ax0. Lanczos found a nifty way to generate an orthogonal basis for such a subspace when the matrix is symmetric. Hestenes and Stiefel proposed an even niftier method, known as the conjugate gradient method, for systems that are both symmetric and positive definite. Over the last 50 years, numerous researchers have improved and extended these algorithms. The current suite includes techniques for non-symmetric systems, with acronyms like GMRES and Bi-CGSTAB. (GMRES and Bi-CGSTAB premiered in SIAM Journal on Scientific and Statistical Computing, in 1986 and 1992, respectively.) 1951: Alston Householder of Oak Ridge National Laboratory formalizes the decompositional approach to matrix computations. The ability to factor matrices into triangular, diagonal, orthogonal, and other special forms has turned out to be extremely useful. The decompositional approach has enabled software developers to produce flexible and efficient matrix packages. It also facilitates the analysis of rounding errors, one of the big bugbears of numerical linear algebra. (In 1961, James Wilkinson of the National Physical Laboratory in London published a seminal paper in the Journal of the ACM, titled “Error Analysis of Direct Methods of Matrix Inversion,” based on the LU decomposition of a matrix as a product of lower and upper triangular factors.) 1957: John Backus leads a team at IBM in developing the Fortran optimizing compiler. The creation of Fortran may rank as the single most important event in the history of computer programming: Finally, scientists The Best of the 20th Century: Editors Name Top 10 Algorithms In terms of wide￾spread use, George Dantzig’s simplex method is among the most successful al￾gorithms of all time. Alston Householder