50th Anniversary of Seminal NBS Publication Celebrated
March 2002
 |
| Magnus Hestenes |
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
http://nvl.nist.gov/pub/nistpubs/sp958-lide/html/081-085.html
http://nvl.nist.gov/pub/nistpubs/sp958-lide/081-085.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.
 |
| Group of NBS Institute for Numerical Analysis researchers in 1950,
including Mark Kac, Edward J. McShane, J. Barkley Rosser, Aryeh Dvoretzky,
George G. Forsythe, John Todd, Olga Taussky-Todd, Everett C. Yowell (?),
Wolfgang R. Wasow, and Magnus R. Hestenes. |
|
