Questo sito utilizza cookie di terze parti per inviarti pubblicità in linea con le tue preferenze. Se vuoi saperne di più clicca QUI 
Chiudendo questo banner, scorrendo questa pagina, cliccando su un link o proseguendo la navigazione in altra maniera, acconsenti all'uso dei cookie. OK

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

Nell'era della computerizzazione l'importanza che rivestono gli algoritmi di calcolo tra matrici non viene messa in discussione. Mentre per la riduzione e la risoluzione di sistemi gli algoritmi sono noti fin dai tempi di Guass; solo nel 1969 si trova un algoritmo per la moltiplicazione tra due matrici, con un tempo di calcolo inferiore all'algoritmo standard. Nel 2003 Cohn e Umans propongono un approccio algebrico per ottenere risultati migliori. La tesi analizza nel dettaglio questo articolo, mostrando la relazione stretta con la moltiplicazione di polinomi, sviluppando le basi della teoria delle rappresentazioni finite di gruppi, e mostrando in che modo si possano usare questi risultati per la moltiplicazione di matrici. La tesi viene scritta con l'obiettivo di porre il lettore che non conosce nulla di tali argomenti nella condizione di capire ogni dimostrazione, pertanto vengono trattati anche argomenti di base.

Mostra/Nascondi contenuto.
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-

Laurea liv.I

Facoltà: Scienze Matematiche, Fisiche e Naturali

Autore: Andrea Astolfi Contatta »

Composta da 39 pagine.

 

Questa tesi ha raggiunto 515 click dal 01/06/2010.

Disponibile in PDF, la consultazione è esclusivamente in formato digitale.