Coppersmith-Winograd algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 28 maj 2022; kontroller kräver 8 redigeringar .

Coppersmith-Winograd-  algoritmen är en algoritm för att multiplicera kvadratiska matriser , föreslagen 1987 av D. Coppersmith och S. Winograd . I den ursprungliga versionen var den asymptotiska komplexiteten hos algoritmen , där  är storleken på sidan av matrisen. Coppersmith–Winograd-algoritmen, med hänsyn till en rad förbättringar och förfinningar under efterföljande år, har den bästa asymptotiken bland de kända algoritmerna för matrismultiplikation.

I praktiken används inte Coppersmith–Winograd-algoritmen, eftersom den har en mycket stor proportionalitetskonstant och börjar överträffa andra välkända algoritmer i hastighet endast för matriser vars storlek överstiger minnet hos moderna datorer.

Algoritmförbättringar

Se även

Anteckningar

  1. ↑ Stothers, Andrew (2010), On the Complexity of Matrix Multiplication , < https://www.era.lib.ed.ac.uk/handle/1842/4734 > Arkiverad 29 augusti 2017 på Wayback Machine . 
  2. ↑ Williams, Virginia (2011), Breaking the Coppersmith-Winograd barrier Arkiverad 26 oktober 2014 på Wayback Machine
  3. ↑ "Även om någon lyckas bevisa en av gissningarna – och därigenom visa att ω = 2 – är det osannolikt att kransproduktens tillvägagångssätt är tillämpbart på de stora matrisproblem som uppstår i praktiken. (...) inmatningsmatriserna måste vara astronomiskt stora för att skillnaden i tid ska vara uppenbar." Le Gall, François (2014), Tensorernas krafter och snabb matrismultiplikation, Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation ( ISSAC 2014) 
  4. ↑ Quanta Magazine

Litteratur