×

Approximate inverse preconditionings for sparse linear systems. (English) Zbl 0762.65025

Authors’ summary: We discuss a procedure for the adaptive construction of sparse approximate inverse preconditionings for general sparse linear systems. The approximate inverses are based on minimizing a consistent norm of the difference between the identity and the preconditioned matrix. The analysis provides positive definiteness and condition number estimates for the preconditioned system under certain circumstances.
We show that for the 1-norm, restricting the size of the difference matrix below 1 may require dense approximate inverses. However, this requirement does not hold for the 2-norm, and similarly reducing the Frobenius norm below 1 does not generally require that much fill-in. Moreover, for the Frobenius norm, the calculation of the approximate inverses yields naturally column-oriented parallelism.
General sparsity can be exploited in a straightforward fashion. Numerical criteria are considered for determining which columns of the sparse approximate inverse require additional fill-in. Sparse algorithms are discussed for the location of potential fill-in within each column. Results using a minimum-residual-type iterative method are presented to illustrate the potential of the method.
Reviewer: J.Mandel (Denver)

MSC:

65F35 Numerical computation of matrix norms, conditioning, scaling
65F05 Direct numerical methods for linear systems and matrix inversion
65F50 Computational methods for sparse matrices
65F10 Iterative numerical methods for linear systems
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Appleyard, J. R. and Cheshire, I. M. 1983.Reservoir Simulation Symposium. Nested factorization, SPE 12264. Nov15-181983, San Francisco. pp.315–324.
[2] Benson M. W., Utilitas Math. 22 pp 127– (1982)
[3] DOI: 10.1080/00207168408803441 · Zbl 0563.65019
[4] DOI: 10.1137/0906018 · Zbl 0556.65022
[5] Cosgrove, J. D. F. and Días, J. C. Proceedings of the Second Workshop on Applied Computing. Fully parallel preconditionings for sparse systems of equations. Tulsa, Oklahoma. Edited by: Uselton, S. pp.29–34. The University of Tulsa.
[6] Cosgrove, J. D. F. and Díaz, J. C. Proceedings of the 1990 Symposium on Applied Computing. Structural properties of the graph of augmented approximate inverses. Edited by: Berghel, H., Talburt, J., Roach, D., Fayetteville and Arkansas. pp.131–136. Los Alamitos, California: IEEE Computer Society Press.
[7] DOI: 10.1002/nme.1620270306 · Zbl 0714.65035
[8] Duff I. S., Sparsity structure and gaussian elimination, ACM SIGNUM 23 pp 2– (1988)
[9] Elmann H., Iterative methods for large, sparse, non-symmetric systems of linear equations (1982)
[10] DOI: 10.1007/BF01932737 · Zbl 0689.65014
[11] DOI: 10.1007/BF01374987 · Zbl 0664.65042
[12] DOI: 10.1515/rnam.1986.1.4.293
[13] Kolotilina L. Y., SIAM J. Matrix Anal, and Appl.
[14] Leaf G. K., Mathematics for Large Scale Computing pp 217– (1989)
[15] Ortega J. M., Iterative Solution of Nonlinear Equations in Several Variables (1970) · Zbl 0241.65046
[16] DOI: 10.1137/0609040 · Zbl 0684.65062
[17] Paprzycki M., Parallelization of boundary value problem software (1990)
[18] Stewart G. W., Introduction to Matrix Computations (1973) · Zbl 0302.65021
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.