×

Convergence analysis of Krylov subspace methods. (English) Zbl 1071.65041

Summary: One of the most powerful tools for solving large and sparse systems of linear algebraic equations is a class of iterative methods called Krylov subspace methods. Their significant advantages like low memory requirements and good approximation properties make them very popular, and they are widely used in applications throughout science and engineering. The use of the Krylov subspaces in iterative methods for linear systems is even counted among the “Top 10” algorithmic ideas of the 20th century.
Convergence analysis of these methods is not only of a great theoretical importance but it can also help to answer practically relevant questions about improving the performance of these methods. As we show, the question about the convergence behavior leads to complicated nonlinear problems. Despite intense research efforts, these problems are not well understood in some cases.
The goal of this survey is to summarize known convergence results for three well-known Krylov subspace methods (CG, MINRES and GMRES) and to formulate open questions in this area.

MSC:

65F10 Iterative numerical methods for linear systems
65-02 Research exposition (monographs, survey articles) pertaining to numerical analysis
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] M. ARIOLI A stopping criterion for the conjugate gradient algorithms in a nite element method framework, Numer. Math., 97 (2004), pp. 1-24. · Zbl 1048.65029
[2] ARIOLI, Stopping criteria for iterative methods: applications to PDE’s, Calcolo 38 pp 97– (2001) · Zbl 1072.65045
[3] ARIOLI, Krylov sequences of maximal length and convergence of GMRES, BIT 38 pp 636– (1998) · Zbl 0916.65031
[4] ASHBY, A taxonomy for conjugate gradient methods, SIAM J. Numer. Anal. 27 pp 1542– (1990) · Zbl 0723.65018
[5] O. AXELSSON Iterative solution methods, Cambridge University Press, Cambridge, 1994.
[6] AXELSSON, On the sublinear and superlinear rate of convergence of conjugate gradient methods, Numer. Algorithms 25 pp 1– (2000) · Zbl 0972.65024
[7] BECKERMANN, Superlinear convergence of conjugate gradients, SIAM J. Numer. Anal. 39 pp 300– (2001) · Zbl 0997.65058
[8] Superlinear CG convergence for special right-hand sides, Electron. Trans. Numer. Anal. 14 pp 1– (2002) · Zbl 1024.65102
[9] M. BENZI G. H. GOLUB J. LIESEN Numerical solution of saddle point problems, Acta Numer., (submitted). · Zbl 1115.65034
[10] BROYDEN, A new taxonomy of conjugate gradient methods, Comput. Math. Appl. pp 7– (1996) · Zbl 0874.65024
[11] B. A. CIPRA The Best of the 20th Century: Editors Name Top 10 Algorithms, SIAM News, 33 (2000).
[12] P. CONCUS G. H. GOLUB D. P. O’LEARY A generalized conjugate gradient method for the numerical solution of elliptic partial differential equations, in Sparse matrix computations (Proc. Sympos., Argonne Nat. Lab., Lemont, III., 1975), Academic Press, New York, 1976, pp. 309-332.
[13] CULLUM, Relations between Galerkin and norm-minimizing iterative methods for solving linear systems, SIAM J. Matrix Anal. Appl. 17 pp 223– (1996) · Zbl 0855.65021
[14] EIERMANN, Fields of values and iterative methods, Linear Algebra Appl. 180 pp 167– (1993) · Zbl 0784.65022
[15] EIERMANN, Geometric aspects of the theory of Krylov subspace methods, Acta Numer. 10 pp 251– (2001) · Zbl 1105.65328
[16] EISENSTAT, Variational iterative methods for nonsymmetric systems of linear equations, SIAM J. Numer. Anal. 20 pp 345– (1983) · Zbl 0524.65019
[17] H. C. ELMAN Iterative methods for large sparse nonsymmetric systems of linear equations., PhD thesis, Yale University, New Haven, 1982.
[18] M. EMBREE How descriptive are GMRES convergence bounds?, Numerical Analysis Report 99/08, Oxford University Computing Laboratory, 1999.
[19] ERNST, Residual-minimizing Krylov subspace methods for stabilized discretizations of convection-diffusion equations, SIAM J. Matrix Anal. Appl. 21 pp 1079– (2000) · Zbl 0961.65098
[20] FABER, The polynomial numerical hulls of Jordan blocks and related matrices, Linear Algebra Appl. 374 pp 231– (2003) · Zbl 1044.15019
[21] FABER, Minimal residual method stronger than polynomial preconditioning, SIAM J. Matrix Anal. Appl. 17 pp 707– (1996) · Zbl 0862.65019
[22] D. K. FADDEEV V. N. FADDEEVA Computational methods of linear algebra, W. H. Freeman and Co., San Francisco, 1963.
[23] B. FISCHER Polynomial based iteration methods for symmetric linear systems, Wiley-Teubner Series Advances in Numerical Mathematics, John Wiley & Sons Ltd., Chichester, 1996. · Zbl 0852.65031
[24] FISCHER, Chebyshev polynomials are not always optimal, J. Approx. Theory 65 pp 261– (1991) · Zbl 0738.41027
[25] FISCHER, On parameter choice and iterative convergence for stabilised discretisations of advection-diffusion problems, Comput. Methods Appl. Mech. Engrg. 179 pp 179– (1999) · Zbl 0977.76043
[26] FREUND, Iterative solution of linear systems, Acta Numer. 1 pp 57– (1992)
[27] F. R. GANTMACHER The theory of matrices. Vols. 1, 2, Chelsea Publishing Co., New York, 1959.
[28] GREENBAUM, Comparison of splittings used with the conjugate gradient algorithm, Numer. Math. 33 pp 181– (1979) · Zbl 0394.65011
[29] A. GREENBAUM Iterative methods for solving linear systems, vol. 17 of Frontiers in Applied Mathematics, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. · Zbl 0883.65022
[30] Generalizations of the eld of values useful in the study ofpolynomialfunctions of a matrix, Linear Algebra Appl. 347 pp 233– (2002) · Zbl 1004.15027
[31] Card shuffing and the polynomial numerical hull of degree k, SIAM J. Sci. Comput. 25 pp 408– (2003) · Zbl 1047.15013
[32] Some theoretical results derived from polynomial numerical hulls of Jordan blocks., Electron. Trans. Numer. Anal. 18 pp 81– (2004) · Zbl 1068.15039
[33] GREENBAUM, Max-min properties of matrix factor norms, SIAM J. Sci. Comput. 15 pp 348– (1994) · Zbl 0799.15014
[34] GREENBAUM, Any nonincreasing convergence curve is possible for GMRES, SIAM J. Matrix Anal. Appl. 17 pp 465– (1996) · Zbl 0857.65029
[35] A. GREENBAUM Matrices that generate the same Krylov residual spaces, in Recent advances in iterative methods, vol. 60 of IMA Vol. Math. Appl., Springer, New York, 1994, pp. 95-118. · Zbl 0803.65029
[36] GREENBAUM, GMRES/CR and Arnoldi/Lanczos as matrix approximation problems, SIAM J. Sci. Comput. 15 pp 359– (1994) · Zbl 0806.65031
[37] W. HACKBUSCH Iterative solution of large sparse systems of equations, vol. 95 of Applied Mathematical Sciences, Springer-Verlag, New York, 1994. · Zbl 0789.65017
[38] HESTENES, Methods of conjugate gradients for solving linear systems, J. Research Nat. Bur. Standards 49 pp 409– (1952) · Zbl 0048.09901
[39] HOCHBRUCK, Error analysis of Krylov methods in a nutshell, SIAM J. Sci. Comput. 19 pp 695– (1998) · Zbl 0914.65024
[40] A. S. HOUSEHOLDER The theory of matrices in numerical analysis, Dover Publications Inc., New York, 1975.
[41] HUHTANEN, Minimal decompositions and iterative methods, Numer. Math. 86 pp 257– (2000) · Zbl 0969.65022
[42] JOUBERT, A robust GMRES-based adaptive polynomial preconditioning algorithm for nonsymmetric linear systems, SIAM J. Sci. Comput. 15 pp 427– (1994) · Zbl 0806.65030
[43] I. E. KAPORIN New convergence results and preconditioning strategies for the conjugate gradient method 1 1994 179 210
[44] KLAWONN, Block triangular preconditioners for nonsymmetric saddle point problems: field-of-values analysis, Numer. Math. 81 pp 577– (1999) · Zbl 0922.65021
[45] KOCH, The conformal ”bratwurst”; maps and associated Faber polynomials, Numer. Math. 86 pp 173– (2000) · Zbl 0960.30006
[46] KRYLOV, On the numerical solution of the equation by which the frequency of small oscillations is determined in technical problems, Izv. Akad. Nauk SSSR Ser. Fiz.-Mat. 4 pp 491– (1931)
[47] LANCZOS, An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. Research Nat. Bur. Standards 45 pp 255– (1950)
[48] Solution of systems of linear equations by minimized iterations, J. Research Nat. Bur. Standards 49 pp 33– (1952)
[49] J. LIESEN Construction and analysis of polynomial iterative methods for non-hermitian systems of linear equations, PhD thesis, Fakultät für Mathematik, Universität Bielefeld, 1998. http://archiv.ub.uni-bielefeld.de/disshabi/mathe.htm.
[50] LIESEN, Computable convergence bounds for GMRES, SIAM J. Matrix Anal. Appl. 21 pp 882– (2000) · Zbl 0958.65036
[51] LIESEN, Convergence of GMRES for tridiagonal Toeplitz matrices, SIAM J. Matrix Anal. Appl. 26 pp 233– (2004) · Zbl 1079.65031
[52] GMRES convergence analysis for a convection-diffusion model problem, SIAM J. Sci. Comput., (to appear). · Zbl 1121.65314
[53] J. LIESEN P. TICHÝ Behavior of CG and MINRES for symmetric tridiagonal Toeplitz matrices, Preprint 34-2004, Institute of Mathematics, Technical University of Berlin, 2004.
[54] LIESEN, The worst-case GMRES for normal matrices, BIT 44 pp 79– (2004) · Zbl 1053.65021
[55] MORET, A note on the superlinear convergence of GMRES, SIAM J. Numer. Anal. 34 pp 513– (1997) · Zbl 0873.65054
[56] NACHTIGAL, How fast are nonsymmetric matrix iterations, SIAM J. Matrix Anal. Appl. 13 pp 778– (1992) · Zbl 0754.65036
[57] NAIMAN, A note on conjugate gradient convergence, Numer. Math. 76 pp 209– (1997) · Zbl 0905.65047
[58] O. NEVANLINNA Convergence of iterations for linear equations, Lectures in Mathematics ETH Zürich, Birkhäuser Verlag, Basel, 1993. · Zbl 0846.47008
[59] PAIGE, Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal. 12 pp 617– (1975) · Zbl 0319.65025
[60] A. QUARTERONI A. VALLI Numerical approximation of partial differential equations, vol. 23 of Springer Series in Computational Mathematics, Springer-Verlag, Berlin, 1994.
[61] J. K. REID On the method of conjugate gradients for the solution of large sparse systems of linear equations, in Large sparse sets of linear equations (Proc. Conf., St. Catherine’s Coll., Oxford, 1970), Academic Press, London, 1971, pp. 231-254.
[62] SAAD, Krylov subspace methods for solving large unsymmetric linear systems, Math. Comp. 37 pp 105– (1981) · Zbl 0474.65019
[63] The Lanczos biorthogonalization algorithm and other oblique projection methods for solving large unsymmetric systems, SIAM J. Numer. Anal. 19 pp 485– (1982) · Zbl 0483.65022
[64] Y. SAAD Iterative methods for sparse linear systems, Society for Industrial and Applied Mathematics, Philadelphia, PA, second ed., 2003. · Zbl 1031.65046
[65] SAAD, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput. 7 pp 856– (1986) · Zbl 0599.65018
[66] SAAD, Iterative solution of linear systems in the 20th century, J. Comput. Appl. Math. 123 pp 1– (2000) · Zbl 0965.65051
[67] STARKE, Field-of-values analysis ofpreconditioned iterative methods for nonsymmetric elliptic problems, Numer. Math. 78 pp 103– (1997) · Zbl 0888.65037
[68] STARKE, A hybrid Arnoldi-Faber iterative method for nonsymmetric systems of linear equations, Numer. Math. 64 pp 213– (1993) · Zbl 0795.65015
[69] Z. STRAKOŠ
[70] Z. STRAKOŠ Theory of convergence and effects offinite precision arithmetic in Krylov subspace methods, D.Sc. thesis, Institute of Computer Science AS CR, Prague, February 2001.
[71] Z. STRAKOŠ J. LIESEN On numerical stability in large scale linear algebraic computations, Z. Angew. Math. Mech., (to appear).
[72] P. TICHÝ J. LIESEN Worst-case and ideal GMRESfor a Jordan block, Linear Algebra Appl., (submitted).
[73] TOH, GMRES vs. ideal GMRES, SIAM J. Matrix Anal. Appl. 18 pp 30– (1997) · Zbl 0877.65014
[74] L. N. TREFETHEN Approximation theory and numerical linear algebra, in Algorithms for ap- proximation, II (Shrivenham, 1988), Chapman and Hall, London, 1990, pp. 336-360.
[75] VAN DER SLUIS, The rate of convergence of conjugate gradients, Numer. Math. 48 pp 543– (1986) · Zbl 0596.65015
[76] H. A. VAN DER VORST Iterative Krylov methods for large linear systems, vol. 13 of Cambridge Monographs on Applied and Computational Mathematics, Cambridge University Press, Cambridge, 2003. · Zbl 1023.65027
[77] WINTHER, Some superlinear convergence results for the conjugate gradient method, SIAM J. Numer. Anal. 17 pp 14– (1980) · Zbl 0447.65021
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.