Coppersmith-Winogradův algoritmus

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 28. května 2022; kontroly vyžadují 8 úprav .

Algoritmus Coppersmith-Winograd je algoritmus pro násobení čtvercových matic , navržený v roce 1987 D. Coppersmithem a S. Winogradem . V původní verzi byla asymptotická složitost algoritmu , kde je velikost strany matice. Algoritmus Coppersmith–Winograd, který bere v úvahu řadu vylepšení a vylepšení v následujících letech, má nejlepší asymptotiku mezi známými algoritmy pro násobení matic. $O(n^{2,3755})$ $n$

V praxi se Coppersmith–Winogradův algoritmus nepoužívá, protože má velmi velkou konstantu proporcionality a rychlost začíná překonávat ostatní známé algoritmy pouze u matic, jejichž velikost přesahuje paměť moderních počítačů.

Vylepšení algoritmu

V roce 2010 Andrew Stothers vylepšil algoritmus na [1] $O(n^{2.374}).$
V roce 2011 Virginia Williams algoritmus ještě jednou vylepšila na [2] $O(n^{2.3728642}).$
V roce 2014 Francois Le Gall zjednodušil Williamsovu metodu a získal nový odhad [3] $O(n^{2.3728639}).$
V roce 2020 Josh Alman a Virginia Williams vylepšili metodu znovu a dosáhli skóre [4] $O(n^{2.3728596}).$

Viz také

Strassenův algoritmus
Strassenova hypotéza
Otevřené matematické problémy - určit přesnou dolní hranici složitosti algoritmu násobení matic.

Poznámky

↑ Stothers, Andrew (2010), On the Complexity of Matrix Multiplication , < https://www.era.lib.ed.ac.uk/handle/1842/4734 > Archivováno 29. srpna 2017 na Wayback Machine .
↑ Williams, Virginia (2011), Breaking the Coppersmith-Winograd bariéra Archivováno 26. října 2014 na Wayback Machine
↑ „I když se někomu podaří prokázat jednu z domněnek – a tím prokázat, že ω = 2 – je nepravděpodobné, že by byl přístup k produktu věnců použitelný na velké maticové problémy, které v praxi vznikají. (…) vstupní matice musí být astronomicky velké, aby byl zřejmý rozdíl v čase.“ Le Gall, François (2014), Síly tenzorů a rychlé násobení matic, sborník příspěvků z 39. mezinárodního sympozia o symbolickém a algebraickém počítání ( ISSAC 2014)
↑ Magazín Quanta

Literatura

Henry Cohn, Robert Kleinberg, Balazs Szegedy a Chris Umans. Teoretické grupové algoritmy pro násobení matic. arXiv : math.GR/0511460 . Proceedings of the 46th Annual Symposium on Foundations of Computer Science , 23.-25. října 2005, Pittsburgh, PA, IEEE Computer Society, pp. 379-388.
Don Coppersmith a Shmuel Winograd . Násobení matic pomocí aritmetických posloupností. Journal of Symbolic Computation , 9:251-280, 1990.
Robinson, Sara (2005), Toward an Optimal Algorithm for Matrix Multiplication , SIAM News Vol . 38 (9) , < http://www.siam.org/pdf/news/174.pdf > . Získáno 20. února 2009. Archivováno 31. března 2010 na Wayback Machine .