Multidimensional Phase Recovery and Interpolative Decomposition Butterfly Factorization

Abstract

This paper focuses on the fast evaluation of the matvec $g=Kf$ for $K\in {\mathbb{C}}^{N\times N}$, which is the discretization of a multidimensional oscillatory integral transform $g(x)=\int K(x,\xi )f(\xi )d\xi$ with a kernel function $K(x,\xi )=e^{2\pi ı\Phi (x,\xi )}$, where $\Phi (x,\xi )$ is a piecewise smooth phase function with $x$ and $\xi$ in ${\mathbb{R}}^d$ for $d=2$ or $3$. A new framework is introduced to compute $Kf$ with $O(N\log N)$ time and memory complexity in the case that only indirect access to the phase function $\Phi$ is available. This framework consists of two main steps: 1) an $O(N\log N)$ algorithm for recovering the multidimensional phase function $\Phi$ from indirect access is proposed; 2) a multidimensional interpolative decomposition butterfly factorization (MIDBF) is designed to evaluate the matvec $Kf$ with an $O(N\log N)$ complexity once $\Phi$ is available. Numerical results are provided to demonstrate the effectiveness of the proposed framework.

References in corpus (10)

• A Butterfly-Based Direct Integral Equation Solver Using Hierarchical LU Factorization for Analyzing Scattering from Electrically Large Conducting Objects
• Butterfly Factorization
• A HSS Matrix-Inspired Butterfly-Based Direct Solver for Analyzing Scattering from Two-dimensional Objects
• Interpolative Butterfly Factorization
• Multidimensional Butterfly Factorization
• A Unified Framework for Oscillatory Integral Transform: When to use NUFFT or Butterfly Factorization?
• 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
• Interpolative Decomposition Butterfly Factorization
• An algorithm for the rapid numerical evaluation of Bessel functions of real orders and arguments

Cited by in corpus (2)

• Rapid Application of the Spherical Harmonic Transform via Interpolative Decomposition Butterfly Factorization
• Approximate inversion of discrete Fourier integral operators