ILU preconditioning based on the FAPINV algorithm

• Autorzy: Salkuyeh D. K. , Rafiei A. , Roohani H.

Identyfikatory

DOI

http://dx.doi.org/10.7494/OpMath.2015.35.2.235

• Języki publikacji: EN

Abstrakty

EN

A technique for computing an ILU preconditioner based on the factored approx­imate inverse (FAPINV) algorithm is presented. We show that this algorithm is well-defined for H-matrices. Moreover, when used in conjunction with Krylov-subspace-based iterative solvers such as the GMRES algorithm, results in reliable solvers. Numerical experiments on some test matrices are given to show the efficiency of the new ILU preconditioner.

Słowa kluczowe

EN

system of linear equations; preconditioner; FAPINV; ILU preconditioner; H-matrix; GMRES

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2015
• Tom: Vol. 35, no. 2
• Strony: 235--250
• Opis fizyczny: Bibliogr. 34 poz., wykr., tab.

Twórcy

autor

Salkuyeh D. K.

• University of Guilan Faculty of Mathematical Sciences Rasht, Iran

autor

Rafiei A.

• Hakim Sabzevari University Department of Mathematics P.O. Box. 397, Sabzevar, Iran

autor

Roohani H.

• Malek Ashtar University of Technology Department of Mathematics

Bibliografia

• [1] M. Benzi, Preconditioning techniques for large linear systems: A survey, J. of Compu­tational Physics 182 (2002), 418-477.
• [2] M. Benzi, J.K. Cullum, M. Tuma, CD. Meyer, Robust approximate inverse precondi­tioning for the conjugate gradient method, SIAM J. Sci. Comput. 22 (2000), 1318-1332.
• [3] M. Benzi, W.D. Joubert, G. Mateescu, Numercal experiments with parallel orderings for ILU preconditioners, ETNA 8 (1999), 88-114.
• [4] M. Benzi, CD. Meyer, M. Tuma, A sparse approximate inverse preconditioner for the conjugate gradient method, SIAM J. Sci. Comput. 17 (1996), 1135-1149.
• [5] M. Benzi, D.B. Szyld, A. van Duin, Ordering for incomplete factorization precondition­ing of nonsymmetric problems, SIAM J. Sci. Comput. 20 (1999), 1652-1670.
• [6] M. Benzi, M. Tuma, A sparse approximate inverse preconditioner for nonsymmetric linear systems, SIAM J. Sci. Comput. 19 (1998), 968-994.
• [7] M. Benzi, M. Tuma, A comparative study of sparse approximate inverse preconditioners, Appl. Numer. Math. 30 (1999), 305-340.
• [8] M. Benzi, M. Tuma, A robust incomplete factorization preconditioner for positive defi­nite 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 Ir­regular Graphs, SIAM J. Sci. Comput. 20 (1998) 1, 359-392.
• [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.
• [12] L.Y. Kolotilina, A.Y. Yeremin, Factorized sparse approximate inverse preconditioning I. Theory, SIAM J. Matrix Anal. Appl. 14 (1993), 45-58.
• [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, Grout version of ILU for general sparse matrices, SIAM J. Sci. Comput. 25 (2003) 2, 716-728.
• [17] J.-G. Luo, A new class of decomposition for symmetric systems, Mechanics Research Communications 19 (1992), 159-166.
• [18] J.-G. Luo, An incomplete inverse as a preconditioner for the conjugate gradient method, Comput. Math. Appl. 25 (1993), 73-79.
• [19] J.-G. Luo, A new class of decomposition for inverting asymmetric and indefinite ma­trices, Comput. Math. Appl. 25 (1993), 95-104.
• [20] T. Manteuffel, An incomplete factorization technique for positive definite linear systems, Math. Comput. 34 (1980), 473-497.
• [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.
• [22] G. Meurant, The block preconditioned conjugate gradient method on vector computers, BIT 24 (1984), 623-633.
• [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.
• [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.
• [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.
• [28] Y. Saad, M.H. Schultz, GMRES: A generalized minimal residual algorithm for nonsym­metric linear systems, SIAM J. Sci. Statist. Comput. 7 (1986), 856-869.
• [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.
• [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.
• [31] D.K. Salkuyeh, A sparse approximate inverse preconditioner for nonsymmetric posi­tive definite matrices, Journal of Applied Mathematics and Informatics 28 (2010), 1131-1141.
• [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.
• [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.