矩陣乘法，當一個尺寸遠遠大於其他

Question

所以我讀了施特拉森的矩陣乘法算法的複雜度爲O（n^2.8） 但它只能如果A爲n×n和B是n×n的 如果 A是MXN和B是NXO ，m是比N和O非常非常大，但N和O仍然是非常大的 填充用零可能使乘法需要更長的時間

我這樣做，需要這樣一個矩陣的乘法這樣一個項目，我希望得到一些建議 我應該使用傳統的算法還是有辦法修改Strassen的算法來更快地實現它？

Answer 1

https://en.m.wikipedia.org/wiki/Strassen_algorithm

• 大小的產物[2N×N個] * [N X 10N]可以做到20個單獨的[N×N個] * [N X N]的操作，設置成形成結果;

• 大小爲[N×10N] * [10N×N]的乘積可以作爲10次單獨的[N×N] * [N×N]運算完成，相加形成結果。

這些技術將使實現更復雜，相比之下，簡單地填充到2的冪次方;然而，這是一個合理的假設，任何人實施斯特拉森而不是傳統的乘法，將會使計算效率的優先級高於實現的簡單性。