乘法简史

[FoxMe]

整数乘法的复杂度：Kolmogrov认为不会小于O(n^2), 他的学生Karatsuba的算法O(n^1.58)，目前已经证明最低复杂度为O(n log n)。

矩阵乘法：Strassen把Karatsuba的算法推广到矩阵，复杂度O(n^2.8)，目前的记录是O(n^2.37)，猜想最低复杂度是O(n^2 log n)。

Alphatensor的复杂度有没有低于O(n^2.37)？

[FoxMe]

世界上最早的整数乘法算法（O(n^2)复杂度）应该是中国最先提出的。

[FoxMe]

具体到这个不清楚，但是这些算法基本上都是构造性的。

比如Karatsuba算法O(n^1.58)：1.58 = log_2 (3)，因为他能把4次乘法降到3次。

Strassen算法O(n^2.8)：2.8 = log_2 (7)，因为他能把8次乘法降到7次。

目前实用的算法也是基于这些算法的。一个数学公式顶调参十年。

[Caravel]

具体到这个不清楚，但是这些算法基本上都是构造性的。

比如Karatsuba算法O(n^1.58)：1.58 = log_2 (3)，因为他能把4次乘法降到3次。

Strassen算法O(n^2.8)：2.8 = log_2 (7)，因为他能把8次乘法降到7次。

目前实用的算法也是基于这些算法的。一个数学公式顶调参十年。

我在想有没有库真正用这个算法
wiki

Practical implementations of Strassen's algorithm switch to standard methods of matrix multiplication for small enough submatrices, for which those algorithms are more efficient. The particular crossover point for which Strassen's algorithm is more efficient depends on the specific implementation and hardware. Earlier authors had estimated that Strassen's algorithm is faster for matrices with widths from 32 to 128 for optimized implementations.[2] However, it has been observed that this crossover point has been increasing in recent years, and a 2010 study found that even a single step of Strassen's algorithm is often not beneficial on current architectures, compared to a highly optimized traditional multiplication, until matrix sizes exceed 1000 or more, and even for matrix sizes of several thousand the benefit is typically marginal at best (around 10% or less).[3] A more recent study (2016) observed benefits for matrices as small as 512 and a benefit around 20%

[Caravel]

看了一下wiki，就是把matrix元素线性叠加一下，这种算法，传统的计算机也可以search把，alphazero为什么厉害一点？靠猜答案？

[FoxMe]

我在想有没有库真正用这个算法
wiki

Practical implementations of Strassen's algorithm switch to standard methods of matrix multiplication for small enough submatrices, for which those algorithms are more efficient. The particular crossover point for which Strassen's algorithm is more efficient depends on the specific implementation and hardware. Earlier authors had estimated that Strassen's algorithm is faster for matrices with widths from 32 to 128 for optimized implementations.[2] However, it has been observed that this crossover point has been increasing in recent years, and a 2010 study found that even a single step of Strassen's algorithm is often not beneficial on current architectures, compared to a highly optimized traditional multiplication, until matrix sizes exceed 1000 or more, and even for matrix sizes of several thousand the benefit is typically marginal at best (around 10% or less).[3] A more recent study (2016) observed benefits for matrices as small as 512 and a benefit around 20%

有：
Strassen's algorithm ... appears in several libraries, such as BLAS.[9]

[FoxMe]

看了一下wiki，就是把matrix元素线性叠加一下，这种算法，传统的计算机也可以search把，alphazero为什么厉害一点？靠猜答案？

使得，传统的计算机也可以优化。人工算主要靠凑，凭感觉。如果真的实质性的提高，应该发表在数学杂志，而不是Nature这种娱乐场所。

复杂度一般是以乘法数量来计算的（历史原因，过去乘法比加法慢），把matrix元素线性叠加，减少了乘法，代价是加法多了。但是现在的CPU乘法和加法速度没有什么区别，不知道光算乘法有没有意义。

我感觉光计乘法是错误的方向，这可能是Strassen算法的优势越来越小的原因。