A theoretical overview of Krylov subspace methods. (English) Zbl 0854.65031
This excellent paper contains a wide spectrum of iterative methods for solving linear systems. The author presents a survey of Krylov subspace methods for solving nonsymmetric and not positive definite linear systems. To provide a framework for these methods, the outline of an orthogonalization method is presented. Estimates of a norm of the residual and error vector for generalized minimum error methods and conjugate Krylov subspace methods, including BCG, BICO, QMR, TFQMR, the rank-3 update CKS method, the residual or error-minimizing CG, and the energy norm-minimizing CG are given. Discussion and practical experiences with described methods conclude this paper.
Reviewer: J.Zítko (Praha)
MSC:
| 65F10 | Iterative numerical methods for linear systems |
Keywords:
iterative methods; Krylov subspace methods; orthogonalization method; generalized minimum error methodsReferences:
| [1] | Ashby, S. F.; Manteuffel, T. A.; Saylor, P. E., A taxonomy for conjugate gradient methods, SIAM J. Numer. Anal., 27, 1542-1568 (1990) · Zbl 0723.65018 |
| [2] | Axelsson, O., Iterative Solution Methods (1994), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0795.65014 |
| [3] | Axelsson, O.; Lindskog, G., On the rate of convergence of the preconditioned conjugate gradient method, Numer. Math., 48, 499-523 (1986) · Zbl 0564.65017 |
| [4] | Barret, R.; Berry, M.; Chan, T.; Demmel, J.; Donato, J.; Dongarra, J.; Eijkhout, V.; Pozo, R.; Romine, C.; van der Vorst, H., Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (1994), SIAM: SIAM Philadelphia, PA |
| [5] | T. Barth and T. Manteuffel, Estimating the spectrum of A using the roots of the polynomials associated with the QMR iteration, SIAM J. Matrix Anal. (to appear).; T. Barth and T. Manteuffel, Estimating the spectrum of A using the roots of the polynomials associated with the QMR iteration, SIAM J. Matrix Anal. (to appear). |
| [6] | Barth, T.; Manteuffel, T., Variable metric conjugate gradient methods, (Natori, N.; Nodera, T., Matrix Analysis and Parallel Computing, PCG ’94. Matrix Analysis and Parallel Computing, PCG ’94, Advances in Numerical Methods for Large Sparse Sets of Linear Equations, 10 (1994), Keio University: Keio University Yokohama), 165-188 · Zbl 0811.65027 |
| [7] | Brezinski, C.; Redivo-Zaglia, M.; Sadok, H., Avoiding breakdown and near-breakdown in Lanczos type algorithms, Numer. Algorithms, 1, 261-284 (1991) · Zbl 0748.65033 |
| [8] | Brezinski, C.; Redivo-Zaglia, M.; Sadok, H., A breakdown-free Lanczos type algorithm for solving linear systems, Numer. Math., 63, 29-38 (1992) · Zbl 0739.65027 |
| [9] | Brezinski, C.; Sadok, H., Avoiding breakdown in the CGS algorithm, Numer. Algorithms, 1, 199-206 (1991) · Zbl 0766.65024 |
| [10] | Chan, T. F.; Szeto, T., Composite step product methods for solving nonsymmetric linear systems, (UCLA CAM Tech. Rept. (1994), University of California at Los Angeles: University of California at Los Angeles CA) · Zbl 0862.65018 |
| [11] | Chin, P.; Forsyth, P. A., A comparison of GMRES and CGSTAB accelerations for incompressible Navier-Stokes problems, J. Comput. Appl. Math., 46, 415-426 (1993) · Zbl 0772.76059 |
| [12] | Craig, E. J., The \(n\)-step iteration procedures, Math. Phys., 34, 64-73 (1955) · Zbl 0065.10901 |
| [13] | Cullum, J., Peaks, plateaus, numerical instabilities in a Galerkin/minimal residual pair of methods for solving \(Ax = b\), Appl. Numer. Math., 19 (1995), pp. · Zbl 0855.65022 |
| [14] | Elman, H. C., Iterative methods for large sparse nonsymmetric systems of linear equations, (Ph.D. Thesis (1982), Department of Computer Science, Yale University: Department of Computer Science, Yale University New Haven, CT) · Zbl 1203.76098 |
| [15] | Faber, V.; Manteuffel, T. A., Orthogonal error methods, SIAM J. Numer. Anal., 24, 170-187 (1987) · Zbl 0613.65030 |
| [16] | Fletcher, R., Conjugate gradient methods for indefinite systems, (Watson, G. A., Proceedings Dundee Biennial Conference on Numerical Analysis (1975), Springer: Springer Berlin), 73-89 · Zbl 0326.65033 |
| [17] | Fokkema, D. R.; Sleijpen, G. L.G.; van der Vorst, H. A., Generalized conjugate gradient squared, (Internal Report 851 (1994), University of Utrecht: University of Utrecht Utrecht) · Zbl 0856.65021 |
| [18] | Freund, R. W., On conjugate gradient type methods and polynomial preconditioners for a class of non-Hermitian matrices, Numer. Math., 57, 285-312 (1990) · Zbl 0702.65034 |
| [19] | Freund, R. W., A transpose-free quasi-minimal residual algorithm for non-Hermitian linear systems, SIAM J. Sci. Comput., 14, 470-482 (1993) · Zbl 0781.65022 |
| [20] | Freund, R. W.; Golub, G. H.; Nachtigal, N. M., Iterative solution of linear systems, Acta Numerica, 57-100 (1992) · Zbl 0762.65019 |
| [21] | Freund, R. W.; Gutknecht, M. H.; Nachtigal, N. M., An implementation of the Look-Ahead Lanczos algorithm for non-Hermitian matrices, SIAM J. Sci. Comput., 14, 137-158 (1993) · Zbl 0770.65022 |
| [22] | Freund, R. W.; Nachtigal, N. M., QMR: a quasi-minimal residual method for non-Hermitian linear systems, Numer. Math., 60, 315-339 (1991) · Zbl 0754.65034 |
| [23] | Fridman, V. M., The method of minimum iterations with minimum errors for a system of linear algebraic equations with a symmetrical matrix, USSR Comput. Math. Math. Phys., 2, 362-363 (1963) · Zbl 0136.12702 |
| [24] | Golub, G. H.; O’Leary, D. P., Some history of the conjugate gradient and Lanczos algorithms: 1948-1976, SIAM Rev., 31, 50-102 (1989) · Zbl 0673.65017 |
| [25] | Greenbaum, A.; Strakoš, Z., Matrices that generate the same Krylov residual space, (The IMA Volumes in Mathematics and its Applications, 60 (1993), Springer: Springer New York), 95-119 · Zbl 0803.65029 |
| [26] | Gutknecht, M. H., Stationary and almost stationary \((k, l)\)-step methods for linear and nonlinear systems of equations, Numer. Math., 56, 179-213 (1989) · Zbl 0685.65044 |
| [27] | Gutknecht, M. H., A completed theory of the unsymmetric Lanczos process and related algorithms, SIAM J. Matrix Anal., 13, 594-639 (1992), part 1 · Zbl 0760.65039 |
| [28] | Gutknecht, M. H., Changing the norm in conjugate gradient type algorithms, SIAM J. Numer. Anal., 30, 40-56 (1993) · Zbl 0851.65017 |
| [29] | Gutknecht, M. H., Variants of BiCGStab for matrices with complex spectrum, SIAM J. Sci. Comput., 14, 1020-1033 (1993) · Zbl 0837.65031 |
| [30] | Hestenes, M. R.; Stiefel, E., Methods of conjugate gradients for solving linear systems, J. Res. Nat. Bur. Standards, 49, 409-435 (1952) · Zbl 0048.09901 |
| [31] | Hochbruck, M., Lanczos- und Krylov-Verfahren für nicht-Hermitische lineare Systeme, (Ph.D. Thesis (1992), Universität Karlsruhe: Universität Karlsruhe Karlsruhe) · Zbl 0773.65018 |
| [32] | Joly, P.; Meurant, G., Complex conjugate gradient methods, (Recherche Scientifique 93006 (1993), Laboratoire d’Analyse Numérique, Université Pierre et Marie Curie: Laboratoire d’Analyse Numérique, Université Pierre et Marie Curie Paris Cedex) · Zbl 0780.65021 |
| [33] | (Kincaid, D. R.; Hayes, L. J., Iterative Methods for Large Linear Systems (1990), Academic Press: Academic Press Boston, MA) |
| [34] | Lanczos, C., An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. Res. Nat. Bur. Standards, 45, 255-282 (1950) |
| [35] | Lanczos, C., Solution of systems of linear equations by minimized iterations, J. Res. Nat. Bur. Standards, 49, 33-53 (1952) |
| [36] | Meier Yang, U., Preconditioned conjugate gradient-like methods for nonsymmetric linear systems, (Tech. Rept. CSRD 1210 (1992), Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaign: Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaign Urbana, IL) |
| [37] | Paige, C. C.; Saunders, M. A., Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., 12, 4 (1975) · Zbl 0319.65025 |
| [38] | Parlett, B. N.; Taylor, D.; Liu, Z. S., A look-ahead Lanczos algorithm for unsymmetric matrices, Math. Comput., 44, 105-124 (1985) · Zbl 0564.65022 |
| [39] | Rozložník, M.; Strakoš, Z., Variants of the residual-minimizing Krylov space methods (1994), Institute of Computer Science, Academy of Sciences of the Czech Republic: Institute of Computer Science, Academy of Sciences of the Czech Republic Prague |
| [40] | Saad, Y.; Schultz, M. H., GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 7, 856-869 (1986) · Zbl 0599.65018 |
| [41] | Schönauer, W., Scientific Computing on Vector Computers (1987), North-Holland: North-Holland Amsterdam |
| [42] | Schönauer, W.; Schlichte, M.; Weiss, R., Wrong ways and promising ways towards robust and efficient iterative linear solvers, (Advances in Computer Methods for Partial Differential Equations VI (1987), IMACS: IMACS New Brunswick, NJ), 7-14 |
| [43] | Schönauer, W.; Weiss, R., An engineering approach to generalized conjugate gradient methods and beyond, Appl. Numer. Math., 19 (1995), pp. · Zbl 0854.65030 |
| [44] | Sleijpen, G. L.G.; Fokkema, D. R., BiCGStab \((l)\) for linear equations involving unsymmetric matrices with complex spectrum, Electron. Trans. Numer. Anal., 1, 11-32 (1993) · Zbl 0820.65016 |
| [45] | Sleijpen, G. L.G.; van der Vorst, H. A., Maintaining convergence properties of BiCGstab methods in finite precision arithmetic, (Internal Report 861 (1994), University of Utrecht: University of Utrecht Utrecht) · Zbl 0842.65018 |
| [46] | also Numer. Algorithms (to appear); also Numer. Algorithms (to appear) |
| [47] | Sleijpen, G. L.G.; van der Vorst, H. A.; Fokkema, D. R., BiCGSTAB(l) and other hybrid Bi-CG methods, Numer. Algorithms, 775 (1994) · Zbl 0810.65027 |
| [48] | Sonneveld, P., CGS, a fast Lanczos-type solver for nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 10, 36-52 (1989) · Zbl 0666.65029 |
| [49] | Stoer, J.; Freund, R. W., On the solution of large indefinite systems of linear equations by conjugate gradient algorithms, (Proceedings International Symposium on Computing Methods in Applied Sc. and Engineering. Proceedings International Symposium on Computing Methods in Applied Sc. and Engineering, Versailles (1981), North-Holland: North-Holland Amsterdam), 35-53 · Zbl 0499.65018 |
| [50] | Temple, G., The general theory of relaxation methods applied to linear systems, (Proc. Roy. Soc. London Ser. A, 169 (1939)), 476-500, (939) · JFM 65.0530.01 |
| [51] | van der Vorst, H. A., BI-CGSTAB: A fast and smoothly converging variant of BI-CG for the solution of nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 13, 631-644 (1992) · Zbl 0761.65023 |
| [52] | Vinsome, P. K.W., ORTHOMIN, an iterative method for solving sparse sets of simultaneous linear equations, (Symposium 4th Numerical Simulation of Reservoir Performance of SPE of AIME. Symposium 4th Numerical Simulation of Reservoir Performance of SPE of AIME, Los Angeles, CA (1976)), paper SPE 5739 |
| [53] | Walker, H. F., Implementations of the GMRES method, Comput. Phys. Comm., 53, 311-320 (1989) · Zbl 0798.65041 |
| [54] | Weiss, R., Convergence behavior of generalized conjugate gradient methods, (Internal report 43/90 (1990), Computing Center, University of Karlsruhe: Computing Center, University of Karlsruhe Karlsruhe) · Zbl 0738.90074 |
| [55] | Weiss, R., Error-minimizing Krylov subspace methods, SIAM J. Sci. Comput., 15, 511-527 (1994) · Zbl 0798.65048 |
| [56] | Weiss, R., Minimization properties and short recurrences for Krylov subspace methods, Electron. Trans. Numer. Anal., 2, 57-75 (1994) · Zbl 0809.65027 |
| [57] | Weiss, R., Orthogonalization methods, (Internal report 52/94 (1994), Computing Center, University of Karlsruhe: Computing Center, University of Karlsruhe Karlsruhe) |
| [58] | Weiss, R., Relations between smoothing and QMR, (Internal report 53/94 (1994), Computing Center, University of Karlsruhe: Computing Center, University of Karlsruhe Karlsruhe) |
| [59] | Ye, Q., A breakdown-free variation of the nonsymmetric Lanczos algorithms, Math. Comput., 62, 205, 179-207 (1994) · Zbl 0796.65046 |
| [60] | Young, D. M., Iterative Solution of Large linear Systems (1971), Academic Press: Academic Press New York · Zbl 0204.48102 |
| [61] | Young, D. M., A historical overview of iterative methods, Comput. Phys. Comm., 53, 1-17 (1989) · Zbl 0798.65035 |
| [62] | Zhou, L.; Walker, H. F., Residual smoothing techniques for iterative methods, SIAM J. Sci. Comput., 15, 297-312 (1994) · Zbl 0802.65041 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
