DAA - Multiplication matricielle de Strassen

Dans ce chapitre, nous discuterons d'abord de la méthode générale de multiplication matricielle et plus tard, nous discuterons de l'algorithme de multiplication matricielle de Strassen.

Énoncé du problème

Considérons deux matrices X et Y. Nous voulons calculer la matrice résultanteZ en multipliant X et Y.

Méthode naïve

Tout d'abord, nous discuterons de la méthode naïve et de sa complexité. Ici, nous calculonsZ = X × Y. En utilisant la méthode Naïve, deux matrices (X et Y) peut être multipliée si l'ordre de ces matrices est p × q et q × r. Voici l'algorithme.

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]

Complexité

Ici, nous supposons que les opérations entières prennent O(1)temps. Il ya troisforboucles dans cet algorithme et l'une est imbriquée dans l'autre. Par conséquent, l'algorithme prendO(n3) temps à exécuter.

Algorithme de multiplication matricielle de Strassen

Dans ce contexte, en utilisant l'algorithme de multiplication Matrix de Strassen, la consommation de temps peut être un peu améliorée.

La multiplication de la matrice de Strassen ne peut être effectuée que sur square matricesn est un power of 2. L'ordre des deux matrices estn × n.

Diviser X, Y et Z en quatre matrices (n / 2) × (n / 2) comme représenté ci-dessous -

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

En utilisant l'algorithme de Strassen, calculez ce qui suit -

$$ M_ {1} \: \ deux points = (A + C) \ fois (E + F) $$

$$ M_ {2} \: \ deux points = (B + D) \ fois (G + H) $$

$$ M_ {3} \: \ deux points = (AD) \ fois (E + H) $$

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

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

$$ M_ {6} \: \ deux points = (A + B) \ fois (H) $$

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

Ensuite,

$$ 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} $$

Une analyse

$ T (n) = \ begin {cases} c & if \: n = 1 \\ 7 \: x \: T (\ frac {n} {2}) + d \: x \: n ^ 2 & sinon \ end {cases} $ où c et d sont des constantes

En utilisant cette relation de récurrence, nous obtenons $ T (n) = O (n ^ {log7}) $

Par conséquent, la complexité de l'algorithme de multiplication matricielle de Strassen est $ O (n ^ {log7}) $.