Strassens hypotes

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 8 mars 2020; verifiering kräver 1 redigering .

I teorin om beräkningskomplexitet och linjär algebra anger Strassens hypotes att man för kvadratiska matriser kan specificera tillräckligt stora dimensioner , för vilka det finns en algoritm som gör att man kan multiplicera dem med en hastighet godtyckligt nära . Trots ansträngningar från många matematiker, har gissningen som lades fram 1969 ännu inte bevisats och är ett av de olösta problemen i linjär algebra . $n$ $O(n^{2})$

Hypotes

För godtyckligt liten finns det en algoritm som, för tillräckligt stora naturliga tal n , garanterar multiplikationen av två matriser av storlek i operationer. $\varepsilon >0$ $n\ gånger n$ ${O}(n^{{2+\varepsilon }})$

Diskussion

Uppgiften att multiplicera två stora kvadratiska matriser är mödosam och förekommer ofta i applikationer. Således är accelerationen av denna operation av stor praktisk betydelse. Eftersom när man multiplicerar matriser är det nödvändigt att beräkna nya, generellt sett, olika värden på matriselement, kan detta inte göras i mindre än operationer. Standardalgoritmen enligt definitionen av matrismultiplikation kräver operationer. 1969 föreslog den tyske matematikern Volker Strassen den första snabbare algoritmen [1] som krävde multiplikationer. Han lade också fram hypotesen att det är möjligt att multiplicera matriser ännu snabbare. 1990 bevisades det att det finns tillräckligt med operationer ( Coppersmith-Winograd-algoritmen ) [2] . Denna algoritm är av teoretisk betydelse och kan inte användas i praktiken, eftersom den faktiskt påskyndar multiplikationen endast för astronomiskt stora matriser. Därefter gjordes flera mycket små förbättringar av den senaste uppskattningen baserat på samma metod [3] . Detta tillåter oss att tala om existensen av "Coppersmith-Winograd-barriären" i teoretiska uppskattningar av komplexiteten i detta problem, även om de flesta forskare tror att Strassens hypotes är korrekt. Exponenten i praktiska algoritmer har förbättrats något jämfört med exponenten för Strassen-algoritmen, men än så länge är den fortfarande betydligt större än exponenten för Coppersmith-Winograd-algoritmen. $n^{2}$ $O(n^{2})$ $O(n^{3})$ ${O}(n^{{\log _{2}7)))\approx {O}(n^{{2.81)))$ ${O}(n^{{2 376}})$

Se även

Anteckningar

↑ Strassen, Volker, Gaussisk eliminering är inte optimal , Numer. Matematik. 13, sid. 354-356, 1969
↑ Don Coppersmith och Shmuel Winograd. Matrismultiplikation via aritmetiska progressioner. Journal of Symbolic Computation , 9:251-280, 1990.
↑ Williams, Virginia (2011), Breaking the Coppersmith-Winograd barrier Arkiverad 20 januari 2013 på Wayback Machine

Länkar

Strassen V. Gaussisk eliminering är inte optimal // Antal . Math / F. Brezzi - Springer Science + Business Media , 1969. - Vol. 13, Iss. 4. - s. 354-356. — ISSN 0029-599X ; 0945-3245 - doi:10.1007/BF02165411