On Numerical Stability of Iterative Methods for Solving Large Scale
Linear Algebraic Systems


(Abstract for the PANM 13 in Honor of Prof. Ivo Babuska)


Zdenek Strakos,
Institute of Computer Science,
Academy of Sciences of the Czech Republic, Prague



The process of numerical solution of real-world problems typically
consists of several stages. After describing the problem in
a mathematical language, its proper reformulation and discretization,
the resulting algebraic problem has to be solved. We focus
on this last stage, and specifically consider numerical stability
of iterative methods for solving linear systems.

In iterative methods, rounding errors have two main effects: They
can delay convergence and they can limit the attainable accuracy.
The goal of numerical stability analysis is to find algorithms and
their parts that are safe (numerically stable), and to identify
algorithms and their parts that are not.

We consider different implementations of the generalized minimal
residual method (GMRES), with different choices of the bases and 
orthogonalization techniques. We will analyze their numerical behavior
and explain, why a wrong basis, though computed with the maximal 
possible accuracy, can make the implementation inherently unstable.
Here we do not deal with trivial examples, but with implementations
used in practical computations, where the source of the trouble is
revealed after a thorough analysis. The contribution will close with
a very recent solution of the classical problem: the modified
Gram-Schmidt implementation of the GMRES method is proved
backward stable.


This contribution will present results obtained in collaboration with
C. C. Paige, McGill University, M. Rozloznik, UI AV CR and J. Liesen,
TU Berlin.