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

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

Задача перемножения двух больших квадратных матриц является трудоёмкой и часто встречается в приложениях. Таким образом, ускорение этой операции имеет большое практическое значение. Поскольку при умножении матриц надо вычислить ${\displaystyle n^{2}}$ новых, вообще говоря, разных значений элементов матриц, это нельзя сделать менее, чем за ${\displaystyle O(n^{2})}$ операций. Стандартный алгоритм согласно определению умножения матриц требует ${\displaystyle O(n^{3})}$ операций. В 1969 году немецкий математик Фолькер Штрассен предложил первый более быстрый алгоритм[1], который требовал ${\displaystyle {O}(n^{\log _{2}7})\approx {O}(n^{2,81})}$ умножений. Он же выдвинул гипотезу о том, что перемножать матрицы можно ещё быстрее. В 1990 году было доказано, что достаточно ${\displaystyle {O}(n^{2,376})}$ операций (алгоритм Копперсмита — Винограда)[2] . Этот алгоритм имеет теоретическое значение и не может использоваться на практике, поскольку реально ускоряет умножение только для астрономически больших матриц. В дальнейшем было получено несколько очень незначительных улучшений последней оценки на базе того же метода[3]. Это позволяет говорить о существовании «барьера Копперсмита — Винограда» в теоретических оценках сложности этой задачи, хотя большинство исследователей полагает, что гипотеза Штрассена верна. Показатель степени в практических алгоритмах был несколько улучшен по сравнению с показателем алгоритма Штрассена, но пока он остаётся существенно больше показателя алгоритма Копперсмита — Винограда.

• Алгоритм Штрассена
• Умножение матриц

• Strassen V. Gaussian Elimination is not Optimal (англ.) // 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