Algorithme de Coppersmith-Winograd

Cet article est une ébauche concernant l’informatique et les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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

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

↑ 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 $n^{2}$ 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.

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

[1]

[2]

[3]

[4]