Back to Search
Start Over
Sparse Approximate Multifrontal Factorization with Composite Compression Methods.
- Source :
-
ACM Transactions on Mathematical Software . Sep2023, Vol. 49 Issue 3, p1-28. 28p. - Publication Year :
- 2023
-
Abstract
- 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *FACTORIZATION
*LINEAR systems
*WAVE equation
*BUTTERFLIES
Subjects
Details
- Language :
- English
- ISSN :
- 00983500
- Volume :
- 49
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- ACM Transactions on Mathematical Software
- Publication Type :
- Academic Journal
- Accession number :
- 172425406
- Full Text :
- https://doi.org/10.1145/3611662