Incomplete LU Factorization on Projection Method

Seyed Abolfazl Shahzadeh Fazelı; Azam Ghodratnama; Azam Sadeghıan; Seyed Mehdi Karbassı

doi:10.17776/csj.18615

Incomplete LU Factorization on Projection Method

Year 2016, Volume: 37 Issue: 3, 164 - 175, 16.09.2016

Seyed Abolfazl Shahzadeh Fazelı , Azam Ghodratnama Azam Sadeghıan Seyed Mehdi Karbassı

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

Seyed Abolfazl Shahzadeh Fazelı , Azam Ghodratnama Azam Sadeghıan Seyed Mehdi Karbassı

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

Keywords

Ö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.

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.