In linearer Algebra war der Coppersmith-Winograd-Algorithmus benannt nach Don Coppersmith und Shmuel Winograd, der asymptotisch schnellste bekannte Matrix-Multiplikationsalgorithmus von 1990 bis 2010. Er kann zwei Matrizen in Zeit [1] (siehe Große O-Notation).
Dies ist eine Verbesserung gegenüber dem naiven Zeitalgorithmus und der time Strassen-Algorithmus. Algorithmen mit einer besseren asymptotischen Laufzeit als der Strassen-Algorithmus werden in der Praxis selten verwendet, da sie aufgrund der großen konstanten Faktoren ihrer Laufzeit unpraktisch sind. [2]
Es ist möglich, den Exponenten weiter zu verbessern; der Exponent muss jedoch mindestens 2 sein (da eine Matrix von hat Werte, und alle müssen mindestens einmal gelesen werden, um das genaue Ergebnis zu berechnen.) .
Im Jahr 2010 gab Andrew Stothers eine Verbesserung des Algorithmus, [3][4] Im Jahr 2011 kombinierte Virginia Vassilevska Williams eine mathematische Abkürzung von Stothers 'Papier mit eigenen Einsichten und automatisierter Optimierung am Computer, wodurch die Bindung an
The Coppersmith Der Winograd-Algorithmus wird häufig als Baustein in anderen Algorithmen verwendet, um theoretische Zeitgrenzen nachzuweisen.
Im Gegensatz zum Strassen-Algorithmus wird er jedoch in der Praxis nicht verwendet, da er nur für Matrizen von Vorteil ist, die so groß sind, dass sie nicht mit moderner Hardware verarbeitet werden können. [7]
Henry Cohn, Robert Kleinberg, Balázs Szegedy und Chris Umans haben den Coppersmith-Winograd-Algorithmus unter Verwendung einer gruppentheoretischen Konstruktion neu abgeleitet. Sie zeigten auch, dass eine von zwei verschiedenen Vermutungen impliziert, dass der optimale Exponent der Matrixmultiplikation 2 ist, wie schon lange vermutet wird. Sie waren jedoch nicht in der Lage, eine spezifische Lösung zu formulieren, die zu einer besseren Laufzeit als Coppersmith-Winograd führte. [8] Einige ihrer Vermutungen wurden von Blasiak, Cohn, Church, Grochow, Naslund, Sawin und Umans widerlegt die Slice-Rank-Methode. [9]
Siehe auch [ edit ]
Referenzen [ edit ]
- ^ Coppersmith, Don; Winograd, Shmuel (1990), "Matrixmultiplikation über arithmetische Abläufe" (PDF) Journal of Symbolic Computation 9 (3): 251, doi: 10.1016 / S0747-7171 (08) 80013-2
- ^ Le Gall, F. (2012), "Schnellere Algorithmen für die Matrixmatrixvervielfachung", Verfahren des 53. jährlichen IEEE-Symposiums über Grundlagen von Computern Science (FOCS 2012) S. 514–523, arXiv: 1204.1111 doi: 10.1109 / FOCS.2012.80 .
- ^ Stothers, Andrew (2010), Zur Komplexität der Matrixmultiplikation
- Davie, AM; Stothers, A.J. (2013), "Verbesserte Komplexität der Matrixmultiplikation", Verfahren der Royal Society of Edinburgh 143A : 351–370, doi: 10.1017 / S0308210511001648
- ^ Williams, Virginia Vassilevska (2011), Durchbruch der Kupferschmied-Winograd-Barriere (PDF)
- ^ "Auch wenn es jemandem gelingt, eine der Vermutungen zu beweisen - und damit beweist, dass ω = 2 ist - Der Kranzproduktansatz ist wahrscheinlich nicht auf die großen Matrixprobleme anwendbar, die in der Praxis auftreten. (...) Die Eingabematrizen müssen astronomisch groß sein, damit der Zeitunterschied sichtbar wird. " Le Gall, François ( 2014), "Potenzen von Tensoren und schnelle Matrixmultiplikation", Verfahren des 39. Internationalen Symposiums für symbolische und algebraische Berechnung (ISSAC 2014) arXiv: 1401.7714 Bibcode: 2014arXiv1401.7714L
- ^ Robinson, Sara (2005), "Auf dem Weg zu einem optimalen Algori für Matrix Multiplication " (PDF) SIAM News 38 (9)
- ^ Cohn, H .; Kleinberg, R .; Szegedy, B .; Umans, C. (2005). "Gruppentheoretische Algorithmen zur Matrixmultiplikation". 46. jährliches IEEE-Symposium über Grundlagen der Informatik (FOCS'05) . p. 379. doi: 10.1109 / SFCS.2005.39. ISBN 0-7695-2468-0.
- ^ Blasiak, J.; Cohn, H .; Church, T .; Grochow, J .; Naslund, E .; Sawin, W .; Umans, C. "Auf Obergrenzen und der gruppentheoretische Ansatz zur Matrixmultiplikation". Diskrete Analyse . doi: 10.19086 / da.1245.
Weiterführende Literatur [ edit
- Bürgisser, P .; Clausen, M .; Shokrollahi, M.A. (1997). Algebraische Komplexitätstheorie . Grundlehren der mathematischen Wissenschaften. 315 . Springer Verlag.
No comments:
Post a Comment