Conjugate Gradients and Related KMP Algorithms: The Beginnings

Abstract

In the late 1940's and early 1950's, newly available computing machines generated intense interest in solving ``large'' systems of linear equations. Among the algorithms developed were several related methods, all of which generated bases for Krylov subspaces and used the bases to minimize or orthogonally project a measure of error. These methods include the conjugate gradient algorithm and the Lanczos algorithm. We refer to these algorithms as the KMP family and discuss its origins, emphasizing research themes that continue to have central importance. (Also cross-referenced as UMIACS-TR-95-107)