Buchberger-Algorithmus

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 von Computeralgebrasystemen lösbar, etwa das Idealzugehörigkeitsproblem oder das Lösen bestimmter nicht-linearer Gleichungssysteme (als Beschreibung einer affinen Varietät).

Das Buchberger-Kriterium

Sei

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

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

${\displaystyle 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 ${\displaystyle \operatorname {LT} (f)}$ den Leitterm eines Polynoms ${\displaystyle f}$ bezeichne, also das bezüglich der Monomordnung ${\displaystyle \prec }$ größte Monom zusammen mit seinem Koeffizienten.

Das Buchbergerkriterium sagt dann, dass ein Erzeugendensystem ${\displaystyle H=(h_{1},\dots ,h_{k})}$ von ${\displaystyle I}$ genau dann eine Gröbnerbasis ist, wenn alle ${\displaystyle S(h_{i},h_{j})}$ bei (verallgemeinerter Polynom-) Division durch ${\displaystyle H}$ den Rest ${\displaystyle 0}$ liefern.^[1]

Der Algorithmus

Der Buchberger-Algorithmus lässt sich dann wie folgt formulieren.^[2]

Die Idee ist, dass nach und nach alle ${\displaystyle S(h_{i},h_{j})}$ gebildet werden (für sämtliche Paare von verschiedenen Erzeugern ${\displaystyle h_{i}}$ und ${\displaystyle h_{j}}$) und die von ${\displaystyle 0}$ verschiedenen Reste zum Erzeugendensystem hinzugefügt werden. Mit dem so erweiterten Erzeugendensystem wird das Verfahren so lange wiederholt, bis schließlich alle ${\displaystyle S(h_{i},h_{j})}$ verschwinden; damit ist das Buchberger-Kriterium erfüllt.

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

Da in jedem Durchlauf der inneren Schleife ${\displaystyle s\in I}$ gilt, ist auch ${\displaystyle \langle G\cup \{s\}\rangle =\langle G\rangle =I}$, man erhält also am Ende wirklich ein Erzeugendensystem von ${\displaystyle I}$ (und nicht etwa von einem größeren Ideal). Dass dieses Erzeugendensystem eine Gröbnerbasis ist, folgt dann aus dem Buchberger-Kriterium. Beachte: ${\displaystyle s\in I\Rightarrow s=0}$ gilt genau dann, wenn durch eine Gröbnerbasis dividiert wird.

Wenn nach dem ${\displaystyle j}$-ten Durchlauf der äußeren Schleife ${\displaystyle I_{j}}$ das Ideal ist, das von den Leitmonomen von ${\displaystyle G_{j}}$ erzeugt wird, so erhalten wir eine Kette ${\displaystyle I_{1}\subseteq I_{2}\subseteq \dots \subseteq I}$ von Idealen. Da eine Kette von Idealen in ${\displaystyle {\mathcal {P}}}$ 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 ${\displaystyle 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 ${\displaystyle h_{1}=X}$ und ${\displaystyle h_{2}=X^{2}+1}$ im ${\displaystyle \mathbb {R} [X]}$.

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

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

Siehe auch

• Verfahren nach Quine und McCluskey

Einzelnachweise

1. Cox, Little, O’Shea: Ideals, Varieties, and Algorithms. 2007, 2.6. Theorem 6.
2. Cox, Little, O’Shea: Ideals, Varieties, and Algorithms. 2007, 2.7. Theorem 2.

Literatur

• David A. Cox, John B. Little, Donal O’Shea: Ideals, Varieties, and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra (= Undergraduate Texts in Mathematics). 3. Auflage. Springer, New York 2007, ISBN 978-0-387-35650-1, 2.7. Buchberger's Algorithm.