Towards Faster Feasible Matrix Multiplication by Trilinear Aggregation
Preprint
Abstract
Matrix multiplication is a fundamental kernel in high performance computing. Many algorithms for fast matrix multiplication can only be applied to enormous matrices ($n>10^{100}$) and thus cannot be used in practice. Of all algorithms applicable to feasible input, Pan's $O(n^{2.773372})$ algorithm (1982) is asymptotically the fastest. We obtain an $O(n^{2.773203})$ algorithm applicable to the same input sizes as Pan's algorithm. This algorithm is the fastest matrix multiplication algorithm with base case smaller than $1000$. Further, our method obtains the best asymptotic complexity for many small base cases, starting at $n_0=28$. We also obtain better exponents for larger base cases. To construct our algorithm, we use the trilinear aggregation method. We find parts of the algorithms that are equivalent to matrix multiplication with smaller base case, and use the de Groote equivalence to replace these parts in a way that allows further optimization of our algorithms. Finally, we improve the additive complexity of our algorithms by finding a sparse decomposition and reducing the leading coefficient. These mark a fundamental step towards outperforming existing fast matrix multiplication algorithms in practice.
Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- Discovering faster matrix multiplication algorithms with reinforcement learningNature, 2022
- New ways to multiply 3 × 3-matricesJournal of Symbolic Computation, 2021
- On the arithmetic complexity of Strassen-like matrix multiplicationsJournal of Symbolic Computation, 2017
- Optimization techniques for small matrix multiplicationTheoretical Computer Science, 2011
- The aggregation and cancellation techniques as a practical tool for faster matrix multiplicationTheoretical Computer Science, 2004
- On practical algorithms for accelerated matrix multiplicationLinear Algebra and its Applications, 1992
- Trilinear aggregating with implicit canceling for a new acceleration of matrix multiplicationComputers & Mathematics with Applications, 1982
- Relations between exact and approximate bilinear algorithms. ApplicationsCalcolo, 1980
- O(n2.7799) complexity for n × n approximate matrix multiplicationInformation Processing Letters, 1979
- On varieties of optimal algorithms for the computation of bilinear mappings II. optimal algorithms for 2 × 2-matrix multiplicationTheoretical Computer Science, 1978