Upload
diego-lusa
View
252
Download
3
Embed Size (px)
DESCRIPTION
A apresentação descreve o problema da multiplicação entre matrizes, descrevendo as principais características e métodos de resolução. São abortados os métodos tradicional, de Strassen, Winograd e Coppersmith-Winograd
Citation preview
MatrizesMatrizes e a Computacao
Metodos para multiplicacao de matrizesConsideracoes finais
Multiplicacao de MatrizesDo O(n3) ao O(n2)
Diego Antonio Lusa
Universidade de Passo Fundo
3 de julho de 2014
1 / 29
MatrizesMatrizes e a Computacao
Metodos para multiplicacao de matrizesConsideracoes finais
Roteiro
1 MatrizesOperacoes envolvendo matrizes
2 Matrizes e a Computacao
3 Metodos para multiplicacao de matrizesTradicionalStrassenWinogradCoppersmith-WinogradConsideracoes acerca dos metodos
4 Consideracoes finais
2 / 29
MatrizesMatrizes e a Computacao
Metodos para multiplicacao de matrizesConsideracoes finais
Operacoes envolvendo matrizes
Matrizes
Arranjo retangular composto por m linhas e n colunas;
Cada elemento e identificado em termos da linha e coluna aqual pertence;
Quando o numero de colunas m for igual ao numeros delinhas n, a matriz e dita quadrada de ordem n;
Matriz generica
M3×4 =
m11 m12 m13 m14
m21 m22 m23 m24
m31 m32 m33 m34
3 / 29
MatrizesMatrizes e a Computacao
Metodos para multiplicacao de matrizesConsideracoes finais
Operacoes envolvendo matrizes
Matrizes Quadradas
Matrizes quadradas tem uma diagonal principal e umadiagonal secundaria;
Diagonal principal e secundaria
M3×3
12 30 4013 15 4814 50 22
Mpri
12 . . . . . .. . . 15 . . .. . . . . . 22
Msec
. . . . . . 40. . . 15 . . .14 . . . . . .
4 / 29
MatrizesMatrizes e a Computacao
Metodos para multiplicacao de matrizesConsideracoes finais
Operacoes envolvendo matrizes
Matriz Identidade
A matriz identidade possui todos os elementos da diagonalprincipal iguais a 1;
Os demais elementos sao todos iguais a 0 (zero);
Caracteriza-se por ser o elemento neutro em operacoes demultiplicacao;
Matriz Identidade
I3 =
1 0 00 1 00 0 1
5 / 29
MatrizesMatrizes e a Computacao
Metodos para multiplicacao de matrizesConsideracoes finais
Operacoes envolvendo matrizes
Representacao Computacional
Representadas atraves de tipos de dados estruturados;
Os arranjos sao as estruturas comumente utilizadas paraarmazenar matrizes;
Algoritmo generico
1. define A[2][2];
2. A[1][2] = 3;
6 / 29
MatrizesMatrizes e a Computacao
Metodos para multiplicacao de matrizesConsideracoes finais
Operacoes envolvendo matrizes
Operacoes
Pode-se aplicar operacoes como soma, subtracao emultiplicacao em matrizes;
A soma requer o mesmo numero de linhas e colunas emambas as matrizes;
A complexidade assintotica de uma operacao de soma e iguala O(n2);
Considerando-se duas matrizes quaisquer A e B, a operacaode adicao C = A + B e definida por:
Definicao matematica da soma
cij = aij + bij
7 / 29
MatrizesMatrizes e a Computacao
Metodos para multiplicacao de matrizesConsideracoes finais
Operacoes envolvendo matrizes
Operacoes - Soma
Exemplo
(I) A2×2 =
[1 23 4
](II) B2×2 =
[5 −6−8 9
](III) C2×2 = A2×2 + B2×2 =
[1 + 5 2− 63− 8 4 + 9
](IV) C2×2 =
[6 −4−5 13
]
8 / 29
MatrizesMatrizes e a Computacao
Metodos para multiplicacao de matrizesConsideracoes finais
Operacoes envolvendo matrizes
Operacoes - Multiplicacao
A multiplicacao requer que o numero de colunas da primeiramatriz seja igual ao numero de linhas da segunda;
A complexidade assintotica de uma operacao de multiplicacaoe igual a O(n3);
A multiplicacao de matrizes e associativa, mas nao ecomutativa. A× B × C e identico a A× (B × C ). Contudo,A× B e diferente de B × A;
Definicao matematica da multiplicacao
pij =a∑
k=1
mik × nkj
9 / 29
MatrizesMatrizes e a Computacao
Metodos para multiplicacao de matrizesConsideracoes finais
Operacoes envolvendo matrizes
Operacoes - Multiplicacao
Exemplo
(I) M2×2 =
[1 23 4
](II) N2×3 =
[5 6 78 9 10
](III) P2×3 = M2×2 × N2×3
(IV) P2×3 =
[1× 5 + 2× 8 1× 6 + 2× 9 1× 7 + 2× 103× 5 + 4× 8 3× 6 + 4× 9 3× 7 + 4× 10
](V) P2×3 =
[21 24 2747 54 61
]
10 / 29
MatrizesMatrizes e a Computacao
Metodos para multiplicacao de matrizesConsideracoes finais
Matrizes e a Computacao
A multiplicacao de matrizes e uma das operacoes mais basicaspara a computacao numerica e simbolica;
Aplica-se a diversos problemas de algebra linear, fatoracaopolinomial, transformacoes geometricas, entre outros;
O calculo do produto entre matrizes e uma operacao queapresenta complexidade assintotica O(n3);
Por muito tempo pensou-se que nao seria possıvel reduzir estecomplexidade;
11 / 29
MatrizesMatrizes e a Computacao
Metodos para multiplicacao de matrizesConsideracoes finais
TradicionalStrassenWinogradCoppersmith-WinogradConsideracoes acerca dos metodos
Metodos para multiplicacao de matrizes
Por meio de pesquisas, demostrou-se que seria possıvel obtercoeficientes de complexidade menores que O(n3);
Neste contexto, destacam-se os metodos de:
StrassenWinogradCoppersmith-Winograd
12 / 29
MatrizesMatrizes e a Computacao
Metodos para multiplicacao de matrizesConsideracoes finais
TradicionalStrassenWinogradCoppersmith-WinogradConsideracoes acerca dos metodos
Metodo Tradicional
Possui complexidade assintotica O(n3);
Ate 1960, era considerado o algoritmo otimo;
Caracterısticas
Executa (n3) multiplicacoes;
Executa n2(n − 1) somas;
13 / 29
MatrizesMatrizes e a Computacao
Metodos para multiplicacao de matrizesConsideracoes finais
TradicionalStrassenWinogradCoppersmith-WinogradConsideracoes acerca dos metodos
Pseudo-algoritmo
1. define A[2][2];
2. define B[2][3];
3. define C[2][3];
4. para cada i de 1 a 2 faca:
5. para cada j de 1 a 3 faca:
6. para cada k de 1 a 2 faca:
7. C[i][j] = C[i][j] + A[i][k]*B[k][j];
8. fim para;
9. fim para;
10. fim para;
14 / 29
MatrizesMatrizes e a Computacao
Metodos para multiplicacao de matrizesConsideracoes finais
TradicionalStrassenWinogradCoppersmith-WinogradConsideracoes acerca dos metodos
Metodo de Strassen
Desenvolvido pelo matematico alemao Volker Strassen em1969;
Obteve complexidade assintotica O(nlog 7) ;
Serviu de referencia para trabalhos posteriores;
Enquanto o metodo tradicional requer 8 multiplicacoes e 4somas para multiplicar duas matrizes de ordem 2, o metodode Strassem executa 7 multiplicacoes e 18 somas/subtracoes;
Requer que a ordem das matrizes seja quadrada;
Caracterısticas
Executa 7(n2
)3multiplicacoes;
Executa (11n − 4)×(n2
4
)somas;
15 / 29
MatrizesMatrizes e a Computacao
Metodos para multiplicacao de matrizesConsideracoes finais
TradicionalStrassenWinogradCoppersmith-WinogradConsideracoes acerca dos metodos
Matrizes de origem
A3
1 2 34 5 67 8 9
B3
1 4 72 5 83 6 9
Tornando a ordem quadratica
A4
1 2 3 04 5 6 07 8 9 00 0 0 0
B4
1 4 7 02 5 8 03 6 9 00 0 0 0
16 / 29
MatrizesMatrizes e a Computacao
Metodos para multiplicacao de matrizesConsideracoes finais
TradicionalStrassenWinogradCoppersmith-WinogradConsideracoes acerca dos metodos
Etapa 1 - Divisao
A11
[1 24 5
]A12
[3 06 0
]A21
[7 80 0
]A22
[9 00 0
]
B11
[1 42 5
]B12
[7 08 0
]B21
[3 60 0
]B22
[9 00 0
]
17 / 29
MatrizesMatrizes e a Computacao
Metodos para multiplicacao de matrizesConsideracoes finais
TradicionalStrassenWinogradCoppersmith-WinogradConsideracoes acerca dos metodos
Etapas 2 - Calculo dos subproblemas
P1 = (A11 + A22)× (B11 + B22)
P2 = (A21 + A22)× B11
P3 = A11 × (B12 − B22)
P4 = A22 × (B21 − B11)
P5 = (A11 + A12)× B22
P6 = (A21 − A11)× (B11 + B12)
P7 = (A12 − A22)× (B21 + B22)
18 / 29
MatrizesMatrizes e a Computacao
Metodos para multiplicacao de matrizesConsideracoes finais
TradicionalStrassenWinogradCoppersmith-WinogradConsideracoes acerca dos metodos
Etapa 3 - Conquista
C11 = P1 + P4 − P5 + P7
C12 = P3 + P5
C21 = P2 + P4
C22 = P1 + P3 − P2 + P6
19 / 29
MatrizesMatrizes e a Computacao
Metodos para multiplicacao de matrizesConsideracoes finais
TradicionalStrassenWinogradCoppersmith-WinogradConsideracoes acerca dos metodos
Resultado
C3 =
[C11 C12
C21 C22
]→
[
14 3232 77
] [50 0
122 0
][
50 1220 0
] [194 0
0 0
]
C3 =
14 32 50 032 77 122 050 122 194 00 0 0 0
C3 =
14 32 5032 77 12250 122 194
20 / 29
MatrizesMatrizes e a Computacao
Metodos para multiplicacao de matrizesConsideracoes finais
TradicionalStrassenWinogradCoppersmith-WinogradConsideracoes acerca dos metodos
Metodos de Winograd
Criado por Shmuel Winograd, em 1987;
Possui a mesma complexidade assintotica que o metodo deStrassen;
Requer um numero menor de somas e subtracoes secomparado ao metodo de Strassen.
Em contrapartida, necessita de um numero maior de passos;
Caracterısticas
Executa 7(n2
)3multiplicacoes;
Executa(
19n3
8
)− n2 somas/subtracoes;
21 / 29
MatrizesMatrizes e a Computacao
Metodos para multiplicacao de matrizesConsideracoes finais
TradicionalStrassenWinogradCoppersmith-WinogradConsideracoes acerca dos metodos
Etapas do processo
S1 = A21 + A22
S2 = S1 − A11
S3 = A11 − A21
S4 = A12 − S2
T1 = B12 − B11
T2 = B22 − T1
T3 = B22 − B12
T4 = B21 − T2
22 / 29
MatrizesMatrizes e a Computacao
Metodos para multiplicacao de matrizesConsideracoes finais
TradicionalStrassenWinogradCoppersmith-WinogradConsideracoes acerca dos metodos
Etapas do processo
P1 = A11 × B11
P2 = A12 × B21
P3 = S1 × T1
P4 = S2 × T2
P5 = S3 × T3
P6 = S4 × B22
P7 = A22 × T4
23 / 29
MatrizesMatrizes e a Computacao
Metodos para multiplicacao de matrizesConsideracoes finais
TradicionalStrassenWinogradCoppersmith-WinogradConsideracoes acerca dos metodos
Etapas do processo
U1 = P1 + P2
U2 = P1 + P4
U3 = U2 + P5
U4 = U3 + P7
U5 = U3 + P3
U6 = U2 + P3
U7 = U6 + P6
C11 = U1
C12 = U7
C21 = U4
C22 = U5
24 / 29
MatrizesMatrizes e a Computacao
Metodos para multiplicacao de matrizesConsideracoes finais
TradicionalStrassenWinogradCoppersmith-WinogradConsideracoes acerca dos metodos
Metodo Coppersmith-Winograd
Metodo criado por Don Coppersmith e Shmuel Winograd em1987;
Foi o primeiro algoritmo da historia a obter coeficiente decomplexidade inferior a 2.5;
A complexidade do metodo e O(n2.376);
Permaneceu por duas decadas como o metodo mais eficienteconhecido;
Maior contribuicao teorica do que pratica;
25 / 29
MatrizesMatrizes e a Computacao
Metodos para multiplicacao de matrizesConsideracoes finais
TradicionalStrassenWinogradCoppersmith-WinogradConsideracoes acerca dos metodos
Consideracoes acerca dos metodos
O algoritmo de Strassen teve grande importancia na evolucaodos metodos;
Contudo, o metodo de Strassen apresenta certa instabilidadenumerica e contem um fator oculto de complexidadeconsideravel;
As submatrizes necessarias ao processo consomem espaco;
O metodo de Don Coppersmith e Shmuel Winograd tevemaior contribuicao teorica do que pratica;
Em 2012, no trabalho “Multiplying matrices faster thanCoppersmith-Winograd”, Virginia Vassileska Williams provouter alcancado coeficiente de complexidade igual a O(n2.3729);
O Metodo Tradicional continua a ter ampla aplicabilidade;
26 / 29
MatrizesMatrizes e a Computacao
Metodos para multiplicacao de matrizesConsideracoes finais
TradicionalStrassenWinogradCoppersmith-WinogradConsideracoes acerca dos metodos
Evolucao dos coeficientes de complexidade para o problema docalculo do produto entre matrizes
Ano Autor(es) Complexidade1969 Strassen log2 8 ≈ 2.8071979 Bini, Capovani, Romani e Lotti’s 3 log12 10 ≈ 2.7791981 Schonhage log6 5 ≈ 2.6941986 Strassen (laser method) 2.481989 Coppersmith e Winograd 2.3762012 Virginia Vassilevska Williams 2.3729
27 / 29
MatrizesMatrizes e a Computacao
Metodos para multiplicacao de matrizesConsideracoes finais
TradicionalStrassenWinogradCoppersmith-WinogradConsideracoes acerca dos metodos
Comparacao entre os metodos em relacao ao numero de operacoesde somas e multiplicacoes necessarias
Tam. (n) Tradicional Strassen WinogradMultip. Somas Multip. Somas Multip. Somas
2 8 4 7 18 7 154 64 48 56 160 56 1368 512 448 448 1.344 448 1.152
16 4.096 3.840 3.584 11.008 3.584 9.47232 32.768 31.744 28.672 89.088 28.672 76.80064 262.144 258.048 229.376 716.800 229.376 618.496
128 2.097.152 2.080.768 1.835.008 5.750.784 1.835.008 4.964.352256 16.777.216 16.711.680 14.680.064 46.071.808 14.680.064 39.780.352
28 / 29
MatrizesMatrizes e a Computacao
Metodos para multiplicacao de matrizesConsideracoes finais
Consideracoes finais
O calculo do produto entre matrizes e umas das operacoesmais basicas tanto para a matematica quanto para acomputacao;O trabalho de Volker Strassen foi muito importante naspesquisas por metodos mais eficientes;O metodo mais adequado para o calculo do produto entrematrizes depende do contexto;A aplicacao do metodo de Strassen em matrizes muitopequenas talvez nao seja mais adequada;A principal questao neste contexto e dimensionarnumericamente a percepcao empırica do que e “pequeno” e“grande”;Mesmo considerando os avancos, o metodo tradicionalcontinua tendo ampla aplicabilidade;
29 / 29