2014
2015
2016
2017
2018
2019

The forty-first meeting of the Prague computer science seminar

Zdeněk Strakoš

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.

March 28, 2019

4:15pm

Auditorium E-107, FEL CTU
Karlovo nám. 13, Praha 2
Show on the map

Lecture annotation

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.

Lecturer

Zdeněk Strakoš

After finishing a degree in Mathematical Engineering at the Czech Technical University (1981) with a focus on ordinary differential equations, Zdeněk Strakoš changed his field and for several years he studied parallel computer architectures and algorithms. This gradually led to an interest in the inaccuracy of computations, including the numerical instability of the conjugate gradient method, to collaboration with A. Greenbaum and G. H. Golub in the 1990's and to several long-term stays in the USA (IMA, University of Minnesota, Stanford University, and Emory University). Since 2000, Zdeněk Strakoš has worked permanently in the Czech Republic. His work spans various areas of computational mathematics. He attempts to see research topics from various viewpoints and make connections between different fields. The conjugate gradient method remains a topic of his interest (from the first paper in 1991 to the most recent one on the spectral information in preconditioned elliptic partial differential equations and behavior of the method). Zdeněk Strakoš is a coauthor of two monographs (Oxford University Press, 2013; SIAM, 2015) and about 50 papers (e. g. Acta Numerica, SIAM Review, IMAJNA, SIMAX, SISC, Numerische Mathematik, Parallel Computing). He has received several international honors. He also serves the international community as a member and chair of evaluation panels (e. g., ERC AdG Panel PE6 - Computer Science and Informatics, 2008-2014) and prize committees (e. g., ICIAM Collatz Prize 2019, SIAM G. Pólya Prize 2019).

ABOUT THE PRAGUE COMPUTER SCIENCE SEMINAR

The seminar takes place usually on the 4th Thursday of each month at 4:15pm (except June, July, August and December) alternately in the buildings of Faculty of Electrical Engineering, Czech Technical University in Prague, Karlovo nám. 13, Praha 2 and Faculty of Mathematics and Physics, Charles University, Malostranské nám. 25, Praha 1.

Its program consists of a one-hour lecture followed by a discussion. The lecture is based on an (internationally) exceptional or remarkable achievement of the lecturer, presented in a way which is comprehensible and interesting to a broad computer science community. The lectures are in English.

The seminar is organized by the organizational committee consisting of Roman Barták (Charles University, Faculty of Mathematics and Physics), Jaroslav Hlinka (Czech Academy of Sciences, Computer Science Institute), Michal Chytil, Pavel Kordík (CTU in Prague, Faculty of Information Technologies), Michal Koucký (Charles University, Faculty of Mathematics and Physics), Jan Kybic (CTU in Prague, Faculty of Electrical Engineering), Michal Pěchouček (CTU in Prague, Faculty of Electrical Engineering), Jiří Sgall (Charles University, Faculty of Mathematics and Physics), Vojtěch Svátek (University of Economics, Faculty of Informatics and Statistics), Michal Šorel (Czech Academy of Sciences, Institute of Information Theory and Automation), Tomáš Werner (CTU in Prague, Faculty of Electrical Engineering), and Filip Železný (CTU in Prague, Faculty of Electrical Engineering)

The idea to organize this seminar emerged in discussions of the representatives of several research institutes on how to avoid the undesired fragmentation of the Czech computer science community.

Supporters

Contact