Baza Gröbnera

Baza Gröbnera – szczególny sposób generowania podzbioru ideału I w pierścieniu wielomianów R. Można ją uważać za nieliniowe uogólnienie następujących algorytmów:

• algorytmu Euklidesa obliczania największego wspólnego dzielnika dwóch wielomianów jednej zmiennej,
• metody eliminacji Gaussa dla układów równań liniowych,
• metody sympleksu w programowaniu liniowym.

Teoria baz Gröbnera dla pierścieni wielomianowych została odkryta przez Bruno Buchbergera w roku 1965^[1], który nazwał ją tak na cześć swojego nauczyciela Wolfganga Gröbnera. The Association for Computing Machinery przyznało mu za tę pracę w roku 2007 nagrodę Paris Kanellakis Theory and Practice Award. Analogiczne koncepcje dla pierścieni lokalnych były niezależnie odkryte przez Heisuke Hironakę w 1964, który nazwał je bazami standardowymi. Podobna teoria dla wolnych algebr Liego została odkryta przez rosyjskiego matematyka A. I. Szirszowa w 1962 roku^[2], ale jego praca nie była znana poza ZSRR.

Definicja formalna

Baza Gröbnera^[3] G ideału I w pierścieniu wielomianowym R nad ciałem jest charakteryzowana jedną z następujących własności, odpowiadających pewnemu uporządkowaniu jednomianowemu:

• ideał generowany przez największe wyrazy wielomianów z I jest jednocześnie generowany przez największe wyrazy G;
• największy wyraz każdego wielomianu w I jest podzielny przez największy wyraz pewnego wielomianu w G;
• dzielenie wielu zmiennych każdego wielomianu z pierścienia wielomianowego R przez G daje jednoznaczną resztę;
• dzielenie wielu zmiennych każdego wielomianu ideału I przez G daje 0.

Wszystkie te własności są równoważne; różni autorzy używają różnych definicji w zależności od wybranego celu. Ostatnie dwie własności pozwalają obliczyć pierścień ilorazowy R/I w taki sam sposób, jak w arytmetyce modularnej. Doniosłym faktem algebry przemiennej jest to, że baza Gröbnera zawsze istnieje i może być efektywnie wyznaczona dla każdego ideału wyznaczonego przez zbiór generatorów.

Dzielenie wielu zmiennych wymaga uporządkowania jednomianów. Dlatego bazy zależą od wyboru tego porządku, a różne porządki mogą prowadzić do różnych baz Gröbnera. Dwoma z najbardziej używanych porządków są porządek leksykograficzny i porządek leksykograficzny odwrotnego stopnia (nazywany także porządkiem leksykograficznym z odwrotną gradacją). Porządek leksykograficzny pozwala na eliminację zmiennych, jednak otrzymywane bazy Gröbnera są często bardzo duże i żmudne w obliczeniach. Porządek leksykograficzny odwrotnego stopnia zwykle umożliwia szybsze obliczenie bazy Gröbnera.

W większości przypadków (wielomiany skończenie wielu zmiennych o wspólczynnikach zespolonych lub, bardziej ogólnie, o współczynnikach w dowolnym ciele), bazy Gröbnera istnieją dla dowolnego porządku jednomianów. algorytm Buchbergera jest najstarszą i najbardziej znaną metodą ich obliczania. Innymi metodami są algorytm Faugère F4, oparty na tych samych ideach matematycznych, co algorytm Buchbergera, podejścia potęgowe, oparte na ideach algebry różniczkowej^[4]. Istnieją także trzy algorytmy pozwalające na przekształcenie bazy Gröbnera względem jednego uporządkowania jednomianów w bazę Gröbnera względem innego uporządkowania jednomianów: algorytm FGLM, algorytm Hilbert Driven i algorytm Gröbner walk. algorytmy te są często wykorzystywane do obliczania (trudnych) leksykograficznych baz Gröbnera bazując na (łatwiejszych) baz Gröbnera z odwrotną gradacją.

Koncepcja i algorytmy bazy Gröbnera zostały uogólnione na moduły nad `pierścieniami wielomianowymi, na wolne nieprzemienne pierścienie wielomianowe oraz, przez Weispfenning i jego szkołę, na rozwiązalne pierścienie wielomianowe, takie jak algebry Weyla.

Przypisy

Bibliografia

• William W. Adams, Philippe Loustaunau (1994). An Introduction to Gröbner Bases. American Mathematical Society, Graduate Studies in Mathematics, Volume 3. ISBN 0-8218-3804-0
• Thomas Becker, Volker Weispfenning (1998). Gröbner Bases. Springer Graduate Texts in Mathematics 141. ISBN 0-387-97971-9
• Bruno Buchberger (1965). An Algorithm for Finding the Basis Elements of the Residue Class Ring of a Zero Dimensional Polynomial Ideal. Ph.D. dissertation, University of Innsbruck. English translation by Michael Abramson in Journal of Symbolic Computation 41 (2006): 471–511. [This is Buchberger's thesis inventing Gröbner bases.]
• Bruno Buchberger (1970). An Algorithmic Criterion for the Solvability of a System of Algebraic Equations. Aequationes Mathematicae 4 (1970): 374–383. English translation by Michael Abramson and Robert Lumbert in Gröbner Bases and Applications (B. Buchberger, F. Winkler, eds.). London Mathematical Society Lecture Note Series 251, Cambridge University Press, 1998, 535–545. ISBN 0-521-63298-6 (This is the journal publication of Buchberger's thesis.)
• Chapter 2: Gröbner Bases. W: David Cox, John Little, and Donal O'Shea: Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer, 1997. ISBN 0-387-94680-2.brak strony w książce
• Ralf Fröberg: An Introduction to Gröbner Bases. Wiley & Sons, 1997. ISBN 0-471-97442-0.brak strony w książce
• Bernd Sturmfels. What is . . . a Gröbner Basis?. „Notices of the American Mathematical Society”. 52 (10), s. 1199–1200, November 2005. 
• A. I. Shirshov. Certain algorithmic problems for Lie algebras. „ACM SIGSAM Bulletin”. 33 (2), s. 3–6, 1999.  (translated from Sibirsk. Mat. Zh. Siberian Mathemaics Journal, 3 (1962), 292–296)
• M. Aschenbrenner and C. Hillar, Finite generation of symmetric ideals, Trans. Amer. Math. Soc. 359 (2007), 5171–5192 (on infinite dimensional Gröbner bases for polynomial rings in infinitely many indeterminates).

Linki zewnętrzne

• B. Buchberger, Groebner Bases: A Short Introduction for Systems Theorists in Proceedings of EUROCAST 2001.
• Buchberger, B. and Zapletal, A. Gröbner Bases Bibliography.
• Comparative Timings Page for Gröbner Bases Software
• ogb. grobner.nuigalway.ie. [zarchiwizowane z tego adresu (2011-07-17)]. Online Gröbner Basis, Galway, Éire
• Java applet for computing Gröbner bases. iisdavinci.it. [zarchiwizowane z tego adresu (2011-07-22)]. by Fabrizio
• Gröbner Basis Theory Leicester University
• Prof. Bruno Buchberger Bruno Buchberger