More Web Proxy on the site http://driver.im/

research-article

A Power Schur Complement Low-Rank Correction Preconditioner for General Sparse Linear Systems

Authors:

Qingqing Zheng,

Yousef SaadAuthors Info & Claims

SIAM Journal on Matrix Analysis and Applications, Volume 42, Issue 2

Pages 659 - 682

https://doi.org/10.1137/20M1316445

Published: 01 January 2021 Publication History

Abstract

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.

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.

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

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

[4]

M. Bebendorf, Hierarchical Matrices: A Means to Efficiently Solve Elliptic Boundary Value Problems, Lect. Notes Comput. Sci. Eng., Springer, Berlin, 2008.

[5]

M. Benzi and M. Tuma, A sparse approximate inverse preconditioner for nonsymmetric linear systems, SIAM J. Sci. Comput., 19 (1998), pp. 968--994.

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

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

[8]

E. Chow and Y. Saad, Approximate inverse preconditioners via sparse-sparse iterations, SIAM J. Sci. Comput., 19 (1998), pp. 995--1023.

[9]

T. A. Davis and Y. Hu, The University of Florida sparse matrix collection, ACM Trans. Math. Software, 38 (2011) 1.

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

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

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

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

[14]

M. Grote and T. Huckle, Parallel preconditioning with sparse approximate inverses, SIAM J. Sci. Comput., 18 (1997), pp. 838--853.

[15]

W. Hackbusch and S. Börm, $\mathcal{H}^2$-matrix approximation of integral operators by interpolation, Appl. Numer. Math., 43 (2002), pp. 129--143.

[16]

J. C. Haws, M. Benzi, and M. Tuma, Preconditioning highly indefinite and nonsymmetric matrices, SIAM J. Sci. Comput., 22 (2000), pp. 1333--1353.

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

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

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

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

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

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

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

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

[26]

Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, Philadelpha, PA, 2003.

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

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

[29]

Y. Xi and Y. Saad, A rational function preconditioner for indefinite sparse linear systems, SIAM J. Sci. Comput., 39 (2017), pp. A1145--A1167.

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

[31]

J. Xia, Efficient structured multifrontal factorization for general large sparse matrices, SIAM J. Sci. Comput., 35 (2013), pp. A832--A860.

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

[33]

J. Xia, Y. Xi, S. Cauley, and V. Balakrishnan, Fast sparse selected inversion, SIAM J. Matrix Anal. Appl., 36 (2015), pp. 1283--1314.

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

Cited By

Weber SHong JCremers D(2024)Power Variable Projection for Initialization-Free Large-Scale Bundle AdjustmentComputer Vision – ECCV 202410.1007/978-3-031-72624-8_7(111-126)Online publication date: 29-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-72624-8_7
Beddig RBehrens JLe Borne S(2023)A low-rank update for relaxed Schur complement preconditioners in fluid flow problemsNumerical Algorithms10.1007/s11075-023-01548-394:4(1597-1618)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1007/s11075-023-01548-3

Index Terms

A Power Schur Complement Low-Rank Correction Preconditioner for General Sparse Linear Systems

Index terms have been assigned to the content through auto-classification.

Recommendations

A Hierarchical Low Rank Schur Complement Preconditioner for Indefinite Linear Systems

Nonsymmetric and highly indefinite linear systems can be quite difficult to solve by iterative methods. This paper combines ideas from the multilevel Schur low rank preconditioner developed by Y. Xi, R. Li, and Y. Saad [SIAM J. Matrix Anal., 37 (2016), pp. ...
Low-Rank Correction Methods for Algebraic Domain Decomposition Preconditioners

This paper presents a parallel preconditioning method for distributed sparse linear systems, based on an approximate inverse of the original matrix, that adopts a general framework of distributed sparse matrices and exploits domain ...
Constraint Schur complement preconditioners for nonsymmetric saddle point problems

We consider constraint preconditioners for block two-by-two generalized saddle point problems, this is the general nonsymmetric, nonsingular case where the (1,2) block need not equal the transposed (2,1) block and the (2,2) block may not be zero. The ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Matrix Analysis and Applications

SIAM Journal on Matrix Analysis and Applications Volume 42, Issue 2

DOI:10.1137/sjmael.42.2

Issue’s Table of Contents

© 2021, Society for Industrial and Applied Mathematics.

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 2021

Author Tags

Author Tag

65F10

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Weber SHong JCremers D(2024)Power Variable Projection for Initialization-Free Large-Scale Bundle AdjustmentComputer Vision – ECCV 202410.1007/978-3-031-72624-8_7(111-126)Online publication date: 29-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-72624-8_7
Beddig RBehrens JLe Borne S(2023)A low-rank update for relaxed Schur complement preconditioners in fluid flow problemsNumerical Algorithms10.1007/s11075-023-01548-394:4(1597-1618)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1007/s11075-023-01548-3

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents