Butterfly Factorization with Error Guarantees
SIAM Journal on Matrix Analysis and Applications · 31.12.2025 · 46 (4) · 2253-2309
DOI: 10.1137/24m1708796 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Matrix Analysis and Applications, online erschienen am 10.10.2025. Verfasst von Quoc-Tung Le und 3 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 44 Literaturangaben. Gefördert von: Toulouse School of Economics, CIFRE, Agence Nationale de la Recherche.
Abstract (Originalsprache)
In this paper, we investigate the butterfly factorization problem, i.e., the problem of approximating a matrix by a product of sparse and structured factors. We propose a new formal mathematical description of such factors, that encompasses many different variations of butterfly factorization with different choices of the prescribed sparsity patterns. Among these choices we identify those that ensure that the factorization problem admits an optimum, thanks to a new property called “chainability”. For those supports we propose a new butterfly algorithm that yields an approximate solution to the butterfly factorization problem and that is supported by stronger theoretical guarantees than existing factorization methods. Specifically, we show that the ratio of the approximation error by the minimum value is bounded by a constant, independent of the target matrix. Reproducibility of computational results. This paper has been awarded the “SIAM Reproducibility Badge: Code and data available” as a recognition that the authors have followed reproducibility principles valued by SIMAX and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available at https://inria.hal.science/hal-04720713v1 . [Formula: see text]
Förderung
- Toulouse School of Economics
- CIFRE
- Agence Nationale de la Recherche
- Air Force Office of Scientific Research
Zitieren
APA
Le, Q., Zheng, L., Riccietti, E., & Gribonval, R. (2025). Butterfly Factorization with Error Guarantees. SIAM Journal on Matrix Analysis and Applications, 46(4), 2253-2309. https://doi.org/10.1137/24m1708796
Vancouver
Le Q, Zheng L, Riccietti E, Gribonval R. Butterfly Factorization with Error Guarantees. SIAM Journal on Matrix Analysis and Applications. 2025;46(4):2253-2309. doi:10.1137/24m1708796
BibTeX
@article{Le2025,
author = {Le, Quoc-Tung and Zheng, Léon and Riccietti, Elisa and Gribonval, Rémi},
title = {Butterfly Factorization with Error Guarantees},
journal = {SIAM Journal on Matrix Analysis and Applications},
year = {2025},
volume = {46},
number = {4},
pages = {2253--2309},
doi = {10.1137/24m1708796}
}
EUVIMED