Sparse Approximate Multifrontal Factorization with Composite Compression Methods
Sparse Approximate Multifrontal Factorization with Composite Compression Methods
复制标题
复合压缩方法的稀疏近似多锋分解
DOI：
10.1145/3611662
复制
发表时间：
2023
影响因子：
2.7
通讯作者：
Li, Sherry
中科院分区：
文献类型：
--
作者：
Claus, Lisa;Ghysels, Pieter;Liu, Yang;Nhan, Thái Anh;Thirumalaisamy, Ramakrishnan;Bhalla, Amneet Pal;Li, Sherry
本文提出了一种求解大型稀疏线性方程组的快速近似多波前解算器。在Liu等人最近的一项工作中，我们展示了利用蝶形算法及其分层矩阵扩展、HODBF（分层非对角蝶形）压缩来压缩大型前沿矩阵的多前沿求解器的效率。由此产生的多波前求解器可以达到准线性的计算和内存的复杂性时，应用到稀疏的线性系统所产生的空间离散的高频波动方程。为了进一步减少操作的总数，特别是因子分解内存使用量，以扩展到更大的问题大小，在本文中，我们开发了一个复合多锋求解器，采用HODBF格式的大尺寸的前，减少内存版本的非层次块低秩格式的中型前，和一个有损压缩格式的小型前。这使我们能够解决比以前大2.7倍的稀疏线性系统，并在确保相同执行时间的同时减少70%的内存消耗。该代码在GitHub上公开提供。
This article presents a fast and approximate multifrontal solver for large sparse linear systems. In a recent work by Liu et al., we showed the efficiency of a multifrontal solver leveraging the butterfly algorithm and its hierarchical matrix extension, HODBF (hierarchical off-diagonal butterfly) compression to compress large frontal matrices. The resulting multifrontal solver can attain quasi-linear computation and memory complexity when applied to sparse linear systems arising from spatial discretization of high-frequency wave equations. To further reduce the overall number of operations and especially the factorization memory usage to scale to larger problem sizes, in this article we develop a composite multifrontal solver that employs the HODBF format for large-sized fronts, a reduced-memory version of the nonhierarchical block low-rank format for medium-sized fronts, and a lossy compression format for small-sized fronts. This allows us to solve sparse linear systems of dimension up to 2.7 × larger than before and leads to a memory consumption that is reduced by 70% while ensuring the same execution time. The code is made publicly available in GitHub.
登录
查看更多内容
通过 LU 分解求解块低秩线性系统在数值上是稳定的
影响因子：
2.1
作者：
N. Higham;Théo Mary
通讯作者：
Théo Mary
DOI：
10.1137/120903476
发表时间：
2015-06
期刊：
SIAM J. Sci. Comput.
影响因子：
--
作者：
P. Amestoy;C. Ashcraft;O. Boiteau;A. Buttari;J. L’Excellent;Clément Weisbecker
通讯作者：
P. Amestoy;C. Ashcraft;O. Boiteau;A. Buttari;J. L’Excellent;Clément Weisbecker
使用 IEEE 浮点算法进行数值计算
DOI：
--
发表时间：
2001
期刊：
影响因子：
--
作者：
M. Overton
通讯作者：
M. Overton
在 MUMPS 和用于 JOREK 非线性 MHD 模拟的新 PaStiX 6.0 中测试有或没有块低阶压缩的性能
DOI：
--
发表时间：
2019
期刊：
arXiv.org
影响因子：
--
作者：
R. Nies;M. Hoelzl
通讯作者：
M. Hoelzl
影响因子：
3.1
作者：
Azad, Ariful;Buluc, Aydin;Langguth, Johannes
通讯作者：
Langguth, Johannes