L’algoritmo F5 di Faug`ere: una dimostrazione
alternativa ed alcune generalizzazioni
Alberto Arri 27 Settembre 2007
Oggetto di questa tesi sono lo studio e l’implementazione dell’algorit-mo “F5” di J. C. Faug`ere. Questo `e un algoritdell’algorit-mo recentemente presentato per il calcolo di una base di Gr ¨obner di un ideale dato per generatori, nel corso della tesi viene presentata una dimostrazione originale della corret-tezza dell’algoritmo, assieme ad alcune generalizzazioni, in particolare `e descritta una versione dell’algoritmo che rimuove l’ipotesi che l’input sia una successione regolare.
Inizialmente viene introdotta la teoria delle basi di Gr ¨obner: dagli ordi-namenti di termini, fino alle prime applicazioni; viene descritto l’algoritmo di Buchberger,vengono inoltre presentate le prime applicazioni di questo strumento da un punto di vista computazionale.
Successivamente viene introdotta la nozione di successione regolare e viene descritta la sua relazione con le sizigie principali, con queste nozioni si procede a definire il concetto di “polinomio etichettato”. Un polinomio etichettato `e una coppia di elementi (tei, f) dove f `e un polinomio, e tei,
l’etichetta, `e un termine di modulo; sono esaminate le prime propriet`a al-gebriche di questi oggetti. Con questi si procede a definire la matrice di Macaulay ridotta e l’iterazione fondamentale dell’algoritmo. Viene, infine, dimostrata la correttezza dell’algoritmo nell’ipotesi di regolarit`a dell’input. Nel seguito viene esaminato il caso in cui un passo dell’algoritmo “F5” venga applicato senza l’ipotesi di regolarit`a, in questo caso si presentano alcune differenze nella teoria, in particolare esistono sizigie non principali e le matrici di Macaulay ridotte non hanno sempre rango massimo. Queste difficolt`a si sono rivelate superabili, e infatti viene presentato un algoritmo “generalizzato”, che con alcune modifiche rispetto al caso regolare, non solo calcola una base di Gr ¨obner, ma produce anche altre informazioni sulle sizigie, per la precisione, trova tutti termini di testa delle sizigie di grado minore ad un grado fissato.
Nell’ultima parte si trattano i dettagli pi `u tecnici dell’implementazione di alcune parti dell’algoritmo, e si presentano i benchmark sui tempi ed occupazione di memoria. Rispetto ai tempi riportati dallo stesso Faug`ere
questi sono peggiori; nel complesso, rispetto all’algoritmo di Buchberger, per ordinamenti grado compatibili si riscontra una sostanziale riduzione dei tempi per gli ideali di Katsura, anche di un fattore 10, mentre nella maggiorparte degli altri casi i tempi sono di superiori, a volte di poco, a volte sostanzialmente.
