Время его работы равно `Theta(n^{log_2 7}) = O(n^{2.81})`. При достаточно больших значениях `n>500` этот алгоритм
работает быстрее обычного алгоритма умножения. Для разрежённых матриц этот алгоритм дает больший эффект, чем для плотных.
Алгоритм Штрассена можно рассматривать как применение метода декомпозиции
--
Предположим, что мы хотим вычислить произведение `C = AB`, где каждая из матриц имеет размер `n xx n`. Считая,
что `n` является точной степенью 2, поделим каждую из матриц на четыре матрицы
размером `n//2 xx n//2` и перепишем выражение следующим образом:
`((r,s),(t,u))=((a,b),(c,d))((e,f),(g,h))`
где элементы матрицы вычисляются по формулам: `r=ae+bg`, `s=af+bh`, `t=ce+dh`, `u=cf+dh`.
Каждое из этих четырех уравнений требует двух умножений матриц размера `n//2 xx n//2` и сложения получившихся произведений.
--
Мы получаем следующее рекуррентное соотношение для времени такого алгоритма при умножении матриц размера
`n xx n`:
`T(n)=8T(n//2)+Theta(n^2)`
Это рекуррентное соотношение имеет решение `T(n) = Theta(n^3)`, так что этот метод получается не быстрее, чем обычное умножение
матриц.
--
Штрассен предложил способ сократить количество умножений до 7, выполняя операции над подматрицами, которые
вычисляется при помощи сложения или вычитания некоторых из подматриц `A` и подматриц `B` (количество сложений возрастает до 18):
Мы получаем рекуррентное соотношение `T(n)=7T(n//2)+Theta(n^2)`, которое имеет решение `T(n)=Theta(n^{log_2 7})`
Существует модификация (алгоритм Винограда - Штрассена), для которой требуется 7 умножений и 15 сложений.
В 1990 году Копперсмит и Виноград опубликовали алгоритм, асимптотическая сложность которого составляла `O(n^{2.3755})`.
На практике этот алгоритм не используется, так как он имеет очень большую константу пропорциональности и
начинает выигрывать в быстродействии у других известных алгоритмов только для матриц, размер которых превышает
память современных компьютеров.
Начало
Учебные материалы
Матрицы