c++ - Strassen 算法中的递归

Question

我想知道您将如何在 Strassen 的算法中进行递归调用，以及它们究竟需要在哪里。

我知道 7 个乘数比我们原本拥有的 8 个更有效，但我对如何递归计算这些乘数感到困惑。特别是，如果我们遵循分而治之的范式，我们究竟要“划分”矩阵的哪一部分，以及在我们达到可以分别征服递归部分的基本情况之前，我们将如何做呢？

谢谢！

Answer 1

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

Answer 2

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

对于不是2^nx 2^n 类型的矩阵，您可以将填充归零，直到满足要求。