Skip to main content
Open Access Publications from the University of California

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


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(N log2 N) computation and O(N) memory complexity when applied to an N × N sparse system arising from 3D high-frequency Helmholtz and Maxwell problems.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View