DAA - Multiplicación de matrices de Strassen

En este capítulo, primero discutiremos el método general de multiplicación de matrices y luego discutiremos el algoritmo de multiplicación de matrices de Strassen.

Planteamiento del problema

Consideremos dos matrices X y Y. Queremos calcular la matriz resultanteZ multiplicando X y Y.

Método ingenuo

Primero, discutiremos el método ingenuo y su complejidad. Aquí, estamos calculandoZ = X × Y. Utilizando el método Naive, dos matrices (X y Y) se puede multiplicar si el orden de estas matrices es p × q y q × r. A continuación se muestra el 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]

Complejidad

Aquí, asumimos que las operaciones enteras toman O(1)hora. Hay tresforbucles en este algoritmo y uno está anidado en otro. Por lo tanto, el algoritmo tomaO(n³) tiempo para ejecutar.

Algoritmo de multiplicación de matrices de Strassen

En este contexto, utilizando el algoritmo de multiplicación de matrices de Strassen, el consumo de tiempo se puede mejorar un poco.

La multiplicación de matrices de Strassen solo se puede realizar en square matrices dónde n es un power of 2. El orden de ambas matrices esn × n.

Dividir X, Y y Z en cuatro (n / 2) × (n / 2) matrices como se representa a continuación -

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

Usando el algoritmo de Strassen, calcule lo siguiente:

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

Luego,

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

Análisis

$ T (n) = \ begin {cases} c & if \: n = 1 \\ 7 \: x \: T (\ frac {n} {2}) + d \: x \: n ^ 2 y de otro modo \ end {casos} $, donde c y d son constantes

Usando esta relación de recurrencia, obtenemos $ T (n) = O (n ^ {log7}) $

Por tanto, la complejidad del algoritmo de multiplicación de matrices de Strassen es $ O (n ^ {log7}) $.