Coppersmith-Winograd algoritmus

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. május 28-án felülvizsgált verziótól ; az ellenőrzések 8 szerkesztést igényelnek .

A Coppersmith-Winograd algoritmus négyzetmátrixok szorzására szolgáló algoritmus , amelyet 1987-ben D. Coppersmith és S. Winograd javasolt . Az eredeti változatban az algoritmus aszimptotikus összetettsége , ahol a mátrix oldalának mérete. A Coppersmith–Winograd algoritmus, figyelembe véve a következő években végzett fejlesztések és finomítások sorozatát, a legjobb aszimptotikával rendelkezik az ismert mátrixszorzási algoritmusok közül. $O(n^{2.3755})$ $n$

A gyakorlatban a Coppersmith–Winograd algoritmust nem használják, mivel nagyon nagy arányossági állandóval rendelkezik, és csak a modern számítógépek memóriáját meghaladó mátrixok esetén kezd gyorsabban felülmúlni a többi jól ismert algoritmust.

Algoritmus fejlesztések

2010-ben Andrew Stothers továbbfejlesztette az algoritmust [1] $O(n^{2,374}).$
2011-ben Virginia Williams ismét továbbfejlesztette az algoritmust [2] $O(n^{2.3728642}).$
2014-ben Francois Le Gall egyszerűsítette a Williams-módszert, és új becslést kapott [3] $O(n^{2.3728639}).$
2020-ban Josh Alman és Virginia Williams ismét javított a módszeren, és elérte a pontszámot [4] $O(n^{2.3728596}).$

Lásd még

Strassen algoritmus
Strassen hipotézise
Nyitott matematikai feladatok – a mátrixszorzó algoritmus összetettségének pontos alsó határának meghatározásához.

Jegyzetek

↑ Stothers, Andrew (2010), On the Complexity of Matrix Multiplication , < https://www.era.lib.ed.ac.uk/handle/1842/4734 > Archivált : 2017. augusztus 29. a Wayback Machine -nél .
↑ Williams, Virginia (2011), Breaking the Coppersmith-Winograd barrier Archivált : 2014. október 26. a Wayback Machine -nél
↑ "Még ha valakinek sikerül is bebizonyítania az egyik sejtést – ezzel bizonyítva, hogy ω = 2 –, a koszorútermék megközelítés valószínűleg nem alkalmazható a gyakorlatban felmerülő nagy mátrixproblémákra. (…) a bemeneti mátrixoknak csillagászatilag nagynak kell lenniük ahhoz, hogy az időbeli különbség nyilvánvaló legyen.” Le Gall, François (2014), Tenzorok hatványai és gyors mátrixszorzás, Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation ( ISSAC 2014)
↑ Quanta magazin

Irodalom

Henry Cohn, Robert Kleinberg, Szegedy Balázs és Chris Umans. Csoportelméleti algoritmusok mátrixszorzáshoz. arXiv : math.GR/0511460 . Proceedings of the 46th Annual Symposium on Foundations of Computer Science , 2005. október 23–25., Pittsburgh, PA, IEEE Computer Society, pp. 379-388.
Don Coppersmith és Shmuel Winograd . Mátrixszorzás aritmetikai progresszióval. Journal of Symbolic Computation , 9:251-280, 1990.
Robinson, Sara (2005), Toward an Optimal Algorithm for Matrix Multiplication , SIAM News 38. kötet (9) , < http://www.siam.org/pdf/news/174.pdf > . Letöltve: 2009. február 20. Archiválva : 2010. március 31. a Wayback Machine -nél .