# Sparse Approximate Multifrontal Factorization with Butterfly Compression for High Frequency Wave Equations

arXiv: https://arxiv.org/abs/2007.00202 · HTML: https://mlsanity.com/paper/2007.00202/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jul 2020.

## Built on by (most cited first, 1 of 1)

- [Efficient Tensor Completion Algorithms for Highly Oscillatory Operators](https://mlsanity.com/paper/2510.17734/) (2025)

## Abstract (arXiv)

We present a fast and approximate multifrontal solver for large-scale sparse linear systems arising from finite-difference, finite-volume or finite-element discretization of high-frequency wave equations. The proposed solver leverages the butterfly algorithm and its hierarchical matrix extension for compressing and factorizing large frontal matrices via graph-distance guided entry evaluation or randomized matrix-vector multiplication-based schemes. Complexity analysis and numerical experiments demonstrate O(Nlog2 N) computation and O(N) memory complexity when applied to an N× N sparse system arising from 3D high-frequency Helmholtz and Maxwell problems.