A robust multilevel approximate inverse preconditioner for symmetric positive definite matrices. (English) Zbl 1383.65019
Summary: The use of factorized sparse approximate inverse (FSAI) preconditioners in a standard multilevel framework for symmetric positive definite (SPD) matrices may pose a number of issues as to the definiteness of the Schur complement at each level. The present work introduces a robust multilevel approach for SPD problems based on FSAI preconditioning, which eliminates the chance of algorithmic breakdowns independently of the preconditioner sparsity. The multilevel FSAI algorithm is further enhanced by introducing descending and ascending low-rank corrections, thus giving rise to the multilevel FSAI with low-rank corrections (MFLR) preconditioner. The proposed algorithm is investigated in a number of test problems. The numerical results show that the MFLR preconditioner is a robust approach that can significantly accelerate the solver convergence rate preserving a good degree of parallelism. The possibly large set-up cost, mainly due to the computation of the eigenpairs needed by low-rank corrections, makes its use attractive in applications where the preconditioner can be recycled along a number of linear solves.
MSC:
| 65F08 | Preconditioners for iterative methods |
| 65F10 | Iterative numerical methods for linear systems |
| 65Y05 | Parallel numerical computation |
Keywords:
preconditioning; approximate inverses; parallel computing; iterative methods; Schur complement; algorithm; numerical resultReferences:
| [1] | P. Amestoy, C. Ashcraft, O. Boiteau, A. Buttari, J. Y. L’Excellent, and C. Weisbecker, {\it Improving multifrontal methods by means of block low-rank representations}, SIAM J. Sci. Comp., 37 (2015), pp. A1451-A1474. · Zbl 1314.05111 |
| [2] | M. Benzi, {\it Preconditioning techniques for large linear systems: A survey}, J. Comput. Phys., 182 (2002), pp. 418-477. · Zbl 1015.65018 |
| [3] | M. Bollhöfer, J. I. Aliaga, A. F. Mart∈, and E. S. Quintana-Ortí, ILUPACK, in {\it Encyclopedia of Parallel Computing}, D. Padua, ed., Springer, New York, 2011, pp. 917-926. |
| [4] | Y. Bu, B. Carpentieri, Z. Shen, and T. Z. Huang, {\it A hybrid recursive multilevel incomplete factorization preconditioner for solving general linear systems}, Appl. Numer. Math., 104 (2016), pp. 141-157. · Zbl 1336.65031 |
| [5] | B. Carpentieri, I. S. Duff, L. Giraud, and G. Sylvand, {\it Combining fast multipole techniques and an approximate inverse preconditioner for large electromagnetism calculations}, SIAM J. Sci. Comput., 27 (2005), pp. 774-792. · Zbl 1089.78023 |
| [6] | B. Carpentieri, J. Liao, and M. Sosonkina, {\it VBARMS: A variable block algebraic recursive multilevel solver for sparse linear systems}, J. Comp. Appl. Math., 259 (2014), pp. 164-173. · Zbl 1291.65095 |
| [7] | T. F. Chan and T. P. Mathew, {\it Domain decomposition algorithms}, Acta Numer., 3 (1994), pp. 61-143. · Zbl 0809.65112 |
| [8] | E. Chow and Y. Saad, {\it Approximate inverse preconditioners via sparse-sparse iterations}, SIAM J. Sci. Comput., 19 (1998), pp. 995-1023. · Zbl 0922.65034 |
| [9] | T. A. Davis and Y. Hu, {\it The University of Florida sparse matrix collection}, ACM Trans. Math. Software, 38 (2011), pp. 1-25. · Zbl 1365.65123 |
| [10] | H. Fang and Y. Saad, {\it A filtered Lanczos procedure for extreme and interior eigenvalue problems}, SIAM J. Sci. Comput., 34 (2012), pp. 2220-2246 · Zbl 1253.65053 |
| [11] | M. Ferronato, {\it Preconditioning for sparse linear systems at the dawn of the 21st century: History, current developments, and future perspectives}, ISRN Appl. Math., (2012), . · Zbl 1264.65037 |
| [12] | A. Franceschini, V. A. Paludetto Magri, C. Janna, and M. Ferronato, {\it Multilevel approaches for FSAI preconditioning}, Numer. Linear Algebra Appl., submitted. · Zbl 1383.65019 |
| [13] | M. W. Gee, C. M. Siefert, J. J. Hu, R. S. Tuminaro, and M. G. Sala, {\it ML 5.0 Smoothed Aggregation User’s Guide}, 2006-2649 Sandia National Laboratories, 2006. |
| [14] | W. Hackbusch, {\it A sparse matrix arithmetic based on H-matrices. Part I: Introduction to H-matrices}, Computing, 62 (1999), pp. 89-108. · Zbl 0927.65063 |
| [15] | N. Halko, P. G. Martinsson, and J. A. Tropp, {\it Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions}, SIAM Rev., 53 (2011), pp. 217-288. · Zbl 1269.65043 |
| [16] | C. Janna and M. Ferronato, {\it Adaptive pattern research for block FSAI preconditioning}, SIAM J. Sci. Comput. 33 (2011), pp. 3357-3380. · Zbl 1273.65045 |
| [17] | C. Janna, M. Ferronato, and G. Gambolati, {\it Multilevel incomplete factorizations for the iterative solution of non-linear finite element problems}, Internat. J. Numer. Methods Engrg., 80 (2009), pp. 651-670. · Zbl 1176.74184 |
| [18] | C. Janna, M. Ferronato, and G. Gambolati, {\it A Block FSAI-ILU parallel preconditioner for symmetric positive definite linear systems}, SIAM J. Sci. Comput., 32 (2010), pp. 2468-2484. · Zbl 1220.65037 |
| [19] | C. Janna, M. Ferronato, and G. Gambolati, {\it Enhanced block FSAI preconditioning using domain decomposition techniques}, SIAM J. Sci. Comput., 35 (2013), pp. S229-S249. · Zbl 1288.65034 |
| [20] | C. Janna, M. Ferronato, F. Sartoretto, and G. Gambolati, {\it FSAIPACK: A software package for high performance FSAI preconditioning}, ACM Trans. Math. Software, 41 (2015), Art. 10. · Zbl 1369.65052 |
| [21] | L. Yu. Kolotilina and A. Yu. Yeremin, {\it Factorized sparse approximate inverse preconditioning I. Theory}, SIAM J. Matrix Anal. Appl., 14 (1993), pp. 45-58. · Zbl 0767.65037 |
| [22] | Z. Li, Y. Saad, and M. Sosonkina, {\it pARMS: a parallel version of the algebraic recursive multilevel solver}, Numer. Lin. Alg. Appl., 10 (2003), pp. 485-509. · Zbl 1071.65532 |
| [23] | R. Li and Y. Saad, {\it Divide and conquer low-rank preconditioners for symmetric matrices}, SIAM J. Sci. Comput., 35 (2013), pp. A2069-A2095. · Zbl 1362.65036 |
| [24] | L. C. McInnes, B. Smith, H. Zhang, and R. T. Mills, {\it Hierarchical Krylov and nested Krylov methods for extreme-scale computing}, Parallel Comput., 40 (2014), 17-31. |
| [25] | P. Raghavan and K. Teranishi, {\it Parallel hybrid preconditioning: Incomplete factorization with selective sparse approximate inversion}, SIAM J. Sci. Comput. 32 (2010), pp. 1323-1345. · Zbl 1213.65052 |
| [26] | Y. Saad and B. Suchomel, {\it ARMS: An algebraic recursive multilevel solver for general sparse linear systems}, Numer. Linear Algebra Appl. 9 (2002), pp. 359-378. · Zbl 1071.65001 |
| [27] | J. A. Scott and M. T\ruma, {\it On positive semidefinite modification schemes for incomplete Cholesky factorization}, SIAM J. Sci. Comput., 36 (2014), pp. A609-A633. · Zbl 1298.65049 |
| [28] | S. Wang, X. S. Li, J. Xia, Y. Situ, and M. V. de Hoop, {\it Efficient scalable algorithms for solving dense linear systems with hierarchically semiseparable structures}, SIAM J. Sci. Comp., 35 (2013), pp. C519-C544. · Zbl 1285.65017 |
| [29] | Y. Xi, R. Li and Y. Saad, {\it An algebraic multilevel preconditioner with low-rank corrections for sparse symmetric matrices}, SIAM J. Matrix Anal. Appl., 37 (2016), pp. 235-259. · Zbl 1376.65036 |
| [30] | J. Xia, {\it On the complexity of some hierarchical structured matrix algorithms}, SIAM J. Matrix Anal. Appl., 33 (2012), pp. 388-410. · Zbl 1250.65050 |
| [31] | J. Xia, {\it Efficient structured multifrontal factorization for general large sparse matrices}, SIAM J. Sci. Comput., 35 (2013), pp. A832-A860. · Zbl 1266.15022 |
| [32] | J. Xia, S. Chandrasekaran, M. Gu, and X. S. Li, {\it Fast algorithms for hierarchically semiseparable matrices}, Numer. Linear Algebra Appl., 17 (2010), pp. 953-976. · Zbl 1240.65087 |
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.
