Algoritmo de Coppersmith-Winograd

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo

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ŭ[redakti | redakti fonton]

Eksteraj ligiloj[redakti | redakti fonton]