Celebrating 50 Years of the Conjugate Gradient Method

June 3, 2002

On hand with tales from the rich history of Krylov subspace methods were pioneering researchers Friedrich Bauer and Urs Hochstrasser.

Dianne O'Leary

The Symposium on Iterative Solvers for Large Linear Systems, co-sponsored by the International Latsis Foundation and by the U.S. National Institute of Standards and Technology (NIST, formerly known as NBS), was held at ETH Zurich, February 18-21. The symposium marked the 50th anniversary of the publication of the paper "Methods of Conjugate Gradients for Solving Linear Systems," by Magnus Hestenes (NBS) and Eduard Stiefel (ETH), in the Journal of Research of the National Bureau of Standards.

A conference in celebration of a paper is certainly an unusual event, but this is no ordinary paper. Science Citation Index lists more than 800 direct citations between 1983 and 1999, evidence of the enormous theoretical and practical impact of the research. The paper 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. In addition, Computing in Science and Engineering, a publication of the IEEE Computer Society and the American Institute of Physics, named Krylov subspace iteration one of the "top 10 algorithms of the century," citing in particular the pioneering work of Hestenes, Stiefel, and Cornelius Lanczos.

The 16 invited speakers at the conference focused on current research in the conjugate gradient family of algorithms (Bernhard Beckermann, Anne Greenbaum, Gerard Meurant, Dianne O'Leary, Chris Paige, Zdenek Strakos), preconditioning strategies (Michael Griebel, Wei-Pai Tang, Gene Wachs-press), and on scientific computing applications that rely on these algorithms, including the solution of convection-diffusion equations (Howard Elman), structural mechanics problems (Charbel Farhat), dynamical systems (Roland Freund), the Ornstein-Zernike equations in chemistry (Tim Kelley), electronic structure models (Youcef Saad), nuclear fusion simulations (Ray Tuminaro), and groundwater pollution models (Gabriel Wittum).

A highlight of the meeting was the emphasis on the history of Krylov subspace algorithms, with special lectures by some of the pioneers in the field. Urs Hochstrasser, as a student of Stiefel, did some of the earliest computations with the conjugate gradient method; he later directed scientific policy for the Swiss government. He recalled the excitement and interaction at the NBS Institute for Numerical Analysis (INA) in Los Angeles.

Friedrich Bauer of Munich discussed the influence of the relay computer Z4, acquired for ETH by Stiefel, on the mathematical work of Heinz Rutishauser, turning his attention to the development of numerical algorithms. John Todd shared the story of Eduard Stiefel's visit to INA, at the invitation of Olga Taussky; recognizing some of his own results in Hestenes's technical report on conjugate gradients in the library, Stiefel had made the decision to collaborate on the joint publication.

The meeting also marked the 70th birthday of Gene Golub, and many speakers and attendees offered reminiscences and thanks to Gene. Walter Gautschi gave a presentation on Gene Golub's contributions at the interface between analysis and linear algebra, and Nick Trefethen gave a tribute to Gene at the conference banquet.

A second milestone celebrated at the symposium was the 70th birthday of Gene Golub (center), shown here at the banquet with Walter Gander and Michael Saunders.

Walter Gautschi discussed Gene Golub's contributions at the interface between analysis and linear algebra.

It was fitting that ETH and NIST, important centers in the numerical analysis revolution of the 1950s, cooperated in organizing the conference. Thanks to the hard work of the local organizers, Walter Gander and Martin Gutknecht, the 130 attendees spent an enjoyable 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.

Further information is available at http://math.nist.gov/mcsd/highlights/cg50.html. Pictures from the conference have been posted at http://www.inf.ethz.ch/personal/broeker/cg50pics.

Dianne O'Leary is a professor of computer science at the University of Maryland, College Park.

Donate · Contact Us · Site Map · Join SIAM · My Account
Facebook Twitter Youtube linkedin google+