Ipoteza lui Strassen

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 8 martie 2020; verificarea necesită 1 editare .

În teoria complexității computaționale și algebrei liniare , ipoteza lui Strassen afirmă că pentru matrice pătrată se pot specifica dimensiuni suficient de mari , pentru care există un algoritm care permite multiplicarea lor cu o viteză arbitrar apropiată de . În ciuda eforturilor multor matematicieni, conjectura prezentată în 1969 nu a fost încă dovedită și este una dintre problemele nerezolvate din algebra liniară . $n$ $O(n^{2})$

Ipoteza

Pentru arbitrar mic , există un algoritm care, pentru numere naturale suficient de mari n , garantează înmulțirea a două matrici de mărime în operații. $\varepsilon >0$ $n\ ori n$ ${O}(n^{{2+\varepsilon }})$

Discuție

Sarcina de a înmulți două matrici pătrate mari este laborioasă și adesea întâlnită în aplicații. Astfel, accelerarea acestei operații are o mare importanță practică. Deoarece la înmulțirea matricelor este necesar să se calculeze noi, în general, valori diferite ale elementelor matricei, acest lucru nu se poate face în mai puțin de operații. Algoritmul standard conform definiției înmulțirii matricelor necesită operații. În 1969, matematicianul german Volker Strassen a propus primul algoritm mai rapid [1] care necesita înmulțiri. El a prezentat, de asemenea, ipoteza că este posibil să se înmulțească matrice și mai rapid. În 1990, s-a dovedit că există suficiente operații ( algoritmul Coppersmith-Winograd ) [2] . Acest algoritm este de importanță teoretică și nu poate fi utilizat în practică, deoarece de fapt accelerează înmulțirea numai pentru matrice astronomic mari. Ulterior, au fost aduse câteva îmbunătățiri foarte minore ultimei estimări pe baza aceleiași metode [3] . Acest lucru ne permite să vorbim despre existența „barierei Coppersmith-Winograd” în estimările teoretice ale complexității acestei probleme, deși majoritatea cercetătorilor consideră că ipoteza lui Strassen este corectă. Exponentul în algoritmi practici a fost ușor îmbunătățit în comparație cu exponentul algoritmului Strassen, dar până acum rămâne semnificativ mai mare decât exponentul algoritmului Coppersmith-Winograd. $n^{2}$ $O(n^{2})$ $O(n^{3})$ ${O}(n^{{\log _{2}7)))\aproximativ {O}(n^{{2,81)))$ ${O}(n^{{2.376}})$

Vezi și

Note

↑ Strassen, Volker, Eliminarea gaussiană nu este optimă , Numer. Matematică. 13, p. 354-356, 1969
↑ Don Coppersmith și Shmuel Winograd. Înmulțirea matricelor prin progresii aritmetice. Journal of Symbolic Computation , 9:251-280, 1990.
↑ Williams, Virginia (2011), Breaking the Coppersmith-Winograd barrier Arhivat 20 ianuarie 2013 la Wayback Machine

Link -uri

Strassen V. Eliminarea gaussiană nu este optimă // Numer . Math / F. Brezzi - Springer Science + Business Media , 1969. - Vol. 13, Iss. 4. - P. 354-356. — ISSN 0029-599X ; 0945-3245 - doi:10.1007/BF02165411