Algorithme de Coppersmith-Winograd

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

1. Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pages 1–6, 1987.
2. On sait que l'exposant ne peut être inférieur à 2 puisque l'algorithme doit au moins lire les ${\displaystyle n^{2}}$ entrées de la matrice.
3. Henry Cohn, Robert Kleinberg, Balazs Szegedy, and Chris Umans. Group-theoretic Algorithms for Matrix Multiplication. Proceedings of the 46th Annual Symposium on Foundations of Computer Science, 23-25 October 2005, Pittsburgh, PA, IEEE Computer Society, pp. 379–388. Disponible sur arXiv ici.
4. (en) On the Complexity of Matrix Multiplication (chap. 4), Andrew James Stothers, thèse de doctorat, université d'Édimbourg, 2010.