Opuscula Math. 35, no. 2 (2015), 235-250
http://dx.doi.org/10.7494/OpMath.2015.35.2.235

 
Opuscula Mathematica

ILU preconditioning based on the FAPINV algorithm

Davod Khojasteh Salkuyeh
Amin Rafiei
Hadi Roohani

Abstract. A technique for computing an ILU preconditioner based on the factored approximate 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.

Keywords: system of linear equations, preconditioner, FAPINV, ILU preconditioner, H-matrix, GMRES.

Mathematics Subject Classification: 65F10, 65F50.

Full text (pdf)

  1. M. Benzi, Preconditioning techniques for large linear systems: A survey, J. of Computational Physics 182 (2002), 418-477.
  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.
  3. M. Benzi, W.D. Joubert, G. Mateescu, Numercal experiments with parallel orderings for ILU preconditioners, ETNA 8 (1999), 88-114.
  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.
  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.
  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 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.
  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, Crout 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 matrices, 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), Accessed 2010, http://www-users.cs.umn.edu/~saad/software
  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 nonsymmetric 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 positive 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.
  • Davod Khojasteh Salkuyeh
  • University of Guilan, Faculty of Mathematical Sciences, Rasht, Iran
  • Amin Rafiei
  • Hakim Sabzevari University, Department of Mathematics, P.O. Box. 397, Sabzevar, Iran
  • Hadi Roohani
  • Malek Ashtar University of Technology, Department of Mathematics, Shahin Shar, Isfahan, P.O. Box 83145-115, Iran
  • Communicated by Zdzisław Jackiewicz.
  • Received: 2014-04-25.
  • Revised: 2014-05-27.
  • Accepted: 2014-06-07.
  • Published online: 2014-11-18.
Opuscula Mathematica - cover

Cite this article as:
Davod Khojasteh Salkuyeh, Amin Rafiei, Hadi Roohani, ILU preconditioning based on the FAPINV algorithm, Opuscula Math. 35, no. 2 (2015), 235-250, http://dx.doi.org/10.7494/OpMath.2015.35.2.235

Download this article's citation as:
a .bib file (BibTeX),
a .ris file (RefMan),
a .enw file (EndNote)
or export to RefWorks.

We advise that this website uses cookies to help us understand how the site is used. All data is anonymized. Recent versions of popular browsers provide users with control over cookies, allowing them to set their preferences to accept or reject all cookies or specific ones.