ITERATIVE ILU PRECONDITIONERS FOR LINEAR SYSTEMS AND EIGENPROBLEMS

doi:10.4208/jcm.2009-m2020-0138

Journal of Computational Mathematics ›› 2021, Vol. 39 ›› Issue (4): 633-654.DOI: 10.4208/jcm.2009-m2020-0138

ITERATIVE ILU PRECONDITIONERS FOR LINEAR SYSTEMS AND EIGENPROBLEMS

Daniele Boffi¹, Zhongjie Lu², Luca F. Pavarino³

1 Computer, Electrical and Mathematical Sciences and Engineering Division, King Abdullah University of Science and Technology (KAUST), Thuwal 23955-6900, Kingdom of Saudi Arabia Dipartimento di Matematica "F. Casorati" University of Pavia Via Ferrata 5, 27100 Pavia, Italy;
2 Dipartimento di Matematica, Università di Pavia, via Ferrata 5, 27100 Pavia, Italy School of Mathematical Sciences, University of Science and Technology of China, Hefei 230026, China;
3 Dipartimento di Matematica, Università di Pavia, via Ferrata 5, 27100 Pavia, Italy

Received:2020-05-27 Revised:2020-08-17 Online:2021-07-15 Published:2021-08-06
Contact: Zhongjie Lu,Email:zhjlu@ustc.edu.cn
Supported by:
The authors are members of the INdAM Research group GNCS and their research is partially supported by IMATI/CNR, by PRIN/MIUR and the Dipartimenti di Eccellenza Program 2018-22-Dept. of Mathematics, University of Pavia.

PDF ( 27 ) Cited

Daniele Boffi, Zhongjie Lu, Luca F. Pavarino. ITERATIVE ILU PRECONDITIONERS FOR LINEAR SYSTEMS AND EIGENPROBLEMS[J]. Journal of Computational Mathematics, 2021, 39(4): 633-654.

Iterative ILU factorizations are constructed, analyzed and applied as preconditioners to solve both linear systems and eigenproblems. The computational kernels of these novel Iterative ILU factorizations are sparse matrix-matrix multiplications, which are easy and efficient to implement on both serial and parallel computer architectures and can take full advantage of existing matrix-matrix multiplication codes. We also introduce level-based and threshold-based algorithms in order to enhance the accuracy of the proposed Iterative ILU factorizations. The results of several numerical experiments illustrate the efficiency of the proposed preconditioners to solve both linear systems and eigenvalue problems.

Key words: Iterative ILU factorization, Matrix-matrix multiplication, Fill-in, Eigenvalue problem, Parallel preconditioner

CLC Number:

[1] A. Abdelfattah, H. Anzt, J. Dongarra, M. Gates, A. Haidar, J. Kurzak, P. Luszczek, S. Tomov, I. Yamazaki, and A. YarKhan. Linear algebra software for large-scale accelerated multicore computing. Acta Numerica, 25(2016), 1-160.
[2] E. Anderson and Y. Saad. Solving sparse triangular linear systems on parallel computers. Internat. J. High Speed Comput., 1:01(1989), 73-95,.
[3] H. Anzt, E. Chow, and J. Dongarra. ParILUT—a new parallel threshold ILU factorization. SIAM J. Sci. Comput., 40:4(2018), C503-C519,.
[4] C.C. Ashcraft and R. G. Grimes. On vectorizing incomplete factorization and ssor preconditioners. SIAM J. Sci. Statist. Comput., 9:1(1988), 122-151.
[5] S. Balay, S. Abhyankar, M. Adams, J. Brown, P. Brune, K. Buschelman, L. Dalcin, V. Eijkhout, W. Gropp, D. Kaushik, et al. Petsc users manual revision 3.8. Technical report, Argonne National Lab.(ANL), Argonne, IL (United States), 2017.
[6] R. Barrett, M.W. Berry, T.F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, and H. van der Vorst. Templates for the solution of linear systems: building blocks for iterative methods, volume 43. SIAM, 1994.
[7] M. Benzi. Preconditioning techniques for large linear systems: a survey. J. Comput. Phys., 182:2(2002), 418-477.
[8] M. Bern, J.R. Gilbert, B. Hendrickson, N. Nguyen, and S. Toledo. Support-graph preconditioners. SIAM J. Matrix Anal. Appl., 27:4(2006), 930-951.
[9] D. Boffi. Finite element approximation of eigenvalue problems. Acta Numer., 19(2010), 1-120.
[10] D. Boffi, F. Brezzi, and M. Fortin. Mixed finite element methods and applications, volume 44. Springer, 2013.
[11] D. Boffi, D. Gallistl, F. Gardini, and L. Gastaldi. Optimal convergence of adaptive fem for eigenvalue clusters in mixed form. Math. Comp., 86:307(2017), 2213-2237.
[12] A. Buluç and J.R. Gilbert. Parallel sparse matrix-matrix multiplication and indexing: Implementation and experiments. SIAM J. Sci. Comput., 34:4(2012), C170-C191.
[13] C. Calgaro, J.P. Chehab, and Y. Saad. Incremental incomplete LU factorizations with applications. Numer. Linear Algebra Appl., 17:5(2010), 811-837.
[14] E. Chow and A. Patel. Fine-grained parallel incomplete LU factorization. SIAM J. Sci. Comput., 37:2(2015), C169-C193.
[15] T.A. Davis and Y. Hu. The University of Florida sparse matrix collection. ACM T. Math. Software (TOMS), 38:1(2011), 1.
[16] H.C. Elman. A stability analysis of incomplete LU factorizations. Math. Comp., 1986, 191-217.
[17] L. Ghezzi, L.F. Pavarino, and E. Zampieri. Overlapping schwarz preconditioned eigensolvers for spectral element discretizations. Appl. Math. Comput., 218:15(2012), 7700-7710.
[18] J.R. Gilbert, C. Moler, and R. Schreiber. Sparse matrices in matlab: Design and implementation. SIAM J. Matrix Anal. Appl., 13:1(1992), 333-356.
[19] A. Greenbaum. Iterative methods for solving linear systems, volume 17. SIAM, 1997.
[20] I. Gustafsson. A class of first order factorization methods. BIT, 18:2(1978), 142-156.
[21] P. Hénon and Y. Saad. A parallel multistage ILU factorization based on a hierarchical graph decomposition. SIAM J. Sci. Comput., 28:6(2006), 2266-2293.
[22] D. Hysom and A. Pothen. A scalable parallel algorithm for incomplete factor preconditioning. SIAM J. Sci. Comput., 22:6(2001), 2194-2215.
[23] D. Hysom and A. Pothen. Level-based incomplete LU factorization: Graph model and algorithms. Preprint UCRL-JC-150789, US Department of Energy, Nov, 2002.
[24] D. S. Kershaw. The incomplete Cholesky conjugate gradient method for the iterative solution of systems of linear equations. J. Comput. Phys., 26:1(1978), 43-65.
[25] A.V. Knyazev. Toward the optimal preconditioned eigensolver: Locally optimal block preconditioned conjugate gradient method. SIAM J. Sci. Comput., 23:2(2001), 517-541.
[26] X.S. Li. An overview of SuperLU: algorithms, implementation, and user interface. ACM T. Math. Software (TOMS), 31:3(2005), 302-325.
[27] S. MacLachlan, D. Osei-Kuffuor, and Y. Saad. Modification and compensation strategies for threshold-based incomplete factorizations. SIAM J. Sci. Comput., 34:1(2012), A48-A75.
[28] M. Magolu monga Made and H.A. van der Vorst. A generalized domain decomposition paradigm for parallel incomplete LU factorization preconditionings. Future Gener. Comp. Sy., 17:8(2001), 925-932.
[29] M. McCourt, B. Smith, and H. Zhang. Sparse matrix-matrix products executed through coloring. SIAM J. Matrix Anal. Appl., 36:1(2015), 90-109.
[30] Y. Notay. Conditioning analysis of modified block incomplete factorizations. Linear Algebra Appl., 154(1991), 711-722.
[31] Y. Saad. ILUT: A dual threshold incomplete LU factorization. Numer. Linear Algebra Appl., 1:4(1994), 387-402.
[32] Y. Saad. Iterative Methods for Sparse Linear Systems, volume 82. SIAM, 2003.
[33] J. Scott and M. Tuma. Improving the stability and robustness of incomplete symmetric indefinite factorization preconditioners. Numer. Linear Algebra Appl., 24:5(2017), e2099.
[34] E. Vecharynski and A.V. Knyazev. Preconditioned locally harmonic residual method for computing interior eigenpairs of certain classes of hermitian matrices. SIAM J. Sci. Comput., 37:5(2015), S3-S29.
[35] A.J. Wathen. Preconditioning. Acta Numer., 24(2015), 329-376.

[1]	Qilong Zhai, Xiaozhe Hu, Ran Zhang. THE SHIFTED-INVERSE POWER WEAK GALERKIN METHOD FOR EIGENVALUE PROBLEMS [J]. Journal of Computational Mathematics, 2020, 38(4): 606-623.
[2]	Hai Bi, Yidu Yang, Yuanyuan Yu, Jiayu Han. NEW ERROR ESTIMATES FOR LINEAR TRIANGLE FINITE ELEMENTS IN THE STEKLOV EIGENVALUE PROBLEM [J]. Journal of Computational Mathematics, 2018, 36(5): 682-692.
[3]	Yunfeng Cai, Zhaojun Bai, John E. Pask, N. Sukumar. CONVERGENCE ANALYSIS OF A LOCALLY ACCELERATED PRECONDITIONED STEEPEST DESCENT METHOD FOR HERMITIAN-DEFINITE GENERALIZED EIGENVALUE PROBLEMS [J]. Journal of Computational Mathematics, 2018, 36(5): 739-760.
[4]	Yingxia Xi, Xia Ji. RECURSIVE INTEGRAL METHOD FOR THE NONLINEAR NON-SELFADJOINT TRANSMISSION EIGENVALUE PROBLEM [J]. Journal of Computational Mathematics, 2017, 35(6): 828-838.
[5]	Davide Forti, Alfio Quarteroni, Simone Deparis. A PARALLEL ALGORITHM FOR THE SOLUTION OF LARGE-SCALE NONCONFORMING FLUID-STRUCTURE INTERACTION PROBLEMS IN HEMODYNAMICS [J]. Journal of Computational Mathematics, 2017, 35(3): 363-380.
[6]	Xiaole Han, Hehu Xie, Fei Xu. A CASCADIC MULTIGRID METHOD FOR EIGENVALUE PROBLEM [J]. Journal of Computational Mathematics, 2017, 35(1): 74-90.
[7]	K.C. Chang, Sihong Shao, Dong Zhang. THE 1-LAPLACIAN CHEEGER CUT: THEORY AND ALGORITHMS [J]. Journal of Computational Mathematics, 2015, 33(5): 443-467.
[8]	Youai Li. CONVERGENCE ANALYSIS FOR THE ITERATED DEFECT CORRECTION SCHEME OF FINITE ELEMENT METHODS ON RECTANGLE GRIDS [J]. Journal of Computational Mathematics, 2015, 33(3): 297-306.
[9]	John C. Urschel, Jinchao Xu, Xiaozhe Hu, Ludmil T. Zikatanov. A CASCADIC MULTIGRID ALGORITHM FOR COMPUTING THE FIEDLER VECTOR OF GRAPH LAPLACIANS [J]. Journal of Computational Mathematics, 2015, 33(2): 209-226.
[10]	Darko Volkov. A NUMERICAL BOUNDARY EIGENVALUE PROBLEM FOR ELASTIC CRACKS IN FREE AND HALF SPACE [J]. Journal of Computational Mathematics, 2011, 29(5): 543-573.
[11]	Hua Dai, Zhong-Zhi Bai. ON SMOOTH LU DECOMPOSITIONS WITH APPLICATIONS TO SOLUTIONS OF NONLINEAR EIGENVALUE PROBLEMS [J]. Journal of Computational Mathematics, 2010, 28(6): 745-766.
[12]	Xin Huang, Zhaojun Bai, Yangfeng Su . NONLINEAR RANK-ONE MODIFICATION OF THE SYMMETRIC EIGENVALUE PROBLEM [J]. Journal of Computational Mathematics, 2010, 28(2): 218-234.
[13]	Zhongzhi Bai, Yonghua Gao . MODIFIED BERNOULLI ITERATION METHODS FOR QUADRATIC MATRIXEQUATION [J]. Journal of Computational Mathematics, 2007, 25(5): 498-511.
[14]	Haixia Liang, Erxiong Jiang . AN INVERSE EIGENVALUE PROBLEM FOR JACOBI MATRICES [J]. Journal of Computational Mathematics, 2007, 25(5): 620-630.
[15]	Jianhua Yuan. AN ADAPTIVE INVERSE ITERATION FEM FOR THE INHOMOGENEOUS DIELECTRIC WAVEGUIDES [J]. Journal of Computational Mathematics, 2007, 25(2): 169-184.

Viewed

Full text

Abstract

ITERATIVE ILU PRECONDITIONERS FOR LINEAR SYSTEMS AND EIGENPROBLEMS

扫码分享