Numerical Stability of GMRES: Recent Results and Open Questions
Miroslav RozloznikSwiss Center for Scientific Computing (CSCS/SCSC)
Swiss Federal Institute of Technology (ETH)
ETH-Zentrum, CH-8092 Zurich, Switzerland
e-mail: miro@scsc.ethz.ch
Wednesday November 25, 2.30 p.m. Parallel Algorithms Seminar CERFACS Conference Room
Abstract :
The classical variant of the Generalized Minimal Residual Method (GMRES) consists of constructing the Arnoldi basis of the Krylov subspaces and then solving the transformed least squares problem at each individual iteration step. In exact arithmetic the Arnoldi vectors are orthogonal. However, in finite precision computation the orthogonality is lost, which may potentially affect both the convergence rate and the ultimate attainable accuracy of the computed approximate solution. One may therefore want to keep the computed orthogonality as close to the machine precision as possible using proper orthogonal transformations, e.g. Householder orthogonalizations.
The price is, unfortunately, too high for most of the applications.
The Gram-Schmidt process is a cheaper alternative and its modified version represents the most frequently used compromise.
Although, the modified Gram-Schmidt orthogonalization may end up with the basis which lost its orthogonality completely, in the GMRES context, however, there is a very important relation between the loss of orthogonality among the Arnoldi vectors and the decrease of the residual of the computed approximation close to its final value.
It was proved that, for the modified Gram-Schmidt GMRES, the Arnoldi vectors loose their orthogonality completely only after the residual of the computed approximation is reduced close to its final level of accuracy, which is proportional to the machine precision multiplied by the condition number of the system matrix. Until the orthogonality is completely lost, the modified Gram-Schmidt GMRES performs almost exactly as well as the Householder implementation. This suggests that unless the system matrix is extremely ill-conditioned, the use of the modified Gram-Schmidt GMRES is theoretically well justified.
The theoretical analysis of the GMRES method has not been finished yet. In the end of our talk we mention some questions related to the rate of convergenceof the implementation in the finite precision arithmetic which are open and still need some effort.
A. Greenbaum, M. Rozlovznik, Z. Strakovs,
Numerical Behaviour of the Modified Gram Schmidt GMRES Method,
BIT 37:3 (1997), 706-719.
J. Drkovsova, A. Greenbaum, M. Rozlovznik, Z. Strakovs,
Numerical Stability of the GMRES method, BIT 35 (1995), 309-330.
Cerfacs' Conferences 1998 Home Page
