ETD system

Electronic theses and dissertations repository

 

Tesi etd-09042007-192950


Thesis type
Tesi di laurea specialistica
Author
Arri, Alberto
URN
etd-09042007-192950
Title
L'algoritmo F5 di Faugère: una dimostrazione alternativa ed alcune generalizzazioni
Struttura
SCIENZE MATEMATICHE, FISICHE E NATURALI
Corso di studi
MATEMATICA
Commissione
Relatore Caboara, Massimo
Parole chiave
  • Basi di Grobner
  • Algebra Lineare
  • Algoritmi
Data inizio appello
28/09/2007;
Consultabilità
completa
Riassunto analitico
Oggetto di questa tesi sono lo studio e l&#39;implementazione dell&#39;algoritmo ``F5&#39;&#39; <br>di J. C. Faug\`ere.<br>Questo \`e un algoritmo recentemente presentato per il calcolo di una base di<br>Groebner di un ideale dato per generatori, nel corso della tesi viene presentata<br>una dimostrazione originale della correttezza dell&#39;algoritmo, assieme<br>ad alcune generalizzazioni, in particolare \`e descritta una versione dell&#39;algoritmo<br>che rimuove l&#39;ipotesi che l&#39;input sia una successione regolare.<br><br>Inizialmente viene introdotta la teoria delle basi di Groebner: dagli<br>ordinamenti di termini, fino alle prime applicazioni; viene descritto<br>l&#39;algoritmo di Buchberger,vengono inoltre presentate le prime<br>applicazioni di questo strumento da un punto di vista computazionale.<br><br>Successivamente viene introdotta la nozione di successione regolare<br>e viene descritta la sua relazione con le sizigie principali, con<br>queste nozioni si procede a definire il concetto di ``polinomio etichettato&#39;&#39;.<br>Un polinomio etichettato \`e una coppia di elementi $(te_i,f)$ dove $f$<br>\`e un polinomio, e $t e_i$, l&#39;etichetta, \`e un termine di modulo; <br>sono esaminate le prime propriet\`a algebriche di questi oggetti.<br>Con questi si procede a definire la matrice di Macaulay ridotta <br>e l&#39;iterazione fondamentale dell&#39;algoritmo. Viene, infine, dimostrata<br>la correttezza dell&#39;algoritmo nell&#39;ipotesi di regolarit\`a dell&#39;input.<br><br><br>Nel seguito viene esaminato il caso in cui un passo dell&#39;algoritmo ``F5&#39;&#39;<br>venga applicato senza l&#39;ipotesi di regolarit\`a, in questo caso si presentano<br>alcune differenze nella teoria, in particolare esistono sizigie non principali<br>e le matrici di Macaulay ridotte non hanno sempre rango massimo. <br>Queste difficolt\`a si sono rivelate superabili, e infatti <br>viene presentato un algoritmo ``generalizzato&#39;&#39;, che con alcune modifiche rispetto <br>al caso regolare, non solo calcola una base di \grob/, ma produce anche altre<br>informazioni sulle sizigie, per la precisione, trova tutti <br>termini di testa delle sizigie di grado minore ad un grado fissato. <br><br>Nell&#39;ultima parte si trattano i dettagli pi\`u tecnici dell&#39;implementazione<br>di alcune parti dell&#39;algoritmo, e si presentano i benchmark sui tempi ed occupazione<br>di memoria. Rispetto ai tempi riportati dallo stesso Faug\`ere questi sono peggiori;<br>nel complesso, rispetto all&#39;algoritmo di Buchberger, per ordinamenti grado compatibili <br>si riscontra una sostanziale riduzione dei tempi per gli ideali di Katsura, anche<br>di un fattore 10, mentre nella maggiorparte degli altri casi i tempi sono<br>di superiori, a volte di poco, a volte sostanzialmente.<br>
File