Butterfly factorization via randomized matrix-vector multiplications

DOI10.1137/20M1315853MaRDI QIDQ5857731zbMATH OpenOpenAlexWikidataFDO

Authors Yang Liu, Xin Xing, Han Guo, Eric Michielssen, Pieter Ghysels, Xiaoye S. Li

Publication date 7 April 2021

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

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

zbMATH Keywords

butterfly factorizationdirect solverfast algorithmnumerical linear algebrarandomized algorithm

Mathematics Subject Classification ID

Factorization of matrices (15A23) Computational methods for sparse matrices (65F50) Numerical methods for integral transforms (65R10) Numerical methods for integral equations (65R20)

Abstract: This paper presents an adaptive randomized algorithm for computing the butterfly factorization of a $mimesn$ matrix with $mapproxn$ provided that both the matrix and its transpose can be rapidly applied to arbitrary vectors. The resulting factorization is composed of $O(logn)$ sparse factors, each containing $O(n)$ nonzero entries. The factorization can be attained using $O(n^{3/2}logn)$ computation and $O(nlogn)$ memory resources. The proposed algorithm applies to matrices with strong and weak admissibility conditions arising from surface integral equation solvers with a rigorous error bound, and is implemented in parallel.

Recommendations

• Butterfly factorization
• Interpolative Decomposition Butterfly Factorization
• Interpolative butterfly factorization
• Multidimensional butterfly factorization
• A parallel butterfly algorithm

Cites work

• A fast butterfly algorithm for the computation of Fourier integral operators
• A fast direct solver for boundary integral equations in two dimensions
• A fast direct solver for scattering problems involving elongated structures
• A Fast Solver for HSS Representations via Sparse Matrices
• A hierarchical butterfly LU preconditioner for two-dimensional electromagnetic scattering problems involving open surfaces
• A multiscale butterfly algorithm for multidimensional Fourier integral operators
• A parallel butterfly algorithm
• A unified framework for oscillatory integral transforms: when to use NUFFT or butterfly factorization?
• An algorithm for the rapid evaluation of special function transforms
• An efficient and highly accurate solver for multi-body acoustic scattering problems involving rotationally symmetric scatterers
• Approximate Separability of the Green's Function of the Helmholtz Equation in the High Frequency Limit
• Butterfly factorization
• Construction and arithmetics of \(\mathcal H\)-matrices
• 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
• Interpolative butterfly factorization
• Interpolative Decomposition Butterfly Factorization
• Multidimensional butterfly factorization
• Multilevel Adaptive Cross Approximation (MLACA)
• Randomized algorithms for the low-rank approximation of matrices
• Robust and accurate stopping criteria for adaptive randomized sampling in matrix-free hierarchically semiseparable construction
• Sparse Fourier Transform via Butterfly Algorithm

Cited in

(21)

• Multidimensional butterfly factorization
• On spectral and numerical properties of random butterfly matrices
• Efficient Construction of an HSS Preconditioner for Symmetric Positive Definite $\mathcal{H}^2$ Matrices
• Sparse approximate multifrontal factorization with butterfly compression for high-frequency wave equations
• Interpolative Decomposition Butterfly Factorization
• 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
• A parallel butterfly algorithm
• Interpolative butterfly factorization
• 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
• Hadamard integrators for wave equations in time and frequency domain: Eulerian formulations via butterfly algorithms
• Butterfly factorization with error guarantees
• A linear-complexity tensor butterfly algorithm for compressing high-dimensional oscillatory integral operators
• Frontal slice approaches for tensor linear systems
• Quasi-optimal hierarchically semi-separable matrix approximation
• Well-conditioned Electric Field Surface Integral Equations using Reflective Generalized Sources
• A recursive butterfly factorization with optimality guarantees
• Operator learning for hyperbolic PDEs

This page was built for publication: Butterfly factorization via randomized matrix-vector multiplications

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