TY - JOUR

T1 - Multicolor low-rank preconditioner for general sparse linear systems

AU - Zheng, Qingqing

AU - Xi, Yuanzhe

AU - Saad, Yousef

PY - 2020/8/1

Y1 - 2020/8/1

N2 - This article presents a multilevel parallel preconditioning technique for solving general large sparse linear systems of equations. Subdomain coloring is invoked to reorder the coefficient matrix by multicoloring the adjacency graph of the subdomains, resulting in a two-level block diagonal structure. A full binary tree structure (Formula presented.) is then built to facilitate the construction of the preconditioner. A key property that is exploited is the observation that the difference between the inverse of the original matrix and that of its block diagonal approximation is often well approximated by a low-rank matrix. This property and the block diagonal structure of the reordered matrix lead to a multicolor low-rank (MCLR) preconditioner. The construction procedure of the MCLR preconditioner follows a bottom-up traversal of the tree (Formula presented.). All irregular matrix computations, such as ILU factorizations and related triangular solves, are restricted to leaf nodes where these operations can be performed independently. Computations in nonleaf nodes only involve easy-to-optimize dense matrix operations. In order to further reduce the number of iteration of the Preconditioned Krylov subspace procedure, we combine MCLR with a few classical block-relaxation techniques. Numerical experiments on various test problems are proposed to illustrate the robustness and efficiency of the proposed approach for solving large sparse symmetric and nonsymmetric linear systems.

AB - This article presents a multilevel parallel preconditioning technique for solving general large sparse linear systems of equations. Subdomain coloring is invoked to reorder the coefficient matrix by multicoloring the adjacency graph of the subdomains, resulting in a two-level block diagonal structure. A full binary tree structure (Formula presented.) is then built to facilitate the construction of the preconditioner. A key property that is exploited is the observation that the difference between the inverse of the original matrix and that of its block diagonal approximation is often well approximated by a low-rank matrix. This property and the block diagonal structure of the reordered matrix lead to a multicolor low-rank (MCLR) preconditioner. The construction procedure of the MCLR preconditioner follows a bottom-up traversal of the tree (Formula presented.). All irregular matrix computations, such as ILU factorizations and related triangular solves, are restricted to leaf nodes where these operations can be performed independently. Computations in nonleaf nodes only involve easy-to-optimize dense matrix operations. In order to further reduce the number of iteration of the Preconditioned Krylov subspace procedure, we combine MCLR with a few classical block-relaxation techniques. Numerical experiments on various test problems are proposed to illustrate the robustness and efficiency of the proposed approach for solving large sparse symmetric and nonsymmetric linear systems.

KW - domain decomposition

KW - Krylov subspace methods

KW - low-rank approximation

KW - parallel preconditioners

KW - recursive multilevel methods

UR - http://www.scopus.com/inward/record.url?scp=85087217289&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85087217289&partnerID=8YFLogxK

U2 - 10.1002/nla.2316

DO - 10.1002/nla.2316

M3 - Article

AN - SCOPUS:85087217289

VL - 27

JO - Numerical Linear Algebra with Applications

JF - Numerical Linear Algebra with Applications

SN - 1070-5325

IS - 4

M1 - e2316

ER -