DAA - Multiplicação da Matriz de Strassen

Neste capítulo, primeiro discutiremos o método geral de multiplicação de matrizes e, posteriormente, discutiremos o algoritmo de multiplicação de matrizes de Strassen.

Declaração do Problema

Vamos considerar duas matrizes X e Y. Queremos calcular a matriz resultanteZ multiplicando X e Y.

Método Naïve

Primeiro, discutiremos o método ingênuo e sua complexidade. Aqui, estamos calculandoZ = X × Y. Usando o método Naïve, duas matrizes (X e Y) pode ser multiplicado se a ordem dessas matrizes forem p × q e q × r. A seguir está o 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]

Complexidade

Aqui, assumimos que as operações inteiras levam O(1)Tempo. Há trêsforloops neste algoritmo e um está aninhado no outro. Portanto, o algoritmo levaO(n3) hora de executar.

Algoritmo de multiplicação de matriz de Strassen

Nesse contexto, usando o algoritmo de multiplicação Matrix de Strassen, o consumo de tempo pode ser um pouco melhorado.

A multiplicação da matriz de Strassen pode ser realizada apenas em square matrices Onde n é um power of 2. A ordem de ambas as matrizes sãon × n.

Dividir X, Y e Z em quatro matrizes (n / 2) × (n / 2), conforme representado abaixo -

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

Usando o algoritmo de Strassen, calcule o seguinte -

$$ M_ {1} \: \ dois pontos = (A + C) \ vezes (E + F) $$

$$ M_ {2} \: \ dois pontos = (B + D) \ vezes (G + H) $$

$$ M_ {3} \: \ dois pontos = (AD) \ vezes (E + H) $$

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

$$ M_ {5} \: \ dois pontos = (C + D) \ vezes (E) $$

$$ M_ {6} \: \ dois pontos = (A + B) \ vezes (H) $$

$$ M_ {7} \: \ dois pontos = D \ vezes (GE) $$

Então,

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

$$ J \: \ dois pontos = M_ {4} + M_ {6} $$

$$ K \: \ dois pontos = M_ {5} + M_ {7} $$

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

Análise

$ T (n) = \ begin {cases} c & if \: n = 1 \\ 7 \: x \: T (\ frac {n} {2}) + d \: x \: n ^ 2 & caso contrário \ end {cases} $ onde c e d são constantes

Usando essa relação de recorrência, obtemos $ T (n) = O (n ^ {log7}) $

Portanto, a complexidade do algoritmo de multiplicação de matrizes de Strassen é $ O (n ^ {log7}) $.