A stability analysis of incomplete factorizations

Author:
Howard C. Elman

Journal:
Math. Comp. **47** (1986), 191-217

MSC:
Primary 65F10; Secondary 65N10, 65N20

DOI:
https://doi.org/10.1090/S0025-5718-1986-0842130-7

MathSciNet review:
842130

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The combination of iterative methods with preconditionings based on incomplete LU factorizations constitutes an effective class of methods for solving the sparse linear systems arising from the discretization of elliptic partial differential equations. In this paper, we show that there are some settings in which the incomplete LU preconditioners are not effective, and we demonstrate that their poor performance is due to numerical instability. Our analysis consists of an analytic and numerical study of a sample two-dimensional non-self-adjoint elliptic problem discretized by several finite-difference schemes.

**[1]**Owe Axelsson,*Conjugate gradient type methods for unsymmetric and inconsistent systems of linear equations*, Linear Algebra Appl.**29**(1980), 1–16. MR**562745**, https://doi.org/10.1016/0024-3795(80)90226-8**[2]**Owe Axelsson & I. Gustafsson, "A modified upwind scheme for convective transport equations and the use of a conjugate gradient method for the solution of non-symmetric systems of equations,"*J. Inst. Math. Appl.*, v. 23, 1979, pp. 321-337.**[3]**R. Chandra,*Conjugate Gradient Methods for Partial Differential Equations*, Ph.D. Thesis, Department of Computer Science, Yale University, 1978. Also available as Technical Report 129.**[4]**Paul Concus, Gene H. Golub, and Dianne P. O’Leary,*A generalized conjugate gradient method for the numerical solution of elliptic partial differential equations*, Sparse matrix computations (Proc. Sympos., Argonne Nat. Lab., Lemont, Ill., 1975) Academic Press, New York, 1976, pp. 309–332. MR**0501821****[5]**Todd Dupont, Richard P. Kendall, and H. H. Rachford Jr.,*An approximate factorization procedure for solving self-adjoint elliptic difference equations*, SIAM J. Numer. Anal.**5**(1968), 559–573. MR**0235748**, https://doi.org/10.1137/0705045**[6]**Stanley C. Eisenstat, Howard C. Elman, and Martin H. Schultz,*Variational iterative methods for nonsymmetric systems of linear equations*, SIAM J. Numer. Anal.**20**(1983), no. 2, 345–357. MR**694523**, https://doi.org/10.1137/0720023**[7]**H. C. Elman,*Iterative Methods for Large, Sparse, Nonsymmetric Systems of Linear Equations*, Ph.D. Thesis, Department of Computer Science, Yale University, 1982. Also available as Technical Report 229.**[8]**H. C. Elman, "Preconditioned conjugate gradient methods for nonsymmetric systems of linear equations," in*Advances in Computer Methods for Partial Differential Equations*, IV (R. Vichnevetsky and R. S. Stepleman, eds.), International Association for Mathematics and Computers in Simulation, IMACS, 1981, pp. 409-417.**[9]**George E. Forsythe and Wolfgang R. Wasow,*Finite-difference methods for partial differential equations*, Applied Mathematics Series, John Wiley & Sons, Inc., New York-London, 1960. MR**0130124****[10]**C. William Gear,*Numerical initial value problems in ordinary differential equations*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1971. MR**0315898****[11]**Ivar Gustafsson,*A class of first order factorization methods*, BIT**18**(1978), no. 2, 142–156. MR**499230**, https://doi.org/10.1007/BF01931691**[12]**Ivar Gustafsson,*Stability and Rate of Convergence of Modified Incomplete Cholesky Factorization Methods*, Ph.D. Thesis, Department of Computer Sciences, Chalmers University of Technology and the University of Göteborg, 1978. Also available as Technical Report 77.04R.**[13]**Peter Henrici,*Elements of numerical analysis*, John Wiley & Sons, Inc., New York-London-Sydney, 1964. MR**0166900****[14]**J. M. Hyman & T. A. Manteuffel, "High-order sparse factorization methods for elliptic boundary value problems," in*Advances in Computer Methods for Partial Differential Equations*, V (R. Vichnevetsky and R. S. Stepleman, eds.), IMACS, 1984, pp. 551-555.**[15]**Werner Liniger,*On factored discretizations of the Laplacian for the fast solution of Poisson’s equation on general regions*, BIT**24**(1984), no. 4, 592–608. MR**764831**, https://doi.org/10.1007/BF01934917**[16]**J. A. Meijerink and H. A. van der Vorst,*An iterative solution method for linear systems of which the coefficient matrix is a symmetric 𝑀-matrix*, Math. Comp.**31**(1977), no. 137, 148–162. MR**0438681**, https://doi.org/10.1090/S0025-5718-1977-0438681-4**[17]**Youcef Saad,*Chebyshev acceleration techniques for solving nonsymmetric eigenvalue problems*, Math. Comp.**42**(1984), no. 166, 567–588. MR**736453**, https://doi.org/10.1090/S0025-5718-1984-0736453-8**[18]**Y. Saad & M. H. Schultz,*GMRES*:*A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems*, Technical Report 254, Department of Computer Science, Yale University, 1983.**[19]**Paul E. Saylor,*Second order strongly implicit symmetric factorization methods for the solution of elliptic difference equations*, SIAM J. Numer. Anal.**11**(1974), 894–908. MR**0421105**, https://doi.org/10.1137/0711071**[20]**A. Segal,*Aspects of numerical methods for elliptic singular perturbation problems*, SIAM J. Sci. Statist. Comput.**3**(1982), no. 3, 327–349. MR**667831**, https://doi.org/10.1137/0903020**[21]**Henk A. van der Vorst,*Iterative solution methods for certain sparse linear systems with a nonsymmetric matrix arising from PDE-problems*, J. Comput. Phys.**44**(1981), no. 1, 1–19. MR**642122**, https://doi.org/10.1016/0021-9991(81)90034-6**[22]**H. S. Wall,*Analytic Theory of Continued Fractions*, D. Van Nostrand Company, Inc., New York, N. Y., 1948. MR**0025596****[23]**David M. Young and Kang C. Jea,*Generalized conjugate-gradient acceleration of nonsymmetrizable iterative methods*, Linear Algebra Appl.**34**(1980), 159–194. MR**591431**, https://doi.org/10.1016/0024-3795(80)90165-2

Retrieve articles in *Mathematics of Computation*
with MSC:
65F10,
65N10,
65N20

Retrieve articles in all journals with MSC: 65F10, 65N10, 65N20

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1986-0842130-7

Article copyright:
© Copyright 1986
American Mathematical Society