论文标题
RCHOL：用于求解SDD线性系统的随机cholesky分解
RCHOL: Randomized Cholesky Factorization for Solving SDD Linear Systems
论文作者
论文摘要
我们引入了一种随机算法，即rChol，以构建给定拉普拉斯矩阵（又称laplacian）的近似cholesky分解。从图表的角度来看，确切的cholesky分解在消除行/列后在基础图中引入了一个集团。通过随机化，RCHOL仅使用Spielman和Kyng开发的随机抽样保留了该集团中边缘的稀疏子集。我们证明RCHOL是无崩溃的，并将其应用于用对称对角线矩阵的大型稀疏线性系统。此外，我们基于共享记忆机的嵌套解剖顺序并行化rchol。我们报告了证明RCHOL的鲁棒性和可扩展性的数值实验。例如，我们的并行代码在单个节点上最多缩放了64个线程，用于求解3D Poisson方程，并在$ 1024 \ times 1024 \ times 1024 $ grid上使用7点模具离散，这个问题具有10亿个未知数。
We introduce a randomized algorithm, namely RCHOL, to construct an approximate Cholesky factorization for a given Laplacian matrix (a.k.a., graph Laplacian). From a graph perspective, the exact Cholesky factorization introduces a clique in the underlying graph after eliminating a row/column. By randomization, RCHOL only retains a sparse subset of the edges in the clique using a random sampling developed by Spielman and Kyng. We prove RCHOL is breakdown-free and apply it to solving large sparse linear systems with symmetric diagonally dominant matrices. In addition, we parallelize RCHOL based on the nested dissection ordering for shared-memory machines. We report numerical experiments that demonstrate the robustness and the scalability of RCHOL. For example, our parallel code scaled up to 64 threads on a single node for solving the 3D Poisson equation, discretized with the 7-point stencil on a $1024\times 1024 \times 1024$ grid, a problem that has one billion unknowns.
