Base di Gröbner

In algebra commutativa, algebra computazionale e geometria algebrica, una base di Gröbner è un tipo particolare di sottoinsieme generativo di un ideale $I$ in un anello dei polinomi $k[x_{1},\ldots ,x_{n}]$ , dove $k$ è un campo.

La teoria delle basi di Gröbner per gli anelli polinomiali è stata sviluppata da Bruno Buchberger nel 1965, che gli diede tale nome in onore del suo mentore Wolfgang Gröbner. Un concetto analogo per gli anelli locali fu sviluppato indipendentemente da Heisuke Hironaka nel 1964, che diede loro il nome di Basi Standard (Standard Basis).

Una base di Gröbner può essere vista come una generalizzazione multivariata non-lineare dell'algoritmo di Euclide per il calcolo del massimo comun divisore univariato, o dell'eliminazione di Gauss-Jordan per i sistemi lineari, o dei problemi di programmazione intera. Le basi di Gröbner hanno il grande vantaggio di ridurre lo studio degli ideali polinomiali a quello degli ideali monomiali (vale a dire generati da monomi).

Definizione formale

Dato un ordine monomiale $<$ sull'anello polinomiale $R$ , un sottoinsieme $G$ dell'ideale $I\subset R$ è detto una base di Gröbner per $I$ rispetto a $<$ se soddisfa una delle seguenti proprietà:

l'ideale dato dai termini principali dei polinomi nell'ideale $I$ è esso stesso generato dai termini principali della base $G$ ;
il termine principale di ciascun polinomio in $I$ è divisibile per il termine principale di un qualche polinomio della base $G$ ;
la divisione multivariata di ciascun polinomio nell'anello polinomiale $R$ per $G$ restituisce un resto univoco;
la divisione multivariata di ciascun polinomio nell'ideale $I$ per $G$ restituisce $0$ .

Tutte queste proprietà sono equivalenti; le ultime due proprietà consentono di effettuare calcoli nell'anello $R/I$ con la stessa facilità dell'aritmetica modulare. È significativo che ogni ideale polinomiale abbia una base di Gröbner, e che essa possa essere ottenuta per ogni ideale partendo con un sottoinsieme generatore.

La divisione multivariata richiede un ordine monomiale: la base dipende dall'ordinamento scelto, e ordinamenti differenti possono portare a basi di Gröbner radicalmente differenti. Due dei più comuni ordinamenti usati sono l'ordine lessicografico e l'ordinamento sul grado totale. Quest'ultimo ordinamento tipicamente fornisce la maggiore velocità di calcolo delle basi di Gröbner; in questo ordine, i monomi sono inizialmente confrontati per grado totale, e in caso di valori uguali viene considerato il monomio più piccolo rispetto all'ordinamento lessicografico.

Nella maggior parte dei casi le basi di Gröbner esistono per qualsiasi ordinamento monomiale. Un metodo per calcolarle è l'algoritmo di Buchberger. Un altro metodo, basato sulle stesse teorie matematiche dell'algoritmo di Buchberger, è l'algoritmo di Faugère F4. Ci sono anche due algoritmi per convertire una base di Gröbner calcolata rispetto ad un ordinamento monomiale ad una calcolata rispetto ad un altro: l'algoritmo FGLM e l'algoritmo Gröbner walk. Questi algoritmi sono spesso impiegati per calcolare Basi di Gröbner lessicografiche (il cui calcolo è solitamente difficile) a partire dal più facile calcolo rispetto all'ordinamento del grado totale.

Una base di Gröbner è detta ridotta se il coefficiente del monomio principale di ciascun elemento della base è 1 e in nessun elemento della base esiste un monomio che sia contenuto nell'ideale generato dai termini principali degli altri elementi della base.

Nel caso peggiore, il calcolo di una base di Gröbner può richiedere un tempo esponenziale rispetto al numero di soluzioni del sistema polinomiale. Malgrado i limiti derivanti da questa complessità, le basi di Gröbner, sia quelle standard che quelle ridotte, sono spesso effettivamente calcolabili, e la maggior parte dei sistemi di computer algebra contiene specifiche routine.

Bibliografia

(EN) M. Kreuzer, L. Robbiano Computational Commutative Algebra 1 and 2, Springer
Giovanni Calcerano, Basi di Groebner, catene regolari: metodi ed algoritmi per gli ideali polinomiali, tesi di laurea presso la facoltà di Matematica dell'Università La Sapienza di Roma, 1995, relatrice Dina Ghinelli
(EN) Heisuke Hironaka: Resolution of singularities of an algebraic variety over a field of characteristic zero. In: Annals of Mathematics 79 (1964), Nr. 1, S. 109–326
(DE) Bruno Buchberger, Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. Österreich, Universität Innsbruck, Diss., 1965
(EN) T. Becker, B. V. Weispfenning, Gröbner bases: a computational approach to commutative algebra. Graduate Texts in Mathematics: readings in mathematics. Bd. 141, New York: Springer Verlag, 1993
(EN) David Cox, John Little, Donald O'Shea, Ideals, varieties, and algorithms. New York: Springer-Verlag, 1997
(EN) Joachim von z. Gathen, Jürgen Gerhard, Modern Computer Algebra. Cambridge University Press, 1999

Collegamenti esterni

CoCoA [1], Computations in Commutative Algebra
B. Buchberger, Groebner Bases: A Short Introduction for Systems Theorists in Proceedings of EUROCAST 2001.
Comparative Timings Page for Gröbner Bases Software, su magma.maths.usyd.edu.au. URL consultato il 24 novembre 2006 (archiviato dall'url originale il 6 dicembre 2006).
ogb Archiviato il 5 dicembre 2006 in Internet Archive. Online Gröbner Basis, Galway, Eire
Gröbner Basis Theory Leicester University