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

07/01/2020

∙

by   Yang Liu, et al.

∙

0

∙

share

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