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

Abstract

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.

References in corpus (11)

• MFEM: a modular finite element methods library
• A Butterfly-Based Direct Integral Equation Solver Using Hierarchical LU Factorization for Analyzing Scattering from Electrically Large Conducting Objects
• L-Sweeps: A scalable, parallel preconditioner for the high-frequency Helmholtz equation
• A HSS Matrix-Inspired Butterfly-Based Direct Solver for Analyzing Scattering from Two-dimensional Objects
• Interpolative Butterfly Factorization
• A Distributed-Memory Algorithm for Computing a Heavy-Weight Perfect Matching on Bipartite Graphs
• A Unified Framework for Oscillatory Integral Transform: When to use NUFFT or Butterfly Factorization?
• A Hierarchical Butterfly LU Preconditioner for Two-Dimensional Electromagnetic Scattering Problems Involving Open Surfaces
• Distributed-memory Hierarchical Interpolative Factorization
• Butterfly factorization via randomized matrix-vector multiplications
• Rapid Application of the Spherical Harmonic Transform via Interpolative Decomposition Butterfly Factorization