Strassen算法证明

Question

我一直在研究Strassen矩阵乘法算法。

《算法导论》中提到，该算法并不直观。然而我好奇是否存在严格的数学证明，以及这个算法的设计实际上涉及了什么。

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

- Dref D

---

这个问题有点不清楚。是否有严谨的数学证明？当然有！可以查看Strassen的论文或后来的综述论文。算法的设计考虑了什么？你得问Strassen。如果你实际上是在询问算法的“高层次”概述，即让你理解其结构和思想而不必费心细节的东西，你可能会在math.SE或cs.SE上找到更好的答案。 - us2012

我找到了一个来源：http://link.springer.com/article/10.1007%2FBF02165411?LI=true#page-1，但它没有包含任何证明。如果您知道其他链接，请分享一下。 - Dref D

你可能想在 http://cs.stackexchange.com/ 或者 http://math.stackexchange.com/ 上提问 - Stack Overflow 是用于编程问题的！ - Shashank

有关CS StackExchange上的这个问题，请参见http://cs.stackexchange.com/questions/14907/strassens-algorithm-proof - pcworld

Answer 1

你应该查看源材料。在这种情况下，是由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

尽管我自己没有阅读过，但我认为这个算法的复杂性会有严格的讨论和证明。

看起来Strassen教授仍在活跃(http://en.wikipedia.org/wiki/Volker_Strassen)，并且有一个主页(http://www.math.uni-konstanz.de/~strassen/)。如果在尽可能了解该算法后，您仍然对学习更多感兴趣，我认为向教授写一封措辞谨慎的电子邮件是可行的。

不幸的是，尽管该工作是在公立大学（加州大学伯克利分校）使用联邦资金（NSF拨款）完成的，但似乎没有免费版本的论文可在线获取，但这是一个完全独立的问题，我们不应在此讨论。

如果您是一名学生，您很可能可以通过学校获得访问权限，或者至少您的学校可以为您免费获取副本。祝你好运。

- Joey

---

下载链接为：http://scgroup.hpclab.ceid.upatras.gr/class/SC/Papers/Strassen.pdf - Axel Kemper

Answer 2

Strassen算法应该存在的证明是一个简单的维数计算（结合了一个证明，即朴素的维数计算给出了正确的答案）。考虑所有双线性映射 $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$ 的双线性映射进行任意精度的逼近。

- user2886619