Parallel Multilevel Sparse Approximate Inverse Preconditioners in Large Sparse Matrix Computations

ABSTRACT

We investigate the use of the multistep successive preconditioning strategies (MSP) to construct a class of parallel multilevel sparse approximate inverse (SAI) preconditioners. We do not use independent set ordering, but a diagonal dominance based matrix permutation to build a multilevel structure. The purpose of introducing multilevel structure into SAI is to enhance the robustness of SAI for solving difficult problems. Forward and backward preconditioning iteration and two Schur complement preconditioning strategies are proposed to improve the performance and to reduce the storage cost of the multilevel preconditioners. One version of the parallel multilevel SAI preconditioner based on the MSP strategy is implemented. Numerical experiments for solving a few sparse matrices on a distributed memory parallel computer are reported.

REFERENCES

• 1: Owe Axelsson, Iterative solution methods, Cambridge University Press, New York, NY, 1995
• 2: [2] M. W. Benson and P. O. Frederickson. Iterative solution of large sparse linear systems arising in certain multidimensional approximation problems. Utilitas Math., 22:127-140, 1982.
• 3: [3] M. W. Benson, J. Krettmann, and M. Wright. Parallel algorithms for the solution of certain large sparse linear systems. Int. J. Comput. Math., 16:245-260, 1984.
• 4: Matthias Bollhöfer , Volker Mehrmann, Algebraic Multilevel Methods and Sparse Approximate Inverses, SIAM Journal on Matrix Analysis and Applications, v.24 n.1, p.191-218, 2002 [doi>10.1137/S0895479899364441]
• 5: Edmond Chow, A Priori Sparsity Patterns for Parallel Sparse Approximate Inverse Preconditioners, SIAM Journal on Scientific Computing, v.21 n.5, p.1804-1822, April 2000 [doi>10.1137/S106482759833913X]
• 6: I. S. Duff , G. A. Meurant, The effect of ordering on preconditioned conjugate gradients, BIT, v.29 n.4, p.635-657, 1989 [doi>10.1007/BF01932738]
• 7: Murli M. Gupta , Jun Zhang, High accuracy multigrid solution of the 3D convection-diffusion equation, Applied Mathematics and Computation, v.113 n.2-3, p.249-274, July 2000 [doi>10.1016/S0096-3003(99)00085-5]
• 8: [8] G. Meurant. A multilevel AINV preconditioner. Numer. Alg., 29(1-3):107-129, 2002.
• 9: Noël M. Nachtigal , Satish C. Reddy , Lloyd N. Trefethen, How fast are nonsymmetric matrix iterations, SIAM Journal on Matrix Analysis and Applications, v.13 n.3, p.778-795, July 1992 [doi>10.1137/0613049]
• 10: Y. Saad, ILUM: a multi-elimination ILU preconditioner for general sparse matrices, SIAM Journal on Scientific Computing, v.17 n.4, p.830-847, July 1996 [doi>10.1137/0917054]
• 11: Y. Saad, Iterative Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003
• 12: Yousef Saad , Jun Zhang, BILUM: Block Versions of Multielimination and Multilevel ILU Preconditioner for General Sparse Linear Systems, SIAM Journal on Scientific Computing, v.20 n.6, p.2103-2121, Nov. 1999 [doi>10.1137/S106482759732753X]
• 13: Yousef Saad , Jun Zhang, BILUTM: A Domain-Based Multilevel Block ILUT Preconditioner for General Sparse Matrices, SIAM Journal on Matrix Analysis and Applications, v.21 n.1, p.279-299, Aug. 1999 [doi>10.1137/S0895479898341268]
• 14: [14] Y. Saad and J. Zhang. Diagonal threshold techniques in robust multi-level ILU preconditioners for general sparse linear systems. Numer. Linear Algebra Appl., 6(4):257-280, 1999.
• 15: Kai Wang , Jun Zhang, MSP: A Class of Parallel Multistep Successive Sparse Approximate Inverse Preconditioning Strategies, SIAM Journal on Scientific Computing, v.24 n.4, p.1141-1156, 2002 [doi>10.1137/S1064827502400832]
• 16: Kai Wang , Jun Zhang, Multigrid treatment and robustness enhancement for factored sparse approximate inverse preconditioning, Applied Numerical Mathematics, v.43 n.4, p.483-500, December 2002 [doi>10.1016/S0168-9274(02)00105-8]
• 17: Jun Zhang, A Multilevel Dual Reordering Strategy for Robust Incomplete LU Factorization of Indefinite Matrices, SIAM Journal on Matrix Analysis and Applications, v.22 n.3, p.925-947, 2000 [doi>10.1137/S0895479899354251]
• 18: [18] J. Zhang. On preconditioning Schur complement and Schur complement preconditioning. Electron. Trans. Numer. Anal., 10:115-130, 2000.
• 19: [19] J. Zhang. Preconditioned Krylov subspace methods for solving nonsymmetric matrices from CFD applications. Comput. Methods Appl. Mech. Engrg., 189(3):825-840, 2000.
• 20: Jun Zhang, Sparse approximate inverse and multilevel block ILU preconditioning techniques for general sparse matrices, Applied Numerical Mathematics, v.35 n.1, p.67-86, Sept. 2000 [doi>10.1016/S0168-9274(99)00047-1]
• 21: [21] J. Zhang. A class of multilevel recursive incomplete LU preconditioning techniques. Korean J. Comput. Appl. Math., 8(2):213-234, 2001.

INDEX TERMS

Keywords:
Parallel preconditioning, sparse approximate inverse, multilevel pre-conditioning