Buchberger-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Der Buchberger-Algorithmus (nach Bruno Buchberger) ist in der Algebra ein Verfahren zur Berechnung einer Gröbnerbasis eines Ideals 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.

Das Buchberger-Kriterium[Bearbeiten]

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(h_i, h_j) 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[Bearbeiten]

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

Die Idee ist, dass nach und nach alle S(h_i, h_j) gebildet werden (für sämtliche Paare von verschiedenen Erzeugern h_i und h_j) und die von 0 verschiedenen zum Erzeugendensystem hinzugefügt werden. Mit dem so erweiterten Erzeugendensystem wird das Verfahren so lange wiederholt, bis schließlich alle S(h_i, h_j) 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. Beachte: s \in I \Rightarrow s=0 gilt genau dann, wenn durch eine Gröbnerbasis dividiert wird.

Wenn nach dem j-ten Durchlauf der äußeren Schleife I_j das Ideal ist, das von den Leitmonomen von G_j 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[Bearbeiten]

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 h_1 = X und h_2 = X^2 + 1 im \R[X].

Durchlauf der Äußeren Schleife G p q s = S(p, q) Rest
Erster: ein Paar zu prüfen (X, X^2+1) X X^2 + 1 \frac{X^2}{X}X - \frac{X^2}{X^2}(X^2 + 1) = -1 -1
Zweiter: drei Paare zu prüfen (X, X^2+1, -1) X X^2 + 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
X^2+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[Bearbeiten]

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