Le colloquium du LAGA aura lieu lundi 17 avril à 10h30, amphi Ampère. Martin Gander, invité sur une chaire FSMP ce semestre, nous parlera de méthodes itératives pour les systèmes linéaires.

A Brief History of Iterative Methods for Linear Systems

Iterative methods for linear systems were invented for the same
reasons as they are used today, namely to reduce computational
cost. Gauss states in a letter to his friend Gerling in 1823: « you
will in the future hardly eliminate directly, at least not when you
have more than two unknowns ».

Richardson’s paper from 1910 was then very influential, and is a model
of a modern numerical analysis paper: modeling, discretization,
approximate solution of the discrete problem, and a real application.
Richardson’s method is much more sophisticated that how it is usually
presented today, and his dream became reality in the PhD thesis of
Gene Golub.

The work of Stiefel, Hestenes and Lanczos in the early 1950 sparked
the success story of Krylov methods, and these methods can also be
understood in the context of extrapolation, pioneered by Bresinzki and
Sidi, based on seminal work by Wynn.

This brings us to the modern iterative methods for solving partial
differential equations, which come in two main classes: domain
decomposition methods and multigrid methods. Domain decomposition
methods go back to the alternating Schwarz method invented by Herman
Amandus Schwarz in 1869 to close a gap in the proof of Riemann’s
famous Mapping Theorem. Multigrid goes back to the seminal work by
Fedorenko in 1961, with main contributions by Brandt and Hackbusch in
the Seventies.

I will show in my presentation how these methods function on the same
model problem of the temperature distribution in a simple room. All
these methods are today used as preconditioners for Krylov methods,
which leads to the most powerful iterative solvers currently known for
linear systems.

[1] L.F. Richardson, The approximate arithmetical solution by finite
  differences of physical problems involving differential equations,
  with an application to the stresses in a masonry dam, Philosophical
  Transactions of the Royal Society of London. Series A, 210 (1911),
  307-357.

[2] E. Stiefel, Über einige Methoden der Relaxationsrechnung, Edouard
  Stiefel, Z. Angew. Math. Phys. 3 (1952), 1-33.

[3] H. A. Schwarz, Über einen Grenzübergang durch alternierendes
  Verfahren, Vierteljahrsschrift der Naturforschenden Gesellschaft in
  Zürich 15 (1870), 272-286.

[4] G. Ciaramella and M.J. Gander, Iterative Methods and
  Preconditioners for Systems of Linear Equations, SIAM
  (2022).

[5] M.J. Gander, P. Henry and G.  Wanner, A History of Iterative
  Methods, in preparation (2023).