Multicolor low‐rank preconditioner for general sparse linear systems
Multicolor low‐rank preconditioner for general sparse linear systems
复制标题
DOI：
10.1002/nla.2316
复制
发表时间：
2020-06
影响因子：
4.3
通讯作者：
Q. Zheng;Yuanzhe Xi;Y. Saad
中科院分区：
文献类型：
--
作者：
Q. Zheng;Yuanzhe Xi;Y. Saad
本文提出了一种用于求解一般大型稀疏线性方程组的多级并行预处理技术。子域着色被调用，通过对子域的邻接图进行多着色来重新排序系数矩阵，从而产生二级块对角线结构。然后构建一个完整的二叉树结构𝒯以方便预处理器的构建。所利用的一个关键属性是观察到原始矩阵的逆矩阵与其块对角线近似的逆矩阵之间的差异通常可以通过低秩矩阵很好地近似。这一属性和重新排序矩阵的块对角结构导致了多色低秩（MCLR）预处理器。 MCLR 预处理器的构造过程遵循自下而上的树 𝒯 遍历。所有不规则矩阵计算，例如 ILU 分解和相关的三角求解，都仅限于可以独立执行这些操作的叶节点。非叶节点中的计算仅涉及易于优化的密集矩阵运算。为了进一步减少预条件 Krylov 子空间过程的迭代次数，我们将 MCLR 与一些经典的块松弛技术相结合。提出了各种测试问题的数值实验，以说明所提出的方法解决大型稀疏对称和非对称线性系统的鲁棒性和效率。
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 𝒯 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 𝒯 . 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.