La scienza procede per errori e piccoli passi. E così fa la matematica. “Un risultato si ottiene al 10% grazie all’ispirazione e al 90% grazie al sudore della fronte” dice una celebre frase di dubbia attribuzione. Quando i  matematici lavorano su un problema, a volte può arrivare anche la grande idea, ma è poi questione di tanto lavoro per aggiungere piccoli miglioramenti fino ad ottenere grandi risultati. Questo è accaduto anche per  gli algoritmi del prodotto matriciale.

Una matrice è una tabella ordinata di numeri, disposti lungo righe e colonne. Se il numero n di righe e di colonne coincidono la matrice è detta quadrata di ordine n e contiene \(n^2\) elementi. L’elemento \(A_{ij}\) è il numero che si ottiene incrociando l’i-esima riga della matrice con la j-esima colonna, in una sorta di battaglia navale.
La teoria delle matrici rientra nell’algebra lineare che è la branca della matematica alla base degli schemi numerici che risolvono a livello computazionale i più svariati problemi: dalle equazioni differenziali che modellano i flussi d’aria fino agli algoritmi usati per la grafica 3D dei videogiochi.

Date due matrici A e B dello stesso ordine n è possibile moltiplicarle tra loro, secondo lo schema della moltiplicazione righe per colonne. La matrice prodotto \(A*B\) è ancora di ordine \(n\) e contiene \(n^2\) elementi. Dunque ci aspettiamo di trovare un algoritmo che consenta di risolvere il problema in \(n^2\) passi. Ma la realtà è purtroppo più complicata di così.

Il primo elemento della matrice prodotto \(A*B\) è ottenuto a partire dalla prima riga di \(A\) e dalla prima colonna di \(B\). \(A\) questo punto si moltiplica il primo elemento della prima riga di \(A\) con il primo elemento della prima colonna di \(B\), il secondo elemento della prima riga di \(A\) con il secondo elemento della prima colonna di \(B\), e così fino ad arrivare all’ultimo. A questo punto si sommano tutti gli elementi e si ottiene l’elemento \(11\) della matrice prodotto.
Qual è la complessità computazionale di questa operazione? Per complessità computazionale si intende il numero di moltiplicazioni effettuate che rappresentano l’operazione elementare per un calcolatore.

Per rispondere, consideriamo due matrici di ordine \(2\):

\[A=\left(\begin{matrix}1 & -2 \\ 0 & 1\end{matrix}\right), B=\left(\begin{matrix}2 & -1 \\ 1 & 0\end{matrix}\right).\]

Il primo elemento della matrice prodotto \(A*B\) è ottenuto fissando la prima riga di \(A\) \((1, \, -2)\) e la prima colonna di \(B\) \((2 , \, 1)\). A questo punto:

\[(A*B)_{11}=1*2+(-2)*1=0.\]

Il calcolo del primo elemento della matrice prodotto si ottiene con \(2\) moltiplicazioni. Svolgendo per \(4\) volte quest’operazione, il calcolo dei \(4\) elementi della matrice prodotto \(A*B\) è fatto di \(8\) moltiplicazioni. In definitiva la complessità computazione è \(8=2^3\), e non \(2^2\).

Per generiche matrici di ordine \(n\), il calcolo della matrice prodotto ha una complessità computazionale di \(n^3\). Da svariati decenni i matematici tentano di rispondere alla domanda: esiste un algoritmo per il calcolo del prodotto matrice di complessità computazionale pari ad \(n^2\)?
Perché è importante? La risoluzione computazionale di un problema di grafica può richiedere molti prodotti matriciali, con matrici dell’ordine di milioni, quindi ridurre quell’esponente significa ottenere il risultato in tempi molto più brevi. Se abbiamo una matrice con un milione di righe, ridurre di un’unità l’esponente vuol dire compiere l’operazione in un milionesimo del tempo.

Nel 1969, il matematico tedesco Volker Strassen sviluppa un algoritmo che consente di ridurre la complessità computazione del calcolo del prodotto matriciale ad \(n^{2,81}\). L’algoritmo di Strassen riduce una matrice in matrici via via più piccole, agevolando il calcolo dei prodotti necessari.
Nel 1981 un altro matematico tedesco, Arnold Schönhage, sviluppa un algoritmo che risolve il problema del calcolo del prodotto matriciale passando per un altro oggetto dell’algebra lineare: il tensore. Questo nuovo algoritmo riduce la complessità computazionale ad \(n^{2,522}\).
Lo sviluppo di algoritmi procede fino al 2014 quando il matematico francese Jean-François Le Gall riduce la complessità ad \(n^{2,3728639}\). Sembra il limite insormontabile. È possibile fare di meglio?

Nell’ottobre 2020 Josh Alman e Virginia Vassilevska Williams del Massachusetts Institute of Technology presentano un nuovo algoritmo per il calcolo del prodotto matriciale nell’articolo “A Refined Laser Method and Faster Matrix Multiplication”. Utilizzando la tecnica del metodo laser, la complessità computazionale è ridotta ad \(n^{2,3728596}\).

Il miglioramento rispetto al precedente algoritmo di Le Gall è di \(10^{-5}\) sull’esponente.
È poca roba? Beh, in ogni modo è un altro “piccolo” passo per aggiungere il traguardo \(n^2\).

[Illustrazione di Luca Manzo]