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

Question

使用与 Strassen's 相同的方法仅 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

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

换句话说，如果我们有一个 O(n^c) 算法来对 n×n 矩阵求平方，那么我们将得到一个 O(n^c) 算法来对 2n×n 矩阵求平方2n分块矩阵

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