A stability analysis of incomplete 𝐿𝑈 factorizations

Elman, Howard C.

doi:10.1090/S0025-5718-1986-0842130-7

A stability analysis of incomplete $LU$ factorizations
HTML articles powered by AMS MathViewer

by Howard C. Elman PDF

Math. Comp. 47 (1986), 191-217 Request permission

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.

References

Owe Axelsson, Conjugate gradient type methods for unsymmetric and inconsistent systems of linear equations, Linear Algebra Appl. 29 (1980), 1–16. MR 562745, DOI 10.1016/0024-3795(80)90226-8

J. Inst. Math. Appl.

Conjugate Gradient Methods for Partial Differential Equations

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
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 235748, DOI 10.1137/0705045
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, DOI 10.1137/0720023

Iterative Methods for Large, Sparse, Nonsymmetric Systems of Linear Equations

Advances in Computer Methods for Partial Differential Equations

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
C. William Gear, Numerical initial value problems in ordinary differential equations, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1971. MR 0315898
Ivar Gustafsson, A class of first order factorization methods, BIT 18 (1978), no. 2, 142–156. MR 499230, DOI 10.1007/BF01931691

Stability and Rate of Convergence of Modified Incomplete Cholesky Factorization Methods

Peter Henrici, Elements of numerical analysis, John Wiley & Sons, Inc., New York-London-Sydney, 1964. MR 0166900

Advances in Computer Methods for Partial Differential Equations

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, DOI 10.1007/BF01934917
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 (1977), no. 137, 148–162. MR 438681, DOI 10.1090/S0025-5718-1977-0438681-4
Youcef Saad, Chebyshev acceleration techniques for solving nonsymmetric eigenvalue problems, Math. Comp. 42 (1984), no. 166, 567–588. MR 736453, DOI 10.1090/S0025-5718-1984-0736453-8

GMRES

A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems

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 421105, DOI 10.1137/0711071
A. Segal, Aspects of numerical methods for elliptic singular perturbation problems, SIAM J. Sci. Statist. Comput. 3 (1982), no. 3, 327–349. MR 667831, DOI 10.1137/0903020
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, DOI 10.1016/0021-9991(81)90034-6
H. S. Wall, Analytic Theory of Continued Fractions, D. Van Nostrand Co., Inc., New York, N. Y., 1948. MR 0025596
David M. Young and Kang C. Jea, Generalized conjugate-gradient acceleration of nonsymmetrizable iterative methods, Linear Algebra Appl. 34 (1980), 159–194. MR 591431, DOI 10.1016/0024-3795(80)90165-2