Baza Gröbnera

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

W algebrze numerycznej, numerycznej geometrii algebraicznej, i numerycznej algebrze przemiennej, baza Gröbnera jest szczególnym sposobem 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:

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[edytuj | edytuj kod]

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

  1. 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.
  2. A. I. Shirshov. Certain algorithmic problems for Lie algebras. „ACM SIGSAM Bulletin”, s. 3–6, 1999.  (translated from Sibirsk. Mat. Zh. Siberian Mathemaics Journal, 3 (1962), 292–296)
  3. Bernd Sturmfels. What is . . . a Gröbner Basis?. „Notices of the American Mathematical Society”, s. 1199–1200, Listopad 2005. 
  4. Vladimir P. Gerdt, Yuri A. Blinkov (1998). Involutive Bases of Polynomial Ideals, Mathematics and Computers in Simulation, 45:519ff

Bibliografia[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]