The story of conjugate gradients

The conjugate gradient method, counted among the top ten algorithms of the 20th century, is included in any reasonable textbook of numerical mathematics and has been implemented in many common software packages. It is therefore a seemingly well-understood topic in mathematical and computer science history. This is, however, far from the case. Despite its indisputable practical usefulness and the beauty and elegance of its mathematical formulation, the conjugate gradient method is still often misunderstood. Presentations, descriptions, and applications of the method are frequently rife with confusion and myths. In short, the primary difficulty arises from persistent attempts to see a highly nonlinear phenomenon through its linear simplification. Additionally, the method of conjugate gradients is based on short recurrences so, orthogonality and linear independence of the generated direction vectors are lost in practice typically dramatically due to rounding errors.

This (seemingly) indicates a collapse of all relevant mathematical theory, which is principally based on the orthogonality of the generated bases. Recalling the seminal works of C. Paige and A. Greenbaum, we show how connections between the method of conjugate gradients (and of the closely related Lanczos method) and classical results from several areas of mathematics lead to a better understanding of computations under the influence of rounding errors. We close by presenting recent results linking the given theory with a new view towards efficient and practical computational approaches.