Strassenova hypotéza

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 8. března 2020; ověření vyžaduje 1 úpravu .

V teorii výpočetní složitosti a lineární algebry Strassenova hypotéza říká, že pro čtvercové matice lze specifikovat dostatečně velké rozměry , pro které existuje algoritmus , který umožňuje násobit je rychlostí libovolně blízkou . Navzdory úsilí mnoha matematiků se domněnka předložená v roce 1969 dosud neprokázala a je jedním z nevyřešených problémů lineární algebry . $n$ $O(n^{2})$

Hypotéza

Pro libovolně malé existuje algoritmus, který pro dostatečně velká přirozená čísla n zaručuje násobení dvou matic velikosti v operacích. $\varepsilon >0$ $n\krát n$ ${O}(n^{{2+\varepsilon }})$

Diskuse

Úkol násobení dvou velkých čtvercových matic je pracný a často se s ním setkáváme v aplikacích. Zrychlení této operace má tedy velký praktický význam. Protože při násobení matic je nutné počítat nové, obecně řečeno různé hodnoty prvků matice, nelze to provést za méně než operace. Standardní algoritmus podle definice násobení matic vyžaduje operace. V roce 1969 navrhl německý matematik Volker Strassen první rychlejší algoritmus [1] , který vyžadoval násobení. Také předložil hypotézu, že je možné násobit matice ještě rychleji. V roce 1990 bylo prokázáno, že operací je dostatek ( Coppersmith-Winogradův algoritmus ) [2] . Tento algoritmus má teoretický význam a v praxi jej nelze použít, protože ve skutečnosti urychluje násobení pouze pro astronomicky velké matice. Následně bylo provedeno několik velmi drobných vylepšení posledního odhadu založeného na stejné metodě [3] . To nám umožňuje hovořit o existenci „Coppersmith-Winogradské bariéry“ v teoretických odhadech složitosti tohoto problému, ačkoli většina badatelů věří, že Strassenova hypotéza je správná. Exponent v praktických algoritmech byl mírně vylepšen ve srovnání s exponentem Strassenova algoritmu, ale zatím zůstává výrazně větší než exponent algoritmu Coppersmith-Winograd. $n^{2}$ $O(n^{2})$ $O(n^{3})$ ${O}(n^{{\log _{2}7)))\přibližně {O}(n^{{2,81)))$ ${O}(n^{{2,376}})$

Viz také

Poznámky

↑ Strassen, Volker, Gaussova eliminace není optimální , Numer. Matematika. 13, str. 354-356, 1969
↑ Don Coppersmith a Shmuel Winograd. Násobení matic pomocí aritmetických posloupností. Journal of Symbolic Computation , 9:251-280, 1990.
↑ Williams, Virginia (2011), Breaking the Coppersmith-Winograd bariéra Archivováno 20. ledna 2013 na Wayback Machine

Odkazy

Strassen V. Gaussova eliminace není optimální // Počet . Matematika / F. Brezzi - Springer Science + Business Media , 1969. - Sv. 13, Iss. 4. - S. 354-356. — ISSN 0029-599X ; 0945-3245 - doi:10.1007/BF02165411