Iterative ILU preconditioners for linear systems and eigenproblems. (English) Zbl 1499.65102
Summary: 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.
MSC:
| 65F08 | Preconditioners for iterative methods |
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
| 15A23 | Factorization of matrices |
Keywords:
iterative ILU factorization; matrix-matrix multiplication; fill-in; eigenvalue problem; parallel preconditionerReferences:
| [1] | D = diag(diag(B)) |
| [2] | D = diag(diag(B)) |
| [3] | threshold ILU factorization IterILUT(τ , p). |
| [4] | Set the initial data L 0 = D = U 0 = 0. 2. for for k = 1, 2, • • • , do 3. B = L 0 U 0 |
| [5] | B = A − B |
| [6] | D = diag(diag(B)) |
| [7] | L 0 = tril(B, −1)D −1 8. execute dropping strategies on L 0 and U 0 according to the threshold τ . 9. end for 10. L = L 0 + I and U = U 0 + D. |
| [8] | A. Abdelfattah, H. Anzt, J. Dongarra, M. Gates, A. Haidar, J. Kurzak, P. Luszczek, S. To-mov, I. Yamazaki, and A. YarKhan. Linear algebra software for large-scale accelerated multicore computing. Acta Numerica, 25 (2016), 1-160. · Zbl 1353.65019 |
| [9] | E. Anderson and Y. Saad. Solving sparse triangular linear systems on parallel computers. Internat. J. High Speed Comput., 1:01 (1989), 73-95,. · Zbl 0726.65026 |
| [10] | H. Anzt, E. Chow, and J. Dongarra. ParILUT-a new parallel threshold ILU factorization. SIAM J. Sci. Comput., 40:4 (2018), C503-C519, . · Zbl 1391.65055 |
| [11] | C.C. Ashcraft and R. G. Grimes. On vectorizing incomplete factorization and ssor preconditioners. SIAM J. Sci. Statist. Comput., 9:1 (1988), 122-151. · Zbl 0641.65028 |
| [12] | 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. |
| [13] | 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. |
| [14] | M. Benzi. Preconditioning techniques for large linear systems: a survey. J. Comput. Phys., 182:2 (2002), 418-477. · Zbl 1015.65018 |
| [15] | 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. · Zbl 1106.65040 |
| [16] | D. Boffi. Finite element approximation of eigenvalue problems. Acta Numer., 19 (2010), 1-120. · Zbl 1242.65110 |
| [17] | D. Boffi, F. Brezzi, and M. Fortin. Mixed finite element methods and applications, volume 44. Springer, 2013. · Zbl 1277.65092 |
| [18] | 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. · Zbl 1364.65234 |
| [19] | A. Buluç and J.R. Gilbert. Parallel sparse matrix-matrix multiplication and indexing: Implemen-tation and experiments. SIAM J. Sci. Comput., 34:4 (2012), C170-C191. · Zbl 1252.05112 |
| [20] | C. Calgaro, J.P. Chehab, and Y. Saad. Incremental incomplete LU factorizations with applications. Numer. Linear Algebra Appl., 17:5 (2010), 811-837. · Zbl 1240.65091 |
| [21] | E. Chow and A. Patel. Fine-grained parallel incomplete LU factorization. SIAM J. Sci. Comput., 37:2 (2015), C169-C193. · Zbl 1320.65048 |
| [22] | T.A. Davis and Y. Hu. The University of Florida sparse matrix collection. ACM T. Math. Software (TOMS), 38:1 (2011), 1. · Zbl 1365.65123 |
| [23] | H.C. Elman. A stability analysis of incomplete LU factorizations. Math. Comp., 1986, 191-217. · Zbl 0621.65024 |
| [24] | L. Ghezzi, L.F. Pavarino, and E. Zampieri. Overlapping schwarz preconditioned eigensolvers for spectral element discretizations. Appl. Math. Comput., 218:15 (2012), 7700-7710. · Zbl 1242.65231 |
| [25] | 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. · Zbl 0752.65037 |
| [26] | A. Greenbaum. Iterative methods for solving linear systems, volume 17. SIAM, 1997. · Zbl 0883.65022 |
| [27] | I. Gustafsson. A class of first order factorization methods. BIT, 18:2 (1978), 142-156. · Zbl 0386.65006 |
| [28] | 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. · Zbl 1126.65028 |
| [29] | D. Hysom and A. Pothen. A scalable parallel algorithm for incomplete factor preconditioning. SIAM J. Sci. Comput., 22:6 (2001), 2194-2215. · Zbl 0986.65048 |
| [30] | D. Hysom and A. Pothen. Level-based incomplete LU factorization: Graph model and algorithms. Preprint UCRL-JC-150789, US Department of Energy, Nov, 2002. |
| [31] | 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. · Zbl 0367.65018 |
| [32] | A.V. Knyazev. Toward the optimal preconditioned eigensolver: Locally optimal block precondi-tioned conjugate gradient method. SIAM J. Sci. Comput., 23:2 (2001), 517-541. · Zbl 0992.65028 |
| [33] | X.S. Li. An overview of SuperLU: algorithms, implementation, and user interface. ACM T. Math. Software (TOMS), 31:3 (2005), 302-325. · Zbl 1136.65312 |
| [34] | 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. · Zbl 1241.65032 |
| [35] | 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. · Zbl 1032.68171 |
| [36] | M. McCourt, B. Smith, and H. Zhang. Sparse matrix-matrix products executed through coloring. SIAM J. Matrix Anal. Appl., 36:1 (2015), 90-109. · Zbl 1327.65092 |
| [37] | Y. Notay. Conditioning analysis of modified block incomplete factorizations. Linear Algebra Appl., 154 (1991), 711-722. · Zbl 0735.65028 |
| [38] | Y. Saad. ILUT: A dual threshold incomplete LU factorization. Numer. Linear Algebra Appl., 1:4 (1994), 387-402. · Zbl 0838.65026 |
| [39] | Y. Saad. Iterative Methods for Sparse Linear Systems, volume 82. SIAM, 2003. · Zbl 1002.65042 |
| [40] | J. Scott and M. Tuma. Improving the stability and robustness of incomplete symmetric indefinite factorization preconditioners. Numer. Linear Algebra Appl., 24:5 (2017), e2099. · Zbl 1424.65022 |
| [41] | 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. · Zbl 1325.65054 |
| [42] | A.J. Wathen. Preconditioning. Acta Numer., 24 (2015), 329-376. · Zbl 1316.65039 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
