A Unified Framework for Oscillatory Integral Transform: When to use NUFFT or Butterfly Factorization?

Abstract

This paper concerns the fast evaluation of the matvec $g=Kf$ for $K\in {\mathbb{C}}^{N\times N}$, which is the discretization of the oscillatory integral transform $g(x)=\int K(x,\xi )f(\xi )d\xi$ with a kernel function $K(x,\xi )=\alpha (x,\xi )e^{2\pi ı\Phi (x,\xi )}$, where $\alpha (x,\xi )$ is a smooth amplitude function, and $\Phi (x,\xi )$ is a piecewise smooth phase function with $O(1)$ discontinuous points in $x$ and $\xi$. A unified framework is proposed to compute $Kf$ with $O(N\log N)$ time and memory complexity via the non-uniform fast Fourier transform (NUFFT) or the butterfly factorization (BF), together with an $O(N)$ fast algorithm to determine whether NUFFT or BF is more suitable. This framework works for two cases: 1) explicit formulas for the amplitude and phase functions are known, 2) only indirect access of the amplitude and phase functions are available. Especially in the case of indirect access, our main contributions are: 1) an $O(N\log N)$ algorithm for recovering the amplitude and phase functions is proposed based on a new low-rank matrix recovery algorithm, 2) a new stable and nearly optimal BF with amplitude and phase functions in a form of a low-rank factorization (IBF-MAT) is proposed to evaluate the matvec $Kf$. Numerical results are provided to demonstrate the effectiveness of the proposed framework.

References in corpus (7)

• A Butterfly-Based Direct Integral Equation Solver Using Hierarchical LU Factorization for Analyzing Scattering from Electrically Large Conducting Objects
• A HSS Matrix-Inspired Butterfly-Based Direct Solver for Analyzing Scattering from Two-dimensional Objects
• Interpolative Butterfly Factorization
• Lecture Notes on Randomized Linear Algebra
• An algorithm for the numerical evaluation of the associated Legendre functions that runs in time independent of degree and order
• Pseudodifferential multi-product representation of the solution operator of a parabolic equation
• Fast Algorithms for the Multi-dimensional Jacobi Polynomial Transform

Cited by in corpus (7)

• A Hierarchical Butterfly LU Preconditioner for Two-Dimensional Electromagnetic Scattering Problems Involving Open Surfaces
• Butterfly factorization via randomized matrix-vector multiplications
• Multidimensional Phase Recovery and Interpolative Decomposition Butterfly Factorization
• Rapid Application of the Spherical Harmonic Transform via Interpolative Decomposition Butterfly Factorization
• Fast Algorithms for the Multi-dimensional Jacobi Polynomial Transform
• Interpolative Decomposition Butterfly Factorization
• Sparse Approximate Multifrontal Factorization with Butterfly Compression for High Frequency Wave Equations