APPROXIMATE INVERSE PRECONDITIONINGS FOR SPARSE LINEAR-SYSTEMS

被引:83
作者
COSGROVE, JDF
DIAZ, JC
GRIEWANK, A
机构
[1] UNIV TULSA,CTR PARALLEL & SCI COMP,TULSA,OK 74104
[2] ARGONNE NATL LAB,DIV MATH & COMP SCI,ARGONNE,IL 60439
基金
美国国家科学基金会;
关键词
INVERSE PRECONDITIONING; SPARSE LINEAR SYSTEMS; ADAPTIVE METHOD;
D O I
10.1080/00207169208804097
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
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. Spare 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.
引用
收藏
页码:91 / 110
页数:20
相关论文
共 18 条
[11]  
Kolotilina L. Y., 1988, J SOVIET MATH, V43, P2566
[12]  
KOLOTILINA LY, IN PRESS SIAM J MATR
[13]  
LEAF GK, 1989, MATH LARGE SCALE COM, P217
[14]  
Ortega J.M., 1970, OCLC1154227410, Patent No. 1154227410
[15]   ON MINIMIZING THE SPECTRAL-RADIUS OF A NONSYMMETRIC MATRIX FUNCTION - OPTIMALITY CONDITIONS AND DUALITY-THEORY [J].
OVERTON, ML ;
WOMERSLEY, RS .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 1988, 9 (04) :473-498
[16]  
PAPRZYCKI M, 1990, THESIS SO METHODIST
[17]  
Stewart GW, 1973, INTRO MATRIX COMPUTA
[18]  
UOLOTILINA LY, 1986, SOV J NUMER ANAL MAT, V1, P293