Fast Computation of Fourier Integral Operators

DOI10.1137/060671139zbMATH Open1157.65522arXivmath/0610051OpenAlexW2063399239MaRDI QIDQ3545254FDOQ3545254

Authors: Emmanuel J. Candès, Laurent Demanet, Lexing Ying 

Publication date: 10 December 2008

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Abstract: We introduce a general purpose algorithm for rapidly computing certain types of oscillatory integrals which frequently arise in problems connected to wave propagation and general hyperbolic equations. The problem is to evaluate numerically a so-called Fourier integral operator (FIO) of the form $int{e}^{2piiPhi(x,xi)}a(x,xi)hatf(xi)mathrmdxi$ at points given on a Cartesian grid. Here, $xi$ is a frequency variable, $hatf(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 at high frequencies. Because an 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}logN)$ operations, and as low as $O(sqrtN)$ in storage space. 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^{2piiPhi(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 that the separation rank of the residual kernel is emph{provably independent of the problem size}. Several numerical examples demonstrate the efficiency and accuracy of the proposed methodology. We also discuss the potential of our ideas for various applications such as reflection seismology.

Full work available at URL: https://arxiv.org/abs/math/0610051

Recommendations

• A fast butterfly algorithm for the computation of Fourier integral operators
• scientific article; zbMATH DE number 1877173
• Computing Fourier integral operators with caustics
• Multiscale discrete approximation of Fourier integral operators
• A multiscale butterfly algorithm for multidimensional Fourier integral operators

zbMATH Keywords

computational complexitymatrix approximationnumerical examplesrandomized algorithmsFourier integral operatorsoscillatory integralswave propagationnonuniform fast Fourier transformseparated representationgeneralized Radon transformreflection seismologyoperator compressioncurvilinear tomography

Mathematics Subject Classification ID

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

Cited In (42)

• Wigner analysis of Fourier integral operators with symbols in the Shubin classes
• A unified framework for oscillatory integral transforms: when to use NUFFT or butterfly factorization?
• Fast Multiscale Gaussian Beam Method for Three-Dimensional Elastic Wave Equations in Bounded Domains
• Discrete symbol calculus
• Efficient representation and accurate evaluation of oscillatory integrals and functions
• Fast algorithms for the multi-dimensional Jacobi polynomial transform
• Title not available (Why is that?)
• Extraction of digital wavefront sets using applied harmonic analysis and deep neural networks
• An algorithm for the rapid numerical evaluation of Bessel functions of real orders and arguments
• Fast Computation of Multidimensional Fourier Integrals
• A multiscale butterfly algorithm for multidimensional Fourier integral operators
• On the approximation of functions by tanh neural networks
• Deep learning for inverse problems. Abstracts from the workshop held March 7--13, 2021 (hybrid meeting)
• Approximate inversion of discrete Fourier integral operators
• Wave Phenomena
• Regularity and multi-scale discretization of the solution construction of hyperbolic evolution equations with limited smoothness
• Fast computation of Toeplitz forms and some multidimensional integrals
• Optimization methods for synthetic aperture radar imaging
• Krylov subspace spectral methods for the time-dependent Schrödinger equation with non-smooth potentials
• Methods for fast computation of integral transforms
• Nonlinear approximation of functions in two dimensions by sums of wave packets
• A randomized method for one-step extrapolation in reverse time migration
• Resolution analysis of inverting the generalized Radon transform from discrete data in \(\mathbb{R}^3\)
• Multidimensional butterfly factorization
• Multiscale discrete approximations of Fourier integral operators associated with canonical transformations and caustics
• Computing Fourier integral operators with caustics
• Fast and accurate propagation of coherent light
• Fast wave computation via Fourier integral operators
• Quasi-Banach algebras and Wiener properties for pseudodifferential and generalized metaplectic operators
• Resolution analysis of inverting the generalized \(N\)-dimensional Radon transform in \(\mathbb{R}^n\) from discrete data
• Synthetic Aperture Inversion for Statistically Nonstationary Target and Clutter Scenes
• Title not available (Why is that?)
• Composition and differentiation operators and fast approximation
• Fast and approximate computation of Laplace and Fourier transforms
• Simultaneous approximation of a smooth function and its derivatives by deep neural networks with piecewise-polynomial activations
• Solving inverse problems using data-driven models
• Butterfly-net: optimal function representation based on convolutional neural networks
• Interpolative butterfly factorization
• Sparsity of Gabor representation of Schrödinger propagators
• How exponentially ill-conditioned are contiguous submatrices of the Fourier matrix?
• Multiscale discrete approximation of Fourier integral operators
• A fast butterfly algorithm for the computation of Fourier integral operators

This page was built for publication: Fast Computation of Fourier Integral Operators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3545254)