Don't take life too seriously: it's just a temporary situation

Moltiplicazione veloce di matrici (costante della)

Algebra 

La moltiplicazione tra matrici è un’operazione molto frequente in numerose applicazioni pratiche, dal calcolo di strutture a quello di circuiti elettrici, alla simulazione di giacimenti petroliferi. La dimensione sempre maggiore delle matrici utilizzate, resa possibile dall’aumento della memoria disponibile negli elaboratori, ha spinto a cercare algoritmi sempre migliori per eseguire la moltiplicazione.

 

Si chiama “costante della moltiplicazione veloce di matrici” l’esponente k nell’espressione ank del minimo numero di moltiplicazioni necessarie per moltiplicare due matrici n × n, per n grande.

Per moltiplicare due matrici col metodo basato sulla definizione del prodotto di matrici servono n3 moltiplicazioni; nel 1967 S. Vinograd scoprì come ridurre questo numero a circa n^3 / 2 + n^2 per n grande, ma questo equivale a ridurre a nell’espressione, non k. L’algoritmo inoltre richiede n^3 / 2 addizioni in più, quindi di fatto scambia solo moltiplicazioni con addizioni (generalmente più veloci, anche per un calcolatore) e offre vantaggi limitati.

 

Nel 1969 Volker Strassen scoprì un ingegnoso algoritmo per moltiplicare due matrici 2 × 2 con sole 7 moltiplicazioni. Il metodo si può estendere ricorsivamente suddividendo una matrice grande in 4 quarti, 16 sedicesimi ecc., in modo da moltiplicare due matrici con n^(log(7) / log(2)) moltiplicazioni, quindi l’esponente si riduce a circa log(7) / log(2).

La riduzione sembra marginale, ma se n vale 1335, corrisponde a ridurre di circa un fattore 4 il numero di moltiplicazioni e in numerose applicazioni pratiche oggi si utilizzano frequentemente matrici di dimensioni molto maggiori.

 

Nel 1978 Victor Y. Pan trovò un algoritmo per moltiplicare due matrici 70 × 70 con 143640 moltiplicazioni, riducendo l’esponente a log(143640) / log(2), poi altri scoprirono algoritmi simili e un algoritmo di Strassen (1986) ridusse l’esponente a circa 2.479.

 

Nel 1990 Don Coppersmith e Shmuel Winograd trovarono un algoritmo che riduce l’esponente a circa 2.375477.

 

Nel 2010 Andrew Stothers ridusse l’esponente a circa 2.3736.

 

Il record attuale è detenuto da un algoritmo di Virginia Vassilevska Williams (2012), che riduce l’esponente a circa 2.3727.

 

Molti di questi algoritmi hanno una costante a talmente grande, da divenire realmente convenienti solo per matrici enormi, addirittura più grandi di quelle che possono oggi essere affrontate tramite elaboratori elettronici, ma l’interesse nella ricerca sta nel cercare il minimo esponente possibile, indipendentemente dall’effettivo utilizzo della scoperta per scopi pratici.

Il minino valore teoricamente possibile per la costante è 2, perché n2 termini vanno comunque calcolati, e alcuni esperti suppongono che sia possibile arrivarci.

Nel 2005 Henry Cohn, Robert Kleinberg, Balázs Szegedy and Christopher Umans dimostrarono che se fosse vera almeno una di due congetture ritenute molto plausibili, sarebbe possibile ridurre l’esponente a 2, per matrici sufficientemente grandi.

 

Va notato che non abbiamo neppure la certezza che una costante di questo genere esista! Infatti il minimo potrebbe essere dato da un’espressione con un esponente non costante, ma funzione lentamente decrescente di n, come 2 + 1 / log(n).

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.