Distributed O(N) Linear Solver for Dense Symmetric Hierarchical Semi-Separable Matrices
Distributed O(N) Linear Solver for Dense Symmetric Hierarchical Semi-Separable Matrices
复制标题
密集对称分层半可分离矩阵的分布式 O(N) 线性求解器
DOI：
10.1109/mcsoc.2019.00008
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Biros, George
中科院分区：
文献类型：
--
作者：
Yu, Chenhan D.;Reiz, Severin;Biros, George
提出了一种求解对称正定矩阵近似分层分解的分布式存储算法。我们的方法基于分布式内存GOFMM，这是一种出现在SC 18（doi：10.1109/SC.2018.00018）中的算法。GOFMM构造了一个任意SPD矩阵的分层矩阵近似，通过创建非对角块的低秩近似来压缩矩阵。GOFMM方法不能保证对任意SPD矩阵都能成功。(This类似于SVD;不是每个矩阵都有一个好的低秩近似。但对于许多SPD矩阵，GOFMM确实支持压缩，从而实现快速矩阵向量乘法，可以达到N logN时间-而不是密集矩阵所需的N2。GOFMM支持共享和分布式内存并行。在本文中，我们建立了一个近似的“ULV”分解的基础上层次半可分离（HSS）压缩的GOFMM。这个分解需要O（N）的工作（给定压缩矩阵）和O（N=p）+ O（log p）的时间在p个MPI进程上（假设超立方体拓扑）。时间复杂度为O（N logN）。我们提出的因式分解算法，讨论其复杂性，并提出弱和强缩放的结果，我们的算法的“因式分解”和“解决”阶段。我们还讨论了性能的不精确的ULV分解作为一个预条件的几个示例性的大型稠密线性系统。在我们最大的一次运行中，我们能够在不到一秒的时间内分解一个67 M × 67 M的矩阵;并在不到十分之一秒的时间内解决一个具有64个右侧的系统。这次运行是在德克萨斯州高级计算中心Stampede 2系统的SKX分区上的6，144个英特尔“Skylake”核心上进行的。
We present a distributed memory algorithm for the approximate hierarchical factorization of symmetric positive definite (SPD) matrices. Our method is based on the distributed memory GOFMM, an algorithm that appeared in SC18 (doi:10.1109/SC.2018.00018). GOFMM constructs a hierarchical matrix approximation of an arbitrary SPD matrix that compresses the matrix by creating low-rank approximations of the off-diagonal blocks. GOFMM method has no guarantees of success for arbitrary SPD matrices. (This is similar to the SVD; not every matrix admits a good low-rank approximation.) But for many SPD matrices, GOFMM does enable compression that results in fast matrix-vector multiplication that can reach N logN time—as opposed to N2 required for a dense matrix. GOFMM supports shared and distributed memory parallelism. In this paper, we build an approximate "ULV" factorization based on the Hierarchically Semi-Separable (HSS) compression of the GOFMM. This factorization requires O(N) work (given the compressed matrix) and O(N=p) + O(log p) time on p MPI processes (assuming a hypercube topology). The previous state-of-the-art required O(N logN) work. We present the factorization algorithm, discuss its complexity, and present weak and strong scaling results for the "factorization" and "solve" phases of our algorithm. We also discuss the performance of the inexact ULV factorization as a preconditioner for a few exemplary large dense linear systems. In our largest run, we were able to factorize a 67M-by-67M matrix in less than one second; and solve a system with 64 right-hand sides in less than one-tenth of a second. This run was on 6,144 Intel "Skylake" cores on the SKX partition of the Stampede2 system at the Texas Advanced Computing Center.
登录
查看更多内容
用于压缩密集 SPD 矩阵的几何忽略 FMM
DOI：
--
发表时间：
2017
期刊：
International Conference for High Performance Computing, Networking, Storage and Analysis
影响因子：
--
作者：
Chenhan D. Yu;James Levitt;Severin Reiz;G. Biros
通讯作者：
G. Biros
ASKIT：用于高维核求和的高效并行库
影响因子：
3.1
作者：
William B. March;Bo Xiao;Chenhan D. Yu;G. Biros
通讯作者：
G. Biros
利用数据稀疏性进行大规模矩阵计算
DOI：
--
发表时间：
2018
期刊：
European Conference on Parallel Processing
影响因子：
--
作者：
Kadir Akbudak;H. Ltaief;A. Mikhalev;A. Charara;Aniello Esposito;D. Keyes
通讯作者：
D. Keyes
密集 SPD 矩阵的分布式内存分层压缩
DOI：
10.1109/sc.2018.00018
发表时间：
2018
期刊：
SC18: International Conference for High Performance Computing, Networking, Storage and Analysis
影响因子：
--
作者：
Chenhan D. Yu;Severin Reiz;G. Biros
通讯作者：
G. Biros
核矩阵的 N log N 并行快速直接求解器
DOI：
--
发表时间：
2017
期刊：
IEEE International Parallel and Distributed Processing Symposium
影响因子：
--
作者：
Chenhan D. Yu;William B. March;G. Biros
通讯作者：
G. Biros