Coppersmithův-Winogradův algoritmus

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Coppersmithův–Winogradův algoritmus, pojmenovaný po Donovi Coppersmithovi a Shmuelovi Winogradovi, je asymptoticky nejrychlejší známý algoritmus pro násobení matic. Lze s ním vynásobit dvě matice n \times n v čase O(n^{2.376}) \!\ . Jde o zlepšení oproti O(n^3) \!\ u triviálního algoritmu a O(n^{2.807}) \!\ u Strassenova algoritmu. Mohlo by být možné exponent dále zlepšit, nicméně exponent musí být alespoň 2 (protože matice n \times nn^2 hodnot a každou z nich je nutné alespoň jednou přečíst, aby bylo možné spočítat přesný výsledek).

Coppersmithův–Winogradův algoritmus se často používá jako stavební prvek v jiných algoritmech k dokázání jejich teoretické časové náročnosti. Nicméně na rozdíl od Strassenova algoritmu se příliš nepoužívá v praxi, protože je výhodnější až pro matice velmi velkých řádů.[1]

Odkazy[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

V tomto článku byl použit překlad textu z článku Coppersmith–Winograd algorithm na anglické Wikipedii.

  1. Robinson, Sara (2005), "Toward an Optimal Algorithm for Matrix Multiplication", SIAM News 38 (9), http://www.siam.org/pdf/news/174.pdf

Literatura[editovat | editovat zdroj]