對於大小爲k x k的矩陣，Strassen算法有多少個浮點運算？

Question

我想了解this analysis of Strassen's algorithm乘法k×k矩陣。但我仍然不太確定有多少操作被調用。有人可以幫助澄清這一點？

Answer 1

鑑於頁面顯示它大約爲O（N^2.807 ...），我想這應該是浮點運算數的一個很好的近似值。所有循環/迭代都將使用整數運算。

Answer 2

執行的操作次數如下確定。首先，我們將矩陣分成四個大小爲k/2的子小塊，然後對這些矩陣執行7次遞歸乘法。然後，我們會不斷增加這些產品以獲得理想的結果。這給了我們所定義的遞推關係如下：

T（1）= 1

T（K）= 7T（K/2）+ CK

注意，LG的7> 2 ，因爲lg 7> lg 4 = 2（這裏lg是二進制對數）。因此，通過情況中的一個，算法的漸近複雜度是O（k ^{lg 7}）≈ O（k ^2.807）。

希望這會有所幫助！