DAA - mnożenie macierzy Strassena

W tym rozdziale najpierw omówimy ogólną metodę mnożenia macierzy, a później omówimy algorytm mnożenia macierzy Strassena.

Stwierdzenie problemu

Rozważmy dwie macierze X i Y. Chcemy obliczyć wynikową macierzZ przez pomnożenie X i Y.

Metoda naiwna

Najpierw omówimy naiwną metodę i jej złożoność. Tutaj obliczamyZ = X × Y. Używając metody Naïve, dwie macierze (X i Y) można pomnożyć, jeśli kolejność tych macierzy wynosi p × q i q × r. Oto algorytm.

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]

Złożoność

Tutaj zakładamy, że są wykonywane operacje na liczbach całkowitych O(1)czas. Są trzyforpętle w tym algorytmie, a jedna jest zagnieżdżona w innym. Stąd algorytm przyjmujeO(n³) czas na wykonanie.

Algorytm mnożenia macierzy Strassena

W tym kontekście, używając algorytmu mnożenia Matrix Strassena, można nieco poprawić zużycie czasu.

Mnożenie Matrix Strassena można wykonać tylko na square matrices gdzie n jest power of 2. Kolejność obu macierzy ton × n.

Podzielić X, Y i Z na cztery (n / 2) × (n / 2) macierze, jak pokazano poniżej -

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

Korzystając z algorytmu Strassena, obliczyć następujące -

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

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

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

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

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

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

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

Następnie,

$$ I \: \ colon = M_ {2} + M_ {3} - M_ {6} - M_ {7} $$

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

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

$$ L \: \ colon = M_ {1} - M_ {3} - M_ {4} - M_ {5} $$

Analiza

$ T (n) = \ begin {cases} c & if \: n = 1 \\ 7 \: x \: T (\ frac {n} {2}) + d \: x \: n ^ 2 i w przeciwnym razie \ end {cases} $, gdzie c i d są stałymi

Korzystając z tej relacji powtarzania, otrzymujemy $ T (n) = O (n ^ {log7}) $

Stąd złożoność algorytmu mnożenia macierzy Strassena wynosi $ O (n ^ {log7}) $.