Strassens hypotese

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 8. marts 2020; verifikation kræver 1 redigering .

I teorien om beregningsmæssig kompleksitet og lineær algebra siger Strassens hypotese , at man for kvadratiske matricer kan specificere tilstrækkeligt store dimensioner , hvortil der findes en algoritme , der gør det muligt at multiplicere dem med en hastighed vilkårligt tæt på . På trods af mange matematikeres indsats er formodningen fremsat i 1969 endnu ikke blevet bevist og er et af de uløste problemer i lineær algebra . $n$ $O(n^{2})$

Hypotese

For vilkårligt lille er der en algoritme, der for tilstrækkeligt store naturlige tal n garanterer multiplikationen af to størrelsesmatricer i operationer. $\varepsilon >0$ $n\ gange n$ ${O}(n^{{2+\varepsilon }})$

Diskussion

Opgaven med at multiplicere to store kvadratiske matricer er besværlig og forekommer ofte i applikationer. Således er accelerationen af denne operation af stor praktisk betydning. Da det ved multiplicering af matricer er nødvendigt at beregne nye, generelt set, forskellige værdier af matrixelementer, kan dette ikke gøres i mindre end operationer. Standardalgoritmen ifølge definitionen af matrixmultiplikation kræver operationer. I 1969 foreslog den tyske matematiker Volker Strassen den første hurtigere algoritme [1] , der krævede multiplikationer. Han fremsatte også hypotesen om, at det er muligt at multiplicere matricer endnu hurtigere. I 1990 blev det bevist, at der er nok operationer ( Coppersmith-Winograd algoritme ) [2] . Denne algoritme er af teoretisk betydning og kan ikke bruges i praksis, da den faktisk kun fremskynder multiplikationen for astronomisk store matricer. Efterfølgende er der foretaget flere meget mindre forbedringer af det sidste skøn baseret på samme metode [3] . Dette giver os mulighed for at tale om eksistensen af "Kobbersmed-Winograd-barrieren" i teoretiske skøn over kompleksiteten af dette problem, selvom de fleste forskere mener, at Strassens hypotese er korrekt. Eksponenten i praktiske algoritmer er blevet en smule forbedret sammenlignet med eksponenten for Strassen-algoritmen, men indtil videre er den stadig væsentligt større end eksponenten for Coppersmith-Winograd-algoritmen. $n^{2}$ $O(n^{2})$ $O(n^{3})$ ${O}(n^{{\log _{2}7)))\ca. {O}(n^{{2.81)))$ ${O}(n^{{2.376}})$

Se også

Noter

↑ Strassen, Volker, Gaussian Elimination is not Optimal , Numer. Matematik. 13, s. 354-356, 1969
↑ Don Coppersmith og Shmuel Winograd. Matrix multiplikation via aritmetiske progressioner. Journal of Symbolic Computation , 9:251-280, 1990.
↑ Williams, Virginia (2011), Breaking the Coppersmith-Winograd barriere Arkiveret 20. januar 2013 på Wayback Machine

Strassens hypotese

Hypotese

Diskussion

Se også

Noter

Links