Comparisons of the ILU(0),Point-SSOR,and SPAI Preconditioners on the CRAY-T3E for Nonsymmetric Sparse Linear Systems Arising from PDEs on Structured Grids

Abstract

When solving general sparse linear systems, multicoloring techniques can yield a parallelism of order N, where N is the dimension of the matrix. However, this strategy often suffers from the deterioration of the rate of convergence, as in the preconditioned conjugate gradient method. Another technique that does not suffer from this deterioration of the rate of convergence is the wavefront technique, which exploits parallelism that is available in the original matrix. The rate of convergence remains the same, but the maximum parallelism is limited by the length of the wavefronts, which are often nonuniform. Another popular technique is the sparse approximate inverse (SPAI) technique, capturing the inverse in the sparse form, which is very nice for parallel computation. In this paper, the author compares these two approaches of ILU(0), SPAI, and point-SSOR preconditioners using the BICGSTAB method as the outer iterative method on the CRAY-T3E. It was found that for the problems tested, ILU(0) with multicoloring outperforms the other alternatives.

Get full access to this article

View all access options for this article.

References

Elman, H. 1982. Iterative methods for large, sparse, nonsymmetric systems of linear equations. Ph.D. thesis, Yale University.

Grote, M. , and Huckle, T. 1997. Parallel preconditioning with sparse approximate inverses . J. Sci. Computing 18: 838-853 .

Kuo, C.-C.J. , and Chan, T. 1990. Two-color Fourier analysis of iterative algorithms for elliptic problems with red/black ordering . SIAM J. Sci. Stat. 11 (4): 767-793 .

Meijerink, J. A. , and van der Vorst, H. A. 1977. An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix . Math. Comp. 31: 48-162 .

Saad, Y. 1989. Krylov subspace methods on supercomputers . SIAM J. Sci. Stat. 10: 1200-1233 .

Saad, Y. 1994. Highly parallel preconditioners for general sparse matrices. In Recent advances in iterative methods, eds. G. Golub , M. Luskin , and A. Greenbaum , 165-199. Berlin: Springer-Verlag .

Saad, Y. 1996. SPARSKIT: A basic tool kit for sparse computations. In Iterative methods for sparse linear systems. Boston: PWS Publishing .

van der Vorst, H. 1992. BI-CGSTAB: A fast and smoothly converging variant of BI-CG for the solution of nonsymmetric linear systems . SIAM J. Sci. Statist. Comput. 13: 631-644 .