Sparse approximate multifrontal factorization with composite compression methods
Document Type
Article
Publication Date
8-1-2023
Publisher
Association for Computing Machinery
Abstract
This paper presents a fast and approximate multifrontal solver for large sparse linear systems. In a recent paper by Liu et al. we showed the efficiency of a multifrontal solver leveraging the butterfly algorithm and its hierarchical matrix extension, Hierarchically Off-Diagonal Butterfly compression (HODBF), 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 in order to scale to larger problem sizes, in this paper, we develop a composite multifrontal solver that employs the HODBF format for large sized fronts, a reduced-memory version of the non-hierarchical 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 percent while ensuring the same execution time. The code is made publicly available in github.
Recommended Citation
Claus, L., Ghysels, P., Liu, Y., Nhan, T. A., Thirumalaisamy, R., Bhalla, A. P. S., & Li, S. (2023). Sparse approximate multifrontal factorization with composite compression methods. ACM Transactions on Mathematical Software. https://doi.org/10.1145/3611662
