论文标题
二阶精确层次近似分解稀疏SPD矩阵
Second Order Accurate Hierarchical Approximate Factorization of Sparse SPD Matrices
论文作者
论文摘要
我们描述了一种二阶准确方法，以稀疏稀疏的对称阳性确定矩阵的分层近似值化中的偏外块。新方法产生的误差的规范取决于四范围的误差，而不是线性的，而不是线性的。对产生的两级预处理的分析表明，预处理也是二阶精度。我们将新方法纳入了最近的稀疏解剖算法中[Siam J. Matrix肛门。 Appl。，41（2020），第715-746页]，并在各种问题上进行测试。新方法将收敛所需的共轭梯度迭代数量减半，几乎相同的分解复杂性，从而改善了算法的总运行时间。我们的方法可以纳入解决稀疏线性系统的其他等级结构化方法中。
We describe a second-order accurate approach to sparsifying the off-diagonal blocks in the hierarchical approximate factorizations of sparse symmetric positive definite matrices. The norm of the error made by the new approach depends quadratically, not linearly, on the error in the low-rank approximation of the given block. The analysis of the resulting two-level preconditioner shows that the preconditioner is second-order accurate as well. We incorporate the new approach into the recent Sparsified Nested Dissection algorithm [SIAM J. Matrix Anal. Appl., 41 (2020), pp. 715-746], and test it on a wide range of problems. The new approach halves the number of Conjugate Gradient iterations needed for convergence, with almost the same factorization complexity, improving the total runtimes of the algorithm. Our approach can be incorporated into other rank-structured methods for solving sparse linear systems.
