CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20091026-135743447

[img]
Preview
PDF - Published Version
See Usage Policy.

596Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20091026-135743447

Abstract

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
http://dx.doi.org/10.1137/080734339DOIUNSPECIFIED
http://www.siam.org/journals/mms/7-4/73433.htmlPublisherUNSPECIFIED
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.
Funders:
Funding AgencyGrant Number
NSFUNSPECIFIED
NSFDMS-0707921
NSFDMS-0708014
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:https://resolver.caltech.edu/CaltechAUTHORS:20091026-135743447
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
Collection:CaltechAUTHORS
Deposited By: Jason Perez
Deposited On:02 Nov 2009 19:05
Last Modified:03 Oct 2019 01:12

Repository Staff Only: item control page