BibTex RIS Cite

Incomplete LU Factorization on Projection Method

Year 2016, Volume: 37 Issue: 3, 164 - 175, 16.09.2016
https://doi.org/10.17776/csj.18615

Abstract

Abstarct. The projection method allows solving sparse linear systems. Solving the sparse linear systems is a common problem which arises from many complex applications. The problems to be solved often are of very large size. Combination of the preconditioners with the projection methods continues to play an important role in solving the sparse linear system. In this paper, we propose a new technique to solve a linear system. This approach is called incomplete LU factorization on Full Orthogonalization method (ILUFOM). Here we present and examine a number of techniques for solving sparse linear systems using incomplete LU factorization. Particularly GMRES and FOM method with some preconditions are considered. The efficiency of the algorithm is demonstrated using an example. According to our experiments, ILUFOM improves the convergence of FOM.

Keywords: Preconditioning, Projection method, LU Factorization, Full Orthogonalization Method

Özet. Projeksiyon yöntemi seyrek doğrusal sistemleri çözümüne izin verir. Seyrek doğrusal sistemlerinin çözümü, çok karmaşık uygulamalarda ortaya çıkan yaygın bir problemdir. Çözülen problemler sıklıkla çok büyük boyutlardadır. Projeksiyon yöntemleri ile ön şartlandırıcı kombinasyonu seyrek lineer sistem çözümünde önemli bir rol oynamaya devam etmektedir. Bu yazıda, doğrusal bir sistemi çözmek için yeni bir teknik öneriyoruz. Bu yaklaşıma, Tam Ortogonalleştirme metodu (ILUFOM) üzerine eksik LU çarpanlara ayırma denir. Burada mevcut ve eksik LU çarpanlara kullanarak seyrek doğrusal sistemleri çözmek için bir takım teknikler sunduk ve inceledik. Özellikle bazı önkoşullarla GMRES ve FORM yöntemleri ele alınmıştır. Algoritmanın etkinliği bir örnekle gösterilmiştir. Deneylere göre, ILUFOM, FOM yakınsamasını iyileştirmektedir.

Anahtar Kelimeler: Ön koşullandırma, projeksiyon metodu, LU çarpanlara ayırma, Tam Ortogonalleştirme metodu

 

References

  • M. Benzi, Preconditioning techniques for large linear systems. Journal of Computational Physics, 182, 418-477 (2002).
  • M. Benzi, C.D. Meyer & M. Tuma, A sparse approximate inverse preconditioner for the conjugate gradient method. SIAM Journal on Scienti_c Computing, 17, 1135-1149 (1996).
  • P. Birken, J.D. Tebbens, A. Meister & M. Tuma,Preconditioner updates applied to CFD model problems. Applied Numerical Mathematics, 58, 1628-1641 (2008).
  • C. Calgaro, J.P. Chehab & Y. Saad, Incremental incomplete LU factorizations with applications. Numerical Linear Algebra with Applications, 17, 811-837 (2010).
  • E. Chow, Y. Saad, Approximate inverse preconditioners via sparse-sparse iterations. SIAM Journal on Scienti_c Computing, 19, 995-1023 (1998).
  • E. Chow, Y. Saad, Approximate inverse techniques for block-partitioned matrices.SIAM Journal on Scientific Computing, 18, 1657-1675 (1997).
  • B. Datta, Numerical Linear Algebra and Applications, Second Edition (2010). SIAM
  • T.A. Davis, Direct Methods for Sparse Linear Systems (2006). SIAM: Philadelphia, PA.
  • H.C. Elman, A stability analysis of incomplete LU factorizations. Mathematics of Com-putation, 17, 191-217 (1986).
  • Essai, Weighted FOM, GMRES for solving nonsymmetric linear systems. NumericalAlgorithms, 18, 277-292 (1998).
  • R.M. Holland, A.J. Wathen & G. Shaw, Sparse approximate inverses, target matrices. SIAM Journal on Scienti_c Computing, 26, 1000-1011 (2005).
  • Y. Saad, H. Martin, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM journal on scientific, statistical computing, 7, 856-869 (1986).
  • Y. Saad, Preconditioning techniques for nonsymmetric, inde_nite linear systems. Journal of Computational , Applied Mathematics , 24, 89-105 (1988).
  • Y. Saad, ILUT: A dual threshold incomplete LU factorization. Numerical linear algebra with applications, 1, 387-402 (1994).
  • Y. Saad, Iterative methods for sparse linear systems (2003). SIAM: Philadelpha, PA.
Year 2016, Volume: 37 Issue: 3, 164 - 175, 16.09.2016
https://doi.org/10.17776/csj.18615

Abstract

Projeksiyon yöntemi seyrek doğrusal sistemleri çözümüne izin verir. Seyrek doğrusal sistemlerinin çözümü, çok karmaşık uygulamalarda ortaya çıkan yaygın bir problemdir. Çözülen problemler sıklıkla çok büyük boyutlardadır. Projeksiyon yöntemleri ile ön şartlandırıcı kombinasyonu seyrek lineer sistem çözümünde önemli bir rol oynamaya devam etmektedir. Bu yazıda, doğrusal bir sistemi çözmek için yeni bir teknik öneriyoruz. Bu yaklaşıma, Tam Ortogonalleştirme metodu (ILUFOM) üzerine eksik LU çarpanlara ayırma denir. Burada mevcut ve eksik LU çarpanlara kullanarak seyrek doğrusal sistemleri çözmek için bir takım teknikler sunduk ve inceledik. Özellikle bazı önkoşullarla GMRES ve FORM yöntemleri ele alınmıştır. Algoritmanın etkinliği bir örnekle gösterilmiştir.Deneylere göre, ILUFOM, FOM yakınsamasını iyileştirmektedir

References

  • M. Benzi, Preconditioning techniques for large linear systems. Journal of Computational Physics, 182, 418-477 (2002).
  • M. Benzi, C.D. Meyer & M. Tuma, A sparse approximate inverse preconditioner for the conjugate gradient method. SIAM Journal on Scienti_c Computing, 17, 1135-1149 (1996).
  • P. Birken, J.D. Tebbens, A. Meister & M. Tuma,Preconditioner updates applied to CFD model problems. Applied Numerical Mathematics, 58, 1628-1641 (2008).
  • C. Calgaro, J.P. Chehab & Y. Saad, Incremental incomplete LU factorizations with applications. Numerical Linear Algebra with Applications, 17, 811-837 (2010).
  • E. Chow, Y. Saad, Approximate inverse preconditioners via sparse-sparse iterations. SIAM Journal on Scienti_c Computing, 19, 995-1023 (1998).
  • E. Chow, Y. Saad, Approximate inverse techniques for block-partitioned matrices.SIAM Journal on Scientific Computing, 18, 1657-1675 (1997).
  • B. Datta, Numerical Linear Algebra and Applications, Second Edition (2010). SIAM
  • T.A. Davis, Direct Methods for Sparse Linear Systems (2006). SIAM: Philadelphia, PA.
  • H.C. Elman, A stability analysis of incomplete LU factorizations. Mathematics of Com-putation, 17, 191-217 (1986).
  • Essai, Weighted FOM, GMRES for solving nonsymmetric linear systems. NumericalAlgorithms, 18, 277-292 (1998).
  • R.M. Holland, A.J. Wathen & G. Shaw, Sparse approximate inverses, target matrices. SIAM Journal on Scienti_c Computing, 26, 1000-1011 (2005).
  • Y. Saad, H. Martin, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM journal on scientific, statistical computing, 7, 856-869 (1986).
  • Y. Saad, Preconditioning techniques for nonsymmetric, inde_nite linear systems. Journal of Computational , Applied Mathematics , 24, 89-105 (1988).
  • Y. Saad, ILUT: A dual threshold incomplete LU factorization. Numerical linear algebra with applications, 1, 387-402 (1994).
  • Y. Saad, Iterative methods for sparse linear systems (2003). SIAM: Philadelpha, PA.
There are 15 citations in total.

Details

Journal Section Engineering Research Article
Authors

Seyed Abolfazl Shahzadeh Fazelı

Azam Ghodratnama This is me

Azam Sadeghıan This is me

Seyed Mehdi Karbassı

Publication Date September 16, 2016
Published in Issue Year 2016 Volume: 37 Issue: 3

Cite

APA Shahzadeh Fazelı, S. A., Ghodratnama, A., Sadeghıan, A., Karbassı, S. M. (2016). Incomplete LU Factorization on Projection Method. Cumhuriyet Üniversitesi Fen Edebiyat Fakültesi Fen Bilimleri Dergisi, 37(3), 164-175. https://doi.org/10.17776/csj.18615
AMA Shahzadeh Fazelı SA, Ghodratnama A, Sadeghıan A, Karbassı SM. Incomplete LU Factorization on Projection Method. Cumhuriyet Üniversitesi Fen Edebiyat Fakültesi Fen Bilimleri Dergisi. October 2016;37(3):164-175. doi:10.17776/csj.18615
Chicago Shahzadeh Fazelı, Seyed Abolfazl, Azam Ghodratnama, Azam Sadeghıan, and Seyed Mehdi Karbassı. “Incomplete LU Factorization on Projection Method”. Cumhuriyet Üniversitesi Fen Edebiyat Fakültesi Fen Bilimleri Dergisi 37, no. 3 (October 2016): 164-75. https://doi.org/10.17776/csj.18615.
EndNote Shahzadeh Fazelı SA, Ghodratnama A, Sadeghıan A, Karbassı SM (October 1, 2016) Incomplete LU Factorization on Projection Method. Cumhuriyet Üniversitesi Fen Edebiyat Fakültesi Fen Bilimleri Dergisi 37 3 164–175.
IEEE S. A. Shahzadeh Fazelı, A. Ghodratnama, A. Sadeghıan, and S. M. Karbassı, “Incomplete LU Factorization on Projection Method”, Cumhuriyet Üniversitesi Fen Edebiyat Fakültesi Fen Bilimleri Dergisi, vol. 37, no. 3, pp. 164–175, 2016, doi: 10.17776/csj.18615.
ISNAD Shahzadeh Fazelı, Seyed Abolfazl et al. “Incomplete LU Factorization on Projection Method”. Cumhuriyet Üniversitesi Fen Edebiyat Fakültesi Fen Bilimleri Dergisi 37/3 (October 2016), 164-175. https://doi.org/10.17776/csj.18615.
JAMA Shahzadeh Fazelı SA, Ghodratnama A, Sadeghıan A, Karbassı SM. Incomplete LU Factorization on Projection Method. Cumhuriyet Üniversitesi Fen Edebiyat Fakültesi Fen Bilimleri Dergisi. 2016;37:164–175.
MLA Shahzadeh Fazelı, Seyed Abolfazl et al. “Incomplete LU Factorization on Projection Method”. Cumhuriyet Üniversitesi Fen Edebiyat Fakültesi Fen Bilimleri Dergisi, vol. 37, no. 3, 2016, pp. 164-75, doi:10.17776/csj.18615.
Vancouver Shahzadeh Fazelı SA, Ghodratnama A, Sadeghıan A, Karbassı SM. Incomplete LU Factorization on Projection Method. Cumhuriyet Üniversitesi Fen Edebiyat Fakültesi Fen Bilimleri Dergisi. 2016;37(3):164-75.