期刊
SIAM JOURNAL ON SCIENTIFIC COMPUTING
卷 38, 期 5, 页码 S358-S384出版社
SIAM PUBLICATIONS
DOI: 10.1137/15M1010117
关键词
sparse Gaussian elimination; multifrontal method; HSS matrices; parallel algorithm
资金
- Scientific Discovery through Advanced Computing (SciDAC) program
- Office of Science of the U.S. Department of Energy [DE-AC02-05CH11231]
- Lawrence Berkeley National Laboratory [DE-AC02-05CH11231]
- U.S. Department of Energy
We present a sparse linear system solver that is based on a multifrontal variant of Gaussian elimination and exploits low-rank approximation of the resulting dense frontal matrices. We use hierarchically semiseparable (HSS) matrices, which have low-rank off-diagonal blocks, to approximate the frontal matrices. For HSS matrix construction, a randomized sampling algorithm is used together with interpolative decompositions. The combination of the randomized compression with a fast ULV HSS factorization leads to a solver with lower computational complexity than the standard multifrontal method for many applications, resulting in speedups up to sevenfold for problems in our test suite. The implementation targets many-core systems by using task parallelism with dynamic runtime scheduling. Numerical experiments show performance improvements over state-of-the-art sparse direct solvers. The implementation achieves high performance and good scalability on a range of modern shared memory parallel systems, including the Intel Xeon Phi (MIC). The code is part of a software package called STRUMPACK (STRUctured Matrices PACKage), which also has a distributed memory component for dense rank-structured matrices.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据