Strassen计算矩阵平方的方法有什么问题？

Question

使用与Strassen's相同的方法，只需5次乘法就足以计算矩阵的平方。如果A2 = a，b，c，d，则乘法为a* a，d* d，b* (a + d)，c * (a + d)，b*c。

如果我们将这个算法推广到求矩阵的平方，复杂度就会降低到n^log5，基数为2。

我被问到一个问题，要找出这个算法的错误之处，以及当它失败时，如果我们推广这个算法来求矩阵的平方？

Answer 1

该算法不能工作，因为矩阵乘法是不可交换的。

ab+bd != b(a+d)，因为b(a+d) = ba+bd，对于矩阵乘法，ab!=ba。所以我们不能减少任何乘法。此算法仅适用于2X2矩阵。

Answer 2

你可以在调用树的根部进行5次乘法运算，但其中一些乘法运算不是平方的，因此对于乘法运算，运行时间并不比Strassen好。

换句话说，如果我们有一个O(n^c)算法来平方一个n-x-n矩阵，那么我们就可以通过平方2n-2n块矩阵得到一个O(n^c)的乘法算法

     2
[0 A]    [AB 0 ]
[B 0]  = [0  BA].

Answer 3

具有矩阵A

ab
cd

我们可以用8次乘法以朴素的方式计算AA：

aa + bc
ab + bd 
ac + cd 
bc + dd

直接应用Strassen乘法可以得到7个乘法。

但是，使用与Strassen类似的方法，我们可以注意到：

ab + bd = b(a + d) 
ac + cd = c(a + d)

因此，实际上，我们只需进行5次乘法即可得到结果：

aa、dd、bc、b(a + d)、c(a + d)。

这个方法没有错，也就是说它对所有的输入都是正确的。

也许你的面试官希望你表达你的想法，并为自己辩护说它实际上没有错，而不是同意它是错的。

如果你的面试官仍然会说这是错误的，一个好主意是问一下“错误”的定义是什么。也许“不是最优的”(就平方、乘法和加法的数量而言)。Good read.

或者它可能是“错误的”，因为它不能放大，例如，它不能用于4x4矩阵。