DAA — матричное умножение Штрассена

В этой главе сначала мы обсудим общий метод умножения матриц, а позже мы обсудим алгоритм умножения матриц Штрассена.

Постановка задачи

Рассмотрим две матрицы X и Y. Мы хотим вычислить результирующую матрицу Z , умножив X и Y.

Наивный метод

Сначала обсудим наивный метод и его сложность. Здесь мы вычисляем Z = X × Y. Используя наивный метод, две матрицы ( X и Y ) могут быть умножены, если порядок этих матриц p × q и q × r . Ниже приводится алгоритм.

Algorithm: Matrix-Multiplication (X, Y, Z) 
for i = 1 to p do 
   for j = 1 to r do 
      Z[i,j] := 0 
      for k = 1 to q do 
         Z[i,j] := Z[i,j] + X[i,k] × Y[k,j] 

сложность

Здесь мы предполагаем, что целочисленные операции занимают O (1) времени. В этом алгоритме есть три цикла for, и один вложен в другой. Следовательно, алгоритм занимает O (n ³ ) времени для выполнения.

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

В этом контексте, используя алгоритм умножения матриц Штрассена, можно немного улучшить потребление времени.

Умножение матрицы Штрассена может быть выполнено только на квадратных матрицах, где n — степень 2 . Порядок обеих матриц n × n .

Разделите X , Y и Z на четыре (n / 2) × (n / 2) матрицы, как показано ниже —

$Z = \ begin {bmatrix} I & J \\ K & L \ end {bmatrix}$ $X = \ begin {bmatrix} A & B \\ C & D \ end {bmatrix}$ и $Y = \ begin {bmatrix} E & F \\ G & H \ end {bmatrix}$

Используя алгоритм Штрассена, вычислите следующее:

M1 colon=(A+C) times(E+F) $$M_ {1} \: \ colon = (A + C) \ times (E + F)$$

M2 colon=(B+D) times(G+H) $$M_ {2} \: \ colon = (B + D) \ times (G + H)$$

M3 colon=(AD) times(E+H) $$M_ {3} \: \ colon = (AD) \ times (E + H)$$

M4 colon=A times(FH) $$M_ {4} \: \ colon = A \ times (FH)$$

M5 colon=(C+D) times(E) $$M_ {5} \: \ colon = (C + D) \ times (E)$$

M6 colon=(A+B) times(H) $$M_ {6} \: \ colon = (A + B) \ times (H)$$

M7 colon=D times(GE) $$M_ {7} \: \ colon = D \ times (GE)$$

Затем,

I colon=M2+M3−M6−M7 $$I \: \ colon = M_ {2} + M_ {3} - M_ {6} - M_ {7}$$

J colon=M4+M6 $$J \: \ colon = M_ {4} + M_ {6}$$

K colon=M5+M7 $$K \: \ colon = M_ {5} + M_ {7}$$

L colon=M1−M3−M4−M5 $$L \: \ colon = M_ {1} - M_ {3} - M_ {4} - M_ {5}$$

Анализ

$T (n) = \ begin {case} c & if \: n = 1 \\ 7 \: x \: T (\ frac {n} {2}) + d \: x \: n ^ 2 & в противном случае \ end {case}$, где c и d — константы

Используя это рекуррентное соотношение, мы получаем $T (n) = O (n ^ {log7})$

Следовательно, сложность алгоритма умножения матриц Штрассена составляет $O (n ^ {log7})$.