Algorithme de Coppersmith-Winograd
Un article de Wikipédia, l'encyclopédie libre.
|
|
L’algorithme de Coppersmith-Winograd est un algorithme de calcul du produit de deux matrices carrées de taille n du à Don Coppersmith et Shmuel Winograd en 1987.[1] Sa complexité algorithmique est en 
ce qui en fait l'algorithme le plus efficace en théorie. 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 implantation de l'algorithme n'est utilisée car la constante dans le grand O est prohibitive.
L'algorithme de Coppersmith-Winograd a été retrouvé par des méthodes de représentation des groupes finis.[3]
[modifier] Voir aussi
[modifier] 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 n2 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.
