Fast Computation of Fourier Integral Operators
Authors:
- Emmanuel CandèsECEmmanuel Candès
- Laurent DemanetLDLaurent Demanet
- Lexing YingLYLexing Ying
- 1 January 2007
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific Computing
- Vol. 29 (6) , 2464-2493
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 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.
Keywords
All Related Versions
This publication has 35 references indexed in Scilit:
- The curvelet representation of wave propagators is optimally sparseCommunications on Pure and Applied Mathematics, 2005
- Curvelets and Fourier Integral OperatorsComptes Rendus Mathematique, 2003
- Efficient Computation of Oscillatory Integrals via Adaptive Multiscale Local Fourier BasesApplied and Computational Harmonic Analysis, 2000
- Rapid Computation of the Discrete Fourier TransformSIAM Journal on Scientific Computing, 1996
- Computation of Pseudo-Differential OperatorsSIAM Journal on Scientific Computing, 1996
- On the Fast Fourier Transform of Functions with SingularitiesApplied and Computational Harmonic Analysis, 1995
- Fast Numerical Computations of Oscillatory Integrals Related to Acoustic Scattering, IApplied and Computational Harmonic Analysis, 1993
- Fast wavelet transforms and numerical algorithms ICommunications on Pure and Applied Mathematics, 1991
- Imaging of discontinuities in the inverse scattering problem by inversion of a causal generalized Radon transformJournal of Mathematical Physics, 1985
- The inversion problem and applications of the generalized radon transformCommunications on Pure and Applied Mathematics, 1984