Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-23T21:47:23.978Z Has data issue: false hasContentIssue false
  • English
  • Français

Iterative solution of linear systems

Published online by Cambridge University Press:  07 November 2008

Roland W. Freund ,
Gene H. Golub  and
Noël M. Nachtigal
Roland W. Freund
Affiliation:
RIACS, Mail Stop Ellis StreetNASA Ames Research CenterMoffett Field, CA 94035, USA, E-mail: [email protected]
Gene H. Golub
Affiliation:
Computer Science DepartmentStanford University, Stanford, CA 94305, USA, E-mail: [email protected]
Noël M. Nachtigal
Affiliation:
RIACS, Mail Stop Ellis StreetNASA Ames Research CenterMoffett Field, CA 94035, USA, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Recent advances in the field of iterative methods for solving large linear systems are reviewed. The main focus is on developments in the area of conjugate gradient-type algorithms and Krylov subspace methods for nonHermitian matrices.

Type
Research Article
Information
Acta Numerica , Volume 1 , January 1992 , pp. 57 - 100
Copyright
Copyright © Cambridge University Press 1992

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Appel, A.W. (1985), ‘An efficient program for many-body simulation’, SIAM J. Sci. Statist. Comput. 6, 85–103.CrossRefGoogle Scholar
Arnoldi, W.E. (1951), ‘The principle of minimized iterations in the solution of the matrix eigenvalue problem’, Quart. Appl. Math. 9, 17–29.CrossRefGoogle Scholar
Ashby, S.F., Manteuffel, T.A. and Saylor, P.E. (1990), ‘A taxonomy for conjugate gradient methods’, SIAM J. Numer. Anal. 27, 1542–1568.CrossRefGoogle Scholar
Axelsson, O. (1980), ‘Conjugate gradient type methods for unsymmetric and inconsistent systems of linear equations’, Lin. Alg. Appl. 29, 1–16.CrossRefGoogle Scholar
Axelsson, O. (1985), ‘A survey of preconditioned iterative methods for linear systems of algebraic equations’, BIT 25, 166–187.CrossRefGoogle Scholar
Axelsson, O. (1987), ‘A generalized conjugate gradient, least square method’, Numer. Math. 51, 209–227.CrossRefGoogle Scholar
Barbour, I.M., Behilil, N.-E., Gibbs, P.E., Rafiq, M., Moriarty, K.J.M. and Schierholz, G. (1987), ‘Updating fermions with the Lanczos method’, J. Comput. Phys. 68, 227–236.CrossRefGoogle Scholar
Bayliss, A. and Goldstein, C.I. (1983), ‘An iterative method for the Helmholtz equation’, J. Comput. Phys. 49, 443–457.CrossRefGoogle Scholar
Boley, D.L. and Golub, G.H. (1991), ‘The nonsymmetric Lanczos algorithm and controllability’, Systems Control Lett. 16, 97–105CrossRefGoogle Scholar
Boley, D.L., Elhay, S., Golub, G.H. and Gutknecht, M.H. (1991), ‘Nonsymmetric Lanczos and finding orthogonal polynomials associated with indefinite weights’, Numer. Algorithms 1, 21–43.CrossRefGoogle Scholar
Brezinski, C., Redivo Zaglia, M. and Sadok, H. (1991), ‘A breakdown-free Lanczos type algorithm for solving linear systems’, Technical Report ANO–239, Université des Sciences et Techniques de Lille Flandres-Artois, Villeneuve d'Ascq.Google Scholar
Broyden, C.G. (1965), ‘A class of methods for solving nonlinear simultaneous equations’, Math. Comput. 19, 577–593.CrossRefGoogle Scholar
Carrier, J., Greengard, L. and Rokhlin, V. (1988), ‘A fast adaptive multipole algorithm for particle simulations’, SIAM J. Sci. Stat. Comput. 9, 669–686.CrossRefGoogle Scholar
Chan, R.H. and Strang, G. (1989), ‘Toeplitz equations by conjugate gradients with circulant preconditioner’, SIAM J. Sci. Stat. Comput. 10, 104–119.CrossRefGoogle Scholar
Chan, T.F., de Pillis, L. and Van der Vorst, H.A. (1991), ‘A transpose-free squared Lanczos algorithm and application to solving nonsymmetric linear systems’, Technical Report, University of California at Los Angeles.Google Scholar
Chandra, R. (1978), ‘Conjugate gradient methods for partial differential equations’, Ph.D. Dissertation, Yale University, New Haven.Google Scholar
Concus, P. and Golub, G.H. (1976), ‘A generalized conjugate gradient method for nonsymmetric systems of linear equations’, in Computing Methods in Applied Sciences and Engineering (Lecture Notes in Economics and Mathematical Systems 134) (Glowinski, R. and Lions, J.L., eds), Springer (Berlin) 56–65.Google Scholar
Concus, P., Golub, G.H. and O'Leary, D.P. (1976), ‘A generalized conjugate gradient method for the numerical solution of elliptic partial differential equations’, in Sparse Matrix Computations (Bunch, J.R. and Rose, D.J., eds.), Academic Press (New York) 309–332.CrossRefGoogle Scholar
Craig, E.J. (1955), ‘The N-step iteration procedures’, J. Math. Phys. 34, 64–73.CrossRefGoogle Scholar
Cullum, J. and Willoughby, R.A. (1985), Lanczos Algorithms for Large Symmetric Eigenvalue Computations, Volume 1, Theory, Birkhäuser (Basel).Google Scholar
Cullum, J. and Willoughby, R.A. (1986), ‘A practical procedure for computing eigenvalues of large sparse nonsymmetric matrices’, in Large Scale Eigenvalue Problems (Cullum, J. and Willoughby, R.A., eds.), North-Holland (Amsterdam)193–240.Google Scholar
Deuflhard, P., Freund, R.W. and Walter, A. (1990), ‘Fast secant methods for the iterative solution of large nonsymmetric linear systems’, IMPACT Comput. Sci. Eng. 2, 244–276.CrossRefGoogle Scholar
Draux, A. (1983), Polynômes Orthogonaux Formels – Applications, (Lecture Notes in Mathematics 974) Springer (Berlin).CrossRefGoogle Scholar
Duff, I.S., Erisman, A.M. and Reid, J.K. (1986), Direct Methods for Sparse Matrices, Oxford University Press (Oxford).Google Scholar
Eiermann, M. (1991), ‘Fields of values and iterative methods’, Preprint, IBM Scientific Center, Heidelberg.Google Scholar
Eiermann, M., Niethammer, W. and Varga, R.S. (1985), ‘A study of semiiterative methods for nonsymmetric systems of linear equations’, Numer. Math. 47, 505–533.CrossRefGoogle Scholar
Eirola, T. and Nevanlinna, O. (1989), ‘Accelerating with rank-one updates’, Lin. Alg. Appl. 121, 511–520.CrossRefGoogle Scholar
Eisenstat, S.C. (1983a), ‘A note on the generalized conjugate gradient method’, SIAM J. Numer. Anal. 20, 358–361.CrossRefGoogle Scholar
Eisenstat, S.C. (1983b), ‘Some observations on the generalized conjugate gradient method’, in Numerical methods, Proceedings, Caracas 1982 (Lecture Notes in Mathematics 1005) (Pereyra, V. and Reinoza, A., eds), Springer (Berlin) 99–107.Google Scholar
Eisenstat, S.C., Elman, H.C. and Schultz, M.H. (1983), ‘Variational iterative methods for nonsymmetric systems of linear equations’, SIAM J. Numer. Anal. 20, 345–357.CrossRefGoogle Scholar
Elman, H.C. (1982), ‘Iterative methods for large sparse nonsymmetric systems of linear equations’, Ph.D. Dissertation, Yale University, New Haven.Google Scholar
Faber, V. and Manteuffel, T. (1984), ‘Necessary and sufficient conditions for the existence of a conjugate gradient method’, SIAM J. Numer. Anal. 21, 352–362.CrossRefGoogle Scholar
Faber, V. and Manteuffel, T. (1987), ‘Orthogonal error methods’, SIAM J. Numer. Anal. 24, 170–187.CrossRefGoogle Scholar
Fischer, B. and Freund, R.W. (1990), ‘On the constrained Chebyshev approximation problem on ellipses’, J. Approx. Theory 62, 297–315.CrossRefGoogle Scholar
Fischer, B. and Freund, R.W. (1991), ‘Chebyshev polynomials are not always optimal’, J. Approx. Theory 65, 261–272.CrossRefGoogle Scholar
Fletcher, R. (1976), ‘Conjugate gradient methods for indefinite systems’, in Numerical Analysis Dundee 1975 (Lecture Notes in Mathematics 506) (Watson, G.A., ed.), Springer (Berlin) 73–89.Google Scholar
Freund, R.W. (1983), ‘Über einige cg-ähnliche Verfahren zur Lösung linearer Gleichungssysteme’, Doctoral Dissertation, Universität Würzburg.Google Scholar
Freund, R.W. (1989a), ‘Pseudo-Ritz values for indefinite Hermitian matrices’, RI-ACS Technical Report 89.33, NASA Ames Research Center, Moffett Field.Google Scholar
Freund, R.W. (1989b), ‘Conjugate gradient type methods for linear systems with complex symmetric coefficient matrices’, RIACS Technical Report 89.54, NASA Ames Research Center, Moffett Field.Google Scholar
Freund, R.W. (1990), ‘On conjugate gradient type methods and polynomial preconditioners for a class of complex nonHermitian matrices’, Numer. Math. 57, 285–312.CrossRefGoogle Scholar
Freund, R.W. (1991a), ‘Krylov subspace methods for complex nonHermitian linear systems’, Habilitation Thesis, Universität Würzburg.Google Scholar
Freund, R.W. (1991b), ‘A transpose-free quasi-minimal residual algorithm for nonHermitian linear systems’, RIACS Technical Report 91.18, NASA Ames Research Center, Moffett Field.Google Scholar
Freund, R.W. (1991c), ‘Quasi-kernel polynomials and their use in nonHermitian matrix iterations’, RIACS Technical Report 91.20, NASA Ames Research Center, Moffett Field.Google Scholar
Freund, R.W. (1992), ‘Conjugate gradient-type methods for linear systems with complex symmetric coefficient matrices’, SIAM J. Sci. Stat. Comput. 13, to appear.CrossRefGoogle Scholar
Freund, R.W. and Nachtigal, N.M. (1991), ‘QMR: a quasi-minimal residual method for nonHermitian linear systems’, Numer. Math., to appear.CrossRefGoogle Scholar
Freund, R.W. and Ruscheweyh, St. (1986), ‘On a class of Chebyshev approximation problems which arise in connection with a conjugate gradient type method’, Numer. Math. 48, 525–542.CrossRefGoogle Scholar
Freund, R.W. and Szeto, T. (1991), ‘A quasi-minimal residual squared algorithm for nonHermitian linear systems’, Technical Report, RIACS, NASA Ames Research Center, Moffett Field.Google Scholar
Freund, R.W. and Zha, H. (1991), ‘Simplifications of the nonsymmetric Lanczos process and a new algorithms for solving indefinite symmetric linear systems’, Technical Report, RIACS, NASA Ames Research Center, Moffett Field.Google Scholar
Freund, R.W., Golub, G.H. and Hochbruck, M. (1991a) ‘Krylov subspace methods for nonHermitian p-cyclic matrices’, Technical Report, RIACS, NASA Ames Research Center, Moffett Field.Google Scholar
Freund, R.W., Gutknecht, M.H. and Nachtigal, N.M. (1991b), ‘An implementation of the look-ahead Lanczos algorithm for nonHermitian matrices’, Technical Report 91.09, RIACS, NASA Ames Research Center, Moffett Field.Google Scholar
Fridman, V.M. (1963), ‘The method of minimum iterations with minimum errors for a system of linear algebraic equations with a symmetrical matrix’, USSR Comput. Math, and Math. Phys. 2, 362–363.CrossRefGoogle Scholar
Gill, P.E., Murray, W., Ponceleón, D.B. and Saunders, M.A. (1990), ‘Preconditioners for indefinite systems arising in optimization’, Technical Report SOL 90-8, Stanford University.Google Scholar
Golub, G.H. and O'Leary, D.P. (1989), ‘Some history of the conjugate gradient and Lanczos algorithms: 1948–1976’, SIAM Review 31, 50–102.CrossRefGoogle Scholar
Golub, G.H. and Van Loan, C.F. (1989), Matrix Computations, second edition, The Johns Hopkins University Press (Baltimore).Google Scholar
Golub, G.H. and Varga, R.S. (1961), ‘Chebyshev semi-iterative methods, successive overrelaxation iterative methods, and second order Richardson iterative methods’, Numer. Math. 3, 147–168.CrossRefGoogle Scholar
Gragg, W.B. (1974), ‘Matrix interpretations and applications of the continued fraction algorithm’, Rocky Mountain J. Math. 4, 213–225.CrossRefGoogle Scholar
Gragg, W.B. and Lindquist, A. (1983), ‘On the partial realization problem’, Lin. Alg. Appl. 50, 277–319.CrossRefGoogle Scholar
Greenbaum, A., Greengard, L. and McFadden, G.B. (1991), ‘Laplace's equation and the Dirichlet-Neumann map in multiply connected domains’, Technical Report, Courant Institute of Mathematical Sciences, New York University.CrossRefGoogle Scholar
Gutknecht, M.H. (1990a), ‘The unsymmetric Lanczos algorithms and their relations to Padé approximation, continued fractions, and the QD algorithm’, in Proc. Copper Mountain Conference on Iterative Methods.Google Scholar
Gutknecht, M.H. (1990b), ‘A completed theory of the unsymmetric Lanczos process and related algorithms, Part I’, SIAM J. Matrix Anal. Appl., to appear.Google Scholar
Gutknecht, M.H. (1990c), ‘A completed theory of the unsymmetric Lanczos process and related algorithms, Part II’, IPS Research Report No. 90–16, ETH Zürich.Google Scholar
Gutknecht, M.H. (1991), ‘Variants of BICGSTAB for matrices with complex spectrum’, IPS Research Report No. 91–14, ETH Zürich.Google Scholar
Hanrahan, P., Salzman, D. and Aupperle, L. (1991), ‘A rapid hierarchical radiosity algorithm’, Computer Graphics (Proc. SIGGRAPH '91) 25, 197–206.CrossRefGoogle Scholar
Heath, M.T., Ng, E. and Peyton, B.W. (1991), ‘Parallel algorithms for sparse linear systems’, SIAM Review 33, 420–460.CrossRefGoogle Scholar
Heinig, G. and Rost, K. (1984), ‘Algebraic methods for Toeplitz-like matrices and operators’, Birkhauser (Basel).Google Scholar
Hestenes, M.R. and Stiefel, E. (1952), ‘Methods of conjugate gradients for solving linear systems’, J. Res. Natl Bur. Stand. 49, 409–436.CrossRefGoogle Scholar
Hockney, R.W. and Eastwood, J.W. (1981), Computer Simulation Using Particles, McGraw-Hill (New York).Google Scholar
Joubert, W.D. (1990), ‘Generalized conjugate gradient and Lanczos methods for the solution of nonsymmetric systems of linear equations’, Ph.D. Dissertation, The University of Texas at Austin.Google Scholar
Joubert, W.D. and Young, D.M. (1987), ‘Necessary and sufficient conditions for the simplification of generalized conjugate-gradient algorithms’, Lin. Alg. Appl. 88/89, 449–485.CrossRefGoogle Scholar
Khabaza, I.M. (1963), ‘An iterative least-square method suitable for solving large sparse matrices’, Comput. J. 6, 202–206.CrossRefGoogle Scholar
Kung, S. (1977), ‘Multivariable and multidimensional systems: analysis and design’, Ph.D. Dissertation, Stanford University.Google Scholar
Lanczos, C. (1950), ‘An iteration method for the solution of the eigenvalue problem of linear differential and integral operators’, J. Res. Natl Bur. Stand. 45, 255–282.CrossRefGoogle Scholar
Lanczos, C. (1952), ‘Solution of systems of linear equations by minimized iterations’, J. Res. Natl Bur. Stand. 49, 33–53.CrossRefGoogle Scholar
Laux, S.E. (1985), ‘Techniques for small-signal analysis of semiconductor devices’, IEEE Trans. Electron Dev. ED-32, 2028–2037.CrossRefGoogle Scholar
Luenberger, D.G. (1969), ‘Hyperbolic pairs in the method of conjugate gradients’, SIAM J. Appl. Math. 17, 1263–1267.CrossRefGoogle Scholar
Manteuffel, T.A. (1977), ‘The Tchebychev iteration for nonsymmetric linear systems’, Numer. Math. 28, 307–327.CrossRefGoogle Scholar
Manteuffel, T.A. (1978), ‘Adaptive procedure for estimating parameters for the nonsymmetric Tchebychev iteration’, Numer. Math. 31, 183–208.CrossRefGoogle Scholar
Manteuffel, T.A. (1991), ‘Recent developments in iterative methods for large sparse linear systems’, Seminar presentation, Numerical Analysis/Scientific Computing Seminar, Stanford University.Google Scholar
Nachtigal, N.M. (1991), ‘A look-ahead variant of the Lanczos algorithm and its application to the quasi-minimal residual method for nonHermitian linear systems’, Ph.D. Dissertation, Massachusetts Institute of Technology, Cambridge.Google Scholar
Nachtigal, N.M., Reddy, S.C. and Trefethen, L.N. (1990a), ‘How fast are nonsymmetric matrix iterations?’, SIAM J. Matrix Anal. Appl., to appear.Google Scholar
Nachtigal, N.M., Reichel, L. and Trefethen, L.N. (1990b), ‘A hybrid GMRES algorithm for nonsymmetric linear systems’, SIAM J. Matrix Anal. Appl., to appear.Google Scholar
Paige, C.C. and Saunders, M.A. (1975), ‘Solution of sparse indefinite systems of linear equations’, SIAM J. Numer. Anal. 12, 617–629.CrossRefGoogle Scholar
Paige, C.C. and Saunders, M.A. (1982), ‘LSQR: an algorithm for sparse linear equations and sparse least squares’, ACM Trans. Math. Softw. 8, 43–71.CrossRefGoogle Scholar
Parlett, P.N. (1990), ‘Reduction to tridiagonal form and minimal realizations’, Preprint, University of California at Berkeley.Google Scholar
Parlett, B.N., Taylor, D.R. and Liu, Z.A. (1985), ‘A look-ahead Lanczos algorithm for unsymmetric matrices’, Math. Comput. 44, 105–124.Google Scholar
Rapoport, D. (1978), ‘A nonlinear Lanczos algorithm and the stationary Navier-Stokes equation’, Ph.D. Dissertation, New York University.Google Scholar
Reid, J.K. (1971), ‘On the method of conjugate gradients for the solution of large sparse systems of linear equations’, in Large Sparse Sets of Linear Equations (Reid, J.K., ed.), Academic Press, New York, 231–253.Google Scholar
Rokhlin, V. (1985), ‘Rapid solution of integral equations of classical potential theory’, J. Comput. Phys. 60, 187–207.CrossRefGoogle Scholar
Ruhe, A. (1987), ‘Closest normal matrix finally found!’, BIT 27, 585–598.CrossRefGoogle Scholar
Saad, Y. (1980), ‘Variations of Arnoldi's method for computing eigenelements of large unsymmetric matrices’, Lin. Alg. Appl. 34, 269–295.CrossRefGoogle Scholar
Saad, Y. (1981), ‘Krylov subspace methods for solving large unsymmetric linear systems’, Math. Comput. 37, 105–126.CrossRefGoogle Scholar
Saad, Y. (1982), ‘The Lanczos bi-orthogonalization algorithm and other oblique projection methods for solving large unsymmetric systems’, SIAM J. Numer. Anal. 19, 485–506.CrossRefGoogle Scholar
Saad, Y. (1984), ‘Practical use of some Krylov subspace methods for solving indefinite and nonsymmetric linear systems’, SIAM J. Sci. Stat Comput. 5, 203–227.CrossRefGoogle Scholar
Saad, Y. (1989), ‘Krylov subspace methods on supercomputers’, SIAM J. Sci. Stat. Comput. 10, 1200–1232.CrossRefGoogle Scholar
Saad, Y. and Schultz, M.H. (1985), ‘Conjugate gradient-like algorithms for solving nonsymmetric linear systems’, Math. Comput. 44, 417–424.CrossRefGoogle Scholar
Saad, Y. and Schultz, M.H. (1986), ‘GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems’, SIAM J. Sci. Stat. Comput. 7, 856–869.CrossRefGoogle Scholar
Saylor, P.E. and Smolarski, D.C. (1991), ‘Implementation of an adaptive algorithm for Richardson's method’, Lin. Alg. Appl. 154–156, 615–646.CrossRefGoogle Scholar
Sonneveld, P. (1989), ‘CGS, a fast Lanczos-type solver for nonsymmetric linear systems’, SIAM J. Sci. Stat. Comput. 10, 36–52.CrossRefGoogle Scholar
Starke, G. and Varga, R.S. (1991), ‘A hybrid Arnoldi-Faber iterative method for nonsymmetric systems of linear equations’, Technical Report ICM-9108-11, Kent State University, Kent.Google Scholar
Stiefel, E. (1955), ‘Relaxationsmethoden bester Strategie zur Lösung linearer Gleichungssysteme’, Comm. Math. Helv. 29, 157–179.CrossRefGoogle Scholar
Stoer, J. (1983), ‘Solution of large linear systems of equations by conjugate gradient type methods’, in Mathematical Programming – The State of the Art (Bachem, A., Grötschel, M. and Korte, B., eds.), Springer (Berlin) 540–565.CrossRefGoogle Scholar
Stoer, J. and Freund, R.W. (1982), ‘On the solution of large indefinite systems of linear equations by conjugate gradient algorithms’, in Computing Methods in Applied Sciences and Engineering V (Glowinski, R. and Lions, J.L., eds.), North-Holland (Amsterdam) 35–53.Google Scholar
Szyld, D.B. and Widlund, O.B. (1989), ‘Variational analysis of some conjugate gradient methods’, Technical Report CS-1989-28, Duke University, Durham.Google Scholar
Taylor, D.R. (1982), ‘Analysis of the look ahead Lanczos algorithm’, Ph.D. Dissertation, University of California at Berkeley.Google Scholar
Trefethen, L.N. (1991), ‘Pseudospectra of matrices’, in Proceedings of the 14th Dundee Biennial Conference on Numerical Analysis (Griffiths, D.F. and Watson, G.A., eds.), to appear.Google Scholar
Van der Vorst, H.A. (1990), ‘Bi-CGSTAB: A fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems’, Preprint, University of Utrecht.Google Scholar
Vinsome, P.K.W. (1976), ‘Orthomin, an iterative method for solving sparse sets of simultaneous linear equations’, in Proc. Fourth Symposium on Reservoir Simulation, Society of Petroleum Engineers of AIME, Los Angeles.Google Scholar
Voevodin, V.V. (1983), ‘The problem of a nonselfadjoint generalization of the conjugate gradient method has been closed’, USSR Comput. Math. Math. Phys. 23, 143–144.CrossRefGoogle Scholar
Vuik, C. (1990), ‘A comparison of some GMRES-like methods’, Technical Report, Delft University of Technology, Delft.Google Scholar
Weiss, R. (1990), ‘Convergence behaviour of generalized conjugate gradient methods’, Doctoral Dissertation, Universität Karlsruhe.Google Scholar
Widlund, O. (1978), ‘A Lanczos method for a class of nonsymmetric systems of linear equations’, SIAM J. Numer. Anal. 15, 801–812.CrossRefGoogle Scholar
Wilkinson, J.H. (1965), The Algebraic Eigenvalue Problem, Oxford University Press (Oxford).Google Scholar
Young, D.M. and Jea, K.C. (1980), ‘Generalized conjugate gradient acceleration of nonsymmetrizable iterative methods’, Lin. Alg. Appl. 34, 159–194.CrossRefGoogle Scholar