Interpolative Butterfly Factorization

DOI10.1137/16M1074941zbMath1365.65292arXiv1605.03616MaRDI QIDQ5738165

Yingzhou Li, Haizhao Yang

Publication date: 31 May 2017

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

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

zbMATH Keywords

randomized algorithmFourier integral operatorsmatrix factorizationdata-sparse matrixoperator compressionbutterfly algorithmnonuniform Fourier transform

Mathematics Subject Classification ID

Related Items (15)

Randomized numerical linear algebra: Foundations and algorithms ⋮ Approximate inversion of discrete Fourier integral operators ⋮ An algorithm for the rapid numerical evaluation of Bessel functions of real orders and arguments ⋮ An algorithm for the numerical evaluation of the associated Legendre functions that runs in time independent of degree and order ⋮ A Fast Butterfly-Compressed Hadamard–Babich Integrator for High-Frequency Helmholtz Equations in Inhomogeneous Media with Arbitrary Sources ⋮ Interpolative Decomposition Butterfly Factorization ⋮ A unified framework for oscillatory integral transforms: when to use NUFFT or butterfly factorization? ⋮ Sparse Approximate Multifrontal Factorization with Butterfly Compression for High-Frequency Wave Equations ⋮ Butterfly-Net: Optimal Function Representation Based on Convolutional Neural Networks ⋮ Rapid Application of the Spherical Harmonic Transform via Interpolative Decomposition Butterfly Factorization ⋮ Preconditioning Orbital Minimization Method for Planewave Discretization ⋮ 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 ⋮ Butterfly Factorization Via Randomized Matrix-Vector Multiplications

Uses Software

• P3DFFT

Cites Work

• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
• A fast algorithm for multilinear operators
• Fast and accurate polar Fourier transform
• MUSIC for single-snapshot spectral estimation: stability and super-resolution
• Fast algorithms for spherical harmonic expansions. III
• Multidimensional 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 Hankel transform by fast sine and cosine transforms: the Mellin connection
• Fast wave computation via Fourier integral operators
• A Butterfly Algorithm for Synthetic Aperture Radar Imaging
• A Fast Analysis-Based Discrete Hankel Transform Using Asymptotic Expansions
• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• Discrete Symbol Calculus
• P3DFFT: A Framework for Parallel Computations of Fourier Transforms in Three Dimensions
• Fast Directional Multilevel Algorithms for Oscillatory Kernels
• Fast Computation of Fourier Integral Operators
• Sparse Fourier Transform via Butterfly Algorithm
• A Fast Butterfly Algorithm for the Computation of Fourier Integral Operators
• A Modified Split-Radix FFT With Fewer Arithmetic Operations
• Accelerating the Nonuniform Fast Fourier Transform
• Computation of Pseudo-Differential Operators
• A Multiscale Butterfly Algorithm for Multidimensional Fourier Integral Operators
• Butterfly Factorization
• The Tangent FFT
• A Parallel Butterfly Algorithm
• Fast Algorithms for Spherical Harmonic Expansions

This page was built for publication: Interpolative Butterfly Factorization