Two level parallel preconditioning derived from an approximate inverse based on the Sherman--Morrison formula

Abstract

The AISM (Approximate Inverse based on the Sherman--Morrison Formula) method is one of the existing effective methods for computing an approximate inverse. This algorithm was proposed by Bru et al. [SIAM J. Sci. Comput., 25, pp.701--715 (2003)]. Although it has been showed that the aism is generally a stable option for large linear systems of equations, its computation cost can be prohibitively high. Complications also arise when an attempt is made to parallelize the algorithm, since a sequential process is necessary. This article proposes a two level AISM in which the coefficient matrix is rearranged to a block form, which is more suitable for parallel computation. This technique can also significantly speed-up computations on a single processor. We implemented this technique on an Origin 2400 system with an MPI to illustrate its efficiency through numerical experiments. References

• Benzi, M., and Tuma, M., A Sparse Approximate Inverse Preconditioner for Nonsymmetric Linear Systems, SIAM J. Sci. Comput., 19 (1998) 968--994. doi:10.1137/S1064827595294691
• Benzi, M., Mar\OT1\i n, J., and Tuma, M., A Two-level Parallel Preconditioner Based on Sparse Approximate Inverse, Iterative Methods in Scientific Computation IV, D.R. Kincaid, A. C. Elster, eds. IMACS Series in Computational and Applied Mathematics, IMACS, New Brunswick, NJ (1999) 167--178 .
• Bru, R., Cerdan, J., Mar\OT1\i n, J., and Mas, J., Preconditioning Sparse Nonsymmetric Linear Systems with the Sherman--Morrison Formula, SIAM J. Sci. Comput., 25 (2003) 701--715 . doi:10.113/S1064827502407524
• Bruaset, A. M., A Survey of Preconditioned Iterative Methods, Pitman Research Notes in Mathematics Series, No. 328, Longman Scientific and Technical, U. K (1995).
• Chow, E., and Saad, Y., Approximate Inverse Techniques for Block-partitioned Matrices, SIAM J. Sci. Comput., 18 (1997) 1657--1675 . doi:10.1137/S1064827595281575
• Chow, E., and Saad, Y., Approximate Inverse Preconditioners via Sparse-sparse Iterations, SIAM J. Sci. Comput., 19 (1997) 995--1023(1997) doi:10.1137/S1064827594270415
• Davis, T., University of Florida Sparse Matrix Collection. NA Digest, 92, 1994, http://www.cise.ufl.edu/research/sparse/matrices
• Grote, M., and Huckel, T.: Parallel Preconditioning with Sparse Approximate Inverses, SIAM J. Sci. Comput., 18 (1997) 838--853 . doi:10.1137/S1064827594276552
• Heath, M. T., Ng, E., and Peyton, B. W., Parallel Algorithms for Sparse Linear Systems, SIAM Review., 33 (1990) 420--460. doi:10.1137/1033099
• Hager, W. W., Updating the Inverse of a Matrix, SIAM Rev., 31 (1989) 221--239, . doi:10.1137/1031049
• Huckel, T., Efficient Computation of Sparse Approximate Inverses, Numer. Lin. Alg. Appl., 5 (1998) 57--71. doi:10.1002/(SICI)1099-1506(199801/02)5:1<57::AID-NLA129>3.0.CO;2-C
• Huckel, T., Approximate Sparsity Patterns for the Inverse of a Matrix and Preconditioning, Appl. Numer. Math., 30 (1999) 291--303. doi:10.1016/S0168-9274(98)00117-2
• Karypis, G., and Kumar, V., A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM J. Sci. Comput., 20 (1998) 359--392. doi:10.1137/S1064827595287997
• Moriya, K. and Nodera, T, The Parallelization of Preconditioner for Large Sparse Linear Systems of Equations, Bulletin of the JSIAM (in Japanese), 12 (2002) 14--28.
• Moriya, K, Zhang, L. and Nodera, T., An Approximate Matrix Inversion Procedure by Parallelization of the Sherman--Morrison formula, The ANZIAM J., 51 (2009) 1--9. doi:10.1017/S1446181109000364
• Moriya, K, Zhang, L. and Nodera, T., Efficient Approximate Inverse Preconditioning Techniques for Reduced Systems on Parallel Computers, Substracting Techniques and Domain Decomposition Method, Edited by: F. Magoules, Saxe-Coburg Pub. (2010) 203--228. doi:10.4203/csets.24.8
• Moriya, K. and Nodera, T., A New Scheme of Computing the Approximate Inverse Preconditioner for the Reduced Linear Systems, J. of Comp. and Appl. Math., 199 (2007) 345--352. doi:10.1016/j.cam.2005.08033
• Sherman, J. and Morrison, W., Adjustment of an Inverse Matrix, Corresponding to a Change in One Element of a Given Matrix, Ann. Math. Statist., 21 (1950) 124--127. doi:10.1244/aoms/1177729893
• Naik, V. K., A Scalable Implementation of the NAS Benchmark BT on Distributed Memory Systems, IBM Systems Journal, 34 (1995) 273--291. doi:10.114/sj.342.0273
• Saad, Y., Iterative Methods for Sparse Linear Systems, 2nd Ed. SIAM (2003). doi:10.1137/1.9780898718003
• Saad, Y., Preconditioning Techniques for Nonsymmetric and Indefinite Linear Systems, J. Comput. Appl. Math., 24 (1988) 89--105. doi:10.1016/0377-0427(88)90345-7
• Saad, Y., and Schultz, M. H., gmres: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems. SIAM J. Sci. Statist. Comput., 7(1986) 856--869 . doi:10.1137/0907058
• Shimoncini, V., On the Convergence of Restarted Krylov Subspace Method, SIAM J. Matrix Anal. Appl., 22 (2000) 430--452. doi:10.1137/S0895479898348507
• Simoncini, V. and Szyld, D. B., Recent Computational Developments in Krylov Subspace Methods for Linear Systems, Numer. Lin. Alg. Appl., 14 (2007) 1--59. doi:10.1002/nla.499
• Van der Vorst, H., Iterative Krylov Methods for Large Linear Systems, Cambridge University Press (2003). doi:10.1017/CBO9780511615115