Sparsifying the Operators of Fast Matrix Multiplication Algorithms
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Numerical CP decomposition of some difficult tensorsJournal of Computational and Applied Mathematics, 2017
- On the arithmetic complexity of Strassen-like matrix multiplicationsJournal of Symbolic Computation, 2017
- Modular Representations of Polynomials: Hyperdense Coding and Fast Matrix MultiplicationIEEE Transactions on Information Theory, 2008
- A practical algorithm for faster matrix multiplicationNumerical Linear Algebra with Applications, 1999
- Matrix multiplication via arithmetic progressionsJournal of Symbolic Computation, 1990
- Noncommutative Bilinear Algorithms for $3 \times 3$ Matrix MultiplicationSIAM Journal on Computing, 1986
- On the Asymptotic Complexity of Matrix MultiplicationSIAM Journal on Computing, 1982
- Some Properties of Disjoint Sums of Tensors Related to Matrix MultiplicationSIAM Journal on Computing, 1982
- Partial and Total Matrix MultiplicationSIAM Journal on Computing, 1981
- O(n2.7799) complexity for n × n approximate matrix multiplicationInformation Processing Letters, 1979