Considere as matrizes quadradas X e Y com n linhas e n colunas cada

No produto X . Y = Z temos que Z também é uma matriz quadrada de dimensão n

Além disso, Z_ij = \sum_k=1^n X_ik . Y_kj

Exemplo com desenho esquemático

Detalhe: Nesta análise vamos usar n para determinar a eficiência dos algoritmos estudados, mas vale lembrar que as matrizes envolvidas tem tamanho n^2. Portanto, apenas para ler a entrada já é necessário gastar tempo Theta(n^2).



Exemplo:

(a b)  (e f) = (ae + bg		af + bh)
(c d)  (g h)   (ce + dg 	cf + dh)

Notem que a fórmula Z_ij = \sum_k=1^n X_ik . Y_kj sugere um algoritmo Theta(n^3) para multiplicar matrizes

 - Isso porque calcular Z_ij leva tempo Theta(n) para qualquer par (i, j) e existem n^2 pares na matriz Z


 
Ideia: aplicar o método de divisão e conquista

Dividir X e Y em quatro matrizes

X = (A B) 	Y = (E F)
	(C D)		(G H)

sendo que A, ..., H são matrizes quadradas com n/2 linhas e colunas.

Além disso, 

X . Y = (AE + BG 	AF + BH)
		(CE + DG	CF + DH)



Isso sugere o seguinte algoritmo recursivo:

 - Dados X e Y na entrada
 
 - Se X e Y tem tamanho 1 então devolva o produto dos seus elementos
 
 - Caso contrário, divida X e Y nas 8 matrizes com metade do tamanho
 
 - Calcule recursivamente os 8 produtos envolvendo essas matrizes
 
 - Faça as somas necessárias com os resultados dos produtos (em tempo O(n^2))
 
 - Devolva a matriz resultante
 
Recorrência:

T(n) = 8 T(n/2) + c * n^2 = O(n^3)



Algoritmo de Strassen precisa apenas de 7 chamadas recursivas

T(n) = 7 T(n/2) + c * n^2 = O(n^log_2 7) ~= O(n^2,807)



P1 = A(F - H)
P2 = (A + B)H
P3 = (C + D)E
P4 = D(G - E)
P5 = (A + D)(E + H)
P6 = (B - D)(G + H)
P7 = (A - C)(E + F)


X . Y = ( P5 + P4 - P2 + P6 	P1 + P2		 	  )
		( P3 + P4				P1 + P5 - P3 - P7 )