Multidimensional phase recovery and interpolative decomposition butterfly factorization

DOI10.1016/J.JCP.2020.109427zbMATH Open1436.65049arXiv1908.09376OpenAlexW3013109659MaRDI QIDQ776691FDOQ776691

Authors: D. Kharzeev 

Publication date: 13 July 2020

Published in: Journal of Computational Physics (Search for Journal in Brave)

Abstract: This paper focuses on the fast evaluation of the matvec $g=Kf$ for $Kinmathbb{C}^{NimesN}$, which is the discretization of a multidimensional oscillatory integral transform $g(x)=intK(x,xi)f(xi)dxi$ with a kernel function $K(x,xi)=e^{2piiPhi(x,xi)}$, where $Phi(x,xi)$ is a piecewise smooth phase function with $x$ and $xi$ in $mathbb{R}^d$ for $d=2$ or $3$. A new framework is introduced to compute $Kf$ with $O(NlogN)$ time and memory complexity in the case that only indirect access to the phase function $Phi$ is available. This framework consists of two main steps: 1) an $O(NlogN)$ algorithm for recovering the multidimensional phase function $Phi$ from indirect access is proposed; 2) a multidimensional interpolative decomposition butterfly factorization (MIDBF) is designed to evaluate the matvec $Kf$ with an $O(NlogN)$ complexity once $Phi$ is available. Numerical results are provided to demonstrate the effectiveness of the proposed framework.

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

Recommendations

• A unified framework for oscillatory integral transforms: when to use NUFFT or butterfly factorization?
• A fast butterfly algorithm for the computation of Fourier integral operators
• scientific article; zbMATH DE number 1877173
• A multiscale butterfly algorithm for multidimensional Fourier integral operators
• Interpolative Decomposition Butterfly Factorization

zbMATH Keywords

interpolative decompositionmatrix completionrandomized algorithmbutterfly factorizationdata-sparse matrixoperator compression

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Numerical methods for trigonometric approximation and interpolation (65T40) Numerical methods for integral transforms (65R10)

Cites Work

• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Fast wave computation via Fourier integral operators
• Title not available (Why is that?)
• Accelerating the Nonuniform Fast Fourier Transform
• Divergence (Runge phenomenon) for least-squares polynomial approximation on an equispaced grid and mock-Chebyshev subset interpolation
• High order finite difference schemes on non-uniform meshes with good conservation properties
• A fast butterfly algorithm for the computation of Fourier integral operators
• An O(n log n) algorithm for the all-nearest-neighbors problem
• Computation of Pseudo-Differential Operators
• A fast directional algorithm for high frequency acoustic scattering in two dimensions
• An algorithm for the rapid evaluation of special function transforms
• Delaunay Triangulations in O(sort(n)) Time and More
• Fixed-radius near neighbors search algorithms for points and segments
• A high-resolution finite-difference scheme for nonuniform grids
• Parallel Delaunay triangulation in three dimensions
• An algorithm for the numerical evaluation of the associated Legendre functions that runs in time independent of degree and order
• A unified framework for oscillatory integral transforms: when to use NUFFT or butterfly factorization?
• Pseudodifferential Multi-Product Representation of the Solution Operator of a Parabolic Equation
• Numerical Differentiation by High Order Interpolation
• A nonuniform fast Fourier transform based on low rank approximation
• Butterfly factorization
• Fourier-Integral-Operator Approximation of Solutions to First-Order Hyperbolic Pseudodifferential Equations I: Convergence in Sobolev Spaces
• Interpolative butterfly factorization
• Fourier-integral-operator approximation of solutions to first-order hyperbolic pseudodifferential equations. II: Microlocal analysis

Cited In (5)

• A unified framework for oscillatory integral transforms: when to use NUFFT or butterfly factorization?
• Approximate inversion of discrete Fourier integral operators
• Rapid application of the spherical harmonic transform via interpolative decomposition butterfly factorization
• Multidimensional butterfly factorization
• Interpolative Decomposition Butterfly Factorization

Uses Software

• BesselEval

This page was built for publication: Multidimensional phase recovery and interpolative decomposition butterfly factorization

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