×

Fast computation of Fourier integral operators. (English) Zbl 1157.65522

Summary: 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) {\text{d}}\xi\) at points given on a Cartesian grid.
Here, \(\xi\) is a frequently 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 fast Fourier transform 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 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 auch as reflection seismology.

MSC:

65T50 Numerical methods for discrete and fast Fourier transforms
65Y20 Complexity and performance of numerical algorithms
86A15 Seismology (including tsunami modeling), earthquakes
44A12 Radon transform
92C55 Biomedical imaging and signal processing
PDFBibTeX XMLCite
Full Text: DOI arXiv Link