Fast Computation of Fourier Integral Operators

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

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

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 (38)

• Optimization Methods for Synthetic Aperture Radar Imaging
• 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
• 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?)
• An algorithm for the rapid numerical evaluation of Bessel functions of real orders and arguments
• Fast Computation of Multidimensional Fourier Integrals
• Resolution Analysis of Inverting the Generalized Radon Transform from Discrete Data in $\mathbb{R}^3$
• A randomized method for one‐step extrapolation in reverse time migration
• 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
• Krylov subspace spectral methods for the time-dependent Schrödinger equation with non-smooth potentials
• Methods for fast computation of integral transforms
• Butterfly-Net: Optimal Function Representation Based on Convolutional Neural Networks
• Nonlinear approximation of functions in two dimensions by sums of wave packets
• How Exponentially Ill-Conditioned Are Contiguous Submatrices of the Fourier Matrix?
• Multidimensional butterfly factorization
• Computing Fourier integral operators with caustics
• Interpolative Butterfly Factorization
• Fast wave computation via Fourier integral operators
• Quasi-Banach algebras and Wiener properties for pseudodifferential and generalized metaplectic operators
• Extraction of Digital Wavefront Sets Using Applied Harmonic Analysis and Deep Neural Networks
• 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
• A Multiscale Butterfly Algorithm for Multidimensional Fourier Integral Operators
• Sparsity of Gabor representation of Schrödinger propagators
• 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)