Algorithme de Coppersmith-Winograd

Un article de Wikipédia, l'encyclopédie libre.
Cet article est une ébauche concernant l’informatique et les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

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 O(n^{2.376}) \!\ 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

  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 n2 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.
Autres langues