algorithm - Strassen 的算法证明

Question

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

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

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

Answer 1

你应该去源 Material 。在这种情况下，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 拨款)完成的，但在线似乎没有免费版本的论文，但这是一个完全独立的问题我们不应该在这里讨论。

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