Fast matrix multiplication and its algebraic neighbourhood

V. Ya. Pan

Sbornik. Mathematics, Tome 208 (2017) no. 11, pp. 1661-1704

Résumé

Matrix multiplication is among the most fundamental operations of modern computations. By 1969 it was still commonly believed that the classical algorithm was optimal, although the experts already knew that this was not so. Worldwide interest in matrix multiplication instantly exploded in 1969, when Strassen decreased the exponent 3 of cubic time to $2.807$. Then everyone expected to see matrix multiplication performed in quadratic or nearly quadratic time very soon. Further progress, however, turned out to be capricious. It was at stalemate for almost a decade, then a combination of surprising techniques (completely independent of Strassen's original ones and much more advanced) enabled a new decrease of the exponent in 1978–1981 and then again in 1986, to $2.376$. By 2017 the exponent has still not passed through the barrier of $2.373$, but most disturbing was the curse of recursion — even the decrease of exponents below $2.7733$ required numerous recursive steps, and each of them squared the problem size. As a result, all algorithms supporting such exponents supersede the classical algorithm only for inputs of immense sizes, far beyond any potential interest for the user. We survey the long study of fast matrix multiplication, focusing on neglected algorithms for feasible matrix multiplication. We comment on their design, the techniques involved, implementation issues, the impact of their study on the modern theory and practice of Algebraic Computations, and perspectives for fast matrix multiplication. Bibliography: 163 titles.

Détail

Keywords: bilinear algorithms, feasible matrix multiplication
Mots-clés : matrix multiplication, tensor decomposition, exponent of matrix multiplication.