Strassen hipotézise

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. március 8-án felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A számítási bonyolultság és a lineáris algebra elméletében Strassen hipotézise azt állítja, hogy négyzetes mátrixokhoz kellően nagy dimenziókat lehet megadni , amelyekhez létezik egy algoritmus , amely lehetővé teszi, hogy tetszőlegesen közeli sebességgel szorozzuk meg őket . Számos matematikus erőfeszítése ellenére az 1969 -ben felhozott sejtést még nem sikerült bebizonyítani, és ez a lineáris algebra egyik megoldatlan problémája . $n$ $O(n^{2})$

Hipotézis

Tetszőlegesen kicsire van egy algoritmus, amely kellően nagy n természetes számok esetén garantálja két méretű mátrix megszorzását műveletekben . $\varepsilon >0$ $n\szer n$ ${O}(n^{{2+\varepszilon }})$

Vita

Két nagy négyzetmátrix szorzása fáradságos és gyakran előfordul az alkalmazásokban. Így ennek a műveletnek a gyorsítása nagy gyakorlati jelentőséggel bír. Mivel a mátrixok szorzásakor a mátrixelemek új, általában véve eltérő értékeit kell kiszámítani, ezt nem lehet kevesebb művelettel megtenni. A mátrixszorzás definíciója szerinti szabványos algoritmus műveleteket igényel. 1969- ben Volker Strassen német matematikus javasolta az első gyorsabb algoritmust [1] , amely szorzást igényelt. Azt a hipotézist is felvetette, hogy még gyorsabban lehet mátrixokat szorozni. 1990 - ben bebizonyosodott, hogy van elég művelet ( Coppersmith-Winograd algoritmus ) [2] . Ez az algoritmus elméleti jelentőségű, a gyakorlatban nem használható, mivel valójában csak csillagászatilag nagy mátrixok esetén gyorsítja a szorzást. Ezt követően számos nagyon apró javítást végeztek az utolsó becslésen ugyanazon a módszeren [3] . Ez lehetővé teszi, hogy a probléma összetettségének elméleti becslése során beszéljünk a "Coppersmith-Winograd akadály" létezéséről, bár a legtöbb kutató úgy véli, hogy Strassen hipotézise helyes. A gyakorlati algoritmusok kitevője némileg javult a Strassen-algoritmus kitevőjéhez képest, de eddig lényegesen nagyobb maradt, mint a Coppersmith-Winograd algoritmus kitevője. $n^{2}$ $O(n^{2})$ $O(n^{3})$ ${O}(n^{{\log _{2}7)))\kb. {O}(n^{{2,81)))$ ${O}(n^{{2,376}})$

Lásd még

Jegyzetek

↑ Strassen, Volker, Gauss-elimináció nem optimális , szám. Math. 13. o. 354-356, 1969
↑ Don Coppersmith és Shmuel Winograd. Mátrixszorzás aritmetikai progresszióval. Journal of Symbolic Computation , 9:251-280, 1990.
↑ Williams, Virginia (2011), Breaking the Coppersmith-Winograd barrier Archiválva : 2013. január 20. a Wayback Machine -nél

Linkek

Strassen V. A Gauss-elimináció nem optimális // Szám . Math / F. Brezzi - Springer Science + Business Media , 1969. - Vol. 13, Iss. 4. - P. 354-356. — ISSN 0029-599X ; 0945-3245 - doi:10.1007/BF02165411