Algoritmo de Coppersmith-Winograd
Em álgebra linear, o algoritmo de Coppersmith–Winograd é um algoritmo de multiplicação de matrizes quadradas que, apresenta a maior velocidade assimptótica conhecida até o ano de 2008. O algoritmo recebe o nome de Don Coppersmith e Shmuel Winograd e é capaz de multiplicar matrizes quadradas de dimensão n num tempo de (ver notação Grande-O), tendo então desempenho superior quando comparado com o algoritmo trivial, que corre num tempo , e com o algoritmo de Strassen, de tempo . Pode ser viável melhorar ainda mais o expoente, no entanto ele deve ser pelo menos 2 (uma vez que uma matriz tem valores que precisam ser lidos ao menos uma vez para calcular o resultado exato).
O algoritmo de Coppersmith–Winograd é usado frequentemente como base para a construção de outros algoritmos para provar cotas teóricas sobre tempo de processamento. Porém, ao contrário do algoritmo de Strassen, ele não é usado na prática porque só é vantajoso para matrizes tão grandes que não podem ser processadas pelo hardware existente atualmente.[1]
Henry Cohn, Robert Kleinberg, Balázs Szegedy e Christopher Umans obtiveram novamente o algoritmo de Coppersmith–Winograd usando uma construção da teoria de grupos. Eles também mostraram que qualquer uma de duas conjecturas diferentes implicariam que o expoente ótimo para a multiplicação de matrizes é 2, como se suspeita há muito tempo.
Notas
- ↑ Robinson (2005)
Referências
- Henry Cohn, Robert Kleinberg, Balazs Szegedy, and Chris Umans. Group-theoretic Algorithms for Matrix Multiplication. arXiv:math.GR/0511460. Proceedings of the 46th Annual Symposium on Foundations of Computer Science, 23–25 October 2005, Pittsburgh, PA, IEEE Computer Society, pp. 379-388.
- Coppersmith, Don; Winograd, Shmuel (1990), «Matrix multiplication via arithmetic progressions» (PDF), Journal of Symbolic Computation, 9 (3): 251-280, doi:10.1016/S0747-7171(08)80013-2, consultado em 15 de outubro de 2010, cópia arquivada (PDF) em
|arquivourl=
requer|arquivodata=
(ajuda) 🔗 - Robinson, Sara (2005), «Toward an Optimal Algorithm for Matrix Multiplication» (PDF), SIAM News, 38 (9), consultado em 15 de outubro de 2010, cópia arquivada (PDF) em
|arquivourl=
requer|arquivodata=
(ajuda) 🔗 .
![]() | Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.
|