A recursive butterfly factorization with optimality guarantees

DOI10.48550/arXiv.2607.29361MaRDI QIDQ7284536arXivFDO

Authors David Persson, Paul G. Beckman, Tyler Chen, Diana Halikias, Christopher Musco

Publication date 31 July 2026

Published in arXiv

Tldr This paper introduces a recursive butterfly factorization format and a corresponding optimal approximation algorithm with guaranteed performance bounds. The method computes a quasi-optimal butterfly matrix in O(N^2) operations or uses O(sqrt(N)) matrix-vector products with high probability.

Full work available at URL https://doi.org/10.48550/arXiv.2607.29361

Mathematics Subject Classification ID

Numerical methods for low-rank matrix approximation; matrix compression (65F55) Randomized algorithms (68W20) Approximation algorithms (68W25)

arXiv classification

math.NA

Cites work

• A Butterfly-Accelerated Manifold Harmonic Transform
• A Butterfly-Based Direct Integral Equation Solver Using Hierarchical LU Factorization for Analyzing Scattering from Electrically Large Conducting Objects
• A Butterfly-Based Direct Integral Equation Solver Using Hierarchical LU Factorization for Analyzing Scattering from Electrically Large Conducting Objects
• A fast butterfly algorithm for the computation of Fourier integral operators
• A fast direct solver for boundary integral equations in two dimensions
• A Nonuniform Fast Hankel Transform
• A parallel non-uniform fast Fourier transform library based on an "exponential of semicircle" kernel
• A Tight Analysis of Hutchinson's Diagonal Estimator
• An algorithm for the rapid evaluation of special function transforms
• An estimator for the diagonal of a matrix
• Approximating Sparse Matrices and their Functions using Matrix-vector products
• Block Low-Rank Matrices with Shared Bases: Potential and Limitations of the BLR^2 Format
• Butterfly factorization
• Butterfly factorization via randomized matrix-vector multiplications
• Butterfly factorization with error guarantees
• Efficient Identification of Butterfly Sparse Matrix Factorizations
• Estimation of Sparse Jacobian Matrices
• Estimation of Sparse Jacobian Matrices and Graph Coloring Blems
• Fast and stable randomized low-rank matrix approximation
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Fixed-sparsity matrix approximation from matrix-vector products
• Interpolative butterfly factorization
• Interpolative Decomposition Butterfly Factorization
• Krylov Methods are (nearly) Optimal for Low-Rank Approximation
• Krylov methods are (nearly) optimal for low-rank approximation
• Low-rank approximation with 1/𝜖 ^1/3 matrix-vector products
• On randomized trace estimates for indefinite matrices with an application to determinants
• Projection-Cost-Preserving Sketches: Proof Strategies and Constructions
• Quasi-optimal hierarchically semi-separable matrix approximation
• Recovery of Sparse Matrices via Matrix Sketching
• Sketching Sparse Matrices, Covariances, and Graphs via Tensor Products
• Sparse approximate multifrontal factorization with butterfly compression for high-frequency wave equations
• Sparse Cholesky factorization by Kullback-Leibler minimization
• Stochastic diagonal estimation: probabilistic bounds and an improved algorithm
• The Cyclic Coloring Problem and Estimation of Sparse Hessian Matrices
• Tight query complexity lower bounds for PCA via finite sample deformed Wigner law
• Toeplitz Low-Rank Approximation with Sublinear Query Complexity

This page was built for publication: A recursive butterfly factorization with optimality guarantees

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