A Multiscale Butterfly Algorithm for Multidimensional Fourier Integral Operators

Abstract

This paper presents an efficient multiscale butterfly algorithm for computing Fourier integral operators (FIOs) of the form $(\mathcal{L}f)(x)={\int }_{R^d}a(x,\xi )e^{2\pi ı\Phi (x,\xi )}\hat{f}(\xi )d\xi$, where $\Phi (x,\xi )$ is a phase function, $a(x,\xi )$ is an amplitude function, and $f(x)$ is a given input. The frequency domain is hierarchically decomposed into a union of Cartesian coronas. The integral kernel $a(x,\xi )e^{2\pi ı\Phi (x,\xi )}$ in each corona satisfies a special low-rank property that enables the application of a butterfly algorithm on the Cartesian phase-space grid. This leads to an algorithm with quasi-linear operation complexity and linear memory complexity. Different from previous butterfly methods for the FIOs, this new approach is simple and reduces the computational cost by avoiding extra coordinate transformations. Numerical examples in two and three dimensions are provided to demonstrate the practical advantages of the new algorithm.

References in corpus (1)

• Multi-scale discrete approximations of Fourier integral operators associated with canonical transformations and caustics

Cited by in corpus (6)

• Butterfly Factorization
• Interpolative Butterfly Factorization
• Fast hyperbolic Radon transform represented as convolutions in log-polar coordinates
• Multidimensional Butterfly Factorization
• A Unified Framework for Oscillatory Integral Transform: When to use NUFFT or Butterfly Factorization?
• Total variation-based reconstruction and phase retrieval for diffraction tomography