Portál:Matematika/Odporúčaný článok/30 2016

Strassenov algoritmus, pomenovaný podľa Volkera Strassena, je algoritmus na násobenie matíc. Oproti štandardnému algoritmu násobiacemu matice priamo podľa vzťahu z definície, s časovou zložitosťou $O(n^{3})$, má Strassenov algoritmus o niečo lepšiu asymptotickú časovú zložitosť $O(N^{\log _{2}7})\approx O(N^{2.81})$, čo znamená, že pre veľké matice je Strassenov algoritmus rýchlejší, než štandardný algoritmus.

Strassenov algoritmus nie je asymptoticky optimálny. Najrýchlejší známy algoritmus násobenia matíc, tzv. Coppersmithov–Winogradov algoritmus, má časovú zložitosť približne $O(n^{2.376})$, ale vzhľadom na veľmi veľký konštantný faktor sa táto výhoda prejaví len pre extrémne veľké matice.

Algoritmus

Nech $A,B$ sú matice typu $2^{n}\times 2^{n}$ (v prípade, že matice nie sú typu $2^{n}\times 2^{n}$, je možné doplniť chýbajúce riadky a stĺpce nulami) nad okruhom $R$. Označme $C=A\cdot B$ súčin týchto matíc. Potom platí

Celý článok...