Produto de matrizes: diferenças entre revisões

Conteúdo apagado Conteúdo adicionado
Kaktus Kid (discussão | contribs)
+ predef
Linha 64:
== Algoritmos para a multiplicar matrizes eficientemente ==
{{Não resolvido|ciência da computação|Qual é o algoritmo mais rápido para a multiplicação de matrizes?}}
O [[tempo de execução]] da multiplicação de matrizes quadradas, se efetuada de forma intuitiva, é <math>O( n^3 )</math>. O tempo de execução para a multiplicação de matrizes retangulares (uma matriz ''m×p'' e outra ''p''×''n'') é ''O''(''mnp''), no entanto, existem algoritmos mais eficientes, tais como o [[algoritmo de Strassen|algo]], concebido por [[Volker Strassen]] em 1969, e chamado frequentemente de "multiplicação rápida de matrizes". Ele baseia-se em uma forma de multiplicar matrizes 2×2 que exige apenas 7 multiplicações (em vez das 8 usuais), em troca de fazer algumas oprerações de adição e subtração. A aplicação recursiva desse método produz um algoritmo cujo custo multiplicativo é <math>O( n^{\log_{2}7}) \approx O(n^{2.807})</math>. O algoritmo de Strassen é mais complexo se comparado com o algoritmo intuitivo, e ele carece de [[estabilidade numérica]]. Mesmo assim, está disponível em diversas bibliotecas, tais como [[BLAS]], em que sua eficiência é significativamente maior para matrizes de dimensão ''n'' > 100,<ref>Press 2007, p.&nbsp;108.</ref> e é muito útil para matrizes grandes sobre domínios exatos tais como corpos finitos, em que a estabilidade numérica não é um problema.
 
{{Referências|Notas e referências}}