A Caltech Library Service

Fast Computation of Fourier Integral Operators

Candès, Emmanuel and Demanet, Laurent and Ying, Lexing (2007) Fast Computation of Fourier Integral Operators. SIAM Journal on Scientific Computing, 29 (6). pp. 2464-2493. ISSN 1064-8275.

See Usage Policy.


Use this Persistent URL to link to this item:


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 so-called 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
Related URLs:
URLURL TypeDescription
Candès, Emmanuel0000-0001-9234-924X
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 CCF-0515362 and a DOE grant DE-FG03-02ER25529. 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:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:9430
Deposited By: Archive Administrator
Deposited On:30 Dec 2007
Last Modified:09 Mar 2020 13:18

Repository Staff Only: item control page