Multidimensional butterfly factorization

DOI10.1016/j.acha.2017.04.002zbMath1390.44016arXiv1509.07925OpenAlexW2228229434MaRDI QIDQ1742823

Yingzhou Li, Haizhao Yang, Lexing Ying

Publication date: 12 April 2018

Published in: Applied and Computational Harmonic Analysis (Search for Journal in Brave)

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

zbMATH Keywords

randomized algorithmFourier integral operatorsoperator compressionbutterfly algorithmdata-sparse matrix factorization

Mathematics Subject Classification ID

Numerical methods for discrete and fast Fourier transforms (65T50) Numerical methods for integral transforms (65R10) Discrete operational calculus (44A55)

Related Items

Randomized numerical linear algebra: Foundations and algorithms, Approximate inversion of discrete Fourier integral operators, Wide-Band Butterfly Network: Stable and Efficient Inversion Via Multi-Frequency Neural Networks, An analysis of a butterfly algorithm, Interpolative Decomposition Butterfly Factorization, A hierarchical butterfly LU preconditioner for two-dimensional electromagnetic scattering problems involving open surfaces, Butterfly-Net: Optimal Function Representation Based on Convolutional Neural Networks, Interpolative Butterfly Factorization, Block Basis Factorization for Scalable Kernel Evaluation, Butterfly Factorization Via Randomized Matrix-Vector Multiplications

Cites Work

• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
• A fast algorithm for multilinear operators
• Fast construction of hierarchical matrix representation from matrix-vector multiplication
• A randomized algorithm for the decomposition of matrices
• A fast randomized algorithm for the approximation of matrices
• Fast algorithms for spherical harmonic expansions. III
• An algorithm for the rapid evaluation of special function transforms
• A fast directional algorithm for high frequency acoustic scattering in two dimensions
• Fourier integral operators. I
• Randomized algorithms for the low-rank approximation of matrices
• A Fast Randomized Algorithm for Computing a Hierarchically Semiseparable Representation of a Matrix
• Fast Computation of Fourier Integral Operators
• Sparse Fourier Transform via Butterfly Algorithm
• A Fast Butterfly Algorithm for the Computation of Fourier Integral Operators
• A Multiscale Butterfly Algorithm for Multidimensional Fourier Integral Operators
• Butterfly Factorization
• A Parallel Butterfly Algorithm