Pour les articles homonymes, voirCoppersmith etWinograd.
Cet article est uneébauche concernant l’informatique et lesmathématiques.
L’algorithme de Coppersmith-Winograd est unalgorithme de calcul duproduit de deuxmatrices carrées de taille dû àDon Coppersmith etShmuel Winograd en1987[1]. Sacomplexité algorithmique est en ce qui en fait l'algorithme actuel le plus efficace asymptotiquement. Rien n'indique que la complexité est optimale, l'exposant 2 étant généralement considéré comme optimal[2].
L'algorithme est utilisé comme brique de base pour prouver des résultats théoriques sur la complexité algorithmique. Mais aucune implémentation de l'algorithme n'est utilisée car la constante dans legrand O est prohibitive (il est moins performant quecelui de Strassen sur toute matrice qui tiendrait dans la mémoire d’un ordinateur actuel).
L'algorithme de Coppersmith-Winograd a été retrouvé par des méthodes dereprésentation desgroupes finis[3].
Dans sa thèse, Andrew Stothers améliore la borne sur la complexité de l'algorithme, montrant qu'elle est inférieure à 2,3737[4].
| |||||
| Propriétés | |||||
| Exemples | |||||
| Algorithmes de multiplication |
| ||||
| Algorithmes de vérification |
| ||||
