Abstract
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]
Funding Information
  • Toulouse School of Economics
  • CIFRE (N°2020/1643)
  • Agence Nationale de la Recherche (ANR-19-CHIA-0009, ANR-23-PEIA-0008)
  • Agence Nationale de la Recherche (ANR-19-PI3A0004)
  • Air Force Office of Scientific Research (FA8655-22-1-7012)

This publication has 29 references indexed in Scilit: