# Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations

arXiv: https://arxiv.org/abs/1903.05895 · HTML: https://mlsanity.com/paper/1903.05895/

## Key facts

- Cited by 76 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Mar 2019.

## Built on by (most cited first, 30 of 76)

- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Hyena Hierarchy: Towards Larger Convolutional Language Models](https://mlsanity.com/paper/2302.10866/) (2023)
- [Sparse VideoGen: Accelerating Video Diffusion Transformers with Spatial-Temporal Sparsity](https://mlsanity.com/paper/2502.01776/) (2025)
- [Scatterbrain: Unifying Sparse and Low-rank Attention Approximation](https://mlsanity.com/paper/2110.15343/) (2021)
- [Parameter-Efficient Orthogonal Finetuning via Butterfly Factorization](https://mlsanity.com/paper/2311.06243/) (2023)
- [Monarch: Expressive Structured Matrices for Efficient and Accurate Training](https://mlsanity.com/paper/2204.00595/) (2022)
- [Learning to Grow Pretrained Models for Efficient Transformer Training](https://mlsanity.com/paper/2303.00980/) (2023)
- [Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models](https://mlsanity.com/paper/2112.00029/) (2021)
- [Simple Hardware-Efficient Long Convolutions for Sequence Modeling](https://mlsanity.com/paper/2302.06646/) (2023)
- [Mixture-of-Subspaces in Low-Rank Adaptation](https://mlsanity.com/paper/2406.11909/) (2024)
- [Hydra: Bidirectional State Space Models Through Generalized Matrix Mixers](https://mlsanity.com/paper/2407.09941/) (2024)
- [Log-Linear Attention](https://mlsanity.com/paper/2506.04761/) (2025)
- [FlashFFTConv: Efficient Convolutions for Long Sequences with Tensor Cores](https://mlsanity.com/paper/2311.05908/) (2023)
- [Adaptable Butterfly Accelerator for Attention-based NNs via Hardware and Algorithm Co-design](https://mlsanity.com/paper/2209.09570/) (2022)
- [The Efficiency Spectrum of Large Language Models: An Algorithmic Survey](https://mlsanity.com/paper/2312.00678/) (2023)
- [Rethinking Neural Operations for Diverse Tasks](https://mlsanity.com/paper/2103.15798/) (2021)
- [Memory Caching: RNNs with Growing Memory](https://mlsanity.com/paper/2602.24281/) (2026)
- [Learning quantum data with the quantum Earth Mover's distance](https://mlsanity.com/paper/2101.03037/) (2021)
- [Searching for Efficient Linear Layers over a Continuous Space of Structured Matrices](https://mlsanity.com/paper/2410.02117/) (2024)
- [ButterflyFlow: Building Invertible Layers with Butterfly Matrices](https://mlsanity.com/paper/2209.13774/) (2022)
- [ButterflyQuant: Ultra-low-bit LLM Quantization through Learnable Orthogonal Butterfly Transforms](https://mlsanity.com/paper/2509.09679/) (2025)
- [Simplex Random Features](https://mlsanity.com/paper/2301.13856/) (2023)
- [Position: Curvature Matrices Should Be Democratized via Linear Operators](https://mlsanity.com/paper/2501.19183/) (2025)
- [Reparameterized LLM Training via Orthogonal Equivalence Transformation](https://mlsanity.com/paper/2506.08001/) (2025)
- [Scaling Probabilistic Circuits via Monarch Matrices](https://mlsanity.com/paper/2506.12383/) (2025)
- [Deformable Butterfly: A Highly Structured and Sparse Linear Transform](https://mlsanity.com/paper/2203.13556/) (2022)
- [CoLA: Exploiting Compositional Structure for Automatic and Efficient Numerical Linear Algebra](https://mlsanity.com/paper/2309.03060/) (2023)
- [Symmetry-Based Structured Matrices for Efficient Approximately Equivariant Networks](https://mlsanity.com/paper/2409.11772/) (2024)
- [Training Energy-Based Normalizing Flow with Score-Matching Objectives](https://mlsanity.com/paper/2305.15267/) (2023)
- [SWAT: Scalable and Efficient Window Attention-based Transformers Acceleration on FPGAs](https://mlsanity.com/paper/2405.17025/) (2024)

## Abstract (arXiv)

Fast linear transforms are ubiquitous in machine learning, including the discrete Fourier transform, discrete cosine transform, and other structured transformations such as convolutions. All of these transforms can be represented by dense matrix-vector multiplication, yet each has a specialized and highly efficient (subquadratic) algorithm. We ask to what extent hand-crafting these algorithms and implementations is necessary, what structural priors they encode, and how much knowledge is required to automatically learn a fast algorithm for a provided structured transform. Motivated by a characterization of fast matrix-vector multiplication as products of sparse matrices, we introduce a parameterization of divide-and-conquer methods that is capable of representing a large class of transforms. This generic formulation can automatically learn an efficient algorithm for many important transforms; for example, it recovers the O(N log N) Cooley-Tukey FFT algorithm to machine precision, for dimensions N up to 1024. Furthermore, our method can be incorporated as a lightweight replacement of generic matrices in machine learning pipelines to learn efficient and compressible transformations. On a standard task of compressing a single hidden-layer network, our method exceeds the classification accuracy of unconstrained matrices on CIFAR-10 by 3.9 points -- the first time a structured approach has done so -- with 4X faster inference speed and 40X fewer parameters.