Abstract
In [6] the Generalized Minimal Residual Method (GMRES) which constructs the Arnoldi basis and then solves the transformed least squares problem was studied. It was proved that GMRES with the Householder orthogonalization-based implementation of the Arnoldi process (HHA), see [9], is backward stable. In practical computations, however, the Householder orthogonalization is too expensive, and it is usually replaced by the modified Gram-Schmidt process (MGSA). Unlike the HHA case, in the MGSA implementation the orthogonality of the Arnoldi basis vectors is not preserved near the level of machine precision. Despite this, the MGSA-GMRES performs surprisingly well, and its convergence behaviour and the ultimately attainable accuracy do not differ significantly from those of the HHA-GMRES. As it was observed, but not explained, in [6], it is thelinear independence of the Arnoldi basis, not the orthogonality near machine precision, that is important. Until the linear independence of the basis vectors is nearly lost, the norms of the residuals in the MGSA implementation of GMRES match those of the HHA implementation despite the more significant loss of orthogonality.
In this paper we study the MGSA implementation. It is proved that the Arnoldi basis vectors begin to lose their linear independenceonly after the GMRES residual norm has been reduced to almost its final level of accuracy, which is proportional to κ(A)ε, where κ(A) is the condition number ofA and ε is the machine precision. Consequently, unless the system matrix is very ill-conditioned, the use of the modified Gram-Schmidt GMRES is theoretically well-justified.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
M. Arioli and C. Fassino,Roundoff error analysis of algorithms based on Krylov subspace methods, BIT, 36 (1996), pp. 189–206.
Å. Björck,Solving linear least squares problems by Gram-Schmidt orthogonalization, BIT, 7 (1967), pp. 1–21.
Å. Björck,Stability analysis of the method of seminormal equations for linear least squares problems, Linear Algebra Appl., 88/89 (1987), pp. 31–48.
Å. Björck and C. C. Paige,Loss and recapture of orthogonality in the modified Gram-Schmidt algorithm, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 176–190.
J. R. Bunch and Ch. P. Nielsen,Updating the singular value decomposition, Numer. Math., 31 (1978), pp. 111–129.
J. Drkošová, A. Greenbaum, M. Rozložník, and Z. Strakoš,Numerical stability of the GMRES method, BIT, 35 (1995), pp. 309–330.
C. L. Lawson and R. J. Hanson,Solving Least Squares Problems, Prentice-Hall, Englewood Cliffs, NJ, 1974.
Y. Saad and M. H. Schultz,GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7 (1986), pp. 856–869.
H. F. Walker,Implementation of the GMRES method using Householder transformations, SIAM J. Sci. Stat. Comput., 9 (1988), pp. 152–163.
P. Å. Wedin,Perturbation theory for pseudoinverses, BIT, 13 (1973), pp. 217–232.
Author information
Authors and Affiliations
Additional information
This work was supported by the GA AS CR under grants 230401 and A 2030706, by the NSF grant Int 921824, and by the DOE grant DEFG0288ER25053. Part of the work was performed while the third author visited Department of Mathematics and Computer Science, Emory University, Atlanta, USA.
Rights and permissions
About this article
Cite this article
Greenbaum, A., Rozložník, M. & Strakoš, Z. Numerical behaviour of the modified gram-schmidt GMRES implementation. Bit Numer Math 37, 706–719 (1997). https://doi.org/10.1007/BF02510248
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02510248