  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 $\mathcal{O}(N\log^2 N)$
computation and $\mathcal{O}(N)$ memory complexity when applied to an $N\times
N$ sparse system arising from 3D high-frequency Helmholtz and Maxwell problems.
