DAA - Moltiplicazione della matrice di Strassen

In questo capitolo discuteremo prima il metodo generale di moltiplicazione di matrici e successivamente discuteremo l'algoritmo di moltiplicazione di matrici di Strassen.

Dichiarazione problema

Consideriamo due matrici X e Y. Vogliamo calcolare la matrice risultanteZ moltiplicando X e Y.

Metodo naïve

Per prima cosa, discuteremo del metodo ingenuo e della sua complessità. Qui stiamo calcolandoZ = X × Y. Utilizzando il metodo Naïve, due matrici (X e Y) può essere moltiplicato se l'ordine di queste matrici è p × q e q × r. Di seguito è riportato l'algoritmo.

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]

Complessità

Qui, assumiamo che le operazioni su interi richiedano O(1)tempo. Ce ne sono treforloop in questo algoritmo e uno è annidato in un altro. Quindi, l'algoritmo accettaO(n³) tempo di eseguire.

Algoritmo di moltiplicazione della matrice di Strassen

In questo contesto, utilizzando l'algoritmo di moltiplicazione Matrix di Strassen, il consumo di tempo può essere leggermente migliorato.

La moltiplicazione Matrix di Strassen può essere eseguita solo su square matrices dove n è un power of 2. L'ordine di entrambe le matrici èn × n.

Dividere X, Y e Z in quattro (n / 2) × (n / 2) matrici come rappresentato di seguito -

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

Utilizzando l'algoritmo di Strassen, calcola quanto segue:

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

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

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

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

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

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

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

Poi,

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

$$ J \: \ due punti = M_ {4} + M_ {6} $$

$$ K \: \ due punti = M_ {5} + M_ {7} $$

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

Analisi

$ T (n) = \ begin {cases} c & if \: n = 1 \\ 7 \: x \: T (\ frac {n} {2}) + d \: x \: n ^ 2 & altrimenti \ end {case} $ dove c e d sono costanti

Usando questa relazione di ricorrenza, otteniamo $ T (n) = O (n ^ {log7}) $

Quindi, la complessità dell'algoritmo di moltiplicazione di matrici di Strassen è $ O (n ^ {log7}) $.