斯特拉森算法中的递归

Question

我想知道如何在斯特拉森算法中进行递归调用，以及它们究竟需要什么。

我知道7个乘法器比8个我们会有更多的效率，但我很困惑这些乘法器是如何递归计算的。特别是，如果我们遵循分而治之的范式，那么矩阵的哪一部分就是我们“划分”的，我们如何去做这件事，直到我们得到一个基本案例，我们可以分别征服递归部分。

谢谢！

Answer 1

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

Answer 2

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

对于矩阵而不是类型2^n x 2^n您可以将零点填充到满足要求。