Strassen算法中的递归

Question

我想知道如何在Strassen算法中进行递归调用，以及需要它们的确切位置。

我知道7个乘法器比8个更有效，但是我不明白这些乘法器是如何递归计算的。特别是，如果我们遵循分而治之的范式，那么我们到底是在“划分”矩阵的哪一部分，以及在我们达到可以分别征服递归部分的基本情况之前，我们如何做到这一点？

谢谢!

Answer 1

我们在计算这7个乘数时进行递归调用。首先，我们将矩阵的大小扩展到2的幂，然后在每一步，我们将每个矩阵分成4个部分。

Answer 2

我们将A和B平均划分为四分之一、十六分之一或六十四等，以便将它们减少到2x2矩阵。Strassen方法只能应用于2^n×2^n类型的矩阵。

对于不是2^nx2^n类型的矩阵，可以进行零填充，直到满足要求为止。