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

Question

使用与Strassen相同的方法，仅 5 次乘法就足以计算矩阵的平方。如果 A[2][2] = [a, b, c, d]，则乘法为 a * a, d * d, b * (a + d), c * (a + d), b * c。

如果我们推广该算法以获取矩阵的平方，则复杂度降低到以 2 为底的 n^log5。

我被问到这个算法有什么问题，如果我们推广这个算法来找到矩阵的平方，它什么时候会失败？

Answer 1

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

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

Answer 2

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

换句话说，如果我们有一个 O(n^c) 算法来平方 n×n 矩阵，那么我们将得到一个 O(n^c) 算法，通过平方 2n×2n 块矩阵来进行乘法运算

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

Answer 3

有一个矩阵A：

ab
cd

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

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)。

这种方法没有任何问题，即它对所有输入都是正确的。

也许你的面试官希望你展示你的想法并捍卫它实际上并没有错，而不是同意它是错误的。

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

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