Interpolative Decomposition Butterfly Factorization
From MaRDI portal
Abstract: This paper introduces a "kernel-independent" interpolative decomposition butterfly factorization (IDBF) as a data-sparse approximation for matrices that satisfy a complementary low-rank property. The IDBF can be constructed in operations for an matrix via hierarchical interpolative decompositions (IDs), if matrix entries can be sampled individually and each sample takes operations. The resulting factorization is a product of sparse matrices, each with non-zero entries. Hence, it can be applied to a vector rapidly in operations. IDBF is a general framework for nearly optimal fast matvec useful in a wide range of applications, e.g., special function transformation, Fourier integral operators, high-frequency wave computation. Numerical results are provided to demonstrate the effectiveness of the butterfly factorization and its construction algorithms.
Recommendations
- Interpolative butterfly factorization
- Multidimensional butterfly factorization
- Butterfly factorization
- Multidimensional phase recovery and interpolative decomposition butterfly factorization
- Butterfly factorization via randomized matrix-vector multiplications
- Rapid application of the spherical harmonic transform via interpolative decomposition butterfly factorization
- Decomposing Farkas Interpolants
- Iterative variable-Blaschke factorization
- On butterfly factorizations
- scientific article; zbMATH DE number 428959
Cites work
- A Fast Analysis-Based Discrete Hankel Transform Using Asymptotic Expansions
- 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 recursive skeletonization factorization based on strong admissibility
- A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
- A wideband fast multipole method for the Helmholtz equation in three dimensions
- An algorithm for the rapid evaluation of special function transforms
- An algorithm for the rapid numerical evaluation of Bessel functions of real orders and arguments
- Butterfly factorization
- Construction and arithmetics of \(\mathcal H\)-matrices
- CUR matrix decompositions for improved data analysis
- Data-sparse approximation by adaptive \({\mathcal H}^2\)-matrices
- Diagonal forms of translation operators for the Helmholtz equation in three dimensions
- Divergence (Runge phenomenon) for least-squares polynomial approximation on an equispaced grid and mock-Chebyshev subset interpolation
- Fast algorithms for hierarchically semiseparable matrices
- Fast algorithms for Jacobi expansions via nonoscillatory phase functions
- Fast algorithms for spherical harmonic expansions. III
- Fast construction of hierarchical matrix representation from matrix-vector multiplication
- Fast directional computation of high frequency boundary integrals via local FFTs
- Fast Directional Multilevel Algorithms for Oscillatory Kernels
- Fast directional multilevel summation for oscillatory kernels based on Chebyshev interpolation
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- scientific article; zbMATH DE number 1531793 (Why is no real title available?)
- Interpolative butterfly factorization
- Multidimensional butterfly factorization
- Multipole Translation Theory for the Three-Dimensional Laplace and Helmholtz Equations
- Numerical Differentiation by High Order Interpolation
- On the Compression of Low Rank Matrices
- On the degrees of freedom of scattered fields
- Randomized algorithms for the low-rank approximation of matrices
- Rapid solution of integral equations of scattering theory in two dimensions
- Sublinear randomized algorithms for skeleton decompositions
- The Fast Multipole Method I: Error Analysis and Asymptotic Complexity
Cited in
(15)- Multidimensional butterfly factorization
- Approximate inversion of discrete Fourier integral operators
- Sparse approximate multifrontal factorization with butterfly compression for high-frequency wave equations
- Sparse approximate multifrontal factorization with butterfly compression for high-frequency wave equations
- Rapid application of the spherical harmonic transform via interpolative decomposition butterfly factorization
- Butterfly factorization
- Interpolative butterfly factorization
- Butterfly factorization via randomized matrix-vector multiplications
- Efficient Identification of Butterfly Sparse Matrix Factorizations
- A Fast Butterfly-Compressed Hadamard–Babich Integrator for High-Frequency Helmholtz Equations in Inhomogeneous Media with Arbitrary Sources
- Sparse approximate multifrontal factorization with composite compression methods
- A linear-complexity tensor butterfly algorithm for compressing high-dimensional oscillatory integral operators
- A nonuniform fast Hankel transform
- A recursive butterfly factorization with optimality guarantees
- Multidimensional phase recovery and interpolative decomposition butterfly factorization
This page was built for publication: Interpolative Decomposition Butterfly Factorization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5112543)
