Algoritmul Coppersmith-Winograd

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 28 mai 2022; verificările necesită 8 modificări .

Algoritmul Coppersmith-Winograd este un algoritm de înmulțire a matricilor pătrate , propus în 1987 de D. Coppersmith și S. Winograd . În versiunea originală , complexitatea asimptotică a algoritmului a fost , unde este dimensiunea laturii matricei. Algoritmul Coppersmith–Winograd, ținând cont de o serie de îmbunătățiri și perfecționări în anii următori, are cele mai bune asimptotice dintre algoritmii cunoscuți pentru multiplicarea matricei. $O(n^{2,3755})$ $n$

În practică, algoritmul Coppersmith–Winograd nu este utilizat, deoarece are o constantă de proporționalitate foarte mare și începe să depășească alți algoritmi cunoscuți în viteză doar pentru matrice a căror dimensiune depășește memoria calculatoarelor moderne.

Îmbunătățiri ale algoritmului

În 2010, Andrew Stothers a îmbunătățit algoritmul la [1] $O(n^{2,374}).$
În 2011, Virginia Williams a îmbunătățit din nou algoritmul la [2] $O(n^{2,3728642}).$
În 2014, Francois Le Gall a simplificat metoda Williams și a obținut o nouă estimare [3] $O(n^{2,3728639}).$
În 2020, Josh Alman și Virginia Williams au îmbunătățit din nou metoda atingând scorul [4] $O(n^{2,3728596}).$

Vezi și

Algoritmul Strassen
Ipoteza lui Strassen
Probleme matematice deschise - pentru a determina limita inferioară exactă a complexității algoritmului de multiplicare a matricei.

Note

↑ Stothers, Andrew (2010), On the Complexity of Matrix Multiplication , < https://www.era.lib.ed.ac.uk/handle/1842/4734 > Arhivat la 29 august 2017 la Wayback Machine .
↑ Williams, Virginia (2011), Breaking the Coppersmith-Winograd barrier Arhivat 26 octombrie 2014 la Wayback Machine
↑ „Chiar dacă cineva reușește să demonstreze una dintre conjecturi – demonstrând astfel că ω = 2 – este puțin probabil ca abordarea produsului coroană să fie aplicabilă problemelor matricei mari care apar în practică. (…) matricele de intrare trebuie să fie mari din punct de vedere astronomic pentru ca diferența de timp să fie evidentă.” Le Gall, François (2014), Puterile tensorilor și multiplicarea rapidă a matricei, Proceedings of the 39th International Symposium on Symbolic and Algebric Computation ( ISSAC 2014)
↑ Revista Quanta

Literatură

Henry Cohn, Robert Kleinberg, Balazs Szegedy și Chris Umans. Algoritmi teoretici de grup pentru multiplicarea matricelor. arXiv : math.GR/0511460 . Proceedings of the 46th Annual Symposium on Foundations of Computer Science , 23-25 octombrie 2005, Pittsburgh, PA, IEEE Computer Society, pp. 379-388.
Don Coppersmith și Shmuel Winograd . Înmulțirea matricelor prin progresii aritmetice. 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 > . Consultat la 20 februarie 2009. Arhivat la 31 martie 2010 la Wayback Machine .