Visualizza wikitesto di Base di Gröbner

In [[algebra commutativa]], [[Sistema di algebra computazionale|algebra computazionale]] e [[geometria algebrica]], una '''base di Gröbner''' è un tipo particolare di [[insieme di generatori|sottoinsieme generativo]] di un [[Ideale (matematica)|ideale]] <math>I</math>  in un [[polinomio#Anello di polinomi|anello dei polinomi]]  <math>k[x_1, \ldots, x_n]</math>, dove <math>k</math> è 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 [[anello locale|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 [[sistema lineare|sistemi lineari]], o dei problemi di [[programmazione lineare|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 [[monomio|monomi]]).

==Definizione formale==

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

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

Tutte queste proprietà sono equivalenti; le ultime due proprietà consentono di effettuare calcoli nell'anello <math>R/I</math> 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==

* {{Collegamenti esterni}}
* CoCoA [http://cocoa.dima.unige.it], Computations in Commutative Algebra
* B. Buchberger, {{cita testo|url=http://www.risc.uni-linz.ac.at/people/buchberg/papers/2001-02-19-A.pdf|titolo=Groebner Bases: A Short Introduction for Systems Theorists}}  in ''Proceedings of EUROCAST 2001''.
*{{cita web | url = http://magma.maths.usyd.edu.au/users/allan/gb | titolo = Comparative Timings Page for Gröbner Bases Software | accesso = 24 novembre 2006 | urlarchivio = https://web.archive.org/web/20061206134204/http://magma.maths.usyd.edu.au/users/allan/gb/ | urlmorto = sì }}
*{{cita testo|url=http://grobner.nuigalway.ie/|titolo=ogb|urlarchivio=https://web.archive.org/web/20061205013345/http://grobner.nuigalway.ie/ }} Online Gröbner Basis, Galway, Eire
*{{cita testo|url=http://www.cs.le.ac.uk/people/ah83/grobner/|titolo=Gröbner Basis Theory}} Leicester University

{{algebra}}

{{Controllo di autorità}}
{{Portale|matematica}}

[[Categoria:Geometria algebrica]]
[[Categoria:Combinatoria algebrica]]
[[Categoria:Algebra commutativa]]