斯特拉森算法中的遞歸

Question

我想知道如何在斯特拉森算法中進行遞歸調用，以及它們究竟需要什麼。

我知道7個乘法器比8個我們會有更多的效率，但我很困惑這些乘法器是如何遞歸計算的。特別是，如果我們遵循分而治之的範式，那麼矩陣的哪一部分就是我們「劃分」的，我們如何去做這件事，直到我們得到一個基本案例，我們可以分別征服遞歸部分。

謝謝！

Answer 1

我們在計算這7個乘數時進行遞歸調用。首先我們將矩陣的大小擴展到2的冪次，然後在每一步我們將每個矩陣分成4塊。

Answer 2

我們將A和B均勻劃分爲四分之一或十六分之六十四等，以便將它們減少到2×2矩陣。斯特拉森的方法只能應用於2^n x 2^n類型的矩陣。

對於矩陣而不是類型2^n x 2^n您可以將零點填充到滿足要求。