Algorithme de Coppersmith-Winograd

Pour les articles homonymes, voir Coppersmith et Winograd.

Cet article est une ébauche concernant l’informatique et les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

L’algorithme de Coppersmith-Winograd est un algorithme de calcul du produit de deux matrices carrées de taille ${\displaystyle n}$ dû à Don Coppersmith et Shmuel Winograd en 1987^[1]. Sa complexité algorithmique est en ${\displaystyle O(n^{2,376})\!\ }$ 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 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^[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].

Voir aussi

• Algorithme de Strassen
• Complexité de la multiplication de matrices

Références

• Portail de l'informatique théorique
• Portail de l’algèbre