Подразделы

Другие разделы

Дата и время

01/04/2025 09:47:54

Авторизация

Матрицы

Представление матриц Операции над матрицами LU-разложение и вычисление обратной матрицы Умножение матриц Алгоритм умножения матриц Штрассена

Алгоритм умножения матриц Штрассена

Время его работы равно $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):

${: (P_1 =a*(f-h)),(P_2=(a+b)*h),(P_3=(c+d)*e),(P_4=d*(g-e)),(P_5=(a+d)*(e+h)),(P_6=(b-d)*(g+h)),(P_7=(a-c)*(e+f)) :} => {: (r=P_5+P_4-P_2+P_6),(s=P_1+P_2),(t=P_3+P_4),(u=P_5+P_1-P_3-P_7) :}$

Мы получаем рекуррентное соотношение $T(n)=7T(n//2)+Theta(n^2)$ , которое имеет решение $T(n)=Theta(n^{log_2 7})$

Существует модификация (алгоритм Винограда - Штрассена), для которой требуется 7 умножений и 15 сложений.