EUVIMEDEUVIMED entdecken
Crossref

Butterfly Factorization with Error Guarantees

Quoc-Tung Le, Léon Zheng, Elisa Riccietti, Rémi Gribonval

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →