Гипотеза Штрассена - NiNa.Az

Гипотеза Штрассена — утверждение о том, что для сколь угодно малого ${\displaystyle \varepsilon >0}$ существует алгоритм, при достаточно больших натуральных ${\displaystyle n}$ гарантирующий перемножение двух квадратных матриц размера ${\displaystyle n\times n}$ за ${\displaystyle O(n^{2+\varepsilon })}$ операций.

Выдвинута Фолькером Штрассеном в 1969 году; по состоянию на 2023 год остаётся одной из важных нерешенных проблем линейной алгебры и теории сложности вычислений.

Задача перемножения двух больших квадратных матриц часто встречается в приложениях и её ускорение этой операции имеет большое практическое значение. Поскольку при умножении матриц надо вычислить ${\displaystyle n^{2}}$ новых, вообще говоря, разных значений элементов матриц, это нельзя сделать менее, чем за ${\displaystyle O(n^{2})}$ операций. Стандартный алгоритм согласно определению умножения матриц требует ${\displaystyle O(n^{3})}$ операций. Алгоритм Штрассена, опубликованный в 1969 году, требовал ${\displaystyle {O}(n^{\log _{2}7})\approx {O}(n^{2,81})}$ умножений; в той же работе выдвинута гипотеза о возможности перемножать матрицы со скоростью, сколь угодно близкой к ${\displaystyle O(n^{2})}$.

В 1990 году было доказано, что достаточно ${\displaystyle {O}(n^{2,376})}$ операций (алгоритм Копперсмита — Винограда). Этот алгоритм имеет теоретическое значение и не может использоваться на практике, поскольку реально ускоряет умножение только для астрономически больших матриц. В дальнейшем было получено несколько очень незначительных улучшений последней оценки на базе того же метода. Это позволяет предположить существование «барьера Копперсмита — Винограда» в теоретических оценках сложности этой задачи, хотя большинство исследователей полагает, что гипотеза Штрассена верна. Показатель степени в практических алгоритмах был несколько улучшен по сравнению с показателем алгоритма Штрассена, но пока он остаётся существенно больше показателя алгоритма Копперсмита — Винограда.

Примечания

1. Strassen, Volker, Gaussian Elimination is not Optimal, Numer. Math. 13, p. 354—356, 1969
2. Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9:251-280, 1990
3. Williams, Virginia (2011), Breaking the Coppersmith-Winograd barrier Архивная копия от 20 января 2013 на Wayback Machine

Ссылки

• Strassen V. Gaussian Elimination is not Optimal (англ.) // Numerische Mathematik / F. Brezzi — Springer Science+Business Media, 1969. — Vol. 13, Iss. 4. — P. 354—356. — ISSN 0029-599X; 0945-3245 — doi:10.1007/BF02165411