Buchberger-Algorithmus

Buchberger-Algorithmus

Der Buchberger-Algorithmus (nach Bruno Buchberger) ist in der Algebra ein Verfahren zur Berechnung einer Gröbnerbasis von einem Ideal in einem Polynomring.

Durch die Möglichkeit, Gröbnerbasen algorithmisch zu bestimmen sind viele damit lösbare Probleme, etwa das Idealzugehörigkeitsproblem oder das Lösen bestimmter nicht-linearer Gleichungssysteme (als Beschreibung einer affinen Varietät), von Computeralgebrasystemen lösbar.

Inhaltsverzeichnis

Das Buchberger-Kriterium

Es sei …

Ferner sei für je zwei Polynome f, g \in \mathcal{P} \setminus \{0\}

S(f, g) = \frac{\operatorname{kgV}(\operatorname{LT}(f), \operatorname{LT}(g))}{\operatorname{LT}(f)}f - \frac{\operatorname{kgV}(\operatorname{LT}(f), \operatorname{LT}(g))}{\operatorname{LT}(g)}g

erklärt, wobei \operatorname{LT}(f) den Leitterm eines Polynoms f bezeichne, also das bezüglich der Monomordnung \prec größte Monom zusammen mit seinem Koeffizienten.

Das Buchbergerkriterium sagt dann, dass ein Erzeugendensystem H = (h_1, \dots, h_k) von I genau dann eine Gröbnerbasis ist, wenn alle S(hi,hj) bei (verallgemeinerter Polynom-) Division durch H den Rest 0 liefern.

Ein Beweis des Buchberger-Kriteriums ist in Cox, Little, O'Shea: Ideals, Varieties and Algorithms, S. 84-86 zu finden.

Der Algorithmus

Der Buchberger-Algorithmus lässt sich dann wie folgt formulieren.

Die Idee ist, dass nach und nach alle S(hi,hj) gebildet werden (für sämtliche Paare von verschiedenen Erzeugern hi und hj) und die von 0 verschiedenen zum Erzeugendensystem hinzufügt werden. Mit dem so erweiterten Erzeugendensystem wird das Verfahren so lange wiederholt, bis schließlich alle S(hi,hj) verschwinden; damit ist das Buchberger-Kriterium erfüllt.

 INPUT: H = (h_1, \dots, h_s)
 OUTPUT: Gröbnerbasis G = (g_1, \dots, g_t)
 INIT: G: = H
 1. DO
 2.     G': = G
 3.     FOREACH p, q \in G', p \neq q
 4.         s = Rest(S(p,q),G)
 5.         IF s \neq 0 THEN G := G \cup \{s\}
 6.     NEXT
 7. UNTIL G = G'

Da in jedem Durchlauf der inneren Schleife s \in I gilt, ist auch \langle G \cup \{s\}\rangle = \langle G\rangle = I, man erhält also am Ende wirklich ein Erzeugendensystem von I (und nicht etwa von einem größeren Ideal); dass dieses Erzeugendensystem eine Gröbnerbasis ist, folgt dann aus dem Buchberger-Kriterium.

Wenn nach dem j-ten Durchlauf der äußeren Schleife Ij das Ideal ist, das von den Leitmonomen von Gj erzeugt wird, so erhalten wir eine Kette I_1 \subseteq I_2 \subseteq \dots \subseteq I von Idealen. Da eine Kette von Idealen nicht endlos (echt) aufsteigen kann (eine einfache Folgerung aus dem Hilbertschen Basissatz) muss diese Kette schließlich konstant bleiben. Das heißt aber, dass ab dann keine neuen Leitmonome mehr zu G hinzugefügt werden; der Algorithmus terminiert somit an dieser Stelle, d. h. nach endlich vielen Schritten.

Beispiel

Die Gröbnerbasis, die der Algorithmus liefert, wird schnell sehr groß und damit unübersichtlich; außerdem ist auch das Auswerten der Polynomdivisionen recht aufwändig. Daher soll der Algorithmus hier nur für ein sehr kleines und einfaches Beispiel vorgeführt werden: Gegeben seien h1 = X und h2 = X2 + 1 im \R[X].

Durchlauf der Äußeren Schleife G p q s = S(p,q) Rest
Erster: ein Paar zu prüfen (X,X2 + 1) X X2 + 1 \frac{X^2}{X}X - \frac{X^2}{X^2}(X^2 + 1) = -1 − 1
Zweiter: drei Paare zu prüfen (X,X2 + 1, − 1) X X2 + 1 \frac{X^2}{X}X - \frac{X^2}{X^2}(X^2 + 1) = -1 0
X − 1 \frac{X}{X}X - \frac{X}{-1}(-1) = 0 0
X2 + 1 − 1 \frac{X^2}{X^2}(X^2+1) - \frac{X^2}{-1}(-1) = 1 0

Somit ist das Buchberger-Kriterium schon erfüllt, nachdem − 1 als Erzeuger hinzugenommen wurde und der Algorithmus bricht ab, da im zweiten Durchlauf der Schleife kein neuer Erzeuger zu G hinzugefügt wurde.

Literatur

  • David Cox; Little, John; O'Shea, Donald: Ideals, varieties, and algorithms. New York: Springer-Verlag, 1997

Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Bruno Buchberger — 2005 Bruno Buchberger (* 22. Oktober 1942 in Innsbruck) ist ein österreichischer Mathematiker. Inhaltsverzeichnis 1 …   Deutsch Wikipedia

  • Bruno Buchberger — Pour les articles homonymes, voir Buchberger. Bruno Buchberger. Bruno Buchberger est un mathématicien autrichien né le 22  …   Wikipédia en Français

  • Gröbnerbasis — Eine Gröbnerbasis (nach Bruno Buchberger, 1965) bzw. Standardbasis (nach Heisuke Hironaka, 1964) ist ein endliches Erzeugendensystem zu einem Ideal I im Polynomring über dem (kommutativen) Körper K, das besonders gut dafür geeignet ist, zu… …   Deutsch Wikipedia

  • Gröbner-Basis — Eine Gröbnerbasis (nach Bruno Buchberger, 1965) bzw. Standardbasis (nach Heisuke Hironaka, 1964) ist eine endliche Idealbasis zu einem Ideal I im Polynomring über dem (kommutativen) Körper K, die besonders gut dafür geeignet ist, zu entscheiden,… …   Deutsch Wikipedia

  • Paris-Kanellakis-Preis — Der Paris Kanellakis Preis (Paris Kanellakis Theory and Practice Award) ist ein Informatikpreis der Association for Computing Machinery (ACM) für theoretische Errungenschaften, die eine bedeutende Auswirkung in der Praxis des Rechnens haben. Er… …   Deutsch Wikipedia

  • Grafikfähiger Taschenrechner — TI 89, Grafikrechner mit CAS Ein grafikfähiger Taschenrechner (kurz Grafikrechner oder GTR) besitzt die Funktionen eines normalen Taschenrechners. Er hat jedoch ein höherauflösendes Display, das Ein und Ausgaben mehrzeilig darstellen und einfache …   Deutsch Wikipedia

  • Polynomrestfolge — Eine Polynomrestfolge entsteht durch wiederholte Division mit Rest zweier Polynome. Falls es sich um Polynome mit Koeffizienten aus einem Körper handelt, liefert zum Beispiel der euklidische Algorithmus eine solche Folge. Im allgemeineren Fall… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”