RCHOL: Randomized Cholesky Factorization for Solving SDD Linear Systems
RCHOL: Randomized Cholesky Factorization for Solving SDD Linear Systems
复制标题
RCHOL：用于求解 SDD 线性系统的随机 Cholesky 分解
DOI：
10.1137/20m1380624
复制
发表时间：
2021
影响因子：
3.1
通讯作者：
Biros, George
中科院分区：
文献类型：
--
作者：
Chen, Chao;Liang, Tianyu;Biros, George
我们引入了一个随机算法，即rchol，来构造一个给定拉普拉斯矩阵（a.k.a.，图Laplacian）。从图的角度来看，精确的Cholesky分解在消除行/列之后在底层图中引入了一个团。通过随机化，rchol使用Spielman和Kyng开发的随机采样仅保留集团中边缘的稀疏子集[私人通信，2020]。我们证明了rchol是无故障的，并将其应用于求解具有对称对角占优矩阵的大型稀疏线性方程组。此外，我们并行化rchol的基础上嵌套解剖排序共享内存的机器。我们报告的数值实验，证明了鲁棒性和可扩展性的rchol。例如，我们的并行代码在单个节点上扩展到64个线程，用于求解三维泊松方程，在1024 x 1024 x 1024网格上使用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 [private communication, 2020]. 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 three-dimensional Poisson equation, discretized with the 7-point stencil on a 1024 x 1024 x 1024 grid, a problem that hasone billionunknowns.
登录
查看更多内容
不完全 Cholesky 分解预处理器的 Max-Plus 方法
影响因子：
3.1
作者：
J. Hook;J. Scott;F. Tisseur;Jonathan D. Hogg
通讯作者：
Jonathan D. Hogg
DOI：
10.1137/1.9780898718003
发表时间：
2003-05
期刊：
--
影响因子：
--
作者：
Y. Saad
通讯作者：
Y. Saad
并行域分解求解器中的混合精度预处理器
DOI：
--
发表时间：
2008
期刊：
影响因子：
--
作者：
L. Giraud;A. Haidar;L. Watson
通讯作者：
L. Watson
使用混合精度技术提高 GMRES 方法的性能
DOI：
--
发表时间：
2020
期刊：
Smoky Mountains Computational Sciences & Engineering Conference (SMC2020
影响因子：
--
作者：
Lindquist, N.;Luszczek, P.;Dongarra, J.
通讯作者：
Dongarra, J.
可扩展的异步域分解求解器
影响因子：
3.1
作者：
Christian A. Glusa;E. Boman;E. Chow;S. Rajamanickam;D. Szyld
通讯作者：
D. Szyld