Coppersmith-Winograd algoritme

Den Copper-Winograd algoritmen er en algoritme for å beregne produktet av to kvadratiske matriser i størrelse på grunn av Don Copper og Shmuel Winograd på 1,987 . Den algoritmiske kompleksiteten er det som gjør den til den mest asymptotisk effektive nåværende algoritmen. Det er ingen indikasjoner på at kompleksiteten er optimal, med eksponent 2 generelt ansett som optimal. $ikke$ ${\ displaystyle O (n ^ {2,376}) \! \}$

Algoritmen brukes som en byggestein for å bevise teoretiske resultater på algoritmisk kompleksitet. Men ingen implementering av algoritmen brukes fordi konstanten i den store O er uoverkommelig (den er mindre effektiv enn Strassen på en hvilken som helst matrise som passer inn i minnet til en nåværende datamaskin).

Coppersmith-Winograd-algoritmen ble funnet ved metoder for representasjon av endelige grupper .

I sin avhandling forbedrer Andrew Stothers grensen til algoritmens kompleksitet, og viser at den er mindre enn 2.3737.

Se også

Strassen algoritme

Referanser

Don Coppersmith og Shmuel Winograd . Matriksmultiplikasjon via aritmetiske progresjoner. Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing , side 1–6, 1987.
Vi vet at eksponenten ikke kan være mindre enn 2 siden algoritmen må minst lese oppføringene i matrisen. $n ^ {2}$
Henry Cohn, Robert Kleinberg, Balazs Szegedy og Chris Umans. Gruppeteoretiske algoritmer for matriksmultiplikasjon. Proceedings of the 46th Annual Symposium on Foundations of Computer Science , 23.-25. Oktober 2005, Pittsburgh, PA, IEEE Computer Society, pp. 379–388. Tilgjengelig på arXiv her .
(no) On the Complexity of Matrix Multiplication (Ch. 4) , Andrew James Stothers, PhD, University of Edinburgh , 2010.