我一直在研究Strassen矩阵乘法算法。
《算法导论》中提到,该算法并不直观。然而我好奇是否存在严格的数学证明,以及这个算法的设计实际上涉及了什么。
我尝试在Google和stackoverflow上搜索,但所有链接都只是将Strassen的方法与标准矩阵乘法方法进行比较,或者详细解释算法的过程。
我一直在研究Strassen矩阵乘法算法。
《算法导论》中提到,该算法并不直观。然而我好奇是否存在严格的数学证明,以及这个算法的设计实际上涉及了什么。
我尝试在Google和stackoverflow上搜索,但所有链接都只是将Strassen的方法与标准矩阵乘法方法进行比较,或者详细解释算法的过程。
你应该查看源材料。在这种情况下,是由Strassen撰写的原始论文:
Strassen, Volker, Gaussian Elimination is not Optimal, Numer. Math. 13, p. 354-356, 1969
http://link.springer.com/article/10.1007%2FBF02165411?LI=true
尽管我自己没有阅读过,但我认为这个算法的复杂性会有严格的讨论和证明。$C^n\times C^n \rightarrow C^n$
的向量空间,这是一个维数为 $n^3$
的向量空间(在矩阵乘法的情况下,我们有 $n=m^2$
,例如 $2\times 2$
情况下的 $n=4$
)。秩为一的双线性映射的集合,即那些可以使用仅一个标量乘法的算法计算的映射,其维数为 $3(n-1)+1$
,秩不超过 $r$
的双线性映射的集合的维数为 $r[3(n-1)]+r$
和 $n^3$
中的最小值,对于大多数的 $n,r$
值都是如此(当 $r=7,n=4$
时可以检查这是否正确)。因此,任何 双线性映射 $C^4\times C^4\rightarrow C^4$
,几乎总是秩不超过 $7$
,并且总是可以通过秩不超过 $7$
的双线性映射进行任意精度的逼近。