Coppersmith-Winograd-algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 28.5.2022 tarkistetusta versiosta . tarkastukset vaativat 8 muokkausta .

Coppersmith-Winograd- algoritmi on neliömatriisien kertomisalgoritmi , jonka vuonna 1987 ehdottivat D. Coppersmith ja S. Winograd . Alkuperäisessä versiossa algoritmin asymptoottinen monimutkaisuus oli , missä on matriisin sivun koko. Coppersmith–Winograd-algoritmilla, joka ottaa huomioon sarjan parannuksia ja tarkennuksia seuraavina vuosina, on paras asymptotiikka tunnetuista matriisin kertolaskualgoritmeista. $O(n^{2.3755})$ $n$

Käytännössä Coppersmith–Winograd-algoritmia ei käytetä, koska sillä on erittäin suuri suhteellisuusvakio ja se alkaa nopeuttaa muita tunnettuja algoritmeja vain matriiseilla, joiden koko ylittää nykyaikaisten tietokoneiden muistin.

Algoritmin parannukset

Vuonna 2010 Andrew Stothers paransi algoritmia [1] $O(n^{2.374}).$
Vuonna 2011 Virginia Williams paransi algoritmia jälleen [2] $O(n^{2.3728642}).$
Vuonna 2014 Francois Le Gall yksinkertaisti Williamsin menetelmää ja sai uuden arvion [3] $O(n^{2.3728639}).$
Vuonna 2020 Josh Alman ja Virginia Williams paransivat menetelmää jälleen saavuttaen pisteet [4] $O(n^{2.3728596}).$

Katso myös

Strassenin algoritmi
Strassenin hypoteesi
Avoimet matemaattiset tehtävät – matriisin kertolaskualgoritmin monimutkaisuuden tarkan alarajan määrittämiseksi.

Muistiinpanot

↑ Stothers, Andrew (2010), On the Complexity of Matrix Multiplication , < https://www.era.lib.ed.ac.uk/handle/1842/4734 > Arkistoitu 29. elokuuta 2017 Wayback Machinessa .
↑ Williams, Virginia (2011), Breaking the Coppersmith-Winograd barrier Arkistoitu 26. lokakuuta 2014 Wayback Machinessa
↑ "Vaikka joku onnistuisi todistamaan yhden olettamuksista - osoittaen siten, että ω = 2 - seppeletuotteen lähestymistapaa ei todennäköisesti voida soveltaa käytännössä esiin tuleviin suuriin matriisiongelmiin. (…) syöttömatriisien on oltava tähtitieteellisesti suuria, jotta aikaero olisi ilmeinen." Le Gall, François (2014), Tensorien ja nopean matriisin kertolasku, Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation ( ISSAC 2014)
↑ Quanta-lehti

Kirjallisuus

Henry Cohn, Robert Kleinberg, Balazs Szegedy ja Chris Umans. Ryhmäteoreettiset algoritmit matriisikertolaskulle. arXiv : math.GR/0511460 . Proceedings of the 46th Annual Symposium on Foundations of Computer Science , 23.-25.10.2005, Pittsburgh, PA, IEEE Computer Society, s. 379-388.
Don Coppersmith ja Shmuel Winograd . Matriisin kertolasku aritmeettisen progression avulla. 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 > . Haettu 20. helmikuuta 2009. Arkistoitu 31. maaliskuuta 2010 Wayback Machinessa .