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³) время выполнять.

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

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

Умножение матрицы Штрассена может быть выполнено только на square matrices где n это power of 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} $

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

$$ M_ {1} \: \ двоеточие = (A + C) \ times (E + F) $$

$$ M_ {2} \: \ двоеточие = (B + D) \ times (G + H) $$

$$ M_ {3} \: \ двоеточие = (AD) \ times (E + H) $$

$$ M_ {4} \: \ двоеточие = A \ times (FH) $$

$$ M_ {5} \: \ двоеточие = (C + D) \ times (E) $$

$$ M_ {6} \: \ двоеточие = (A + B) \ times (H) $$

$$ M_ {7} \: \ двоеточие = D \ times (GE) $$

Затем,

$$ I \: \ двоеточие = M_ {2} + M_ {3} - M_ {6} - M_ {7} $$

$$ J \: \ двоеточие = M_ {4} + M_ {6} $$

$$ K \: \ двоеточие = M_ {5} + M_ {7} $$