imported>LogicJo: /* growthexperiments-addlink-summary-summary:1|1|0 */

2025-03-18T08:10:29Z

growthexperiments-addlink-summary-summary:1|1|0

Neue Seite

Der '''Buchberger-Algorithmus''' (nach [[Bruno Buchberger]]) ist in der [[Algebra]] ein Verfahren zur Berechnung einer [[Gröbnerbasis]] eines [[Ideal (Ringtheorie)|Ideals]] in einem [[Polynomring]].

Durch die Möglichkeit, Gröbnerbasen algorithmisch zu bestimmen, sind viele damit lösbare Probleme von [[Computeralgebrasystem]]en lösbar, etwa das [[Gröbnerbasis#Lösung des Idealzugehörigkeitsproblems|Idealzugehörigkeitsproblem]] oder das Lösen bestimmter nicht-linearer Gleichungssysteme (als Beschreibung einer [[Algebraische Varietät#Affine Varietäten|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 [[Gröbnerbasis#Verallgemeinerte Polynomdivision|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 [[Leitmonom]]en 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 [[Hilbertscher Basissatz|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>.

{| class="wikitable"
|-
! 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 ==
* [[Verfahren nach Quine und McCluskey]]

== Einzelnachweise ==
<references>
</references>

== Literatur ==
* {{Literatur | Autor=[[David A. Cox]], [[John B. Little]], [[Donal O’Shea]] | Titel=Ideals, Varieties, and Algorithms | TitelErg=An Introduction to Computational Algebraic Geometry and Commutative Algebra | Auflage=3. | Verlag=Springer| Ort=New York | Datum=2007 | Reihe=Undergraduate Texts in Mathematics | ISBN=978-0-387-35650-1 | Kapitel=2.7. Buchberger's Algorithm}}

[[Kategorie:Theorie der Polynome]]

Buchberger-Algorithmus - Versionsgeschichte

imported>LogicJo: /* growthexperiments-addlink-summary-summary:1|1|0 */