Abstract
Two classes of incomplete factorization preconditioners are considered for nonsymmetric linear systems arising from second order finite difference discretizations of non-self-adjoint elliptic partial differential equations. Analytic and experimental results show that relaxed incomplete factorization methods exhibit numerical instabilities of the type observed with other incomplete factorizations, and the effects of instability are characterized in terms of the relaxation parameter. Several stabilized incomplete factorizations are introduced that are designed to avoid numerically unstable computations. In experiments with two-dimensional problems with variable coefficients and on nonuniform meshes, the stabilized methods are shown to be much more robust than standard incomplete factorizations.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
C. C. Ashcraft and R. G. Grimes,On vectorizing incomplete factorization and SSOR preconditioners, SIAM J. Sci. Stat. Comput. 9: 152–164, 1988.
O. Axelsson and 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. Maths. Applics. 23: 321–337, 1979.
O. Axelsson and G. Lindskog,On the eigenvalue distribution of a class of preconditioning methods, Numer. Math. 48: 479–498, 1986.
O. Axelsson and G. Lindskog,On the rate of convergence of the preconditioned conjugate gradient method, Numer. Math. 48: 499–523, 1986.
E. F. F. Botta and A. E. P. Veldman,On local relaxation methods and their application to convection-diffusion equations, J. Comput. Phys. 48: 127–149, 1981.
A. M. Bruaset, A. Tveito and R. Winther,On the stability of relaxed incomplete LU factorizations, Preprint, Institute of Informatics, University of Oslo, 1988.
T. F. Chan,Fourier Analysis of Blended Incomplete Factorization Preconditioners, CAM Report 88-34, Department of Mathematics, UCLA, 1988.
P. Concus, G. H. Golub and G. Meurant,Block preconditioning for the conjugate gradient method, SIAM J. Sci. Stat. Comput. 6: 220–252, 1985.
T. Dupont, R. P. Kendall and H. H. Rachford Jr.,An approximate factorization procedure for solving self-adjoint elliptic difference equations, SIAM J. Numer. Anal. 5: 559–573, 1968.
S. C. Eisenstat, H. C. Elman and M. H. Schultz,Variational iterative methods for nonsymmetric systems of linear equations, SIAM J. Numer. Anal. 20: 345–357, 1983.
H. C. Elman,Preconditioned conjugate-gradient methods for nonsymmetric systems of linear equations, in R. Vichnevetsky and R. S. Stepleman, Editors,Advances in Computer Methods for Partial Differential Equations-IV, IMACS, 1981, pp. 409–417.
H. C. Elman,Iterative Methods for Large, Sparse, Nonsymmetric Systems of Linear Equations, Ph.D. Thesis, Department of Computer Science, Yale University, 1982.
H. C. Elman,A stability analysis of incomplete LU factorizations, Math. Comp. 47: 191–217, 1986.
P. M. Gresho and R. L. Lee,Don't suppress the wiggles — they're telling you something, Computers and Fluids 9: 223–253, 1981.
I. Gustafsson,A class of first order factorizations, BIT 18: 142–156, 1978.
I. Gustafsson,Stability and Rate of Convergence of Modified Incomplete Cholesky Factorization Methods, Ph.D. Thesis, Department of Computer Sciences, Chalmers University of Technology and University of Göteborg, 1978.
W. Hackbusch,Multi-Grid Methods and Applications, Sprnger-Verlag, Heidelberg, 1985.
L. A. Hageman and D. M. Young,Applied Iterative Methods, Academic Press, New York, 1981.
G. W. Hedstrom and A. Osterheld,The effect of cell Reynolds number on the computation of a boundary layer, J. Comput. Phys. 37: 399–421, 1980.
P. Henrici,Elements of Numerical Analysis, John Wiley & Sons, New York, 1964.
T. A. Manteuffel,An incomplete factorization technique for positive definite linear systems, Math. Comp. 34: 473–497, 1980.
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: 148–162, 1977.
P. J. Roache,Computational Fluid Dynamics, Hermosa Publishers, Albuquerque, 1982.
Y. Saad and M. H. Schultz,GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput. 7: 856–869, 1986.
A. Segal,Aspects of numerical methods for elliptic singular perturbation problems, SIAM J. Sci. Stat. Comput. 3: 327–349, 1982.
H. A. van der Vorst,Iterative solution methods for certain sparse linear systems with a non-symmetric matrix arising from PDE-problems, J. Comput. Phys. 44: 1–19, 1981.
G. Wittum,On the robustness of ILU-smoothing, SIAM J. Sci. Stat. Comput. 10: 699–717, 1989.
G. Wittum and F. Liebau,On Truncated Incomplete Decompositions, Report 509, SFB 123, Universitat Heidelberg, 1989.
Author information
Authors and Affiliations
Additional information
The work presented in this paper was supported by the National Science Foundation under grants DMS-8607478, CCR-8818340, and ASC-8958544, and by the U.S. Army Research Office under grant DAAL-0389-K-0016.
Rights and permissions
About this article
Cite this article
Elman, H.C. Relaxed and stabilized incomplete factorizations for non-self-adjoint linear systems. BIT 29, 890–915 (1989). https://doi.org/10.1007/BF01932751
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01932751