Skip to content

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.

CONSULTA INTEGRALMENTE QUESTA TESI

La consultazione è esclusivamente in formato digitale .PDF

Acquista
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-

CONSULTA INTEGRALMENTE QUESTA TESI

La consultazione è esclusivamente in formato digitale .PDF

Acquista
Il miglior software antiplagio

L'unico servizio antiplagio competitivo nel prezzo che garantisce l'aiuto della nostra redazione nel controllo dei risultati.
Analisi sicura e anonima al 100%!
Ottieni un Certificato Antiplagio dopo la valutazione.

Informazioni tesi

  Autore: Andrea Astolfi
  Tipo: Laurea I ciclo (triennale)
  Anno: 2008-09
  Università: Università degli Studi di Torino
  Facoltà: Scienze Matematiche, Fisiche e Naturali
  Corso: Scienze matematiche
  Relatore: Alberto Albano
  Lingua: Italiano
  Num. pagine: 39

FAQ

Per consultare la tesi è necessario essere registrati e acquistare la consultazione integrale del file, al costo di 29,89€.
Il pagamento può essere effettuato tramite carta di credito/carta prepagata, PayPal, bonifico bancario.
Confermato il pagamento si potrà consultare i file esclusivamente in formato .PDF accedendo alla propria Home Personale. Si potrà quindi procedere a salvare o stampare il file.
Maggiori informazioni
Ingiustamente snobbata durante le ricerche bibliografiche, una tesi di laurea si rivela decisamente utile:
  • perché affronta un singolo argomento in modo sintetico e specifico come altri testi non fanno;
  • perché è un lavoro originale che si basa su una ricerca bibliografica accurata;
  • perché, a differenza di altri materiali che puoi reperire online, una tesi di laurea è stata verificata da un docente universitario e dalla commissione in sede d'esame. La nostra redazione inoltre controlla prima della pubblicazione la completezza dei materiali e, dal 2009, anche l'originalità della tesi attraverso il software antiplagio Compilatio.net.
  • L'utilizzo della consultazione integrale della tesi da parte dell'Utente che ne acquista il diritto è da considerarsi esclusivamente privato.
  • Nel caso in cui l’utente che consulta la tesi volesse citarne alcune parti, dovrà inserire correttamente la fonte, come si cita un qualsiasi altro testo di riferimento bibliografico.
  • L'Utente è l'unico ed esclusivo responsabile del materiale di cui acquista il diritto alla consultazione. Si impegna a non divulgare a mezzo stampa, editoria in genere, televisione, radio, Internet e/o qualsiasi altro mezzo divulgativo esistente o che venisse inventato, il contenuto della tesi che consulta o stralci della medesima. Verrà perseguito legalmente nel caso di riproduzione totale e/o parziale su qualsiasi mezzo e/o su qualsiasi supporto, nel caso di divulgazione nonché nel caso di ricavo economico derivante dallo sfruttamento del diritto acquisito.
L'obiettivo di Tesionline è quello di rendere accessibile a una platea il più possibile vasta il patrimonio di cultura e conoscenza contenuto nelle tesi.
Per raggiungerlo, è fondamentale superare la barriera rappresentata dalla lingua. Ecco perché cerchiamo persone disponibili ad effettuare la traduzione delle tesi pubblicate nel nostro sito.
Per tradurre questa tesi clicca qui »
Scopri come funziona »

DUBBI? Contattaci

Contatta la redazione a
[email protected]

Ci trovi su Skype (redazione_tesi)
dalle 9:00 alle 13:00

Oppure vieni a trovarci su

Parole chiave

algebra
algoritmo
cohn
dft
fft
gauss
gruppi finiti
matrice
matrici
moltiplicazione
moltiplicazione di polinomi
moltiplicazione tra matrici
prodotto
rappresentazione
rappresentazioni
tempo di calcolo
teoria dei gruppi
trasformata di fourier
umans

Tesi correlate


Non hai trovato quello che cercavi?


Abbiamo più di 45.000 Tesi di Laurea: cerca nel nostro database

Oppure consulta la sezione dedicata ad appunti universitari selezionati e pubblicati dalla nostra redazione

Ottimizza la tua ricerca:

  • individua con precisione le parole chiave specifiche della tua ricerca
  • elimina i termini non significativi (aggettivi, articoli, avverbi...)
  • se non hai risultati amplia la ricerca con termini via via più generici (ad esempio da "anziano oncologico" a "paziente oncologico")
  • utilizza la ricerca avanzata
  • utilizza gli operatori booleani (and, or, "")

Idee per la tesi?

Scopri le migliori tesi scelte da noi sugli argomenti recenti


Come si scrive una tesi di laurea?


A quale cattedra chiedere la tesi? Quale sarà il docente più disponibile? Quale l'argomento più interessante per me? ...e quale quello più interessante per il mondo del lavoro?

Scarica gratuitamente la nostra guida "Come si scrive una tesi di laurea" e iscriviti alla newsletter per ricevere consigli e materiale utile.


La tesi l'ho già scritta,
ora cosa ne faccio?


La tua tesi ti ha aiutato ad ottenere quel sudato titolo di studio, ma può darti molto di più: ti differenzia dai tuoi colleghi universitari, mostra i tuoi interessi ed è un lavoro di ricerca unico, che può essere utile anche ad altri.

Il nostro consiglio è di non sprecare tutto questo lavoro:

È ora di pubblicare la tesi