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.

Das Buchberger-Kriterium

Es sei …

• K ein Körper, und $\mathcal{P}=K[X_1,\ldots,X_n]$ der zugehörige Polynomring in n Symbolen,
• $I \subseteq \mathcal{P}$ ein Ideal,
• eine Monomordnung „$\prec$“ auf $\mathcal{P}$ gegeben und
• die verallgemeinerte Polynomdivision mit mehreren teilenden Polynomen definiert.

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

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 hinzufü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.

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

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₁ = X und h₂ = X² + 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