algorithm - Strassen 算法证明

Question

我一直在阅读有关矩阵乘法的 Strassen 算法。

正如 Cormen 在算法简介中提到的，该算法并不直观。但是我很想知道是否存在任何严格的算法数学证明以及算法设计的实际内容。

我尝试在 Google 和 stackoverflow 上进行搜索，但所有链接都只是比较 Strassen 的方法与标准矩阵乘法方法，或者它们详细说明了算法提出的过程。

Answer 1

你应该去源材料。在这种情况下，Strassen 的原始论文：

Strassen, Volker, Gaussian Elimination is not Optimal, Numer. 数学。13 页。354-356, 1969

http://link.springer.com/article/10.1007%2FBF02165411?LI=true

即使我自己没有读过它，我也会假设对算法的复杂性进行了严格的讨论和证明。

看起来 Strassen 教授仍然活跃（http://en.wikipedia.org/wiki/Volker_Strassen）并且有一个主页（http://www.math.uni-konstanz.de/~strassen/）。如果在尽可能多地学习了算法之后，你仍然有兴趣了解更多，我认为给教授发一封措辞谨慎的电子邮件是不可能的。

不幸的是，尽管这项工作是在一所公立大学（加州大学伯克利分校）使用联邦基金（NSF 赠款）完成的，但似乎没有在线提供该论文的免费版本，但这是一个完全独立的问题，我们不应该这样做这里不讨论。

如果您是学生，您可能可以通过您的学校访问，或者至少您的学校可以免费为您提供一份副本。祝你好运。

Answer 2

Strassen 算法应该存在的证明是简单的维度计数（结合简单维度计数给出正确答案的证明）。考虑所有双线性映射$C^n\times C^n \rightarrow C^n$的向量空间，这是一个维度的向量空间$n^3$（在矩阵乘法的情况下，我们有$n=m^2$，例如$n=4$对于这种$2\times 2$情况）。秩一的双线性映射集，即仅使用一个标量乘法的算法中可计算的映射，具有维度$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$, 并且最多可以通过 rank 的双线性映射来近似为任意精度$7$。