# A Fast Butterfly Algorithm for the Computation of Fourier Integral Operators - Mathematics > Numerical Analysis

Abstract: This paper is concerned with the fast computation of Fourier integraloperators of the general form $\int {\R^d} e^{2\pi\i \Phix,k} fk d k$,where $k$ is a frequency variable, $\Phix,k$ is a phase function obeying astandard homogeneity condition, and $f$ is a given input. This is of interestfor such fundamental computations are connected with the problem of findingnumerical solutions to wave equations, and also frequently arise in manyapplications including reflection seismology, curvilinear tomography andothers. In two dimensions, when the input and output are sampled on $N \timesN$ Cartesian grids, a direct evaluation requires $ON^4$ operations, which isoften times prohibitively expensive.This paper introduces a novel algorithm running in $ON^2 \log N$ time, i.e. with near-optimal computational complexity, and whose overall structurefollows that of the butterfly algorithm Michielssen and Boag, IEEE TransAntennas Propagat 44 1996, 1086-1093. Underlying this algorithm is amathematical insight concerning the restriction of the kernel $e^{2\pi\i\Phix,k}$ to subsets of the time and frequency domains. Whenever thesesubsets obey a simple geometric condition, the restricted kernel hasapproximately low-rank; we propose constructing such low-rank approximationsusing a special interpolation scheme, which prefactors the oscillatorycomponent, interpolates the remaining nonoscillatory part and, lastly,remodulates the outcome. A byproduct of this scheme is that the whole algorithmis highly efficient in terms of memory requirement. Numerical resultsdemonstrate the performance and illustrate the empirical properties of thisalgorithm.

Author: Emmanuel Candes, Laurent Demanet, Lexing Ying

Source: https://arxiv.org/