Towards Faster Feasible Matrix Multiplication by Trilinear Aggregation

Matrix multiplication is a fundamental kernel in high-performance computing. Many algorithms for fast matrix multiplication can only be applied to enormous matrices (n > 10100) and thus cannot be used in practice. Of all algorithms applicable to feasible input sizes, Pan’s O(n2.773372) algorithm (1982) is asymptotically the fastest. We obtain an O(n2.773203) algorithm applicable to the same input sizes as Pan’s algorithm. This algorithm is the fastest matrix multiplication algorithm with a base case smaller than 1000. Further, our method obtains the best asymptotic complexity for many small base cases, starting at n0 = 28. We also obtain better exponents (e.g., O(n2.773177)) for larger base cases. To construct our algorithm, we use the trilinear aggregation method. We identify parts of the algorithm that are equivalent to matrix multiplication with smaller base cases, 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 algorithm by finding a sparse decomposition and reducing the leading coefficient. These algorithms have the potential to outperform existing fast matrix multiplication algorithms in practice.