Riassunto analitico
Oggetto di questa tesi sono lo studio e l'implementazione dell'algoritmo ``F5''
di J. C. Faug\`ere.
Questo \`e un algoritmo recentemente presentato per il calcolo di una base di
Groebner di un ideale dato per generatori, nel corso della tesi viene presentata
una dimostrazione originale della correttezza 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 Groebner: dagli
ordinamenti 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 $(te_i,f)$ dove $f$
\`e un polinomio, e $t e_i$, l'etichetta, \`e un termine di modulo;
sono esaminate le prime propriet\`a algebriche 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 \grob/, 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.
|
