×

A power Schur complement low-rank correction preconditioner for general sparse linear systems. (English) Zbl 07340707

Summary: A parallel preconditioner is proposed for general large sparse linear systems that combines a power series expansion method with low-rank correction techniques. To enhance convergence, a power series expansion is added to a basic Schur complement iterative scheme by exploiting a standard matrix splitting of the Schur complement. One of the goals of the power series approach is to improve the eigenvalue separation of the preconditioner thus allowing an effective application of a low-rank correction technique. Experiments indicate that this combination can be quite robust when solving highly indefinite linear systems. The preconditioner exploits a domain-decomposition approach, and its construction starts with the use of a graph partitioner to reorder the original coefficient matrix. In this framework, unknowns corresponding to interface variables are obtained by solving a linear system whose coefficient matrix is the Schur complement. Unknowns associated with the interior variables are obtained by solving a block diagonal linear system where parallelism can be easily exploited. Numerical examples are provided to illustrate the effectiveness of the proposed preconditioner, with an emphasis on highlighting its robustness properties in the indefinite case.

MSC:

65F10 Iterative numerical methods for linear systems
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] P. Amestoy, C. Ashcraft, O. Boiteau, A. Buttari, J. Y. L’Excellent, and C. Weisbecker, Improving multifrontal methods by means of block low-rank representations, SIAM J. Sci. Comput., 37 (2015), pp. A1451-A1474. · Zbl 1314.05111
[2] P. Amestoy, A. Buttari, J. Y. L’Excellent, and T. Mary, Performance and scalability of the block low-rank multifrontal factorization on multicore architectures, ACM Trans. Math. Software, 45 (2019), pp. 1-26. · Zbl 1471.65025
[3] A. Aminfar, S. Ambikasaran, and E. Darve, A fast block low-rank dense solver with applications to finite-element matrices, J. Comput. Phys., 304 (2016), pp. 170-188. · Zbl 1349.65595
[4] M. Bebendorf, Hierarchical Matrices: A Means to Efficiently Solve Elliptic Boundary Value Problems, Lect. Notes Comput. Sci. Eng., Springer, Berlin, 2008. · Zbl 1151.65090
[5] M. Benzi and M. Tuma, A sparse approximate inverse preconditioner for nonsymmetric linear systems, SIAM J. Sci. Comput., 19 (1998), pp. 968-994. · Zbl 0930.65027
[6] S. L. Borne and L. Grasedyck, \( \mathcal{H} \)-matrix preconditioners in convection-dominated problems, SIAM J. Matrix Anal. Appl., 27 (2006), pp. 1172-1183. · Zbl 1102.65051
[7] D. Cai, E. Chow, L. Erlandson, Y. Saad, and Y. Xi, SMASH: Structured matrix approximation by separation and hierarchy, Numer. Linear Algebra Appl., 25 (2018), e2204. · Zbl 1513.65128
[8] E. Chow and Y. Saad, 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, The University of Florida sparse matrix collection, ACM Trans. Math. Software, 38 (2011) 1. · Zbl 1365.65123
[10] G. Dillon, V. Kalantzis, Y. Xi, and Y. Saad, A hierarchical low-rank Schur complement preconditioner for indefinite linear systems, SIAM J. Sci. Comput., 40 (2018), pp. A2234-A2252. · Zbl 1392.65027
[11] A. Franceschini, V. A. P. Magri, M. Ferronato, and C. Janna, A robust multilevel approximate inverse preconditioner for symmetric positive definite matrices, SIAM J. Matrix Anal. Appl., 39 (2018), pp. 123-147. · Zbl 1383.65019
[12] P. Ghysels, X. S. Li, F. H. Rouet, S. Williams, and A. Napov, An efficient multicore implementation of a novel HSS-structured multifrontal solver using randomized sampling, SIAM J. Sci. Comput., 38 (2016), pp. S358-S384. · Zbl 1352.65092
[13] A. Gillman, P. Young, and P. G. Martinsson, A direct solver with \(\mathcal{O} \)(n) complexity for integral equations on one-dimensional domains, Front. Math. China, 7 (2012), pp. 217-247. · Zbl 1262.65198
[14] M. Grote and T. Huckle, Parallel preconditioning with sparse approximate inverses, SIAM J. Sci. Comput., 18 (1997), pp. 838-853. · Zbl 0872.65031
[15] W. Hackbusch and S. Börm, \( \mathcal{H}^2\)-matrix approximation of integral operators by interpolation, Appl. Numer. Math., 43 (2002), pp. 129-143. · Zbl 1019.65103
[16] J. C. Haws, M. Benzi, and M. Tuma, Preconditioning highly indefinite and nonsymmetric matrices, SIAM J. Sci. Comput., 22 (2000), pp. 1333-1353. · Zbl 0985.65036
[17] N. J. Higham and T. Mary, A new preconditioner that exploits low-rank approximations to factorization error, SIAM J. Sci. Comput., 41 (2019), pp. A59-A82. · Zbl 1408.65013
[18] Z. Jia and W. J. Kang, A residual based sparse approximate inverse preconditioning procedure for large sparse linear systems, Numer. Linear Algebra Appl., 24 (2017), e2080. · Zbl 1449.65044
[19] G. Karypis and V. Kumar, A fast and high quality multilevel scheme for partitioning irregular graphs, SIAM J. Sci. Comput., 20 (1998), pp. 359-392. · Zbl 0915.68129
[20] R. Li, Y. Xi, and Y. Saad, Schur complement-based domain decomposition preconditioners with low-rank corrections, Numer. Linear Algebra Appl., 23 (2016), pp. 706-729. · Zbl 1399.65238
[21] X. Liu, Y. Xi, Y. Saad, and M. V. de Hoop, Solving the three-dimensional high-frequency Helmholtz equation using contour integration and polynomial preconditioning, SIAM J. Matrix Anal. Appl., 41 (2020), pp. 58-82. · Zbl 1434.65234
[22] X. Liu, J. Xia, and M. V. de Hoop, Parallel randomized and matrix-free direct solvers for large structured dense linear systems, SIAM J. Sci. Comput., 38 (2016), pp. S508-S538. · Zbl 1352.65094
[23] P. G. Martinsson and V. Rokhlin, A fast direct solver for boundary integral equations in two dimensions, J. Comput. Phys., 205 (2005), pp. 1-23. · Zbl 1078.65112
[24] G. Pichon, E. Darve, M. Faverge, P. Ramet, and J. Roman, Sparse supernodal solver using block low-rank compression: Design, performance and analysis, J. Comput. Sci., 27 (2018), pp. 255-270.
[25] Y. Saad, ILUT: A dual threshold incomplete ILU factorization, Numer. Linear Algebra Appl., 1 (1994), pp. 387-402. · Zbl 0838.65026
[26] Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, Philadelpha, PA, 2003. · Zbl 1031.65046
[27] Y. Saad and B. Suchomel, ARMS: An algebraic recursive multilevel solver for general sparse linear systems, Numer. Linear Algebra Appl., 9 (2002), pp. 359-378. · Zbl 1071.65001
[28] Y. Xi, R. Li, and Y. Saad, 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
[29] Y. Xi and Y. Saad, A rational function preconditioner for indefinite sparse linear systems, SIAM J. Sci. Comput., 39 (2017), pp. A1145-A1167. · Zbl 1368.65044
[30] Y. Xi and J. Xia, On the stability of some hierarchical rank structured matrix alogrithms, SIAM J. Matrix Anal. Appl., 37 (2016), pp. 1279-1303. · Zbl 1348.65064
[31] J. Xia, 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, Superfast multifrontal method for large structured linear systems of equations, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 1382-1411. · Zbl 1195.65031
[33] J. Xia, Y. Xi, S. Cauley, and V. Balakrishnan, Fast sparse selected inversion, SIAM J. Matrix Anal. Appl., 36 (2015), pp. 1283-1314. · Zbl 1323.65024
[34] J. Xia and Z. Xin, Effective and robust preconditioning of general spd matrices via structured incomplete factorization, SIAM J. Matrix Anal. Appl., 38 (2017), pp. 1298-1322. · Zbl 1386.15033
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.