Гипотеза Штрассена

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

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

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

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

Ссылки

• 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