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
- <math>K</math> ein Körper, und <math>\mathcal{P}=K[X_1,\ldots,X_n]</math> der zugehörige Polynomring in <math>n</math> Symbolen,
- <math>I \subseteq \mathcal{P}</math> ein Ideal,
- eine Monomordnung „<math>\prec</math>“ auf <math>\mathcal{P}</math> gegeben,
- die verallgemeinerte Polynomdivision mit mehreren teilenden Polynomen definiert.
Ferner sei für je zwei Polynome <math>f, g \in \mathcal{P} \setminus \{0\}</math>
- <math>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</math>
erklärt, wobei <math>\operatorname{LT}(f)</math> den Leitterm eines Polynoms <math>f</math> bezeichne, also das bezüglich der Monomordnung <math>\prec</math> größte Monom zusammen mit seinem Koeffizienten.
Das Buchbergerkriterium sagt dann, dass ein Erzeugendensystem <math>H = (h_1, \dots, h_k)</math> von <math>I</math> genau dann eine Gröbnerbasis ist, wenn alle <math>S(h_i, h_j)</math> bei (verallgemeinerter Polynom-) Division durch <math>H</math> den Rest <math>0</math> liefern.<ref>Cox, Little, O’Shea: Ideals, Varieties, and Algorithms. 2007, 2.6. Theorem 6.</ref>
Der Algorithmus
Der Buchberger-Algorithmus lässt sich dann wie folgt formulieren.<ref>Cox, Little, O’Shea: Ideals, Varieties, and Algorithms. 2007, 2.7. Theorem 2.</ref>
Die Idee ist, dass nach und nach alle <math>S(h_i, h_j)</math> gebildet werden (für sämtliche Paare von verschiedenen Erzeugern <math>h_i</math> und <math>h_j</math>) und die von <math>0</math> verschiedenen Reste zum Erzeugendensystem hinzugefügt werden. Mit dem so erweiterten Erzeugendensystem wird das Verfahren so lange wiederholt, bis schließlich alle <math>S(h_i, h_j)</math> verschwinden; damit ist das Buchberger-Kriterium erfüllt.
INPUT: <math>H = (h_1, \dots, h_s)</math>
OUTPUT: Gröbnerbasis <math>G = (g_1, \dots, g_t)</math>
INIT: <math>G := H</math>
1. DO
2. <math>G' := G</math>
3. FOREACH <math>p, q \in G', p \neq q</math>
4. <math>s = Rest(S(p, q), G)</math>
5. IF <math>s \neq 0</math> THEN <math>G := G \cup \{s\}</math>
6. NEXT
7. UNTIL <math>G = G'</math>
Da in jedem Durchlauf der inneren Schleife <math>s \in I</math> gilt, ist auch <math>\langle G \cup \{s\}\rangle = \langle G\rangle = I</math>, man erhält also am Ende wirklich ein Erzeugendensystem von <math>I</math> (und nicht etwa von einem größeren Ideal). Dass dieses Erzeugendensystem eine Gröbnerbasis ist, folgt dann aus dem Buchberger-Kriterium. Beachte: <math>s \in I \Rightarrow s=0</math> gilt genau dann, wenn durch eine Gröbnerbasis dividiert wird.
Wenn nach dem <math>j</math>-ten Durchlauf der äußeren Schleife <math>I_j</math> das Ideal ist, das von den Leitmonomen von <math>G_j</math> erzeugt wird, so erhalten wir eine Kette <math>I_1 \subseteq I_2 \subseteq \dots \subseteq I</math> von Idealen. Da eine Kette von Idealen in <math>\mathcal{P}</math> 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 <math>G</math> 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 <math>h_1 = X</math> und <math>h_2 = X^2 + 1</math> im <math>\R[X]</math>.
| Durchlauf der Äußeren Schleife | <math>G</math> | <math>p</math> | <math>q</math> | <math>s = S(p, q)</math> | <math>Rest</math> |
|---|---|---|---|---|---|
| Erster: ein Paar zu prüfen | <math>(X, X^2+1)</math> | <math>X</math> | <math>X^2 + 1</math> | <math>\frac{X^2}{X}X - \frac{X^2}{X^2}(X^2 + 1) = -1</math> | <math>-1</math> |
| Zweiter: drei Paare zu prüfen | <math>(X, X^2+1, -1)</math> | <math>X</math> | <math>X^2 + 1</math> | <math>\frac{X^2}{X}X - \frac{X^2}{X^2}(X^2 + 1) = -1</math> | <math>0</math> |
| <math>X</math> | <math>-1</math> | <math>\frac{X}{X}X - \frac{X}{-1}(-1) = 0</math> | <math>0</math> | ||
| <math>X^2+1</math> | <math>-1</math> | <math>\frac{X^2}{X^2}(X^2+1) - \frac{X^2}{-1}(-1) = 1</math> | <math>0</math> |
Somit ist das Buchberger-Kriterium schon erfüllt, nachdem <math>-1</math> als Erzeuger hinzugenommen wurde und der Algorithmus bricht ab, da im zweiten Durchlauf der Schleife kein neuer Erzeuger zu <math>G</math> hinzugefügt wurde.
Siehe auch
Einzelnachweise
<references> </references>
Literatur
- {{#invoke:Vorlage:Literatur|f}}