Multidimensional butterfly factorization

DOI10.1016/J.ACHA.2017.04.002MaRDI QIDQ1742823zbMATH OpenOpenAlexFDO

Authors 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 integral transforms (65R10) Numerical methods for discrete and fast Fourier transforms (65T50) Discrete operational calculus (44A55)

Abstract: This paper introduces the multidimensional butterfly factorization as a data-sparse representation of multidimensional kernel matrices that satisfy the complementary low-rank property. This factorization approximates such a kernel matrix of size $NimesN$ with a product of $O(logN)$ sparse matrices, each of which contains $O(N)$ nonzero entries. We also propose efficient algorithms for constructing this factorization when either (i) a fast algorithm for applying the kernel matrix and its adjoint is available or (ii) every entry of the kernel matrix can be evaluated in $O(1)$ operations. For the kernel matrices of multidimensional Fourier integral operators, for which the complementary low-rank property is not satisfied due to a singularity at the origin, we extend this factorization by combining it with either a polar coordinate transformation or a multiscale decomposition of the integration domain to overcome the singularity. Numerical results are provided to demonstrate the efficiency of the proposed algorithms.

Recommendations

• Butterfly factorization
• Interpolative Decomposition Butterfly Factorization
• Butterfly factorization via randomized matrix-vector multiplications
• Interpolative butterfly factorization
• On butterfly factorizations
• Multidimensional phase recovery and interpolative decomposition butterfly factorization
• On metamorphosis of butterfly factorizations
• On spectral factorization in multidimensions
• Multilinear Cayley factorization
• Matrix factorizations in higher codimension

Cites work

• A fast algorithm for multilinear operators
• A fast butterfly algorithm for the computation of Fourier integral operators
• A fast directional algorithm for high frequency acoustic scattering in two dimensions
• A fast randomized algorithm for computing a hierarchically semiseparable representation of a matrix
• A fast randomized algorithm for the approximation of matrices
• A multiscale butterfly algorithm for multidimensional Fourier integral operators
• A parallel butterfly algorithm
• A randomized algorithm for the decomposition of matrices
• An algorithm for the rapid evaluation of special function transforms
• Butterfly factorization
• Fast Computation of Fourier Integral Operators
• Fast algorithms for spherical harmonic expansions. III
• Fast construction of hierarchical matrix representation from matrix-vector multiplication
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Fourier integral operators. I
• Randomized algorithms for the low-rank approximation of matrices
• Sparse Fourier Transform via Butterfly Algorithm

Cited in

(14)

• Interpolative Decomposition Butterfly Factorization
• Butterfly factorization
• Butterfly-net: optimal function representation based on convolutional neural networks
• Butterfly factorization via randomized matrix-vector multiplications
• Interpolative butterfly factorization
• Approximate inversion of discrete Fourier integral operators
• Block basis factorization for scalable kernel evaluation
• A multiscale butterfly algorithm for multidimensional Fourier integral operators
• A hierarchical butterfly LU preconditioner for two-dimensional electromagnetic scattering problems involving open surfaces
• Efficient Identification of Butterfly Sparse Matrix Factorizations
• Randomized numerical linear algebra: Foundations and algorithms
• Wide-band butterfly network: stable and efficient inversion via multi-frequency neural networks
• An analysis of a butterfly algorithm
• Approximation of high-dimensional kernel matrices by multilevel circulant matrices

This page was built for publication: Multidimensional butterfly factorization

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