Baza Gröbner

În algebra comutativă , algebră de calcul și geometrie algebrică , baza Gröbner este un tip particular de subset generativ al unui ideal $THE$ ${\ displaystyle I}$ $THE$ într-un inel polinomial $R.$ ${\ displaystyle R}$ $R.$ .

Teoria lui Gröbner a bazelor pentru inelele polinomiale a fost dezvoltată de Bruno Buchberger în 1965 , care i-a dat numele în onoarea mentorului său Wolfgang Gröbner . Un concept similar pentru inelele locale a fost dezvoltat independent de Heisuke Hironaka în 1964 , care le-a dat numele de Standard Basis.

O bază Gröbner poate fi văzută ca o generalizare neliniară multivariată a algoritmului lui Euclid pentru calculul celui mai mare divizor comun univariat sau a eliminării Gauss-Jordan pentru sistemele liniare sau a problemelor de programare întregi . Bazele Gröbner au marele avantaj de a reduce studiul idealurilor polinomiale la cel al idealurilor monomiale (adică generate de monomii ).

Definiție formală

Având în vedere o ordine monomială $<$ ${\ displaystyle <}$ $<$ pe inelul polinomial $R.$ ${\ displaystyle R}$ $R.$ , un subset $G.$ ${\ displaystyle G}$ $G.$ a idealului $I\subset R$ ${\ displaystyle I \ subset R}$ ${\ displaystyle I \ subset R}$ se spune că este o bază Gröbner pentru $THE$ ${\ displaystyle I}$ $THE$ în comparație cu $<$ ${\ displaystyle <}$ $<$ dacă îndeplinește una dintre următoarele proprietăți:

idealul dat de termenii principali ai polinoamelor din ideal $THE$ ${\ displaystyle I}$ $THE$ ea însăși este generată de termenii principali ai bazei $G.$ ${\ displaystyle G}$ $G.$ ;
termenul principal al fiecărui polinom în $THE$ ${\ displaystyle I}$ $THE$ este divizibil cu termenul principal al unui polinom de bază $G.$ ${\ displaystyle G}$ $G.$ ;
diviziunea multivariată a fiecărui polinom din inelul polinomial $R.$ ${\ displaystyle R}$ $R.$ pentru $G.$ ${\ displaystyle G}$ $G.$ returnează un rest unic;
împărțirea multivariată a fiecărui polinom în ideal $THE$ ${\ displaystyle I}$ $THE$ pentru $G.$ ${\ displaystyle G}$ $G.$ se intoarce.

Toate aceste proprietăți sunt echivalente; ultimele două proprietăți vă permit să efectuați calcule în ring $R/I$ ${\ displaystyle R / I}$ ${\ displaystyle R / I}$ cu aceeași ușurință a aritmeticii modulare. Este semnificativ faptul că fiecare ideal polinomial are o bază Gröbner și că poate fi obținut pentru fiecare ideal începând cu un subset generator.

Împărțirea multivariată necesită o ordine monomială: baza depinde de ordinea aleasă și o ordonare diferită poate duce la baze Gröbner radical diferite. Două dintre cele mai frecvente ordonări utilizate sunt ordinea lexicografică și ordonarea gradului total . Această ultimă comandă oferă de obicei cel mai rapid calcul al bazelor Gröbner; în această ordine, monomiile sunt comparate inițial în funcție de gradul total, iar în cazul valorilor egale se consideră cel mai mic monom în raport cu ordinea lexicografică.

În majoritatea cazurilor, bazele Gröbner există pentru orice ordine monomială. O metodă pentru calcularea acestora este algoritmul Buchberger . O altă metodă, bazată pe aceleași teorii matematice ca și algoritmul Buchberger, este algoritmul Faugère F4 . Există, de asemenea, doi algoritmi pentru conversia unei baze Gröbner calculată în raport cu o ordonare monomială la una calculată față de alta: algoritmul FGLM și algoritmul de mers Gröbner . Acești algoritmi sunt adesea utilizați pentru a calcula bazele lexicografice Gröbner (al căror calcul este de obicei dificil) pornind de la cel mai ușor calcul comparativ cu ordonarea gradului total.

O bază Gröbner se numește redusă dacă coeficientul monomiului principal al fiecărui element al bazei este 1 și în niciun element al bazei nu există un monomiu care este conținut în idealul generat de termenii principali ai celorlalte elemente ale bazei .

În cel mai rău caz, calculul unei baze Gröbner poate dura un timp exponențial în raport cu numărul de soluții ale sistemului polinomial. În ciuda limitărilor acestei complexități, atât bazele Gröbner standard, cât și cele reduse sunt adesea de fapt calculabile, iar majoritatea sistemelor de algebră computerizată conțin rutine specifice.

Bibliografie

( EN ) M. Kreuzer, L. Robbiano Computational Commutative Algebra 1 and 2 , Springer
Giovanni Calcerano, baze Groebner, lanțuri regulate: metode și algoritmi pentru idealuri polinomiale , teză de diplomă la Facultatea de Matematică a Universității La Sapienza din Roma, 1995, conducător Dina Ghinelli
( EN ) Heisuke Hironaka: Rezoluția singularităților unui soi algebric pe un câmp cu zero caracteristic. În: Annals of Mathematics 79 (1964), No. 1, S. 109–326
( DE ) Bruno Buchberger, Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal . Österreich, Universitatea Innsbruck, Diss., 1965
( EN ) T. Becker, BV Weispfenning, baze Gröbner: o abordare de calcul a algebrei comutative . Texte postuniversitare în matematică: lecturi în matematică. Bd. 141, New York: Springer Verlag, 1993
(EN) David Cox, John Little, Donald O'Shea, Ideals, varietăți și algoritmi. New York: Springer-Verlag, 1997
( EN ) Joachim von z. Gathen, Jürgen Gerhard, Modern Computer Algebra . Cambridge University Press, 1999

linkuri externe

CoCoA [1] , Calcule în algebră comutativă
B. Buchberger, Bazele Groebner: o scurtă introducere pentru teoreticienii sistemelor în procedurile din EUROCAST 2001 .
Pagina de timp comparativ pentru software-ul bazelor Gröbner , la magma.maths.usyd.edu.au . Adus la 24 noiembrie 2006 (arhivat din original la 6 decembrie 2006) .
ogb Arhivat 5 decembrie 2006 la Internet Archive . Online Gröbner Basis, Galway, Eire
Teoria bazei Gröbner Universitatea Leicester

Controlul autorității	LCCN (EN) sh92005856 · GND (DE) 4276378-2 · BNF (FR) cb124219399 (data)

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică