On the iterative methods for solving linear systems of equations
Keywords:
large and sparse linear systems, non-Hermitian matrices, iterative methods, Petrov-Galerkin methods, Krylov subspace methods, conjugate gradient, like methods, preconditioningAbstract
The solution of large systems of linear equations is a problem frequently met in numerical calculations, for example, from finite difference or finite element approximations to partial differential equations. The use of direct methods for solving linear systems of equations is limited by both storage requirement and computing time, and in practice, the only alternative is to use iterative algorithms. This paper presents some basic iterative methods, and also a short survey of recent research on this subject, with emphasis on linear systems whose coefficient matrix is non-Hermitian. We briefly discuss the notion of preconditioning, and we give some practical choices for the preconditioning matrix.
Downloads
References
[ARM 56] Arms R.J ., Gates L.D. and Zondek B., "A method of block iteration",
J. Soc. Indust. Appl. Math., 4, 1956, p. 220-229.
[AXE 85]
[AXE 86]
[AXE 84]
[ABI 84]
[BRI 90]
[CHA 89]
[CON 85]
[CON 76]
Axelsson 0., "A survey of preconditioned iterative methods for linear
systems of algebraic equations", BIT, 25, 1985, p. 166-187.
Axelsson 0., "A general incomplete block-matrix factorization method"
Linear Algebra Appl., 74, 1986, p. 179-190.
Axelsson 0. and Barker V.A., Finite Element Solution of Boundary
Value Problems. Theory and Computation, Academic Press, New York,
Axelsson 0., Brinkkemper S. and Il'in V.P., "On some versions of incomplete
block-matrix factorization iterative methods", Linear Algebra
Appl., 58, 1984, p. 3-15.
Bristeau M.-0., Glowinski R., Dutto L., Periaux J. and Rage G.,
"Compressible viscous flow calculations using compatible finite element
approximations", Int. J. Numer. Methods in Fluids, 11, 1990,
p. 719-749.
Chan T.F., Glowinski R., Periaux J. and Widlund 0., eds., Second
International Symposium on Domain Decomposition Methods, SIAM,
Philadelphia, PA, 1989.
Concus P., Golub G.H. and Meurant G., "Block preconditioning for
the conjugate gradient method", SIAM J. Sci. Stat. Comput., 6, 1985,
p. 309-332.
Concus P., Golub G.H. and O'Leary D.P., "A generalized conjugate
gradient method for the numerical solution of elliptic partial differ
ential equations", in Sparse Matrix Computations ( J. R. Bunch and
D. J. Rose, eds.), Academic Press, New York (1976), p. 309-332.
[CRA 55] Craig E.J., "TheN-step iteration procedures", J. Math. Physics, 34,
, p. 64-73.
[CUT 59] Cuthill E.H. and Varga R.S., "A method of normalized block iteration",
J. Assoc. Comput. Mach., 6, 1959, p. 236-244.
[DAH 92] Dahl 0. and Wille S.0., "An ILU preconditioner with coupled node fillin
for iterative solution of the mixed finite element formulation of the
D and 3D Navier-Stokes equations", Int. J. Numer. Methods Fluids,
, 1992, p. 525-544.
[DAZ 92a] D'Azevedo E.F., Forsyth P.A. and Tang W.-P., "Towards a costeffective
ILU preconditioner with high level fill", BIT, 32, 1992, p. 442-
[DAZ 92b] D'Azevedo E.F.,Forsyth P.A. and Tang W.-P., "Ordering methods for
preconditioned conjugate gradient methods applied to unstructured
grid problems", SIAM J. Mat. Anal. and Appl., 13, 1992, p. 944-961.
[DOU 55] Douglas J. Jr., J. Soc. Indust. Appl. Math., 3, 1955, p. 42.
[DUF 86] Duff I.S., Erisman A.M. and Reid J.K., Direct Methods for Sparse
Matrices, Oxford University Press, Oxford, 1986.
[DUF 89] Duff I.S. and Meurant G.A., "The effect of ordering on preconditioned
conjugate gradients", BIT, 29, 1989, p. 635-657.
[DUT 90] Dutto L.C., Etude de preconditionnements p!JUr la resolution, par la
methode des elements finis, des equations de Navier-Stokes pour un
fl.uide compressible, these de doctorat, universite Pierre et Marie Curie
(Paris VI), France, 1990.
[DUT 93] Dutto L.C., "The effect of ordering on preconditioned GMRES algorithm,
for solving the compressible Navier-Stokes equations", Int.
J. Numer. Methods Eng., 36, 1993, p. 457-497.
[EHR 81] Ehrlich L.W., "An ad hoc SOR method", J. Comput. Phys., 44, 1981,
p. 31-45.
[EIS 83] Eisentat S.C., Elman H.C. and Schultz M.H., "Variational iterative
methods for nonsymmetric systems of linear equations", SIAM J. Numer.
Anal., 20, 1983, p. 345-357.
[ELM 86] Elman H.C., Saad Y. and Saylor P., "A hybrid Chebyshev Krylov subspace
algorithm for solving nonsymmetric systems of linear equations",
SIAM J. Sci. Stat. Comput., 7, 1986, p. 840-855.
[FAB 84] Faber V. and Manteuffel T., "Necessary and sufficient conditions for
the existence of a conjugate gradient method", SIAM J. Numer. Anal.,
, 1984, p. 352-362.
[FAB 87] Faber V. and Manteuffel T., "Orthogonal error methods", SIAM J. Numer.
Anal., 24, 1987, p. 170-187.
[FLE 76] Fletcher R., "Conjugate gradient methods for indefinite systems", in
Numerical Analysis Dundee 1975 (G. A. Watson, ed.), Lecture Notes
in Mathematics 506, Springer, Berlin (1976), p. 73-89.
[FRE 90] Freund R.W., "On conjugate gradient type methods and polynomial
preconditioners for a class of complex non-Hermitian matrices", Numer.
Math., 57, 1990, p. 285-312.
[FRE 92] Freund R.W., "Conjugate gradient-type methods for linear systems
with complex symmetric coefficient matrices", SIAM J. Sci. Stat. Comput.,
, 1992, p. 425-448.
[FGN 92] Freund R.W., Golub G.H. and Nachtigal N.M., "Iterative solution of
linear systems", Acta Numerica, 1992.
[FRE 91) Freund R.W. and Nachtigal N.M., "QMR: a quasi-minimal residual
method for non-Hermitian linear systems", Numer. Math., 60, 1991,
p. 315-339.
[GAU 23] Gauss G.F., Brief an Gerling Werke, 9, 1823, p. 278; translated by
G. E. Forsythe under the title "Gauss to Gerling on Relaxation", Math.
Tables Aids Comput., 5, 1954, p. 255.
[GLO 88] Glowinski R., Golub G.H., Meurant G.A. and Periaux J., eds., First
International Symposium on Domain Decomposition Methods for Partial
Differential Equations, SIAM, Philadelphia, PA, 1988.
[GOL 89] Golub G.H. and O'Leary D.P., "Some history of de conjugate gradient
and Lanczos algorithms: 1948-1976", SIAM Review, 31, 1989, p. 50-
[GUS 78) Gustafsson I., "A class of first order factorization methods", BIT, 18,
, p. 142-156.
[HAB 61] Habetler G.J. and Wachspress E.L., "Symmetric successive overrelaxation
in solving diffusion difference equations", Math. Comput., 15,
, p. 356-362.
[HEA 91] Heath M.T., Ng E. and Peyton B.W., "Parallel algorithms for sparse
linear systems", SIAM Review, 33, 1991, p. 420-460.
[HES 52] Hestenes M.R. and Stiefel E., "Methods of conjugate gradients for
solving linear systems", J. Res. Nat. Bur. Stand., 49, 1952, p. 409-
[JAC 45] Jacobi C.G.J., Astr:. Nachr., 22, 1845, p. 297.
[LAN 50] Lanczos C., "An iteration method for the solution of the eigenvalue
problem of linear differential and integral operators", J. Res. Mat h.
Bur. Stand., 45, 1950, p. 255-282.
[LAN 52] Lanczos C., "Solution of systems of linear equations by minimized
iterations", J. Res. Math. Bur. Stand., 49, 1952, p. 33-53.
[LAS 87] Lascaux P. and Theodor R., Analyse numerique matricielle appliquee
a /'art de l'ingenieur, Tome 2, Masson, Paris, 1987.
[MEl 77] Meijerink J .A. and van der Vorst H.A., "An iterative solution method
for linear systems of which the coefficient matrix is a symmetrix Mmatrix",
Math. Comput., 31, 1977, p. 148-162.
[NAC 91] Nachtigal N.M., A look-ahead variant of the Lanczos algorithm and its
application to the quasi-minimal residual method for non-Hermitian
linear systems, Ph.D dissertation, Massachusetts Institute of Technology,
Cambridge, 1991.
[NAC 92] Nachtigal N.M., Reddy S.C. and Treffethen L.N., "How fast are nonsymmetric
matrix iterations?", SIAM J. Matrix Anal. Appl., 1992; also
in Num. Anal. Rep., 90-2, MIT, 1990.
[ORT 85] Ortega J .M. and Voigt R.G., "Solution of partial differential equatins
on vector and parallel computers", SIAM Review, 27, 1985, p. 149-240.
[PEA 55] Peaceman D.W. and Rachford H.H. Jr., "The numerical solution of
parabolic and elliptic differential equations", J. Soc. Indust. Appl.
Math., 3, 1955, p. 28-41.
[REI 71) Reid J .K., "On the method of conjugate gradients for the solution
of large sparse systems of linear equations", in Large Sparse Sets of
Linear Equations (J. K. Reid, ed.), Academic Press, New York (1971),
p. 231-253.
[SAA 81] Saad Y., "Krylov subspace methods for solving large unsymmetric linear
systems", Math. Comput., 37, 1981, p. 105-126.
[SAA 82] Saad Y., "The Lanczos biorthogonalization algorithm and other oblique
projection methods for solving large unsymmetric systems", SIAM
J. Numer. Anal., 19, 1982, p. 485-506.
[SAA 89) Saad Y., "Krylov subspace methods on supercomputers", SIAM J. Sci.
Stat. Comput., 10, 1989, p. 1200-1232.
[SAA 90] Saad Y., "SPARSKIT: a basic tool kit for sparse matrix computations",
Technical Report 90.20, RIACS, NASA Ames Research Center, 1990.
[SAA 85) Saad Y. and Schultz M.H., "Conjugate gradient-like algorithms for
solving nonsymmetric linear systems", Math. Comput., 44, 1985, p. 417-
[SAA 86] Saad Y. and Schultz M.H., "GMRES: a Generalized Minimal Residual
algorithm for solving nonsymmetric linear systems", SIAM J. Sci. Stat.
Comput., 7, 1986, p. 856-869.
[SEI 74) Seidel 1., Abh. "Math.-Phys. Kl. Bayerische Akad. Wiss. Miinchen, 11
(III), 1874, p. 81.
[SHE 55) Sheldon J., Math. Tables Aids Comput., 9, 1955, p. 101.
[SON 89) Sonneveld P., "CGS,, a fast Lanczos type solver for nonsymmetric linear
systems", SIAM J. Sci. Stat. Comput., 10, 1989, p. 36-52.
[SOU 46) Southwell R.V., Relaxation Methods in Theoretical Physics, Oxford
Univ. Press, New York, 1946.
[STO 83) Stoer J., "Solution of large systems of equations by conjugate gradient
type methods", in Mathematical Programming- The State of the Art
(A. Bachem, M. Grotschel and B. Korte, eds.), Springer, Berlin (1983),
p. 540-565.
[VAN 86) van der Sluis A. and van der Vorst H.A., "The rate of convergence of
conjugate gradients", Numer. Math., 48, 1986, p. 543-560.
[VAN 92) 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. Stat. Comput., 13, 1992, p. 631-644.
[VIN 76) Vinsome P.K.W., "Orthomin, an iterative method for solving sparse
sets of simultaneous linear equations", Proceeding of the Fourth Symposium on Reservoir Simulation, Society of Petroleum Engineers of
AIME (1976), p. 149-159.
[WAT 81] Watts J.W. III, "A conjugate gradient truncated direct method for the
iterative solution of the reservoir simulation presure equation", Society
of Petrolum Engineer J., 21, 1981, p. 345-353.
[WIN 80] Winther R., "Some superlinear convergence results for the conjugate
gradient method' SIAM J. Numer. Anal., 17, 1980, p. 14-17.
[YOU 71] Young D.M., Iterarive Solution of Large Linear Systems, Academic
Press, New York, 1971.
[YOU 89] Young D.M., "A historical overview of iterarive methods", Camp.
Phys. Comm., 53, 1989, p. 1-17.
[YOU 80] Young D.M. and Jea K.C., "Generalized conjugate gradient acceleration
of nonsymmetrizable iterative methods", Linear Algebra Appl.,
, 1980, p. 159-194.
[YSE 86] Yserentant H., "On the multi-level splitting of finite element spaces",
Numer. Math., 49, 1986, p. 379-412.
[ZLA 82] Zlatev Z., "Use of iterative refinement in the solution of sparse linear
systems", SIAM J. Numer. Anal., 19, 1982, p. 381-399.
