×

ILU preconditioning based on the FAPINV algorithm. (English) Zbl 1334.65071

The technique of obtaining a preconditioner for a real matrix by computing an approximate L(D)U factorization (ILU) of its inverse, is known as the FAINV method; see for example [J.-C. Luo, Comput. Math. Appl. 25, No. 2, 73–79 (1993; Zbl 0765.65041)]. Several versions were since then derived for different types of matrices. The purpose of this paper is to show that a forward version (FFAINV) is breakdown-free when applied to nonsymmetric positive definite matrices and \(H\)-matrices. A pseudo-code for the algorithm and numerical simulations are included.

MSC:

65F08 Preconditioners for iterative methods
65F10 Iterative numerical methods for linear systems
65F50 Computational methods for sparse matrices

Citations:

Zbl 0765.65041
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] M. Benzi, Preconditioning techniques for large linear systems: A survey, J. of Computational Physics 182 (2002), 418–477. · Zbl 1015.65018
[2] M. Benzi, J.K. Cullum, M. Tuma, C.D. Meyer, Robust approximate inverse preconditioning for the conjugate gradient method, SIAM J. Sci. Comput. 22 (2000), 1318–1332. · Zbl 0985.65035
[3] M. Benzi, W.D. Joubert, G. Mateescu, Numercal experiments with parallel orderings for ILU preconditioners, ETNA 8 (1999), 88–114. · Zbl 0923.65012
[4] M. Benzi, C.D. Meyer, M. Tuma, A sparse approximate inverse preconditioner for the conjugate gradient method, SIAM J. Sci. Comput. 17 (1996), 1135–1149. · Zbl 0856.65019
[5] M. Benzi, D.B. Szyld, A. van Duin, Ordering for incomplete factorization preconditioning of nonsymmetric problems, SIAM J. Sci. Comput. 20 (1999), 1652–1670. · Zbl 0940.65033
[6] M. Benzi, M. Tuma, A sparse approximate inverse preconditioner for nonsymmetric linear systems, SIAM J. Sci. Comput. 19 (1998), 968–994. · Zbl 0930.65027
[7] M. Benzi, M. Tuma, A comparative study of sparse approximate inverse preconditioners, Appl. Numer. Math. 30 (1999), 305–340. · Zbl 0949.65043
[8] M. Benzi, M. Tuma, A robust incomplete factorization preconditioner for positive definite matrices, Numer. Linear Algebra Appl. 10 (2003), 385–400.
[9] T. Davis, University of Florida sparse matrix collection, NA Digest, 92 (1994), http://www.cise.ufl.edu/research/sparse/matrices.
[10] G. Karypis, V. Kumar, Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM J. Sci. Comput. 20 (1998) 1, 359–392. · Zbl 0915.68129
[11] S.A. Kharchenko, L.Yu. Kolotilina, A.A. Nikishin, A.Yu. Yeremin, A robust AINV-type method for constructing sparse approximate inverse preconditioners in factored form, Numer. Linear Algebra Appl. 8 (2001), 165–179. · Zbl 1051.65057
[12] L.Y. Kolotilina, A.Y. Yeremin, Factorized sparse approximate inverse preconditioning I. Theory, SIAM J. Matrix Anal. Appl. 14 (1993), 45–58. · Zbl 0767.65037
[13] L.Y. Kolotilina, A.Y. Yeremin, Factorized sparse approximate inverse preconditioning II: Solution of 3D FE systems on massively parallel computers, Int. J. High Speed Comput. 7 (1995), 191–215.
[14] E.-J. Lee, J. Zhang, A two-phase preconditioning strategy of sparse approximate inverse for indefinite matrices, Technical Report No. 476-07, Department of Computer Science, University of Kentuky, Lexington, KY, 2007.
[15] E.-J. Lee, J. Zhang, Fatored approximate inverse preonditioners with dynamic sparsity patterns, Technial Report No. 488-07, Department of Computer Science, University of Kentuky, Lexington, KY, 2007.
[16] N. Li, Y. Saad, E. Chow, Crout version of ILU for general sparse matrices, SIAM J. Sci. Comput. 25 (2003) 2, 716–728. · Zbl 1042.65025
[17] J.-G. Luo, A new class of decomposition for symmetric systems, Mechanics Research Communications 19 (1992), 159–166. · Zbl 0757.65027
[18] J.-G. Luo, An incomplete inverse as a preconditioner for the conjugate gradient method, Comput. Math. Appl. 25 (1993), 73–79. · Zbl 0765.65041
[19] J.-G. Luo, A new class of decomposition for inverting asymmetric and indefinite matrices, Comput. Math. Appl. 25 (1993), 95–104. · Zbl 0776.65021
[20] T. Manteuffel, An incomplete factorization technique for positive definite linear systems, Math. Comput. 34 (1980), 473–497. · Zbl 0422.65018
[21] J.A. Meijerink, H.A. van der Vorst, An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix, Math. Comput. 31 (1977), 148–162. · Zbl 0349.65020
[22] G. Meurant, The block preconditioned conjugate gradient method on vector computers, BIT 24 (1984), 623–633. · Zbl 0556.65023
[23] M. Rezghi, S.M. Hosseini, An ILU preconditioner for nonsymmetric positive definite matrices by using the conjugate Gram-Schmidt process, J. Comput. Appl. Math. 188 (2006), 150–164. · Zbl 1096.65042
[24] Y. Saad, Sparskit and sparse examples, NA Digest (1994), http://www-users.cs.umn.edu/ saad/software, Accessed 2010.
[25] Y. Saad, ILUT: A dual theshold incomplete LU preconditioner, Numer. Linear Algebra Appl. 1 (1994), 387–402. · Zbl 0838.65026
[26] Y. Saad, Iterative Methods for Sparse Linear Systems, PWS Press, New York, 1995.
[27] Y. Saad, ILUM: A multi-elimination ILU preconditioner for general sparse matrices, SIAM J. Sci. Comput. 174 (1996), 830–847. · Zbl 0858.65029
[28] Y. Saad, M.H. Schultz, GMRES: A generalized minimal residual algorithm for nonsymmetric linear systems, SIAM J. Sci. Statist. Comput. 7 (1986), 856–869. · Zbl 0599.65018
[29] Y. Saad, J. Zhang, BILUM: Block versions of multi-elimination and multilevel ILU preconditioner for general linear sparse systems, SIAM J. Sci. Comput. 20 (1999), 2103–2121. · Zbl 0956.65026
[30] Y. Saad, J. Zhang, BILUTM: a domain-based multilevel block ILUT preconditioner for general sparse matrices, SIAM J. Matrix Anal. Appl. 21 (1999), 279–299. · Zbl 0942.65045
[31] D.K. Salkuyeh, A sparse approximate inverse preconditioner for nonsymmetric positive definite matrices, Journal of Applied Mathematics and Informatics 28 (2010), 1131–1141. · Zbl 1278.65029
[32] H.A. van der Vorst, Bi-CGSTAB: a fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems, SIAM J. Sci. Statist. Comput. 12 (1992), 631–644. · Zbl 0761.65023
[33] J. Zhang, A procedure for computing factored approximate inverse, M.Sc. Dissertation, Department of Computer Science, University of Kentucky, 1999.
[34] J. Zhang, A sparse approximate inverse technique for parallel preconditioning of general sparse matrices, Appl. Math. Comput. 130 (2002), 63–85. · Zbl 1028.65044
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.