Multidimensional phase recovery and interpolative decomposition butterfly factorization

DOI10.1016/j.jcp.2020.109427zbMath1436.65049arXiv1908.09376OpenAlexW3013109659MaRDI QIDQ776691

D. Kharzeev

Publication date: 13 July 2020

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

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

zbMATH Keywords

matrix completionrandomized algorithminterpolative decompositionbutterfly factorizationdata-sparse matrixoperator compression

Mathematics Subject Classification ID

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

Related Items (2)

Approximate inversion of discrete Fourier integral operators ⋮ Rapid Application of the Spherical Harmonic Transform via Interpolative Decomposition Butterfly Factorization

Uses Software

• BesselEval

Cites Work

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

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