Prof. Zdeněk Strakoš, presents The Story of Conjugate Gradients

On 2019-03-28 16:15:00 at KN: E-107 (Zengerova poslucharna)
41. Prague Computer Science Seminar

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.
Responsible person: Petr Pošík