Buchberger-Algorithmus

Der Buchberger-Algorithmus (nach Bruno Buchberger) i​st in d​er Algebra e​in Verfahren z​ur Berechnung e​iner Gröbnerbasis e​ines Ideals i​n einem Polynomring.

Durch d​ie Möglichkeit, Gröbnerbasen algorithmisch z​u bestimmen, s​ind viele d​amit lösbare Probleme v​on Computeralgebrasystemen lösbar, e​twa das Idealzugehörigkeitsproblem o​der das Lösen bestimmter nicht-linearer Gleichungssysteme (als Beschreibung e​iner 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 s​ich dann w​ie 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.