Algorithme de Coppersmith-Winograd
![Page d’aide sur l’homonymie](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Logo_disambig.svg/20px-Logo_disambig.svg.png)
Pour les articles homonymes, voir Coppersmith et Winograd.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/02/Circle-icons-computer.svg/35px-Circle-icons-computer.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1f/Racine_carr%C3%A9e_bleue.svg/35px-Racine_carr%C3%A9e_bleue.svg.png)
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 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].
Voir aussi
- Algorithme de Strassen
- Complexité de la multiplication de matrices
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.
v · m | |||||
---|---|---|---|---|---|
| |||||
Propriétés | |||||
Exemples | |||||
Algorithmes de multiplication |
| ||||
Algorithmes de vérification |
|
Portail de l'informatique théorique
Portail de l’algèbre