50th Anniversary of Seminal NBS Publication Celebrated
The year 2002 marks the fiftieth anniversary of a numerical method for the solution of linear systems of equations which has been hailed as one of the top 10 algorithms of the twentieth century, spawning the work of an army of mathematical researchers, and enabling the solution of innumerable difficult problems in the sciences and engineering. The algorithm was the work of researchers from NBS and the Swiss Eidgenössische Technische Hochschule (ETH). This milestone was the subject of a recent symposium held at the ETH in Zurich, Switzerland, and co-sponsored by ITL's Mathematical and Computational Sciences Division (MCSD).
In December 1952 a paper entitled Methods of Conjugate Gradients for Solving Linear Systems by Magnus Hestenes and Eduard Stiefel was published in the Journal of Research of the NBS. The work described in this paper was done at the Institute for Numerical Analysis (INA), a part of NBS on the campus of UCLA. This institute was an incredibly fertile environment for the development of algorithms that might exploit the potential of the newly emerging automatic computing engines, especially algorithms for the solution of linear systems and matrix eigenvalue problems. Some of these algorithms are classified today under the term Krylov Subspace Iteration, and this paper described the first of these methods to solve linear systems.
The impact of this work on scientific research has been enormous. More than 800 articles citing the original paper appeared during the period 1983-99, and many thousands more feature the term "conjugate gradients" in their title or abstract. In January 2000, Computing in Science and Engineering, a publication of the IEEE Computer Society and the American Institute of Physics, named Krylov Subspace Iteration as one of the Top 10 Algorithms of the Century, citing in particular the pioneering work of Hestenes, Stiefel, and NBS colleague Cornelius Lanczos. The paper of Hestenes and Stiefel was also celebrated in the NIST centennial publication A Century of Excellence in Measurements, Standards, and Technology, A Chronicle of Selected NBS/NIST Publications, 1901-2000. The description there provides additional information about Hestenes, Steifel, their collaboration at the INA, and subsequent developments (HTML, PDF).
The 50th anniversary of the conjugate gradient was recently the subject of the Symposium on Iterative Solvers for Large Linear Systems held at ETH in Zurich. The Swiss Latsis Foundation and NIST co-sponsored the event, which took place on February 18-21, 2002. Sixteen invited speakers focused on current research in the conjugate gradient family of algorithms and on scientific computing applications that rely on them, including nuclear fusion computations, solution of the Ornstein-Zernike equations in chemistry, and groundwater pollution modeling. Dianne O'Leary, a faculty appointee in MCSD, presented an invited lecture entitled "Toward Understanding the Convergence of Krylov Subspace Methods". Ronald Boisvert of MCSD served as a member of the Program Committee.
A highlight of the meeting was the emphasis on the history of the algorithms, with special lectures from some of the pioneers in the field. John Todd, Professor Emeritus of Mathematics at Caltech, who was Chief of the NBS Computation Laboratory from 1949-54, shared the story of how Eduard Stiefel came to the INA at the invitation of Olga Taussky (a consultant to NBS). Stiefel recognized some of his own results in Hestenes' technical report on conjugate gradients in the INA library, and made the decision to collaborate on the joint publication. Urs Hochstrasser, a student of Stiefel who also spent time at the INA, did some of the earliest computations with the conjugate gradient method. He recalled the excitement and interaction at NBS's INA. He later directed scientific policy for the Swiss government. Finally, Friedrich Bauer of the Technical University of Munich discussed the contributions of Stiefel and Heinz Rutishauser in Zurich. Transcribed remarks, lecture notes, and slides from the presentations of Todd, Hochstrasser, and Bauer have been made available online.
The 130 attendees enjoyed a week learning some history and delineating new research directions in preconditioning, understanding stagnation, making the algorithms more generally applicable, and providing better information on the accuracy of the solutions.