×

Numerical experiments with two approximate inverse preconditioners. (English) Zbl 0909.65027

The solution of a large and sparse system of linear equations \(Ax=b\) by iterative technique combined with preconditioner is considered. There is interest in an alternative form of preconditioning based on approximating the matrix inverse \(A^{-1}\). With this kind of preconditioner the computation can be performed in parallel.
The most popular approach to approximate inverse preconditioning – the SPAI algorithm – is based on the idea of Frobenius norm minimization. Another approach for computing a factorized approximate inverse, suggested by the authors, is based on incomplete biconjugation. For general sparse matrices it is very difficult to prescribe the sparsity pattern in advance and so SPAI becomes very expensive. The construction of the AINV preconditioner does not require that the sparsity pattern be known in advance, and applicable to general sparse matrices.
The authors present the results of numerical experiments aimed at comparing SPAI and AINV, performed on a set of sparse matrices. Results for a standard ILU preconditioner are also included. From the point of view of robustness and rates of convergence, SPAI and AINV are comparable and AINV is somewhat better on average.

MSC:

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

References:

[1] S. T. Barnard and R. L. Clay,A portable MPI implementation of the SPAI preconditioner in ISIS++, in Proceedings of the Eight SIAM Conference on Parallel Processing for Scientific Computing, M. Heath et al., eds., SIAM, Philadelphia, 1997.
[2] R. Barrett, M. Berry, T. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, and H. van der Vorst,Templates for the Solution of Linear Systems, SIAM, Philadelphia, 1994.
[3] M. Benzi, C. D. Meyer, and M. Tuma,A sparse approximate inverse preconditioner for the conjugate gradient method, SIAM J. Sci. Comput., 17 (1996), pp. 1135–1149. · Zbl 0856.65019
[4] M. Benzi and M. Tuma,A sparse approximate inverse preconditioner for nonsymmetric linear systems, SIAM J. Sci. Comput., 19 (1998), pp. 968–994. · Zbl 0930.65027
[5] M. Benzi and M. Tuma,A comparative study of sparse approximate inverse preconditioners, Appl. Numer. Math., to appear. · Zbl 0949.65043
[6] M. Benzi and M. Tuma,The effect of ordering and partitioning on factorized approximate inverse preconditioners, in preparation. · Zbl 0959.65047
[7] T. Chan, W.-P. Tang, and W. Wan,Wavelet sparse approximate inverse preconditioners, BIT, 37 (1997), pp. 644–660. · Zbl 0891.65048
[8] E. Chow and Y. Saad,Approximate inverse preconditioners via sparse-sparse iterations, SIAM J. Sci. Comput., 19 (1998), pp. 995–1023. · Zbl 0922.65034
[9] J. D. F. Cosgrove, J. C. Diaz, and A. Griewank,Approximate inverse preconditionings for sparse linear systems, Intern. J. Comput. Math., 44 (1992), pp. 91–110. · Zbl 0762.65025
[10] I. S. Duff, R. G. Grimes, and J. G. Lewis,Sparse matrix test problems, ACM Trans. Math. Software, 15 (1989), pp. 1–14. · Zbl 0667.65040
[11] N. I. M. Gould and J. A. Scott,Sparse approximate-inverse preconditioners using norm-minimization techniques, SIAM J. Sci. Comput., 19 (1998), 605–625. · Zbl 0911.65037
[12] M. Grote and T. Huckle,Parallel preconditioning with sparse approximate inverses, SIAM J. Sci. Comput., 18 (1997), pp. 838–853. · Zbl 0872.65031
[13] M. A. Heroux, P. Vu, and C. Yang,A parallel preconditioned conjugate gradient package for solving sparse linear systems on a Cray Y-MP, Appl. Num. Math., 8 (1991), pp. 93–115. · Zbl 0738.65025
[14] L. Yu. Kolotilina and A. Yu. Yeremin,Factorized sparse approximate inverse preconditioning I: Theory, SIAM J. Matrix Anal. Appl., 14 (1993), pp. 45–58. · Zbl 0767.65037
[15] 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), pp. 148–162. · Zbl 0349.65020
[16] Y. Saad,Iterative Methods for Sparse Linear Systems, PWS Publishing Company, Boston, 1996. · Zbl 1031.65047
[17] H. A. van der Vorst,Bi-CGSTAB: A fast and smoothly converging variant of Bi-CG for the solution of non-symmetric linear systems, SIAM J. Sci. Stat. Comput., 12 (1992), pp. 631–644. · Zbl 0761.65023
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.