Algorithme de Coppersmith-Winograd

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

L’algorithme de Coppersmith-Winograd est un algorithme de calcul du produit de deux matrices carrées de taille n dû à Don Coppersmith et Shmuel Winograd en 1987[1]. Sa complexité algorithmique est en 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.

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[modifier | modifier le code]

Références[modifier | modifier le code]

  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 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.