A Caltech Library Service

A Fast Butterfly Algorithm for the Computation of Fourier Integral Operators

Candès, Emmanuel and Demanet, Laurent and Ying, Lexing (2009) A Fast Butterfly Algorithm for the Computation of Fourier Integral Operators. Multiscale Modeling and Simulation, 7 (4). pp. 1727-1750. ISSN 1540-3459. doi:10.1137/080734339.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


This paper is concerned with the fast computation of Fourier integral operators of the general form ∫_(R^d) e^[(2πiΦ)(x,k)]f(k)dk, where k is a frequency variable, Φ(x, k) is a phase function obeying a standard homogeneity condition, and f is a given input. This is of interest, for such fundamental computations are connected with the problem of finding numerical solutions to wave equations and also frequently arise in many applications including reflection seismology, curvilinear tomography, and others. In two dimensions, when the input and output are sampled on N × N Cartesian grids, a direct evaluation requires O(N^4) operations, which is often times prohibitively expensive. This paper introduces a novel algorithm running in O(N^2 log N) time, i.e., with near-optimal computational complexity, and whose overall structure follows that of the butterfly algorithm. Underlying this algorithm is a mathematical insight concerning the restriction of the kernel e^[2πiΦ(x,k)] to subsets of the time and frequency domains. Whenever these subsets obey a simple geometric condition, the restricted kernel is approximately low-rank; we propose constructing such low-rank approximations using a special interpolation scheme, which prefactors the oscillatory component, interpolates the remaining nonoscillatory part, and finally remodulates the outcome. A byproduct of this scheme is that the whole algorithm is highly efficient in terms of memory requirement. Numerical results demonstrate the performance and illustrate the empirical properties of this algorithm.

Item Type:Article
Related URLs:
URLURL TypeDescription
Candès, Emmanuel0000-0001-9234-924X
Additional Information:© 2009 SIAM. Received September 3, 2008; accepted March 30, 2009; published June 12, 2009. EC's research was partially supported by the Waterman Award from the National Science Foundation and by ONR grant N00014-08-1-0749. LD's research was partially supported by National Science Foundation grant DMS-0707921. LY's research was partially supported by an Alfred P. Sloan Fellowship and National Science Foundation grant DMS-0708014. The authors thank the anonymous reviewers for their comments and suggestions.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-08-1-0749
Alfred P. Sloan fellowshipUNSPECIFIED
Subject Keywords:Fourier integral operators; butterfly algorithm, dyadic partitioning; Lagrange interpolation; separated representation; multiscale computations
Issue or Number:4
Classification Code:AMS subject classifications. 44A55, 65R10, 65T50
Record Number:CaltechAUTHORS:20091026-135743447
Persistent URL:
Official Citation:A Fast Butterfly Algorithm for the Computation of Fourier Integral Operators Emmanuel Candes, Laurent Demanet, and Lexing Ying, Multiscale Model. Simul. 7, 1727 (2009), DOI:10.1137/080734339
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:16481
Deposited On:02 Nov 2009 19:05
Last Modified:08 Nov 2021 23:27

Repository Staff Only: item control page