# Sparsifying the Operators of Fast Matrix Multiplication Algorithms

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Aug 2020.

## Built on by (most cited first, 1 of 1)

- [Fast Tree-Field Integrators: From Low Displacement Rank to Topological Transformers](https://mlsanity.com/paper/2406.15881/) (2024)

## Abstract (arXiv)

Fast matrix multiplication algorithms may be useful, provided that their running time is good in practice. Particularly, the leading coefficient of their arithmetic complexity needs to be small. Many sub-cubic algorithms have large leading coefficients, rendering them impractical. Karstadt and Schwartz (SPAA'17, JACM'20) demonstrated how to reduce these coefficients by sparsifying an algorithm's bilinear operator. Unfortunately, the problem of finding optimal sparsifications is NP-Hard. We obtain three new methods to this end, and apply them to existing fast matrix multiplication algorithms, thus improving their leading coefficients. These methods have an exponential worst case running time, but run fast in practice and improve the performance of many fast matrix multiplication algorithms. Two of the methods are guaranteed to produce leading coefficients that, under some assumptions, are optimal.