L'algoritmo di Strassen

Quanto è dispendioso, dal punto di vista computazionale, moltiplicare due matrici $n \times n$?

La risposta che viene subito in mente è che servono al più $O(n^3)$ operazioni, dato che l'algoritmo standard (insegnato nei corsi base di Algebra Lineare) richiede $n \times n \times n=n^3$ moltiplicazioni e possiamo trascurare il contributo dato delle addizioni, computazionalmente irrilevante.

Nel 1969 V. Strassen, mentre cercava di dimostrare che l'algoritmo standard è ottimale, fece l'inaspettata scoperta che è possibile moltiplicare due matrici $2 \times 2$ utilizzando solo sette moltiplicazioni invece di otto. In suo onore, questo metodo di moltiplicazione matriciale è oggi chiamato algoritmo di Strassen.

V. Strassen nel 1979 (fonte Wikipedia)

L'algoritmo di Strassen può essere generalizzato a matrici $n \times n$, e permette di moltiplicare due tali matrici utilizzando $O(n^{\log_2(7)+o(1)}) = O(n^{2,8074})$ operazioni, invece delle $O(n^3)$ richieste dall'algoritmo standard. Con l'architettura dei moderni processori, implementare l'algoritmo di Strassen invece di quello usuale permette un guadagno in efficienza di circa il 20%, almeno per quanto riguarda matrici non strutturate e di grossa taglia ($n>2000$).

Essendo la moltiplicazione di matrici uno strumento centrale in ogni branca dell'Analisi Numerica, la scoperta di nuovi algoritmi di bassa complessità computazionale ha evidentemente un impatto drammatico sulla disciplina. Infatti, l'algoritmo di Strassen inaugurò un nuovo settore di ricerca noto come Fast Matrix Multiplication.

Al momento, uno degli algoritmi più veloci è quello di Coppersmith–Winograd, che ha una complessità computazionale pari a $O(n^{2,375477})$. Esistono anche algoritmi asintoticamente più efficienti, ma in pratica essi sono raramente implementati a causa delle enormi costanti che compaiono nell'espressione esplicita del tempo di esecuzione richiesto [2].

Notiamo che, in ogni caso, conoscere una matrice $n \times n$ richiede la conoscenza di tutti i suoi $n^2$ elementi, quindi la complessità computazionale di un'operazione binaria fra matrici deve essere almeno $O(n^2)$. Una sorprendente congettura (al momento non dimostrata) è che per ogni numero naturale $n$ e per ogni numero reale $\epsilon >0$ esiste un algoritmo capace di moltiplicare due matrici $n \times n$ con complessità computazionale $O(n^{2+ \epsilon})$. In altre parole, almeno asintoticamente, moltiplicare due matrici non dovrebbe essere più dispendioso che sommarle.

L'algoritmo di Strassen ha una moderna interpretazione nell'ambito della Geometria Algebrica e della Teoria delle Rappresentazioni. Le tecniche utilizzate hanno la loro origine nei lavori della scuola italiana sulle Varietà delle Secanti (inizio '900), si veda [1] per una trattazione sistematica dell'argomento.


Riferimenti:

[1] J. M. Landsberg: Geometry and Complexity Theory, Cambridge Studies in Advanced Mathematics 169, Cambridge University Press 2017.
[2] S. Robinson: Toward an Optimal Algorithm for Matrix Multiplication, SIAM News, 38 (9), 2005.