Algoritmo de Coppersmith-Winograd

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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 O(n^{2.375}) (ver notação Grande-O), tendo então desempenho superior quando comparado com o algoritmo trivial, que corre num tempo O(n^{3}), e com o algoritmo de Strassen, de tempo O(n^{2.807}). Pode ser viável melhorar ainda mais o expoente, no entanto ele deve ser pelo menos 2 (uma vez que uma matriz n \times n tem n^2 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[editar | editar código-fonte]

  1. Robinson (2005)

Referências[editar | editar código-fonte]


Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.