A Fast Butterfly Algorithm for the Computation of Fourier Integral Operators

DOI10.1137/080734339zbMath1184.65125arXiv0809.0719OpenAlexW2038019732MaRDI QIDQ3653214

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

Publication date: 21 December 2009

Published in: Multiscale Modeling & Simulation (Search for Journal in Brave)

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

zbMATH Keywords

numerical examples low-rank approximation highly oscillatory integral separated representation multiscale computations butterfly algorithm discrete Fourier integral operator dyadic partitioning fast Fourier-type transform

Mathematics Subject Classification ID

Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42B10) Numerical methods for discrete and fast Fourier transforms (65T50)

Related Items

``Interpolated factored Green function method for accelerated solution of scattering problems ⋮ Efficient Identification of Butterfly Sparse Matrix Factorizations ⋮ Randomized numerical linear algebra: Foundations and algorithms ⋮ Total Variation-Based Reconstruction and Phase Retrieval for Diffraction Tomography ⋮ Fast wave computation via Fourier integral operators ⋮ Approximate inversion of discrete Fourier integral operators ⋮ An asymptotic Green's function method for the wave equation ⋮ Wide-Band Butterfly Network: Stable and Efficient Inversion Via Multi-Frequency Neural Networks ⋮ Babich's expansion and the fast Huygens sweeping method for the Helmholtz wave equation at high frequencies ⋮ An algorithm for the rapid numerical evaluation of Bessel functions of real orders and arguments ⋮ Multiscale Reverse-Time-Migration-Type Imaging Using the Dyadic Parabolic Decomposition of Phase Space ⋮ Fast Huygens sweeping methods for Helmholtz equations in inhomogeneous media in the high frequency regime ⋮ Compressed Absorbing Boundary Conditions via Matrix Probing ⋮ Computation of 2D Fourier transforms and diffraction integrals using Gaussian radial basis functions ⋮ Approximation of the high-frequency Helmholtz kernel by nested directional interpolation: error analysis ⋮ An analysis of a butterfly algorithm ⋮ On the approximation of functions by tanh neural networks ⋮ A pedestrian introduction to fast multipole methods ⋮ Spurious Valleys, NP-Hardness, and Tractability of Sparse Matrix Factorization with Fixed Support ⋮ A Fast Butterfly-Compressed Hadamard–Babich Integrator for High-Frequency Helmholtz Equations in Inhomogeneous Media with Arbitrary Sources ⋮ Computing Fourier integral operators with caustics ⋮ Massively parallelized interpolated factored Green function method ⋮ Resolution analysis of inverting the generalized $N$-dimensional Radon transform in $\mathbb{R}^n$ from discrete data ⋮ Interpolative Decomposition Butterfly Factorization ⋮ Unnamed Item ⋮ Resolution Analysis of Inverting the Generalized Radon Transform from Discrete Data in $\mathbb{R}^3$ ⋮ A unified framework for oscillatory integral transforms: when to use NUFFT or butterfly factorization? ⋮ Semiclassical Sampling and Discretization of Certain Linear Inverse Problems ⋮ Simultaneous approximation of a smooth function and its derivatives by deep neural networks with piecewise-polynomial activations ⋮ Fast Huygens Sweeping Methods for Time-Dependent Schrödinger Equation with Perfectly Matched Layers ⋮ Multidimensional butterfly factorization ⋮ Separability of the Kernel Function in an Integral Formulation for the Anisotropic Radiative Transfer Equation ⋮ Sparse Approximate Multifrontal Factorization with Butterfly Compression for High-Frequency Wave Equations ⋮ Butterfly-Net: Optimal Function Representation Based on Convolutional Neural Networks ⋮ Randomized estimation of spectral densities of large matrices made accurate ⋮ Interpolative Butterfly Factorization ⋮ Intrinsic Complexity and Scaling Laws: From Random Fields to Random Vectors ⋮ Fast algorithms for spherical harmonic expansions. III ⋮ The method of polarized traces for the 2D Helmholtz equation ⋮ Eulerian Geometrical Optics and Fast Huygens Sweeping Methods for Three-Dimensional Time-Harmonic High-Frequency Maxwell's Equations in Inhomogeneous Media ⋮ A second-order fast Huygens sweeping method for time-dependent Schrödinger equations with perfectly matched layers ⋮ Fast Fourier transforms of piecewise polynomials ⋮ SwitchNet: A Neural Network Model for Forward and Inverse Scattering Problems ⋮ Multidimensional phase recovery and interpolative decomposition butterfly factorization ⋮ Sparse Approximate Multifrontal Factorization with Butterfly Compression for High-Frequency Wave Equations ⋮ A pure source transfer domain decomposition method for Helmholtz equations in unbounded domain ⋮ Butterfly Factorization Via Randomized Matrix-Vector Multiplications ⋮ Wideband nested cross approximation for Helmholtz problems ⋮ A Multiscale Butterfly Algorithm for Multidimensional Fourier Integral Operators ⋮ Butterfly Factorization