Analisi di alcune simmetrie dell'algoritmo di Strassen per la moltiplicazione di matrici

La moltiplicazione tra matrici è un operazione di fondamentale importanza. Da decenni è stata centro di studi per il miglioramento delle prestazioni. Fu nel 1969 che Volker Strassen presentò un algoritmo rivoluzionario capace di ridurre l’esponente della moltiplicazione matriciale \omega da 3 a \log_{2}7\approx2.807, dando avvio a una lunga linea di ricerca che continua ancora oggi. Nella seguente tesi si propone di esaminare l'algoritmo di Strassen applicato a matrici di ordine n=4, introducendo una modifica nella fase di Divide che non cambia la logica dell'algoritmo originale. L'attenzione è rivolta in particolare allo studio delle foglie dell'albero ricorsivo, ossia gli elementi di ordine n=1 che compaiono all'ultimo livello della ricorsione. Dopo aver calcolato le 49 foglie associate alle matrici A e B, si osserva una simmetria strutturale tra di esse, descrivibili mediante opportune permutazioni. Tale simmetria ha permesso di calcolare il numero di elementi e il valore di una foglia specifica per matrici di grandi dimensioni senza compiere l'intero algoritmo. Infine, sulla base delle proprietà individuate, viene sviluppato l’algoritmo ricorsivo SearchFoglia che, data la taglia delle matrici n e un intero k con 0\leq k<n^{\log_{2}7}, consente di determinare gli scalari associati alla foglia k mediante una regola generale e sistematica per il calcolo diretto degli indici della foglia, ottimizzando ulteriormente la ricerca delle foglie.