Butterfly Factorization

Abstract

The paper introduces the butterfly factorization as a data-sparse approximation for the matrices that satisfy a complementary low-rank property. The factorization can be constructed efficiently if either fast algorithms for applying the matrix and its adjoint are available or the entries of the matrix can be sampled individually. For an $N\times N$ matrix, the resulting factorization is a product of $O(\log N)$ sparse matrices, each with $O(N)$ non-zero entries. Hence, it can be applied rapidly in $O(N\log N)$ operations. Numerical results are provided to demonstrate the effectiveness of the butterfly factorization and its construction algorithms.

References in corpus (1)

• A Multiscale Butterfly Algorithm for Multidimensional Fourier Integral Operators

Cited by in corpus (14)

• A Butterfly-Based Direct Integral Equation Solver Using Hierarchical LU Factorization for Analyzing Scattering from Electrically Large Conducting Objects
• Interpolative Butterfly Factorization
• Fast hyperbolic Radon transform represented as convolutions in log-polar coordinates
• A Butterfly-Accelerated Volume Integral Equation Solver for Broad Permittivity and Large-Scale Electromagnetic Analysis
• Multidimensional Butterfly Factorization
• 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
• An algorithm for the numerical evaluation of the associated Legendre functions that runs in time independent of degree and order
• Block Basis Factorization for Scalable Kernel Matrix Evaluation
• Multidimensional Phase Recovery and Interpolative Decomposition Butterfly Factorization
• A Simplified Fast Multipole Method Based on Strong Recursive Skeletonization
• Direct interpolative construction of the discrete Fourier transform as a matrix product operator
• Sparse Approximate Multifrontal Factorization with Butterfly Compression for High Frequency Wave Equations
• Approximate inversion of discrete Fourier integral operators