×

zbMATH — the first resource for mathematics

A sparse approximate inverse preconditioner for parallel preconditioning of general sparse matrices. (English) Zbl 1028.65044
The factored approximate inverse preconditioner of J.-C. Luo [Comput. Math. Appl. 25, 113-122 (1993; Zbl 0778.65018); ibid. 25, No. 5, 83-90 (1993; Zbl 0778.65019); ibid. 25, No. 4, 95-104 (1993; Zbl 0776.65021); ibid. 25, No. 2, 73-79 (1993; Zbl 0765.65041)] is investigated and adapted for sparse parallel implementation. The exploitation of sparsity patters and threshold strategies for dropping small elements are discussed. Numerical experiments show that factored sparse approximate inverse methods are cheap in construction on sequential machines, unlike techniques based on norm minimization, but the inherent parallelism which is more prominent in these methods than in other incomplete LU factorizations is not easily exploited in general.

MSC:
65F35 Numerical computation of matrix norms, conditioning, scaling
65F50 Computational methods for sparse matrices
65F10 Iterative numerical methods for linear systems
65Y05 Parallel numerical computation
Software:
BILUM; BILUTM; ILUT
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Banerjee, R.N.; Benson, M.W., An approximate inverse based multigrid approach to the biharmonic problem, Int. J. comput. math., 40, 201-210, (1991) · Zbl 0746.65083
[2] S.T. Barnard, L.M. Bernardo, H.D. Simon, An MPI implementation of the SPAI preconditioner on the T3E, Technical Report LBNL-40794, Ernest Orlando Lawrance Berkeley National Laboratory, Berkeley, CA, 1997
[3] Benson, M.W.; Frederickson, P.O., Iterative solution of large sparse linear systems arising in certain multidimensional approximation problems, Utilitas math., 22, 127-140, (1982) · Zbl 0502.65020
[4] Benzi, M.; Meyer, C.D.; Tuma, M., A sparse approximate inverse preconditioner for the conjugate gradient method, SIAM J. sci. comput., 17, 5, 1135-1149, (1996) · Zbl 0856.65019
[5] Benzi, M.; Tuma, M., A sparse approximate inverse preconditioner for nonsymmetric linear systems, SIAM J. sci. comput., 19, 3, 968-994, (1998) · Zbl 0930.65027
[6] Benzi, M.; Tuma, M., A comparative study of sparse approximate inverse preconditioners, Appl. numer. math., 30, 2-3, 305-340, (1999) · Zbl 0949.65043
[7] Chan, T.F.; Tang, W.P.; Wan, W.L., Wavelet sparse approximate inverse preconditioners, Bit, 37, 3, 644-660, (1997) · Zbl 0891.65048
[8] E. Chow, A priori sparsity patterns for parallel sparse approximate inverse preconditioners, Technical Report UCRL-JC-130719, Center for Applied Scientific Computing, Lawrence Livermore National Laboratory, Livermore, CA, 1998 · Zbl 0957.65023
[9] Chow, E.; Saad, Y., Approximate inverse techniques for block-partitioned matrices, SIAM J. sci. comput., 18, 1657-1675, (1997) · Zbl 0888.65035
[10] Chow, E.; Saad, Y., Approximate inverse preconditioners via sparse – sparse iterations, SIAM J. sci. comput., 19, 3, 995-1023, (1998) · Zbl 0922.65034
[11] Concus, P.; Golub, G.H.; Meurant, G., Block preconditioning for the conjugate gradient method, SIAM J. sci. stat. comput., 6, 187-209, (1983)
[12] Cosgrove, J.D.F.; Diaz, J.C.; Griewank, A., Approximate inverse preconditionings for sparse linear systems, Int. J. comput. math., 44, 91-110, (1992) · Zbl 0762.65025
[13] Golub, G.H.; van der Vorst, H.A., Closer to the solution: iterative linear solvers, (), 63-92 · Zbl 0881.65025
[14] Gould, N.I.M.; Scott, J.A., Sparse approximate-inverse preconditioners using norm-minimization techniques, SIAM J. sci. comput., 19, 2, 605-625, (1998) · Zbl 0911.65037
[15] Gravvanis, G.A., An approximate inverse matrix technique for arrowhead matrices, Int. J. comput. math., 70, 35-45, (1998) · Zbl 0933.65031
[16] Grote, M.; Huckle, T., Parallel preconditioning with sparse approximate inverses, SIAM J. sci. comput., 18, 838-853, (1997) · Zbl 0872.65031
[17] Huckel, T.K., Efficient computation of sparse approximate inverse, Numer. linear algebra appl., 5, 1, 57-71, (1998) · Zbl 0937.65055
[18] Kolotina, L.Y.; Yeremin, A.Y., Factorized sparse approximate inverse preconditioning I: theory, SIAM J. matrix anal. appl., 14, 45-58, (1993)
[19] Luo, J.-G., Extended concept of stair-shape sparsity for the inverse of an asymmetric matrix, Comput. math. appl., 25, 4, 113-122, (1993) · Zbl 0778.65018
[20] Luo, J.-G., An incomplete inverse as a preconditioner for the conjugate gradient method, Comput. math. appl., 25, 2, 73-79, (1993) · Zbl 0765.65041
[21] Luo, J.-G., A new class of decomposition for inverting asymmetric and indefinite matrices, Comput. math. appl., 25, 4, 95-104, (1993) · Zbl 0776.65021
[22] Luo, J.-G., A sparsity for decomposing a symmetric matrix, Comput. math. appl., 25, 5, 83-90, (1993) · Zbl 0778.65019
[23] Meijerink, J.A.; van der Vorst, H.A., An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix, Math. comp., 31, 148-162, (1977) · Zbl 0349.65020
[24] Nachtigal, N.M.; Reddy, S.C.; Trefethen, L.N., How fast are nonsymmetric matrix iterations?, SIAM matrix anal. appl., 13, 3, 778-795, (1992) · Zbl 0754.65036
[25] Saad, Y., ILUT: a dual threshold incomplete LU preconditioner, Numer. linear algebra appl., 1, 4, 387-402, (1994) · Zbl 0838.65026
[26] Saad, Y., Iterative methods for sparse linear systems, (1996), PWS Publishing New York · Zbl 1002.65042
[27] Y. Saad, M. Sosonkina, J. Zhang, Domain decomposition and multi-level type techniques for general sparse linear systems, in: J. Mandel, C. Farhat, X.-C. Cai (Eds.), Domain Decomposition Methods 10, No. 218 in Contemporary Mathematics, Providence, RI, 1998, AMS, pp. 174-190 · Zbl 0909.65020
[28] Saad, Y.; Zhang, J., BILUM: block versions of multielimination and multilevel ILU preconditioner for general sparse linear systems, SIAM J. sci. comput., 20, 6, 2103-2121, (1999) · Zbl 0956.65026
[29] Saad, Y.; Zhang, J., BILUTM: a domain-based multilevel block ILUT preconditioner for general sparse matrices, SIAM J. matrix anal. appl., 21, 1, 279-299, (1999) · Zbl 0942.65045
[30] Saad, Y.; Zhang, J., Enhanced multilevel block ILU preconditioning strategies for general sparse linear systems, J. comput. appl. math., 130, 99-118, (2001) · Zbl 1010.65014
[31] Tang, W.-P., Towards an effective sparse approximate inverse preconditioner, SIAM J. matrix anal. appl., 20, 4, 970-986, (1999) · Zbl 0937.65056
[32] W.-P. Tang, W.L. Wan, Sparse approximate inverse smoother for multi-grid, Technical Report CAM 98-18, Department of Mathematics, University of California at Los Angeles, Los Angeles, CA, 1998
[33] Zhang, J., Preconditioned Krylov subspace methods for solving nonsymmetric matrices from CFD applications, Comput. meth. appl. mech. eng., 189, 3, 825-840, (2000) · Zbl 0991.76067
[34] Zhang, J., Sparse approximate inverse and multilevel block ILU preconditioning techniques for general sparse matrices, Appl. numer. math., 35, 1, 89-108, (2000)
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.