algorithme de Coppersmith-Winograd

L’algorithme de Coppersmith-Winograd est un algorithme de calcul du produit de deux matrices carrées de taille dû à Don Coppersmith et Shmuel Winograd en 1987. Sa complexité 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. 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 le grand O est prohibitive (il est moins performant que celui 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 de représentation des groupes finis. Dans sa thèse, Andrew Stothers améliore la borne sur la complexité de l'algorithme, montrant qu'elle est inférieure à 2,3737.