Algoritmo Coppersmith – Winograd - Coppersmith–Winograd algorithm

Na álgebra linear , o algoritmo Coppersmith – Winograd , nomeado após Don Coppersmith e Shmuel Winograd , foi o algoritmo de multiplicação de matrizes conhecido assintoticamente mais rápido de 1990 até 2010. Ele pode multiplicar duas matrizes no tempo (ver notação Big O ). ${\ displaystyle n \ times n}$${\ displaystyle {\ mathcal {O}} (n ^ {2.375477})}$

Esta é uma melhoria sobre o algoritmo de tempo ingênuo e o algoritmo de Strassen de tempo . Algoritmos com melhor tempo de execução assintótico do que o algoritmo Strassen raramente são usados ​​na prática, porque os grandes fatores constantes em seus tempos de execução os tornam impraticáveis. É possível melhorar ainda mais o expoente; entretanto, o expoente deve ser pelo menos 2 (porque há valores no resultado que devem ser calculados). ${\ displaystyle {\ mathcal {O}} (n ^ {3})}$${\ displaystyle {\ mathcal {O}} (n ^ {2.807355})}$${\ displaystyle n \ times n = n ^ {2}}$

Em 2010, Andrew Stothers deu uma melhoria ao algoritmo, em 2011, Virginia Vassilevska Williams combinou um atalho matemática do papel Stothers' com suas próprias percepções e otimização automática em computadores, melhorar a obrigado a Em 2014, François Le Gall simplificou o métodos de Williams e obteve um limite melhorado de ${\ displaystyle {\ mathcal {O}} (n ^ {2.374}).}$${\ displaystyle {\ mathcal {O}} (n ^ {2.3728642}).}$${\ displaystyle {\ mathcal {O}} (n ^ {2.3728639}).}$

O algoritmo Coppersmith – Winograd é freqüentemente usado como um bloco de construção em outros algoritmos para provar limites de tempo teóricos. No entanto, ao contrário do algoritmo Strassen, não é usado na prática porque só fornece uma vantagem para matrizes tão grandes que não podem ser processadas por hardware moderno (tornando-se um algoritmo galáctico ).

Henry Cohn , Robert Kleinberg , Balázs Szegedy e Chris Umans derivaram novamente o algoritmo Coppersmith – Winograd usando uma construção teórica de grupo . Eles também mostraram que qualquer uma das duas conjecturas diferentes implicaria que o expoente ótimo da multiplicação da matriz é 2, como há muito se suspeitava. No entanto, eles não foram capazes de formular uma solução específica levando a um melhor tempo de execução do que Coppersmith – Winograd. Várias de suas conjecturas foram desmentidas por Blasiak, Cohn, Church, Grochow, Naslund, Sawin e Umans usando o método Slice Rank.

Veja também

• Complexidade computacional de operações matemáticas
• Eliminação de Gauss-Jordan
• Conjunto Salem – Spencer
• Algoritmo Strassen

Referências

Leitura adicional

• Bürgisser, P .; Clausen, M .; Shokrollahi, MA (1997). Teoria da Complexidade Algébrica . Grundlehren der mathematischen Wissenschaften. 315 . Springer Verlag. ISBN   3-540-60582-7 .