论文标题
矩阵乘法，算术复杂性较小，复杂性
Matrix Multiplication with Less Arithmetic Complexity and IO Complexity
论文作者
论文摘要
在Strassen提出了第一个亚立方体基质乘法算法后，介绍了许多Strassen样算法。他们中的大多数具有低渐近成本的隐藏领导系数很大，因此不切实际。为了降低领先的系数，CENK和HASAN提供了一种一般方法，将领先的系数<2,2,2; 7> $ - 算法降低到$ 5 $，但增加了IO的复杂性。在2017年，Karstadt和Schwartz还将领先的系数<2,2,2; 7> $ - 算法降低到$ 5 $ $ 5 $，从而通过替代基矩阵乘法方法。同时，它们的方法在算术复杂性中降低了IO的复杂性和低阶单位。 2019年，Beniamini和Schwartz概括了替代基矩阵乘法方法，从而降低了算术复杂性但增加IO复杂性的领先系数。在本文中，我们提出了一种新的矩阵乘法算法，该算法降低了算术复杂性和IO复杂性的领先系数。我们将我们的方法应用于Strassen样算法，以提高算术复杂性和IO复杂性（与以前的结果的比较在表1和2中显示）。令人惊讶的是，我们的IO复杂性$ <3,3,3; 23> $ - 算法为$ 14n^{\ log_323} m^{ - \ frac {1} {2} {2}}} + o（n^{\ log_323}） （$ω（n^{\ log_323} m^{1- \ frac {\ log_323} {2}}）$）用于递归类似于strassen的算法。
After Strassen presented the first sub-cubic matrix multiplication algorithm, many Strassen-like algorithms are presented. Most of them with low asymptotic cost have large hidden leading coefficient which are thus impractical. To reduce the leading coefficient, Cenk and Hasan give a general approach reducing the leading coefficient of $<2,2,2;7>$-algorithm to $5$ but increasing IO complexity. In 2017, Karstadt and Schwartz also reduce the leading coefficient of $<2,2,2;7>$-algorithm to $5$ by the Alternative Basis Matrix Multiplication method. Meanwhile, their method reduces the IO complexity and low-order monomials in arithmetic complexity. In 2019, Beniamini and Schwartz generalize Alternative Basis Matrix Multiplication method reducing leading coefficient in arithmetic complexity but increasing IO complexity. In this paper, we propose a new matrix multiplication algorithm which reduces leading coefficient both in arithmetic complexity and IO complexity. We apply our method to Strassen-like algorithms improving arithmetic complexity and IO complexity (the comparison with previous results are shown in Tables 1 and 2). Surprisingly, our IO complexity of $<3,3,3;23>$-algorithm is $14n^{\log_323}M^{-\frac{1}{2}} + o(n^{\log_323})$ which breaks Ballard's IO complexity low bound ($Ω(n^{\log_323}M^{1-\frac{\log_323}{2}})$) for recursive Strassen-like algorithms.
