Algoritmo de Coppersmith-Winograd
En lineara algebro, la algoritmo de Coppersmith-Winograd estas asimptote la plej rapida sciata algoritmo por matrica multipliko de kvadrataj matricoj (kiel en 2008).
La algoritmo estas nomita post Don Coppersmith kaj Shmuel Winograd.
Ĝi povas multipliki du n×n matricojn en tempodaŭro O(n2,376). Ĉi tio estas plibonigo super la bagatela O(n3) de norma algoritmo kaj la O(n2,807) de algoritmo de Strassen.
La norma matrica multiplika algoritmo uzas senperan kalkulon laŭ difino de matrica multipliko
- cik = Σaijbjk
Eble eblas plibonigi la eksponenton super la matrica amplekso n plu. Tamen, la eksponento devas esti minimume 2 ĉar n×n matrico enhavas n2 valorojn, kaj ili ĉiuj devas esti legitaj dum kalkulado por ricevi la akuratan rezulton.
La algoritmo de Coppersmith-Winograd estas ofte uzata kiel parto en aliaj algoritmoj por pruvi teoriajn tempajn komplikecajn barojn. Tamen, malsimile la algoritmo de Strassen, ĝi ne estas uzata en praktiko ĉar ĝi donas avantaĝon nur por matricoj tiel grandaj ke ilin ne povas prilabori moderna aparataro.
Henry Cohn, Robert Kleinberg, Balázs Szegedy kaj Christopher Umans rederivis la algoritmon de Coppersmith-Winograd per grupo-teoria konstruado. Ili ankaŭ montris ke ĉiu el du malsamaj konjektoj implicas ke la eksponento por tempodaŭro de matrica multipliko estas 2, kiel estas longe suspektite.
Vidu ankaŭ |
- Algoritmo de Strassen
Eksteraj ligiloj |
- Henry Cohn, Robert Kleinberg, Balázs Szegedy kaj Christopher Umans. Grupo-teoriaj algoritmoj por matrica multipliko. arXiv:math.GR/0511460. Paperoj de la 46-a Ĉiujara Simpozio sur Fundamentoj de Komputila Scienco, 23-25 Oktobro de 2005, Pittsburgh (Pensilvanio), PA, IEEE Komputila Socio, pp. 379-388.
- Robinson, Sara (2005). Toward an Optimal Algorithm for Matrix Multiplication - Al optimala algoritmo por matrica multipliko. SIAM News - SIAM novaĵoj 38 (9).
