Algoritmo de Strassen - Slides

Prévia do material em texto

Algoritmo de Strassen
GABRIEL SOARES CARDOSO NETO
TABITA LOPES RIBEIRO
Matriz
Matrizes são estruturas numéricas em formato de tabela que possuem m linhas e n colunas
A=
Multiplicação de Matrizes
	 A 		 • 		 B = 	 C
8 multiplicações
4 adições
1. 	n = A • linhas
2. 	seja C uma nova matriz n x n
3. 	for i = 1 to n
4. 		for j = 1 to n
5. 			 =0
6. 				for k = 1 to n
7. 					 = = • 
8. 	retorne c;
Volker Strassen
Desenvolve em 1969 o “Fast-asymptotically matrix multiplication”. É util na prática ao lidar com matrizes grandes.
Para que o algoritmo possa ser aplicado, as matrizes devem ter dimensão x .
Ele ainda é vivo e professor da Universidade de Constança na Alemanha.
O algoritmo:
 = ( + ) • ( + )
 = ( + ) • 
 = • ( - )
 = • ( - )
 = ( + ) • 
 = ( - ) • ( + )
 = ( - ) • ( + )
7 multiplicações
6 adições
4 subtrações
Agora aplicamos os resultados obtidos anteriormente para saber o valor de cada element de C:
 = + - + 
 = + 
 = + 
 = - + + 
6 adições
2 subtrações
Pseudo Código para algoritmo de Strassen:
Strassen(A, B)
1. se n = 1 Output A × B
2. senao
3. Calcule A11, B11, . . ., A22, B22 // onde  m = n/2
4. P1   ← Strassen(A11, B12 − B22)
5. P2   ← Strassen(A11 + A12, B22)
6. P3   ← Strassen(A21 + A22, B11)
7. P4   ← Strassen(A22, B21 − B11)
8. P5   ← Strassen(A11 + A22, B11 + B22)
9. P6   ← Strassen(A12 − A22, B21 + B22)
10. P7 ← Strassen(A11 − A21, B11 + B12)
11. C11 ← P5 + P4 − P2 + P6
12. C12 ← P1 + P2
13. C21 ← P3 + P4
14. C22 ← P1 + P5 − P3 − P7
15. Output C
16. End se
17. End
Pseudo Código para algoritmo de Strassen:
Strassen(A, B)
1. se n = 1 Output A × B
2. senao
3. Calcule A11, B11, . . ., A22, B22 // onde  m = n/2
4. P1   ← Strassen(A11, B12 − B22)
5. P2   ← Strassen(A11 + A12, B22)
6. P3   ← Strassen(A21 + A22, B11)
7. P4   ← Strassen(A22, B21 − B11)
8. P5   ← Strassen(A11 + A22, B11 + B22)
9. P6   ← Strassen(A12 − A22, B21 + B22)
10. P7 ← Strassen(A11 − A21, B11 + B12)
11. C11 ← P5 + P4 − P2 + P6
12. C12 ← P1 + P2
13. C21 ← P3 + P4
14. C22 ← P1 + P5 − P3 − P7
15. Output C
16. End se
17. End
Tempo constante.
Complexidade do algoritmo :
Utilizando o metodo mestre temos:  
Logo, a complexidade do algoritmo de Strassen e:
Obrigado
 
 
	 
 
.MsftOfcResponsive_Fill_e7ced7 {
 fill:#E7CED7; 
}