Algoritmo Coppersmith-Winograd
L' algoritmo Coppersmith-Winograd è un algoritmo per il calcolo del prodotto di due matrici quadrate di dimensioni dovute a Don Coppersmith e Shmuel Winograd nel 1987 . La sua complessità algoritmica è ciò che lo rende l'algoritmo attuale più asintoticamente efficiente. Non vi è alcuna indicazione che la complessità sia ottimale, con esponente 2 generalmente considerato ottimale.
non{\ displaystyle n}
O(non2,376) {\ displaystyle O (n ^ {2,376}) \! \}![{\ displaystyle O (n ^ {2,376}) \! \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d90936216dac22435d530ffe341ddd19b31a70f)
L'algoritmo viene utilizzato come elemento costitutivo per dimostrare i risultati teorici sulla complessità algoritmica. Ma non viene utilizzata alcuna implementazione dell'algoritmo perché la costante nella grande O è proibitiva (è meno efficiente di quella di Strassen su qualsiasi matrice che si adatterebbe alla memoria di un computer corrente).
L'algoritmo Coppersmith-Winograd è stato trovato mediante metodi di rappresentazione di gruppi finiti .
Nella sua tesi, Andrew Stothers migliora il limite sulla complessità dell'algoritmo, dimostrando che è inferiore a 2,3737.
Vedi anche
Riferimenti
-
Don Coppersmith e Shmuel Winograd . Moltiplicazione di matrici tramite progressioni aritmetiche. Atti del diciannovesimo simposio annuale ACM sulla teoria del calcolo , pagine 1–6, 1987.
-
Sappiamo che l'esponente non può essere minore di 2 poiché l'algoritmo deve leggere almeno le voci della matrice.non2{\ displaystyle n ^ {2}}
-
Henry Cohn, Robert Kleinberg, Balazs Szegedy e Chris Umans. Algoritmi di teoria dei gruppi per la moltiplicazione di matrici. Atti del 46th Annual Symposium on Foundations of Computer Science , 23-25 ottobre 2005, Pittsburgh, PA, IEEE Computer Society, pp. 379–388. Disponibile su arXiv qui .
-
(en) On the Complexity of Matrix Multiplication (Cap.4) , Andrew James Stothers, PhD, University of Edinburgh , 2010.
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">