Coppersmithův–Winogradův algoritmus

Coppersmithův–Winogradův algoritmus, pojmenovaný po Donovi Coppersmithovi a Shmuelovi Winogradovi, je asymptoticky velmi rychlý 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, $O(n^{2,807})\!\$ u Strassenova algoritmu (první subkubický algoritmus pro násobení matic, navíc vhodný pro praktické použití). Nalezen byl D. Coppersmithem a S. Winogradem v roce 1990 a měl výrazně lepší asymptotickou složitost než starší algoritmy pro násobení matic (oproti tehdy nejlepšímu algoritmu od V. Strassena z roku 1986 – pozor, nejde o dříve zmíněný Strassenův algoritmus – snížil exponent asymptotické složitosti téměř o $0,1$ ) a na 20 let se stal asymptoticky nejlepším známým algoritmem pro násobení matic. Od roku 2010 se ale objevují návrhy algoritmů založených na tzv. laserové metodě, která je zobecněním právě Coppersmithova-Winogradova algoritmu, s ještě o něco málo nižší asymptotickou složitostí, v červnu 2023 byl nejlepším v preprintu navržený algoritmus s časovou složitostí $O(n^{2.371552})\!\$ .

Podobně jako většina ostatních asymptoticky rychlých algoritmů pro násobení matic je nevhodný pro praktické využití, neboť patří mezi zástupce tzv. galaktických algoritmů, tj. algoritmů s dobrou asymptotickou složitostí, které ale i pro největší matice, které jsme schopni uložit do současných počítačů, běží nesrovnatelně déle než používané algoritmy, a jejich výhoda by se začala projevovat až v případě matic "galaktických rozměrů." Otevřenou otázkou zůstává asymptotická složitost násobení matic, tj. jakou nejmenší složitost musí každý algoritmus pro násobení matic mít. Zatímco horní odhad poskytují zkonstruované algoritmy pro násobení matic, jediným známým dolním odhadem je triviální $O(n^{2})\!\$ , který je dán tím, že matice má $n^{2}\!\$ prvků a každý musí být alespoň jednou přečten.

Odkazy

Reference

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

Literatura

COHN, Henry, et al. Proceedings of the 46th Annual Symposium on Foundations of Computer Science. Pittsburgh, PA, USA: IEEE Computer Society, 23. 10. 2005. Dostupné v archivu. ISBN 0-7695-2468-0. Kapitola Group-theoretic Algorithms for Matrix Multiplication, s. 379–388. (anglicky)
COPPERSMITH, Don; WINOGRAD, Shmuel. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation. 1990, čís. 9, s. 251–280. (anglicky)