Candès, Emmanuel and Demanet, Laurent and Ying, Lexing (2007) Fast Computation of Fourier Integral Operators. SIAM Journal on Scientific Computing, 29 (6). pp. 24642493. ISSN 10648275. http://resolver.caltech.edu/CaltechAUTHORS:CANsiamjsc07

PDF
See Usage Policy. 510Kb 
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:CANsiamjsc07
Abstract
We introduce a general purpose algorithm for rapidly computing certain types of oscillatory integrals which frequently arise in problems connected to wave propagation, general hyperbolic equations, and curvilinear tomography. The problem is to numerically evaluate a socalled Fourier integral operator (FIO) of the form $\int e^{2\pi i \Phi(x,\xi)} a(x,\xi) \hat{f}(\xi) \d\xi$ at points given on a Cartesian grid. Here, $\xi$ is a frequency variable, $\hat f(\xi)$ is the Fourier transform of the input $f$, $a(x,\xi)$ is an amplitude, and $\Phi(x,\xi)$ is a phase function, which is typically as large as $\xi$; hence the integral is highly oscillatory. Because a FIO is a dense matrix, a naive matrix vector product with an input given on a Cartesian grid of size $N$ by $N$ would require $O(N^4)$ operations. This paper develops a new numerical algorithm which requires $O(N^{2.5} \log N)$ operations and as low as $O(\sqrt{N})$ in storage space (the constants in front of these estimates are small). It operates by localizing the integral over polar wedges with small angular aperture in the frequency plane. On each wedge, the algorithm factorizes the kernel $e^{2 \pi i \Phi(x,\xi)} a(x,\xi)$ into two components: (1) a diffeomorphism which is handled by means of a nonuniform FFT and (2) a residual factor which is handled by numerical separation of the spatial and frequency variables. The key to the complexity and accuracy estimates is the fact that the separation rank of the residual kernel is provably independent of the problem size. Several numerical examples demonstrate the numerical accuracy and low computational complexity of the proposed methodology. We also discuss the potential of our ideas for various applications such as reflection seismology.
Item Type:  Article 

Additional Information:  ©2007 Society for Industrial and Applied Mathematics. Reprinted with permission. Received by the editors September 30, 2006; accepted for publication (in revised form) April 9, 2007; published electronically October 17, 2007. This work was partially supported by an NSF grant CCF0515362 and a DOE grant DEFG0302ER25529. We are thankful to William Symes for stimulating discussions about Kirchhoff migration and related topics, to Mark Tygert for pointing our attention to the pseudoskeleton approximation, and to the referees for their scrutiny. 
Subject Keywords:  Fourier integral operators; generalized Radon transform; separated representation; nonuniform fast Fourier transform; matrix approximation; operator compression; randomized algorithms; reflection seismology 
Issue or Number:  6 
Record Number:  CaltechAUTHORS:CANsiamjsc07 
Persistent URL:  http://resolver.caltech.edu/CaltechAUTHORS:CANsiamjsc07 
Alternative URL:  http://dx.doi.org/10.1137/060671139 
Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided. 
ID Code:  9430 
Collection:  CaltechAUTHORS 
Deposited By:  Archive Administrator 
Deposited On:  30 Dec 2007 
Last Modified:  26 Dec 2012 09:48 
Repository Staff Only: item control page