Towards Practical Fast Matrix Multiplication based on Trilinear Aggregation.

Pan's four decades old fast matrix multiplication algorithms have the lowest asymptotic complexity of all currently known algorithms applicable to matrices of feasible dimensions. However, the large coefficients in the arithmetic cost of these algorithms make them impractical. We reduce these coefficients by 90%-98%, in some cases to a value of 2, the same leading coefficient as the classical, cubic time algorithm. For this purpose, we utilize fast recursive transformations with sparsification of the linear operators of Pan's algorithms. Existing decomposition methods cannot be applied to Pan's algorithms due to their large base cases. We describe two new methods for finding such decompositions, by utilizing the underlying symmetries of the algorithms, and the linear transformations within the algorithms. With these tools, we obtain algorithms with the same asymptotic complexity as Pan's algorithms, but with small leading coefficients, often the same as that of the cubic time algorithm. In practice, these new algorithms have the potential to outperform the fastest currently known matrix multiplication algorithms on feasible sized inputs. Matched against known lower bounds, we show that our results are optimal or close to being optimal.