Krylov subspace solvers and preconditioners. (English) Zbl 1406.65021

The author offers a special point of view to the subject of numerical solution of systems of linear equations (SLE), with particular emphasis on the Krylov subspace method for the SLE with a symmetric positive definite matrix. The conjugate gradient method is studied in detail and good upper bounds of the distance between \(k\)-th iterate and the exact solution of the SLE are obtained. Good examples to illustrate a super-linear convergence behavior are provided. Analogous questions for the SLE with the “preconditioner” matrix and with a “general” matrix are considered. The investigations are of interest to the following topics: solving large, sparse systems of linear equations.


65F10 Iterative numerical methods for linear systems
65F08 Preconditioners for iterative methods
65F50 Computational methods for sparse matrices


Full Text: DOI


[1] O. Axelsson. Iterative Solution Methods. Cambridge University Press, Cambridge, UK, 1994. · Zbl 0795.65014
[2] O. Axelsson and G. Lindskog. On the eigenvalue distribution of a class of preconditioning methods. Numer. Math., 48:479–498, 1986. · Zbl 0564.65016
[3] R. Barrett, M. Berry, T.F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, and H. van der Vorst. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. SIAM, Philadelphia, 1994.
[4] A. Bj¨orck and T. Elfving. Accelerated projection methods for computing pseudo-inverse solution of systems of linear equations. BIT, 19:145–163, 1979.
[5] E.K. Blum. Numerical Analysis and Computation, Theory and Practice. Addison-Wesley, Reading, 1972. · Zbl 0273.65001
[6] A.M. Bruaset. A Survey of Preconditioned Iterative Methods. Pitman research notes in mathematics series 328. Longman Scientific and Technical, Harlow, 1995.
[7] B.A. Carr´e. The determination of the optimum accelerating factor for successive over-relaxation. Computer Journal, 4:73–78, 1961.
[8] M. Eiermann, W. Niethammer, and R.S. Varga. A study of semiiterative methods for nonsymmetric systems of linear equations. Numer. Math., 47:505–533, 1985. · Zbl 0585.65025
[9] S.C. Eisenstat. Efficient implementation of a class of preconditioned conjugate gradient methods. SIAM J. Sci. Stat. Comput., 2:1–4, 1981. · Zbl 0474.65020
[10] S.C. Eisenstat, H.C. Elman, and M.H. Schultz. Variable iterative methods for nonsymmetric systems of linear equations. SIAM J. Num. Anal., 20:345–357, 1983. · Zbl 0524.65019
[11] M. Embree. The Tortoise and the Hare restart GMRES. SAIM Review, 45:259–266, 2003. · Zbl 1027.65039
[12] Y.A. Erlangga, C.W. Oosterlee, and C. Vuik. A novel multigrid based preconditioner for heterogeneous Helmholtz problems. SIAM J. Sci. Comput., 27:1471–1492, 2006. · Zbl 1095.65109
[13] V. Faber and T. Manteuffel. Necessary and sufficient conditions for the existence of a conjugate gradient method. SIAM J. Num. Anal., 21:356–362, 1984. · Zbl 0546.65010
[14] R. Fletcher. Factorizing symmetric indefinite matrices. Lin. Alg. and its Appl., 14:257–277, 1976. · Zbl 0336.65022
[15] R.W. Freund, G.H. Golub, and N.M. Nachtigal. Iterative solution of linear systems. In A. Iserles, editor, Acta Numerica, pages 57–100. Cambridge University Press, Cambridge, UK, 1992. · Zbl 0762.65019
[16] R.W. Freund, M.H. Gutknecht, and N.M. Nachtigal. An implimentation of the look-ahead Lanczos algorithm for non-Hermitian matrices. SIAM J. Sci. Comp., 14:137–156, 1993. ESAIM: PROCEEDINGS AND SURVEYS43 · Zbl 0770.65022
[17] R.W. Freund and N.M. Nachtigal. QMR: a quasi-minimal residual method for non-Hermitian linear systems. Numer. Math., 60:315–339, 1991. · Zbl 0754.65034
[18] T. Ginsburg. The conjugate gradient method. In J.H. Wilkinson and C. Reinsch, editors, Handbook for Automatic Computation, 2, Linear Algebra, pages 57–69, Berlin, 1971. Springer.
[19] G.H. Golub and C.F. van Loan. Matrix Computations. The Johns Hopkins University Press, Baltimore, 1996. Third edition.
[20] G.H. Golub and R.S. Varga. Chebychev semi-iterative methods, successive over-relaxation iterative methods and second order Richardson iterative methods. Part I and II. Numer. Math., 3:147–156, 157–168, 1961. · Zbl 0099.10903
[21] A. Greenbaum. Iterative Methods for Solving Linear Systems. Frontiers in applied mathmatics 17. SIAM, Philadelphia, 1997. · Zbl 0883.65022
[22] A. Greenbaum, V. Ptak, and Z. Strakos. Any nonincreasing convergence curve is possible for GMRES. SIAM J. Matrix Anal. Appl., 17:465–469, 1996. · Zbl 0857.65029
[23] I.A. Gustafsson. A class of first order factorization methods. BIT, 18:142–156, 1978. · Zbl 0386.65006
[24] L.A. Hageman and D.M. Young. Applied Iterative Methods. Academic Press, New York, 1981. · Zbl 0459.65014
[25] M.R. Hestenes and E. Stiefel. Methods of Conjugate Gradients for Solving Linear Systems. J. Res. Nat. Bur. Stand., 49:409– 436, 1952. · Zbl 0048.09901
[26] R.A. Horn and C.R. Johnson. Matrix Analysis (second edition). Cambridge University Press, Cambrige, 2013.
[27] E.F. Kaasschieter. Preconditioned conjugate gradients for solving singular systems. J. of Comp. Appl. Math., 24:265–275, 1988. · Zbl 0659.65031
[28] T.A. Manteuffel. The Tchebychev iteration for nonsymmetric linear systems. Numer. Math., 28:307–327, 1977. · Zbl 0361.65024
[29] J.A. Meijerink and H.A. van der Vorst. An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix. Math. Comp., 31:148–162, 1977. · Zbl 0349.65020
[30] N.M. Nachtigal, S.C. Reddy, and L.N. Trefethen. How fast are non symmetric matrix iterations. SIAM J. Matrix Anal. Appl., 13:778–795, 1992. · Zbl 0754.65036
[31] C.C. Paige and M.A. Saunders. Solution of sparse indefinite system of linear equations. SIAM J. Num. Anal., 12:617–629, 1975. · Zbl 0319.65025
[32] C.C. Paige and M.A. Saunders. LSQR: an algorithm for sparse linear equations and sparse least square problem. ACM Trans. Math. Softw., 8:44–71, 1982. · Zbl 0478.65016
[33] B.N. Parlett, D.R. Taylor, and Z.A. Liu. A look-ahead Lanczos algorithm for unsymmetric matrices. Math. Comp., 44:105–124, 1985. · Zbl 0564.65022
[34] T. F. Chan J. Demmel J. Donato J. Dongarra V. Eijkhout R. Pozo C. Romine R. Barrett, M. Berry and H. Van der Vorst. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd Edition. SIAM, Philadelphia, 1994. · Zbl 0814.65030
[35] J.K. Reid. The use of conjugate for systems of linear equations posessing property A. SIAM J. Num. Anal., 9:325–332, 1972. · Zbl 0259.65037
[36] Y. Saad. Preconditioning techniques for non symmetric and indefinite linear system. J. Comp. Appl. Math., 24:89–105, 1988. · Zbl 0662.65028
[37] Y. Saad. A flexible inner-outer preconditioned GMRES algorithm. SIAM J. Sci. Stat. Comput., 14:461–469, 1993. · Zbl 0780.65022
[38] Y. Saad. Iterative Methods for Sparse Linear Systems. PWS Publishing, Boston, 1996. · Zbl 1031.65047
[39] Y. Saad. Iterative methods for sparse linear systems, Second Edition. SIAM, Philadelphia, 2003. · Zbl 1031.65046
[40] Y. Saad and M.H. Schultz. GMRES: a generalized minimal residual algorithm for solving non-symmetric linear systems. SIAM J. Sci. Stat. Comp., 7:856–869, 1986. · Zbl 0599.65018
[41] P. Sonneveld. CGS: a fast Lanczos-type solver for nonsymmetric linear systems. SIAM J. Sci. Stat. Comput., 10:36–52, 1989. · Zbl 0666.65029
[42] C. Oosterlee U. Trottenberg and A. Sch¨uller. Multigrid. Academic Press, San Diego, 2001.
[43] A. van der Sluis. Conditioning, equilibration, and pivoting in linear algebraic systems. Numer. Math., 15:74–86, 1970. · Zbl 0182.49002
[44] A. van der Sluis and H.A. van der Vorst. The rate of convergence of conjugate gradients. Numer. Math., 48:543–560, 1986. · Zbl 0596.65015
[45] H.A. van der Vorst. High performance preconditioning. SIAM J. Sci. Stat. Comp., 10:1174–1185, 1989. · Zbl 0693.65027
[46] H.A. van der Vorst. Bi-CGSTAB: a fast and smoothly converging variant of Bi-CG for solution of non-symmetric linear systems. SIAM J. Sci. Stat. Comp., 13:631–644, 1992. · Zbl 0761.65023
[47] H.A. van der Vorst. Iterative Krylov Methods for Large Linear Systems. Cambridge Monographs on Applied and Computational Mathematics, 13. Cambridge University Press, Cambridge, 2003. · Zbl 1023.65027
[48] H.A. van der Vorst and C. Vuik. The superlinear convergence behaviour of GMRES. J. Comput. Appl. Math., 48:327–341, 1993. · Zbl 0797.65026
[49] H.A. van der Vorst and C. Vuik. GMRESR: a family of nested GMRES methods. Num. Lin. Alg. Appl., 1:369–386, 1994. · Zbl 0839.65040
[50] R. S. Varga. Matrix Iterative Analysis. Springer, Berlin, 2000. · Zbl 0998.65505
[51] R.S. Varga. Matrix Iterative Analysis. Prentice-Hall, Englewood Cliffs, N.J., 1962. · Zbl 0133.08602
[52] C. Vuik. Solution of the discretized incompressible Navier-Stokes equations with the GMRES method. Int. J. Num. Meth. in Fluids, 16:507–523, 1993. · Zbl 0825.76552
[53] E.L. Wachspress. Iterative Solution of Elliptic Systems. Prentice-Hall, Englewood Cliffs, 1966. · Zbl 0161.12203
[54] D.M. Young. Iterative Solution of Large Linear Systems. Academic Press, New York, 1971. · Zbl 0231.65034
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.