Interpolative Butterfly Factorization

Abstract

This paper introduces the interpolative butterfly factorization for nearly optimal implementation of several transforms in harmonic analysis, when their explicit formulas satisfy certain analytic properties and the matrix representations of these transforms satisfy a complementary low-rank property. A preliminary interpolative butterfly factorization is constructed based on interpolative low-rank approximations of the complementary low-rank matrix. A novel sweeping matrix compression technique further compresses the preliminary interpolative butterfly factorization via a sequence of structure-preserving low-rank approximations. The sweeping procedure propagates the low-rank property among neighboring matrix factors to compress dense submatrices in the preliminary butterfly factorization to obtain an optimal one in the butterfly scheme. For an $N\times N$ matrix, it takes $O(N\log N)$ operations and complexity to construct the factorization as a product of $O(\log N)$ sparse matrices, each with $O(N)$ nonzero entries. Hence, it can be applied rapidly in $O(N\log N)$ operations. Numerical results are provided to demonstrate the effectiveness of this algorithm.

References in corpus (1)

• P3DFFT: a framework for parallel computations of Fourier transforms in three dimensions

Cited by in corpus (13)

• Warped Convolutions: Efficient Invariance to Spatial Transformations
• A Butterfly-Accelerated Volume Integral Equation Solver for Broad Permittivity and Large-Scale Electromagnetic Analysis
• A Unified Framework for Oscillatory Integral Transform: When to use NUFFT or Butterfly Factorization?
• Butterfly-Net: Optimal Function Representation Based on Convolutional Neural Networks
• An algorithm for the numerical evaluation of the associated Legendre functions that runs in time independent of degree and order
• Butterfly factorization via randomized matrix-vector multiplications
• Sparse Linear Networks with a Fixed Butterfly Structure: Theory and Practice
• Multidimensional Phase Recovery and Interpolative Decomposition Butterfly Factorization
• Butterfly-Net2: Simplified Butterfly-Net and Fourier Transform Initialization
• Asymmetric Multiresolution Matrix Factorization
• Rapid Application of the Spherical Harmonic Transform via Interpolative Decomposition Butterfly Factorization
• Sparse Approximate Multifrontal Factorization with Butterfly Compression for High Frequency Wave Equations
• Approximate inversion of discrete Fourier integral operators