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

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/CBO978051161511