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

Valore della costante della moltiplicazione veloce di matrici (problema del)

Algebra  Problemi 

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.

 

Per moltiplicare due matrici n × n col metodo basato sulla definizione del prodotto di matrici servono n3 moltiplicazioni, ma questo numero è stato successivamente ridotto più volte.

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; dato che si devono calcolare n2 termini, l’esponente non può essere minore di 2

Il miglior valore noto è dato da un algoritmo di Virginia Vassilevska Williams (2012), che riduce l’esponente a circa 2.3727.

 

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.

Contattami

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