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[1]. 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[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].
Références
- 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.
- On sait que l'exposant ne peut être inférieur à 2 puisque l'algorithme doit au moins lire les entrées de la matrice.
- 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.
- (en) On the Complexity of Matrix Multiplication (chap. 4), Andrew James Stothers, thèse de doctorat, université d'Édimbourg, 2010.
