Sparse approximate multifrontal factorization with composite compression methods

Document Type


Publication Date



Association for Computing Machinery


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.