Kobbersmed-Winograd algoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 28. maj 2022; checks kræver 8 redigeringer .

Coppersmith-Winograd- algoritmen er en algoritme til multiplikation af kvadratiske matricer , foreslået i 1987 af D. Coppersmith og S. Winograd . I den originale version var den asymptotiske kompleksitet af algoritmen , hvor er størrelsen på siden af matrixen. Coppersmith-Winograd-algoritmen, der tager højde for en række forbedringer og raffinementer i de efterfølgende år, har den bedste asymptotik blandt de kendte algoritmer til matrixmultiplikation. $O(n^{2.3755})$ $n$

I praksis bruges Coppersmith–Winograd-algoritmen ikke, da den har en meget stor proportionalitetskonstant og begynder at udkonkurrere andre velkendte algoritmer i hastighed kun for matricer, hvis størrelse overstiger moderne computeres hukommelse.

Algoritmeforbedringer

I 2010 forbedrede Andrew Stothers algoritmen til [1] $O(n^{2.374}).$
I 2011 forbedrede Virginia Williams algoritmen endnu en gang til [2] $O(n^{2.3728642}).$
I 2014 forenklede Francois Le Gall Williams-metoden og opnåede et nyt skøn [3] $O(n^{2.3728639}).$
I 2020 forbedrede Josh Alman og Virginia Williams metoden igen og nåede scoren [4] $O(n^{2.3728596}).$

Se også

Strassen algoritme
Strassens hypotese
Åbne matematiske problemer - for at bestemme den nøjagtige nedre grænse for kompleksiteten af matrixmultiplikationsalgoritmen.

Noter

↑ Stothers, Andrew (2010), On the Complexity of Matrix Multiplication , < https://www.era.lib.ed.ac.uk/handle/1842/4734 > Arkiveret 29. august 2017 på Wayback Machine .
↑ Williams, Virginia (2011), Breaking the Coppersmith-Winograd barriere Arkiveret 26. oktober 2014 på Wayback Machine
↑ "Selv hvis det lykkes nogen at bevise en af formodningerne - og derved demonstrere, at ω = 2 - vil kranseprodukttilgangen næppe være anvendelig på de store matrixproblemer, der opstår i praksis. (...) inputmatricerne skal være astronomisk store, for at forskellen i tid er synlig." Le Gall, François (2014), Tensorers kræfter og hurtig matrixmultiplikation, Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation ( ISSAC 2014)
↑ Quanta Magazine

Litteratur

Henry Cohn, Robert Kleinberg, Balazs Szegedy og Chris Umans. Gruppeteoretiske algoritmer til matrixmultiplikation. arXiv : math.GR/0511460 . Proceedings of the 46th Annual Symposium on Foundations of Computer Science , 23-25 oktober 2005, Pittsburgh, PA, IEEE Computer Society, pp. 379-388.
Don Coppersmith og Shmuel Winograd . Matrix multiplikation via aritmetiske progressioner. 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 > . Hentet 20. februar 2009. Arkiveret 31. marts 2010 på Wayback Machine .