Lawrence Berkeley National Laboratory

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.