Moltiplicazione veloce tra matrici: un approccio mediante le rappresentazioni di gruppi finiti

Introduzione Le matrici fecero la loro apparizione in matematica come tabelle per rap- presentare in forma abbreviata le sostituzioni lineari, ad opera di Gauss (1777-1855); il termine matrice invece fu introdotto nel 1850 da J.Sylvester. È però con l'avvento dei computer e con lo sviluppo dell'algebra compu- tazionale, che le matrici dimostrarono tutta la loro utilità, permettendo di implementare calcoli e equazioni risolutrici di sistemi lineari usando la teoria del calcolo matriciale. Risulta quindi ovvio quale importanza rivesta la possibilità di effettuare tali calcoli nel minor tempo possibile. Mentre per operazioni quali la riduzione e l'inversione di una matrice troviamo ottimizzazioni del tempo di calcolo già nei lavori di Gauss, per veder comparire sulla scena matematica un algoritmo di moltiplicazione tra matrici, che fosse più veloce del tempo normalmente impiegato, dobbiamo aspettare fino al 1969 quando Strassen [3] scopre un al- goritmo che permette di calcolare il prodotto di due matrici n×n in O(n2.81) operazioni contro le 2n3 dell'algoritmo standard. Immediatamente ci si chiese quale fosse l'esponente della moltiplicazione tra matrici, cioè qual è il più piccolo numero w tale che per ogni ² > 0, l'algo- ritmo richieda al massimo O(nw+²) operazioni. Chiaramente w ≥ 2 e si congettura che la risposta alla domanda sia proprio w = 2, ma il miglior risultato fino ad ora trovato, dovuto a Coppersmith e Winograd[4], è w < 2.376. Entrambi questi risultati sono stati il frutto di tecniche prevalentemente combinatoriche. Cohn e Umans[1], proposero nel 2003 un approccio di tipo algebrico: co- me i polinomi vengono immersi con la trasformata di Fourier in un group algebra, riuscendo a diminuire il numero di operazioni necessarie per molti- plicarli, così Cohn e Umans si propongono nel loro primo articolo di cercare un ambiente adatto alla moltiplicazione tra matrici. Essi studiano quali pro- prietà un gruppo deve avere per supportare tale operazione. Nel secondo articolo[2], in cui a Cohn e Umans si sono aggiunti Kleinberg e Szegedy, vengono trovati esplicitamente dei gruppi che soddisfino le condizio-