La moltiplicazione tra matrici è alla base del calcolo scientifico, dell’econometria e del deep learning moderno. Dal punto di vista geometrico, moltiplicare due matrici e rappresenta la composizione di due trasformazioni lineari.
Da all’Algoritmo di Strassen
Applicando la definizione standard riga-per-colonna per due matrici quadrate :
il calcolo di tutti gli elementi richiede moltiplicazioni scalari. Per oltre un secolo si è ritenuto che la complessità fosse impossibile da migliorare.
Nel 1969 Volker Strassen dimostrò il contrario, scoprendo che due matrici possono essere moltiplicate utilizzando 7 moltiplicazioni scalari anziché 8, a fronte di alcune somme aggiuntive. Applicando ricorsivamente questa decomposizione a blocchi si ottiene una complessità asintotica pari a:
Reinforcement Learning e AlphaTensor
Decenni di ricerca algebrica hanno progressivamente abbassato l’esponente asintotico (Coppersmith–Winograd e successivi miglioramenti). Nel 2022 DeepMind ha presentato AlphaTensor, formulando la ricerca di decomposizioni a basso rango del tensore della moltiplicazione matriciale come un problema di Reinforcement Learning.
AlphaTensor ha scoperto algoritmi più efficienti per matrici di piccole dimensioni—migliorando anche l’algoritmo di Strassen a due livelli per matrici in aritmetica modulare—seguito poco dopo da ulteriori raffinamenti euristici in .
Riferimenti Bibliografici
- Strassen, V. Gaussian elimination is not optimal. Numer. Math. 13, 354–356 (1969). https://doi.org/10.1007/BF02165411
- Fawzi, A., Balog, M., Huang, A. et al. Discovering faster matrix multiplication algorithms with reinforcement learning. Nature 610, 47–53 (2022). https://doi.org/10.1038/s41586-022-05172-4
- Manuel Kauers and Jakob Moosbauer. The FBHHRBNRSSSHK-algorithm for multiplication in is still not the end of the story. Technical Report 2210.04045, arXiv (2022).