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 http://resolver.caltech.edu/CaltechAUTHORS:20091026-135743447
- Published Version
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20091026-135743447
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.
|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.|
|Subject Keywords:||Fourier integral operators; butterfly algorithm, dyadic partitioning; Lagrange interpolation; separated representation; multiscale computations|
|Classification Code:||AMS subject classifications. 44A55, 65R10, 65T50|
|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.|
|Deposited By:||Jason Perez|
|Deposited On:||02 Nov 2009 19:05|
|Last Modified:||26 Dec 2012 11:30|
Repository Staff Only: item control page