Abstract
The purpose of this paper is to develop a spectral analysis of the Hessenberg matrix obtained by the GMRES algorithm used for solving a linear system with a singular matrix. We prove that the singularity of the Hessenberg matrix depends on the nature of A and some other criteria such as the zero eigenvalue multiplicity and the projection of the initial residual on particular subspaces. We also show some new results about the distinct kinds of breakdown which may occur in the algorithm when the system is singular.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Axelsson, O.: A generalized conjugate gradient, least-square method. Numer. Math. 51, 209–227 (1987)
Brown, P.N.: A theoretical comparison of the Arnoldi and GMRES algorithms. SIAM J. Sci. Statist. Comput. 12, 58–78 (1991)
Brown, P.N., Walker, H.F.: GMRES on (nearly) singular systems. SIAM J. Matrix Anal. Appl. 18, 37–51 (1997)
Calvetti, D., Lewis, B., Reichel, L.: GMRES-type methods for inconsistent systems. Linear Algebra Appl. 316, 157–169 (2000)
Freund, R.W., Hochbruck, M.: On the use of two QMR algorithms for solving singular systems and applications in Markov chain modeling. Numer. Linear Algebra Appl. 1, 403–420 (1994)
Ipsen, I.C.F., Meyer, C.D.: The idea behind Krylov methods. Amer. Math. Monthly 105, 889–899 (1998)
Lang, S.: Algèbre linéaire, vol. 2, pp. 294–295. InterEditions, Paris (1976)
Reichel, L., Ye, Q.: Breakdown-free GMRES for singular systems. SIAM J. Matrix Anal. Appl. 26, 1001–1021 (2005)
Saad, Y.: Krylov subspace methods for solving large unsymmetric linear systems. Math. Comp. 37, 105–26 (1981)
Saad, Y., Schultz, M.H.: GMRES: a generalized residual method for solving nonsymmetric linear systems. SIAM J. Sci. Statist. Comput. 7, 856–869 (1986)
Sidi, A., Kluzner, V.: A Bi-CG type iterative method for Drazin-inverse solution of singular inconsistent nonsymmetric linear systems of arbitrary index. Electron. J. Linear Algebra 6, 72–94 (2000)
Van Der Vorst, H.A., Vuik, C.: The superlinear convergence behaviour of GMRES. J. Comput. Appl. Math. 48, 327–341 (1993)
Wang, G., Wei, Y., Qiao, S.: Generalized Inverses: Theory and Computations. Science, Beijing (2004)
Wei, Y., Wu, H.: Convergence properties of Krylov subspace methods for singular linear systems with aribitrary index. J. Comput. Appl. Math. 114, 305–318 (2000)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by L. Reichel.
Rights and permissions
About this article
Cite this article
Smoch, L. Spectral behaviour of GMRES applied to singular systems. Adv Comput Math 27, 151–166 (2007). https://doi.org/10.1007/s10444-007-9029-4
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10444-007-9029-4