Universität Regensburg Naturwissenschaftliche Fakultät I

Mathematik

Optimierung des Buchberger-Algorithmus

im homogenen Fall

Diplomarbeit

von

Jens Schmidbauer

gestellt von

Prof. Dr. Martin Kreuzer

Abgabetermin: 17. Juli 2002

Inhaltsverzeichnis

Inhaltsverzeichnis 1

Einleitung 2

1 Grundlagen 5 1.1 Terme und Termordnungen . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Normale Reste und Ersetzungsregeln . . . . . . . . . . . . . . . . . . 7 1.3 Graduierungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.4 Syzygien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.5 Gröbnerbasen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.6 Normalformen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2 Der Buchberger-Algorithmus und die Optimierung der abzuarbeitenden Paare 15 2.1 Der Buchberger-Algorithmus . . . . . . . . . . . . . . . . . . . . . . 15 2.2 Die Gebauer-Möller-Installation . . . . . . . . . . . . . . . . . . . . . 17 2.3 Der Buchberger-Algorithmus im homogenen Fall . . . . . . . . . . . 19 2.4 Buchberger-Algorithmus mit Minimalisierung der Paare . . . . . . . 21

3 Optimierung der Reduktion im Buchberger-Algorithmus 24 3.1 Darstellung homogener Polynome in Computersystemen . . . . . . . 24 3.2 Buchberger-Algorithmus mit Multireduktion . . . . . . . . . . . . . . 28 3.3 Faugéres Algorithmus F_{4} . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.4 Optimierung von F_{4} . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4 Effizienzvergleiche zwischen verschiedenen Algorithmen und Optimierungen 40 4.1 Lohnen sich Optimierungen? . . . . . . . . . . . . . . . . . . . . . . 43 4.2 Ist F_{4} konkurrenzfähig? . . . . . . . . . . . . . . . . . . . . . . . . . 44 4.3 Normale Reduktion oder Multireduktion? Paarminimalisierung? … 45

Bezeichnungen 49

Literaturverzeichnis 51

Stichwortverzeichnis 52

Erklärung 54

Einleitung

Als Bruno Buchberger 1965 seine Doktorarbeit ([Bu 1]) vollendete, hätte sich wohl niemand – am wenigsten er selbst – träumen lassen, dass sein ”Algorithmus zum Auffinden der Basiselemente des Restklassenrings nach einem nulldimensionalen Polynomideal“ einst in die Geschichte der Mathematik eingehen und überdies die Lösungsgrundlage für eine Vielzahl praktischer Anwendungen auf den unterschiedlichsten Gebieten sein würde. Tatsächlich blieb seine Idee zunächst einige Zeit unbeachtet und wurde erst Ende der Siebzigerjahre wiederentdeckt. In den Folgejahren wurden auf der ganzen Welt zahlreiche Forschungen zur Verbesserung und Erweiterung des Algorithmus betrieben und die letzten Jahre brachten zahlreiche Bücher hervor, die sich mit dem Thema ”Gröbnerbasis“ befassen. Die so genannte Gröbnerbasis ist nämlich das Ziel von Buchbergers Algorithmus, sozusagen das ”Objekt der Begierde“, denn sie ist das Ergebnis der Berechnungen. Genauer müsste man sagen, das Ergebnis ist eine Gröbnerbasis, da hier keineswegs Eindeutigkeit vorliegt. Es ist jedoch immer möglich, aus einer beliebigen Gröbnerbasis eines Ideals die ”reduzierte“ Gröbnerbasis zu berechnen, die verschärften Bedingungen genügt, welche dann die Eindeutigkeit garantieren. Gröbnerbasen sind spezielle Erzeugendensysteme von Idealen, die etliche nützliche Eigenschaften besitzen, so dass mit ihrer Hilfe verschiedene Berechnungen für das betrachtete Ideal möglich sind, die gewöhnliche Erzeugendensysteme nicht zulassen würden. Auf diese Weise können mit dem Computer in Sekundenschnelle Kalkulationen auf unendlichen Polynomidealen durchgeführt werden, was früher schlichtweg undenkbar war. Beispielsweise kann mithilfe einer Gröbnerbasis durch eine einfache Division mit Rest entschieden werden, ob ein betrachtetes Polynom im fraglichen Ideal liegt oder nicht. Es ist also nicht verwunderlich, dass viele Computeralgebrasysteme (z. B. CoCoA, Singular, Macaulay) die Idee von Gröbnerbasen und Buchberger-Algorithmus aufgriffen oder sogar daraus entstanden, um so als effektives Hilfsmittel vor allem – aber nicht nur – in den Bereichen der kommutativen Algebra und algebraischen Geometrie eingesetzt werden zu können. Weitere Einsatzmöglichkeiten von Gröbnerbasen gibt es nicht nur in mathematischen Bereichen wie Zahlentheorie, Kombinatorik, Statistik, Differentialgleichungen, Codierungstheorie und Kryptographie, sondern auch in Gebieten wie Betriebswirtschaft (Ablaufplanung, Warteschlangentheorie, Finanzierung), Robotik, Informatik (künstliche Intelligenz), Computergrafik (CAD, Splines), usw. Der interessierte Leser findet zahlreiche Anwendungsbeispiele unter anderem in [KrRo 1], [KrRo 2] und [Bu 2]. Den Begriff ”Gröbnerbasis“ führte Buchberger erst im Jahre 1976 ein, zu Ehren seines Doktorvaters Wolfgang Gröbner, der ihn auch zur Verwendung der so genannten S-Polynome inspirierte, einer wichtigen Säule des Buchberger-Algorithmus. Bis zu diesem Zeitpunkt wurde die weniger spezielle Bezeichnung ”Standardbasis“ verwendet, die kurz vor Buchberger schon von Heisuke Hironaka verwendet wurde, der bereits ihre Existenz bewies. Buchberger war jedoch der erste, dem es gelang, einen Algorithmus für die Berechnung zu entwickeln.

Nachdem die Bedeutung der Gröbnerbasen und somit von Buchbergers Algorithmus erkannt worden war, forschte man vielerorts an diversen Optimierungen und zahlreiche Arbeiten befassten sich mit der Thematik. Die erste Möglichkeit, Verbesserungen zu finden, bestand in der Verkleinerung der im Algorithmus verwendeten Menge der ”kritischen Paare“. Diese Menge enthält alle Indexpaare aller im Laufe der Berechnung gefundenen Elemente der Gröbnerbasis; das sind bei s Elementen immerhin \binom{s}{2} Paare. All diese Paare müssen nachfolgend verarbeitet werden bzw. das zum jeweiligen Paar gehörige S-Polynom muss mit den schon bekannten Gröbnerbasiselementen reduziert werden, was durchaus in einem längeren Berechnungsprozess resultieren kann. Da keine neuen Polynome zur Gröbnerbasis hinzugefügt werden, falls sich bei dieser Rechnung 0 ergibt, liegt es nahe, einfach zu überprüfende Kriterien zu suchen, die vorhersagen können, ob das Ergebnis mit Sicherheit 0 sein wird. In diesem Fall müsste man keine Reduktion durchführen und könnte so an Effizienz gewinnen. Diese Effizienzsteigerung ist natürlich umso höher, je mehr Paare man von vornherein ausschließen kann. Die ersten beiden Kriterien zur Verkleinerung der Paarmenge stellte Buchberger selbst auf (siehe [Bu 2]). Das erste Kriterium untersucht Zusammenhänge der kleinsten gemeinsamen Vielfachen von jeweils drei Leittermen von Gröbnerbasiselementen, während das zweite Kriterium nur die beiden zu einem betrachteten Paar gehörigen Elemente benötigt und in Kraft tritt, falls deren Leitterme teilerfremd sind. Die Kriterien Buchbergers untersuchten Rüdiger Gebauer und Hans Michael Möller bald danach genauer (siehe [GeMö]). Es gelang ihnen, diese neu zu formulieren sowie eine dritte Regel zu finden, so dass jeweils nur Teilbarkeiten zwischen denjenigen Termen untersucht werden müssen, die den Paaren entsprechen. Der Buchberger-Algorithmus wurde seit 1988 in den meisten Realisierungen mit diesen drei Regeln implementiert, seither als ”Gebauer-Möller-Installation“ bekannt. Der Weiterentwicklung der Regeln von Gebauer und Möller speziell im homogenen Fall widmeten sich Martin Kreuzer und Lorenzo Robbiano in den letzten Jahren (siehe [CaKrRo]). Mit der Ersetzung der dritten Regel durch die entsprechende ”Antiregel“ werden dabei besonders geeignete Paare zur späteren weiteren Verkleinerung der Menge aller Paare selektiert. Durch diese Vorgehensweise wird die Anzahl der Paare soweit verkleinert, dass nur noch diejenigen Paare abgearbeitet werden müssen, deren assoziierte Syzygien ein minimales Erzeugendensystem des Syzygienmoduls bilden, was in diesem Fall die Bezeichnung ”Buchberger-Algorithmus mit Paarminimalisierung“ rechtfertigt.

Ein anderer Ansatz zur Verbesserung des Buchberger-Algorithmus ist die Optimierung bzw. Ersetzung der normalen Reduktion durch eine dieser entsprechenden Funktion. Diese Methoden sind unabhängig von der Verkleinerung der Menge der kritischen Paare. Das bringt den Vorteil mit sich, dass beide Optimierungsarten kombiniert werden können, um so ein noch besseres Ergebnis zu erzielen. Die Hauptidee dieser Verfahren ist vor allem der Versuch der parallelen Reduktion möglichst vieler Polynome. So kann man beispielsweise anstreben, die vorkommenden Terme so zu durchlaufen, dass für alle Polynome, deren Träger den jeweiligen Term enthält, nur ein einziges mal ein Reduktor gesucht werden muss. Genau dies geschieht bei der Multireduktion. Jean-Charles Faugére versucht, von einer anderen Seite her eine ähnliche Verbesserung zu finden. Sein Algorithmus F_{4} wurde 1999 veröffentlicht ([Fa]) und bedient sich der sog. Interreduktion, die in Matrizen umgewandelte Polynommengen per Gauß-Jordan-Elimination reduziert und das Ergebnis wiederderum in eine Menge von Polynomen umwandelt, wobei anschließend nur diejenigen Verwendung finden, die einen neuem Leitterm besitzen.

Das erste Kapitel dieser Arbeit gibt einen kurzen Abriss über alle in Buchbergers Algorithmus sowie über einige der in den restlichen Kapiteln benötigten Hilfsmittel. Im Einzelnen handelt es sich dabei vorwiegend um Leitterme, Termordnungen, normale Reste, Ersetzungsregeln, Graduierungen, Syzygien, S-Polynome, Liftungen, Normalformen und natürlich Gröbnerbasen. Den Buchberger-Algorithmus im inhomogenen sowie im homogenen Fall beinhaltet Kapitel 2. Außerdem werden noch die beiden bereits erwähnten Optimierungen der Menge der kritischen Paare vorgestellt, die Gebauer-Möller-Installation und im homogenen Fall der Buchberger-Algorithmus mit Paarminimalisierung. Zum homogenen Fall ist zu sagen, dass die Bedingung der Homogenität des betrachteten Ideals nur eine unwesentliche Einschränkung darstellt, da jedes Ideal eine Homogenisierung besitzt, auf die einer der homogenen Algorithmen angewendet werden kann. Das Ergebnis kann dann wieder dehomogenisiert werden (vgl. dazu [KrRo 2]). Den Optimierungen, die eine andere als die normale Reduktion benutzen, ist das dritte Kapitel gewidmet. Es beginnt mit einem einleitenden Abschnitt über die Darstellung homogener Polynome im Computer und einer Analyse über die Durchführbarkeit der naheliegenden Idee, alle Polynome des jeweils betrachteten Grades in eine Matrix umzuwandeln und mit linearen Verfahren zu reduzieren. Mit den Ergebnissen der Analyse kann versucht werden, die Schwächen dieser Idee zu umgehen und ein besseres, ähnliches Verfahren zu finden. Der daraus resultierende Buchberger-Algorithmus mit Multireduktion für homogenene Ideale wird im zweiten Abschnitt vorgestellt. Der Rest von Kapitel 3 beschreibt verschiedene Versionen von Faugéres Algorithmus F_{4}, vom Grundalgorithmus über eine verbesserte Version bis hin zur Spezialisierung auf den homogenen Fall. Im letzten Kapitel schließlich werden alle vorgestellten Algorithmen und Optimierungen in einer neutralen Programmumgebung getestet und vergleichen. Nach einem kurzen Einführungstests über den Sinn der Verwendung von Optimierungen wird die Eignung von F_{4} untersucht. Die interessantesten Ergebnisse dürfte aber der dritte Abschnitt liefern, in dem die vier effizientesten Kombinationen aus Algorithmus und Optimierung an etlichen Beispielen getestet werden.

Zum Abschluss möchte ich mich recht herzlich bei Herrn Kreuzer für die hervorragende Betreuung und Beratung in allen algebraischen, algorithmischen und sonstigen Fragen und besonders für die ständige Erreichbarkeit per E-Mail bedanken.

Kapitel 1

Grundlagen

Bevor wir in Abschnitt 1.5 in die Theorie und in Kapitel 2 in die Berechnung von Gröbnerbasen einsteigen, sollen zuerst alle dafür benötigten Hilfsmittel und Bezeichnungen vorgestellt und eingeführt werden.

1.1 Terme und Termordnungen

Ein Polynom ist üblicherweise eine Summe mit Koeffizienten multiplizierter Terme. Wie diese Terme jedoch angeordnet werden, ist auf den ersten Blick unbedeutend, da klar ist, dass z. B. die Ausdrücke x^{2} + 2x + 1, 2x + 1 + x^{2} und 1 + 2x + x^{2} immer dasselbe Polynom bezeichnen. Ist ein Polynom die Summe aus n Termen, so gibt es n! Möglichkeiten, diese anzuordnen; d. h. die Anzahl der Anordnungsmöglichkeiten steigt drastisch, je ”länger“ das betrachtete Polynom wird, so dass ein visueller Vergleich schon schwieriger wird. Auch für Polynomberechnungen mithilfe eines Computers kann es nur von Vorteil sein, wenn die Anordnung der Terme innerhalb eines Polynoms auf eindeutige Art und Weise vorgegeben ist. Das heißt, im Optimalfall benötigt man eine Totalordnung aller möglichen auftretenden Terme. Welche Anforderungen eine derartige Ordnung erfüllen muss, ob überhaupt solche Ordnungen existieren und wie man sie in Computerprogrammen vorteilhaft nutzen kann, erläutert dieser Abschnitt.

Sei P := K[x_{1}, …, x_{n}] ein Polynomring über einem Körper K.

1.1.1 Definition:

a) Ein Polynom t ∈ P der Form t = x_{1}^{a_{1}}… x_{n}^{a_{n}} mit a_{1}, …, a_{n} ∈ ℕ heißt Term oder Monom. Die Menge aller Terme von P wird mit 𝕋^{n} bezeichnet.

b) Die Abbildung log : 𝕋^{n} ⟶ ℕ^{n}, x_{1}^{a_{1}}… x_{n}^{a_{n}} ⟼ (a_{1}, …, a_{n}), heißt Logarithmus.

c) Jedes Polynom f ∈ P kann dargestellt werden als Summe f = c_{1}t_{1}+⋯+c_{m}t_{m} mit m ∈ ℕ, c_{i} ∈ K und Termen t_{i} ∈ 𝕋^{n}, t_{i} ≠ t_{j} für i, j = 1, …, m und i ≠ j. Die Menge Supp(f) := {t_{1}, …, t_{m}} ⊆ 𝕋^{n} heißt der Träger von f. Der Träger einer Teilmenge F ⊆ P wird definiert als Supp(F) := ⋃_{f∈F} Supp(f) ⊆ 𝕋^{n}.

d) Für t = x_{1}^{a_{1}}… x_{n}^{a_{n}} ∈ 𝕋^{n} mit a_{1}, …, a_{n} ∈ ℕ heißt die Zahl deg(t) := a_{1}+⋯+a_{n} der Grad von t. Für ein beliebiges Polynom f ∈ P \ {0} wird der Grad definiert als deg(f) := max{deg(t) | t ∈ Supp(f)}. Das Nullpolynom 0 ∈ P hat definitionsgemäß jeden Grad d ∈ ℕ.

1.1.2 Bemerkung: Die Menge 𝕋^{n} bildet ein vom Grundkörper K unabhängiges, kommutatives Monoid mit neutralem Element 1 = x_{1}^{0} … x_{n}^{0}. Der Logarithmus log : 𝕋^{n} ⟶ ℕ^{n} ist ein Isomorphismus kommutativer Monoide.

Die Menge 𝕋^{n} aller Terme in n Unbestimmten ist eines der wichtigsten Objekte der Computeralgebra. Sie kann auf unterschiedliche Arten angeordnet werden, jedoch sind nur spezielle Ordnungen algebraisch interessant:

1.1.3 Definition: Sei σ ⊆ 𝕋^{n} × 𝕋^{n} eine vollständige Relation auf 𝕋^{n}. Statt (t_{1}, t_{2}) ∈ σ wollen wir die Schreibweise t_{1} ≤_{σ} t_{2} benutzen.

a) Die Relation σ heißt Termordnung auf 𝕋^{n}, wenn folgende Bedingungen für alle t_{1}, t_{2}, t_{3} ∈ 𝕋^{n} erfüllt sind:

(T_{1}) t_{1} ≤_{σ} t_{1} (Reflexivität)

(T_{2}) t_{1} ≤_{σ} t_{2} und t_{2} ≤_{σ} t_{1} ⟹ t_{1} = t_{2} (Antisymmetrie)

(T_{3}) t_{1} ≤_{σ} t_{2} und t_{2} ≤_{σ} t_{3} ⟹ t_{1} ≤_{σ} t_{3} (Transitivität)

(T_{4}) t_{1} ≤_{σ} t_{2} ⟹ t_{1}t_{3} ≤_{σ} t_{2}t_{3}

(T_{5}) 1 ≤_{σ} t_{1}

b) Eine Termordnung σ auf 𝕋^{n} heißt gradkompatibel, wenn für t_{1}, t_{2} ∈ 𝕋^{n} aus t_{1} ≤_{σ} t_{2} immer deg(t_{1}) ≤ deg(t_{2}) folgt.

c) Für eine nichtleere Teilmenge M ⊆ 𝕋^{n} und eine Termordnung σ auf 𝕋^{n} bezeichnet min_{σ}(M) bzw. max_{σ}(M) das Minimum bzw. Maximum der Menge M bzgl. σ, d. h. für alle t ∈ M gilt min_{σ}(M) ≤_{σ} t ≤_{σ} max_{σ}(M).

Sind t_{1}, t_{2} ∈ 𝕋^{n}, so benutzen wir außerdem noch die Schreibweisen t_{1} ≥_{σ} t_{2} für t_{2} ≤_{σ} t_{1}, t_{1} <_{σ} t_{2} für t_{1} ≤_{σ} t_{2} und t_{1} ≠ t_{2} sowie t_{1} >_{σ} t_{2} für t_{1} ≥_{σ} t_{2} und t_{1} ≠ t_{2}.

Als nächstes sollen die gebräuchlichsten Termordnungen vorgestellt werden.

1.1.4 Definition: Folgende Relationen definieren Termordnungen auf 𝕋^{n}.

a) Sei Lex die Menge aller (t_{1}, t_{2}) ∈ 𝕋^{n} × 𝕋^{n}, für die die erste von 0 verschiedene Komponente von log(t_{2}) − log(t_{1}) positiv ist. Dies ist die lexikographische Termordnung.

b) Sei DegLex die Menge aller (t_{1}, t_{2}) ∈ 𝕋^{n} × 𝕋^{n}, für die deg(t_{1}) < deg(t_{2}) oder deg(t_{1}) = deg(t_{2}) und t_{1} ≤_{Lex} t_{2} gilt. Dies ist die graduiert-lexikographi-sche Termordnung.

c) Sei DegRevLex die Menge aller (t_{1}, t_{2}) ∈ 𝕋^{n} × 𝕋^{n}, für die deg(t_{1}) < deg(t_{2}) gilt oder für die deg(t_{1}) = deg(t_{2}) gilt und die letzte von 0 verschiedene Komponente von log(t_{2}) − log(t_{1}) negativ ist. Dies ist die graduiert-umgekehrt-lexikographische Termordnung.

Es ist leicht nachzuprüfen, dass Lex, DegLex und DegRevLex die Axiome von Definition 1.1.3 a) erfüllen und somit wirklich Termordnungen sind. Sowohl DegLex als auch DegRevLex sind gradkompatibel.

Eine besondere Bedeutung im Hinblick auf Gröbnerbasen kommt dem bezüglich einer Termordnung größten Term eines Polynoms zu:

1.1.5 Definition: Seien f ∈ P \ {0} und σ eine Termordnung auf 𝕋^{n}. Dann gibt

es eine eindeutige Repräsentation f = ∑_{i=1}^{m} c_{i}t_{i} von f mit m ∈ ℕ_{+}, c_{i} ∈ K \ {0} und

t_{i} ∈ 𝕋^{n} für i = 1, …, m sowie t_{1} >_{σ} … >_{σ} t_{m}.

a) Der Term LT_{σ}(f) := t_{1} ∈ 𝕋^{n} heißt der Leitterm von f bzgl. σ. Die Menge der Leitterme einer Menge F ⊆ P ist LT_{σ}{F } := {LT_{σ}(f) | f ∈ F \ {0}}.

b) Das Element LC_{σ}(f) := c_{1} ∈ K \ {0} heißt der Leitkoeffizient von f bzgl. σ. Das Polynom f heißt normiert, falls LC_{σ}(f) = 1 gilt.

c) Es sei LM_{σ}(f) := LC_{σ}(f) · LT_{σ}(f) ∈ P \ {0}.

1.1.6 Definition:

a) Eine nichtleere Menge M ⊆ 𝕋^{n} heißt Monoideal, wenn M · 𝕋^{n} ⊆ M gilt.

b) Ein Ideal I ⊆ P heißt monomiales Ideal, wenn es ein Erzeugendensystem aus Termen besitzt.

c) Seien I ⊆ P ein Ideal und σ eine Termordnung auf 𝕋^{n}. Das Monoideal LT_{σ}{I} erzeugt ein monomiales Ideal LT_{σ}(I) := (LT_{σ}(f) | f ∈ I \ {0}) ⊆ P. Letzteres heißt das Leittermideal von I bzgl. σ.

Der folgende Satz gilt somit insbesondere für Leittermideale.

1.1.7 Satz:

a) Jedes monomiale Ideal besitzt ein endliches Erzeugendensystem aus Termen.

b) Jede aufsteigende Kette von monomialen Idealen wird stationär.

Beweis: vgl. [KrRo 1], S. 44f. □

1.2 Normale Reste und Ersetzungsregeln

Das wichtigste Werkzeug für den Buchberger-Algorithmus, der in Kapitel 2 vorgestellt wird, ist der so genannte normale Rest eines Polynoms. Da dieser als Rest aus dem Divisionsalgorithmus für multivariate Polynome hervorgeht, ist es jederzeit möglich, ihn zu berechnen. Ersetzungsregeln hingegen spielen eine wichtige Rolle für die Definition von Gröbnerbasen (siehe Abschnitt 1.5). Betrachtet man zwei Polynome f und g (wobei g hier zur besseren Veranschaulichung normiert sei) sowie einen Term t im Träger von f und den Leiterm t′ von g und ist t′ ein Teiler von t, so beruht die durch g definierte Ersetzungsregel darauf, dass in f der Term t ersetzt wird durch das Polynom \frac{t}{t′} · (t′ − g), oder anders gesagt: Der ”Kopf“ t′ von g wird durch seinen ”Schwanz“ −(g − t′) ersetzt. Die Verbindung zwischen normalen Resten und Ersetzungsregeln besteht darin, dass im Divisionsalgorithmus die durch mehrere Polynome definierten Ersetzunsgregeln nacheinander angewendet werden bis keine weitere Ersetzung mehr möglich ist. Auf dieser Tatsache basiert auch das Buchberger-Kriterium (2.1.2), das später für den Beweis der Korrektheit des Buchberger-Algorithmus herangezogen wird.

Sei P := K[x_{1}, …, x_{n}] ein Polynomring über einem Körper K. Seien s ∈ ℕ_{+} und g_{1}, …, g_{s} ∈ P \ {0}.

1.2.1 Theorem (Divisionsalgorithmus): Sei f ∈ P. Betrachte die folgenden Instruktionen:

1 Setze h := f, p := 0 und q_{i} := 0 für i = 1, …, s 2 Wiederhole die Schritte 3 bis 8, solange h ≠ 0 gilt 3 Wiederhole die Schritte 4 bis 6, solange ein i ∈ {1, …, s} existiert,

so dass LT_{σ}(h) ein Vielfaches von LT_{σ}(g_{i}) ist 4 Sei i ∈ {1, …, s} der kleinste Index, für den LT_{σ}(h) ein

Vielfaches von LT_{σ}(g_{i}) ist

5 Ersetze q_{i} durch q_{i} + \frac{LM_{σ}(h)}{LM_{σ}(g_{i})}

6 Ersetze h durch h − \frac{LM_{σ}(h)}{LM_{σ}(g_{i})} · g_{i} 7 Ersetze p durch p + LM_{σ}(h) 8 Ersetze h durch h − LM_{σ}(h) 9 Gib (q_{1}, …, q_{s}) und p zurück

Dieser Algorithmus liefert einen Vektor (q_{1}, …, q_{s}) ∈ P^{s} und ein Polynom p ∈ P, so dass f = q_{1}g_{1} + ⋯ + q_{s}g_{s} + p gilt und folgende Bedingungen erfüllt sind:

a) Kein t ∈ Supp(p) liegt im Ideal (LT_{σ}(g_{1}), …, LT_{σ}(g_{s})).

b) Für alle i = 1, …, s mit q_{i} ≠ 0 gilt LT_{σ}(q_{i}g_{i}) ≤_{σ} LT_{σ}(f).

c) Es gilt t · LT_{σ}(g_{i}) ∉ (LT_{σ}(g_{1}), …, LT_{σ}(g_{i−1})) für alle i = 1, …, s und alle t ∈ Supp(q_{i}).

Beweis: vgl. [KrRo 1], S. 71 f. □

1.2.2 Definition: Sei f ∈ P, und sei G das Tupel (g_{1}, …, g_{s}). Nach Anwendung des Divisionsalgorithmus 1.2.1 erhält man einen Vektor (q_{1}, …, q_{s}) ∈ P^{s} und ein Polynom p ∈ P. Dieses Polynom p heißt der normale Rest von f bzgl. G und wird mit NR_{σ,G}(f) bezeichnet.

1.2.3 Definition: Sei f ∈ P ein Polynom.

a) Gibt es f′ ∈ P, i ∈ {1, …, s}, t ∈ 𝕋^{n} und c ∈ K mit f′ = f − ctg_{i} und t · LT_{σ}(g_{i}) ∉ Supp(f′), so reduziert sich f vermöge der durch g_{i} definierten Ersetzungsregel in einem Schritt zu f′. Der Übergang von f zu f′ heißt Reduktionsschritt und wird mit f ⟶^{g_{i}} f′ bezeichnet.

b) Gibt es f′ ∈ P, i_{1}, … i_{m} ∈ {1, …, s} und f_{0}, …, f_{m} ∈ P mit f_{0} = f, f_{m} =

f′ und f_{j−1} ⟶^{g_{i_{j}}} f_{j} für j = 1, …, m, so reduziert sich f vermöge der durch G := {g_{1}, …, g_{s}} definierten Ersetzungsregel zu f′. Die so definierte Relation ⟶^{G} ist der transitive Abschluss der Relationen ⟶^{g_{1}}, …, ⟶^{g_{s}}.

c) Gibt es kein f′ ∈ P mit f ⟶^{G} f′, so ist f irreduzibel bzgl. G.

1.3 Graduierungen

Der Schwerpunkt dieser Arbeit liegt – wie der Titel sagt – auf dem homogenen Fall, d. h. auf der Berechenbarkeit von Gröbnerbasen homogener Ideale. Diese sind Spezialfälle graduierter Moduln, die in diesem Abschnitt vorgestellt werden sollen. Eine weitere spezielle Graduierung, die in Abschnitt 1.4 eingeführt wird, bildet die theoretische Grundlage der Idee von Leitformen und Liftungen.

Seien R ein assoziativer, kommutativer Ring mit Eins und (D, +) ein kommutatives Monoid.

1.3.1 Definition:

a) Der Ring R heißt D-graduiert, wenn es eine Familie {R_{d}}_{d∈D} additiver Un-

tergruppen R_{d} von R gibt mit R = ⨁_{d∈D} R_{d} und R_{d} ·R_{d′} ⊆ R_{d+d′} für d, d′ ∈ D.

b) Für d ∈ D heißen die Elemente r_{d} ∈ R_{d} homogen vom Grad deg(r_{d}) := d.

c) Sei r = ∑_{d∈D} r_{d} ∈ R mit r_{d} ∈ R_{d} für d ∈ D. Dann heißt r_{d} für d ∈ D die

homogene Komponente vom Grad d von r.

Sei R jetzt D-graduiert und sei (S, ∗) ein D-Monomodul.

1.3.2 Definition:

a) Ein R-Modul M heißt S-graduiert, wenn es eine Familie {M_{s}}_{s∈S} von additiven Untergruppen M_{s} ⊆ M von M gibt mit M = ⨁_{s∈S} M_{s} und R_{d} ·M_{s} ⊆ M_{d∗s}

für alle d ∈ D und s ∈ S.

b) Ein R-Untermodul N eines S-graduierten R-Moduls M heißt S-graduierter R-Untermodul, wenn N = ⨁_{s∈S}(N ∩ M_{s}) gilt.

Der folgende Satz erlaubt ein besseres Verständnis von graduierten Moduln und liefert eine Möglichkeit zur schnelleren Überprüfung von Graduierungen.

1.3.3 Satz: Sei N ein R-Untermodul eines S-graduierten R-Moduls M und sei N_{s} := N ∩ M_{s} für alle s ∈ S. Dann sind die folgenden Aussagen äquivalent:

a) Es gilt N = ⨁_{s∈S} N_{s}.

b) Ist n ∈ N und ist n = ∑_{s∈S} n_{s} die Zerlegung von n in homogene Komponenten

n_{s} ∈ M_{s}, so ist n_{s} ∈ N für s ∈ S.

c) Es gibt ein Erzeugendensystem von N bestehend aus homogenen Elementen.

Beweis: vgl. [KrRo 1], S. 79 □

Zum Abschluss dieses Abschnitts soll noch die eingangs erwähnte Standardgraduierung eingeführt werden:

1.3.4 Definition: Sei P := K[x_{1}, …, x_{n}] ein Polynomring über einem Körper K. Für d ∈ ℕ sei P_{d} := {f ∈ P | deg(t) = d für alle t ∈ Supp(f)}.

a) Durch die Zerlegung P = ⨁_{d∈ℕ} P_{d} wird P zu einem ℕ -graduierten Ring. Dies

ist die Standardgraduierung von P.

b) Für d ∈ ℕ heißen die Elemente von P_{d} homogene Polynome vom Grad d.

c) Ein ℕ -graduierter P -Untermodul von P heißt homogenes Ideal.

1.4 Syzygien

Mit den bisher eingeführten Hilfsmitteln ist es zwar bereits möglich, den Buchberger-Algorithmus (Theorem 2.1.3) zu formulieren und einzusetzen, jedoch wird zum Beweis der Korrektheit noch die Idee der Syzygien benötigt, die trotz ihrer einfachen Natur ein effektives Werkzeug für diesen Zweck darstellen. Die Verbindung zu den Ersetzungsregeln aus Abschnitt 1.2 wird mit der Einführung der Gröbnerbasen in Abschnitt 1.5 hergestellt. Dies geschieht mittels der Existenz von Liftungen zwischen Syzygien zweier Syzygienmoduln, welche hier ebenfalls vorgestellt werden.

Seien P := K[x_{1}, …, x_{n}] ein Polynomring über einem Körper K und σ eine Termordnung auf 𝕋^{n}. Seien s ∈ ℕ_{+} und g_{1}, …, g_{s} ∈ P \ {0}. Seien G := (g_{1}, …, g_{s}) und LM_{σ}(G) := (LM_{σ}(g_{1}), …, LM_{σ}(g_{s})).

1.4.1 Definition:

a) Ein Tupel (f_{1}, …, f_{s}) ∈ P^{s} mit f_{1}g_{1} + ⋯ + f_{s}g_{s} = 0 heißt Syzygie von G.

b) Die Menge Syz(G) aller Syzygien von G bildet einen P -Untermodul von P^{s}, den Syzygienmodul von G.

c) Der Syzygienmodul von LM_{σ}(G) wird mit Syz(LM_{σ}(G)) bezeichnet.

Für die anschließende Definition wird eine spezielle Graduierung auf P^{s} benötigt, die nun eingeführt werden soll:

1.4.2 Satz: Seien M := P^{s} und {e_{1}, …, e_{s}} die Standardbasis von M. Sei

M_{t} := { ∑_{j = 1}^{s} c_{j}t_{j}e_{j} ∈ M | c_{j} ∈ K, t_{j} ∈ 𝕋^{n} mit c_{j} = 0 oder t_{j} · LT_{σ}(g_{j}) = t}

für t ∈ 𝕋^{n}. Dann gilt M = ⨁_{t ∈ 𝕋^{n}} M_{t} und M wird so zu einem 𝕋^{n}-graduierten Modul

über dem 𝕋^{n}-graduierten Ring P.

Beweis: vgl. [KrRo 1], S. 101 □

1.4.3 Definition: Seien M := P^{s} und m ∈ M \ {0}, und sei m = ∑_{t ∈ 𝕋^{n}} m_{t} die

Zerlegung von m in homogene Komponenten bezüglich der in Satz 1.4.2 definierten 𝕋^{n}-Graduierung.

a) Der Term deg_{σ,G}(m) := max_{σ}{t ∈ 𝕋^{n} | m_{t} ≠ 0} ∈ 𝕋^{n} heißt σ-Grad von m.

b) Die homogene Komponente LF_{σ,G}(m) := m_{deg_{σ,G}(m)} ∈ M heißt σ-Leitform von m.

Nun sollen noch einige Kurzbezeichnungen eingeführt werden, die den Umgang mit den ursprünglichen und neu berechneten Erzeugern eines Ideals erheblich erleichtern und die auch in den folgenden Kapiteln Verwendung finden, sobald irgendwo Polynome g_{1}, …, g_{s} auftreten.

1.4.4 Definition: Sei {e_{1}, …, e_{s}} die Standardbasis von P^{s}. Treten im Folgenden Polynome g_{1}, …, g_{s} ∈ P \ {0} auf, so sei 𝔹 := {(i, j) ∈ {1, …, s}^{2} | 1 ≤ i < j ≤ s} und es sollen folgende Abkürzungen gelten:

t_{i} := LT_{σ}(g_{i}) ∈ 𝕋^{n}  (i = 1, …, s)
c_{i} := LC_{σ}(g_{i}) ∈ K \ {0}  (i = 1, …, s)
t_{ij} := \frac{kgV(t_{i}, t_{j})}{t_{i}} = \frac{t_{j}}{ggT(t_{i}, t_{j})} ∈ 𝕋^{n}  (i, j = 1, …, s)
σ_{ij} := \frac{1}{c_{i}} t_{ij}e_{i} − \frac{1}{c_{j}} t_{ji}e_{j} ∈ P^{s}  (i, j = 1, …, s)
S_{ij} := \frac{1}{c_{i}} t_{ij}g_{i} − \frac{1}{c_{j}} t_{ji}g_{j} ∈ P  (i, j = 1, …, s)

Der Ausdruck S_{ij} heißt S-Polynom von g_{i} und g_{j}.

Als nächstes soll die Funktion der σ_{ij} im Syzygienmodul Syz(LM_{σ}(G)) veranschaulicht werden.

1.4.5 Satz:

a) Für alle i, j ∈ {1, …, s} mit i < j ist σ_{ij} ∈ P^{s} eine Syzygie von LM_{σ}(G) und homogen vom σ-Grad kgV(t_{i}, t_{j}).

b) Es gilt Syz(LM_{σ}(G)) = ⟨σ_{ij} | 1 ≤ i < j ≤ s⟩.

Beweis: vgl. [KrRo 1], S. 104 f. □

1.4.6 Definition:

a) Die Abbildung LF: P^{s} ⟶ P^{s} ist definiert durch

LF(m) := \{ \begin{matrix}0 falls & m = 0 \\ LF_{σ,G}(m) falls & m ≠ 0 \end{matrix}

b) Ein Element m ∈ P^{s} heißt Liftung von m′ ∈ P^{s}, wenn LF(m) = m′ gilt.

1.5 Gröbnerbasen

Alle bisher eingeführten Begriffe und Definitionen zielen auf ein zentrales Objekt der Computeralgebra hin – die Gröbnerbasis. Jedes Ideal besitzt Gröbnerbasen, und der Plural deutet bereits an, dass hierbei keine Eindeutigkeit vorliegen muss. Aufgrund der besonderen Eigenschaften von Gröbnerbasen müssen diese nicht unbedingt ein minimales Erzeugendensystem darstellen; sie können auch deutlich mehr Elemente besitzen. Das Ziel ist es, eine der Gröbnerbasen eines Ideals mithilfe des Computers zu berechnen, und genau dies ist die Aufgabe des Buchberger-Algorithmus und seiner Varianten (vgl. Kapitel 2).

Seien P := K[x_{1}, …, x_{n}] ein Polynomring über einem Körper K und σ eine Termordnung auf 𝕋^{n}.

1.5.1 Definition: Seien G ⊆ P \ {0} endlich, f ∈ P und t ∈ 𝕋^{n}. Eine Darstellung

f = ∑_{i = 1}^{k} a_{i}m_{i}g_{i} mit a_{i} ∈ K \ {0}, m_{i} ∈ 𝕋^{n}, g_{i} ∈ G und LT_{σ}(m_{i}g_{i}) ≤_{σ} t

für i = 1, …, k heißt t-Repräsentation von f bzgl. G.

1.5.2 Theorem (Charakterisierung von Gröbnerbasen): Seien s ∈ ℕ_{+} und g_{1}, …, g_{s} ∈ P \ {0}. Die Menge G := {g_{1}, …, g_{s}} erzeuge das Ideal I := ( g_{1}, …, g_{s}) ⊆ P. Die folgenden Bedingungen sind äquivalent:

(G_{1}) Für alle i, j ∈ {1, …, s} mit i < j hat S_{ij} eine t-Repräsentation bzgl. G mit t ∈ 𝕋^{n} und t <_{σ} kgV(t_{i}, t_{j}).

(G_{2}) Zu jedem Polynom f ∈ I\{0} gibt es Polynome f_{1}, …, f_{s} ∈ P mit f = ∑_{i = 1}^{s}f_{i}g_{i} und LT_{σ}(f) ≥_{σ} LT_{σ}(f_{i}g_{i}) für i = 1, …, s mit f_{i}g_{i} ≠ 0.

(G_{3}) Ist f ∈ I irreduzibel bzgl. ⟶^{G}, so ist f = 0.

(G_{4}) Zu jedem Polynom f ∈ P gibt es ein eindeutiges, bzgl. ⟶^{G} irreduzibles Poly-

nom f′ ∈ P mit f ⟶^{G} f′.

(G_{5}) Jedes homogene Element von Syz(LM_{σ}(G)) besitzt eine Liftung in Syz(G).

(G_{6}) Es gibt ein endliches Erzeugendensystem von Syz(LM_{σ}(G)) bestehend aus homogenen Elementen, die eine Liftung in Syz(G) besitzen.

Beweis: Für die Äquivalenz von (G_{1}) und (G_{2}) siehe [BeWe], S. 219 ff. Zum Beweis der Äquivalenzen von (G_{2}) bis (G_{6}) vgl. [KrRo 1], S. 111. □

1.5.3 Definition: Seien s ∈ ℕ_{+} und g_{1}, …, g_{s} ∈ P \ {0}. Seien G := {g_{1}, …, g_{s}} und sei I := ( g_{1}, …, g_{s}) ⊆ P das von G erzeugte Ideal.

a) Sind die Bedingungen von Theorem 1.5.2 erfüllt, so heißt G Gröbnerbasis von I bzgl. σ oder σ-Gröbnerbasis von I.

b) Die Menge G heißt reduzierte σ-Gröbnerbasis von I, falls die folgenden Bedingungen erfüllt sind:

α) Für i = 1, …, s gilt LC_{σ}(g_{i}) = 1.

β) Die Menge {LT_{σ}(g_{1}), …, LT_{σ}(g_{s})} bildet ein minimales Erzeugendensys-

tem von LT_{σ}(I).

γ) Für i = 1, …, s gilt Supp(g_{i} − LT_{σ}(g_{i})) ∩ LT_{σ}{I} = ∅.

1.5.4 Satz (Existenz von Gröbnerbasen): Sei I ⊆ P ein Ideal.

a) Gibt es g_{1}, …, g_{s} ∈ I \ {0} mit LT_{σ}(I) = (LT_{σ}(g_{1}), …, LT_{σ}(g_{s})), so gilt I = (g_{1}, …, g_{s}) und G := {g_{1}, …, g_{s}} ist eine σ-Gröbnerbasis von I.

b) Das Ideal I besitzt eine σ-Gröbnerbasis.

c) Das Ideal I besitzt eine eindeutige reduzierte σ-Gröbnerbasis.

Beweis: Zum Beweis von a) und b) vgl. [KrRo 1], S. 112; für den Beweis von c) vgl. [KrRo 1], S. 115 f. □

1.6 Normalformen

In Abschnitt 1.2 wurde der normale Rest eines Polynoms bzgl. eines Polynomtupels G eingeführt, der mithilfe des Divisionsalgorithmus ermittelt wird. Der normale Rest ist deswegen auch von der Reihenfolge der Polynome in G abhängig. Ist die zu G gehörige Menge G jedoch eine Gröbnerbasis eines Ideals, so lässt sich für jedes Polynom in diesem Ideal ein anderes Polynom – Normalform genannt – finden, das eine bestimmte Eindeutigkeitsbedingung erfüllt. Da man in diesem Fall die Gleichheit von normalem Rest und Normalform zeigen kann (siehe Korollar 1.6.3 a)), muss der normale Rest unabhängig von der Anordnung der Elemente in G sein.

Seien P := K[x_{1}, …, x_{n}] ein Polynomring über einem Körper K und σ eine Termordnung auf 𝕋^{n}. Sei I ⊆ P ein Ideal.

1.6.1 Satz: Zu jedem Polynom f ∈ I existiert genau ein f′ ∈ P mit f − f′ ∈ I und Supp(f′) ∩ LT_{σ}{I} = ∅.

Beweis: vgl. [KrRo 1], S. 113 □

Das eindeutige Polynom f′ aus Satz 1.6.1 hängt nicht von der gewählten Gröbnerbasis ab, sondern nur vom Ideal I, da die Gröbnerbasis lediglich als Hilfsmittel für den Beweis benutzt wird. Dabei spielt die Wahl der Gröbnerbasis keine Rolle – jede Gröbnerbasis dieses Ideals erfüllt den Zweck.

1.6.2 Definition: Sei f ∈ I. Das eindeutige Polynom f′ aus Satz 1.6.1 wird mit NF_{σ,I}(f) oder kurz NF_{σ}(f) bezeichnet und heißt Normalform von f bzgl. σ.

1.6.3 Korollar: Seien G := {g_{1}, …, g_{s}} ⊆ P \ {0} eine σ-Gröbnerbasis von I, G := (g_{1}, …, g_{s}) und f ∈ P.

a) Es gilt NF_{σ}(f) = NR_{σ,G}(f).

b) Mit einem weiteren Polynom f′ ∈ P folgt NF_{σ}(f − f′) = NF_{σ}(f) − NF_{σ}(f′).

Beweis: vgl. [KrRo 1], S. 114 □

Teil a) des Korollars zeigt, dass der normale Rest – im Falle der Reduktion bzgl. einer Gröbnerbasis – nicht nur unabhängig von der Anordnung der Elemente von G ist, sondern ebenfalls unabhängig von der gewählten Gröbnerbasis selbst. Lediglich das von dieser Gröbnerbasis erzeugte Ideal bestimmt das Ergebnis.

1.6.4 Satz (Idealmitgliedschaftstest): Seien t ∈ ℕ_{+} und h_{1}, …, h_{t} ∈ P Polynome. Diese erzeugen ein weiteres Ideal J := (h_{1}, …, h_{t}) ⊆ P.

a) Ein Polynom f ∈ P liegt genau dann in I, wenn NF_{σ,I}(f) = 0 gilt.

b) Für f_{1}, f_{2} ∈ P gilt f_{1} − f_{2} ∈ I genau dann, wenn NF_{σ,I}(f_{1}) = NF_{σ,I}(f_{2}) gilt.

c) Die Inklusion J ⊆ I gilt genau dann, wenn NF_{σ,I}(h_{j}) = 0 ist für j = 1, …, t.

d) Es gilt I = J genau dann, wenn NF_{σ,J}(g_{i}) = 0 für alle i = 1, …, s und NF_{σ,I}(h_{j}) = 0 für alle j = 1, …, t gilt.

Beweis: vgl. [KrRo 1], S. 114 □ Die Wichtigkeit des letzten Satzes wird klar, wenn man sich vor Augen führt, wie schwierig es gewöhnlich ist zu entscheiden, ob ein beliebiges Polynom in einem betrachteten Ideal liegt oder nicht. Dies wird umso schwieriger, je mehr Erzeuger dieses Ideal besitzt. Mit dem Idealmitgliedschaftstest ist dies nun kein Problem mehr, natürlich vorausgesetzt, dass eine Gröbnerbasis des Ideals bekannt ist. Offenbar handelt es sich hierbei bereits um eine erste, wichtige Anwendung von Gröbnerbasen in Theorie und Praxis.

Der Buchberger-Algorithmus und die Optimierung der abzuarbeitenden Paare

In Kapitel 1 wurden Gröbnerbasen für Polynomideale definiert sowie alle Hilfsmittel zur Verfügung gestellt, die für ihre Berechnung benötigt werden. Was noch fehlt, ist eine effektive Methode zur Ermittlung einer Gröbnerbasis aus einem vorgegebenen endlichen Erzeugendensystem eines Ideals. Der erste Algorithmus, der diese Aufgabe erfüllte, wurde 1965 von Bruno Buchberger im Rahmen seiner Dissertation ([Bu 1]) entwickelt und in späteren Jahren verbessert. Dieser Algorithmus wird in Abschnitt 2.1 vorgestellt. Der Rest dieses Kapitels behandelt verschiedene Optimierungen, die die darin auftretende Liste von abzuarbeitenden Paaren zu minimieren versuchen.

2.1 Der Buchberger-Algorithmus

Seien P := K[x_{1}, …, x_{n}] ein Polynomring über einem Körper K, σ eine Termordnung auf 𝕋^{n} und I ⊆ P ein Ideal. Seien s ∈ ℕ_{+} und g_{1}, …, g_{s} ∈ P \ {0}. Es gelten weiterhin die Bezeichnungen aus Definition 1.4.4.

2.1.1 Satz: Seien G := {g_{1}, …, g_{s}} ⊆ P \ {0} und G := (g_{1}, …, g_{s}) ∈ P^{s} das zu G gehörige Tupel. Sei (i, j) ∈ 𝔹 mit S_{ij} ⟶^{G} 0. Dann besitzt σ_{ij} eine Liftung in Syz(G).

Beweis: vgl. [KrRo 1], S. 122 □

Aus diesem Satz lässt sich ein neues Kriterium zur Überprüfung eines Erzeugendensystems auf Gröbnerbasiseigenschaft ableiten:

2.1.2 Korollar (Buchberger-Kriterium): Seien G := {g_{1}, …, g_{s}} ⊆ P \ {0} und G := (g_{1}, …, g_{s}) ∈ P^{s} das zu G gehörige Tupel. Folgende Bedingungen sind äquivalent:

a) Die Menge G ist eine σ-Gröbnerbasis des Ideals I.

b) Für alle Paare (i, j) ∈ 𝔹 gilt NR_{σ,G}(S_{ij}) = 0.

Beweis: vgl. [KrRo 1], S. 122 □ Das Buchberger-Kriterium schlägt eine Brücke von den Syzygien und deren Liftungen zu den S-Polynomen und liefert damit einen wichtigen Baustein zum Verständnis des Buchberger-Algorithmus.

2.1.3 Theorem (Buchberger-Algorithmus): Es gelte I = (g_{1}, …, g_{s}). Betrachte die folgenden Instruktionen:

1 Setze s′ := s, G := {g_{1}, …, g_{s}}, G := (g_{1}, …, g_{s}) und B := 𝔹 2 Wiederhole die Schritte 3 bis 8, solange B ≠ ∅ ist 3 Wähle ein Paar (i, j) ∈ B und streiche es aus B 4 Berechne S_{ij} und NR_{σ,G}(S_{ij}) 5 Gilt NR_{σ,G}(S_{ij}) = 0, so fahre mit Schritt 2 fort,

andernfalls führe die Schritte 6 bis 8 durch 6 Erhöhe s′ um 1 7 Hänge g_{s′} := NR_{σ,G}(S_{ij}) an G und G an 8 Füge die Paare (1, s′), …, (s′ − 1, s′) zu B hinzu 9 Gib G zurück

Dieser Algorithmus berechnet eine σ-Gröbnerbasis des Ideals I.

Beweis: In jedem Durchlauf der Schleife wird in Schritt 3 ein Paar (i, j) ∈ B gestrichen. Da die Instruktionsfolge abgebrochen wird, sobald B = ∅ ist, folgt die Endlichkeit, wenn nur endlich viele Vergrößerungen von B stattfinden, d.h. wenn Schritt 8 nur endlich oft ausgeführt wird bzw. die Bedingung in Schritt 5 nur endlich oft nicht erfüllt ist. Wäre dies nämlich der Fall, so entstünde eine unendliche Idealkette (LT_{σ}(g_{1}), …, LT_{σ}(g_{s})) ⊊ (LT_{σ}(g_{1}), …, LT_{σ}(g_{s+1})) ⊊ …, da nach Theorem 1.2.1 a) in Schritt 7 stets g′ = NR_{σ,G}(S_{ij}) ∉ (LT_{σ}(g_{1}), …, LT_{σ}(g_{s′})) gilt. Da dies aber im Widerspruch zu Satz 1.1.7 b) stünde, müssen die Anweisungen nach endlich vielen Schritten abbrechen. Um zu beweisen, dass G eine Gröbnerbasis ist, genügt es nach 2.1.2 zu zeigen, dass am Ende für alle Paare (i, j) mit 1 ≤ i < j ≤ s′ die normale Reduktion NR_{σ,G}(S_{ij}) = 0 ist. Dies muss der Fall sein, da all diese Paare im Algorithmus abgearbeitet werden und die normalen Reste der entsprechenden S-Polynome zu G hinzugefügt werden, sofern sie nicht 0 sind. □

2.1.4 Bemerkung:

a) Natürlich wird der Buchberger-Algorithmus in so gut wie allen Werken über Gröbnerbasen ausführlich vorgestellt und auch bewiesen (vgl. z. B. [KrRo 1], S. 123 f.). Der Beweis wurde hier aufgrund der Zentralität des Theorems für das Thema und diese Arbeit und der leichten strukturellen Abweichung des Algorithmus gegenüber anderen Quellen dennoch ausgeführt.

b) Für die Korrektheit des Buchberger-Algorithmus ist offensichtlich nicht entscheidend, welches Paar in Schritt 3 gewählt wird. Die Praxis zeigt jedoch, dass es – besonders bei gradkompatiblen Termordnungen – ratsam ist, immer dasjenige Paar (i, j) ∈ B zu wählen, für das kgV(t_{i}, t_{j}) minimal ist, um eine möglichst hohe Effizienz zu erreichen. Diese Vorgehensweise heißt normale Auswahlstrategie und wurde schon von Buchberger selbst vorgeschlagen (vgl. z. B. [Bu 2]). Will man den Vergleich bzgl. der gewählten Termordnung vermeiden, so kann man auch schon Erfolge verbuchen, wenn man jeweils eines der Paare (i, j) ∈ B wählt, für das deg(t_{i}, t_{j}) minimal ist. Diese Methode eignet sich besonders für Termordnungen, die nicht gradkompatibel sind – wie z. B. Lex.

Der folgende Satz führt zu einer weiteren von Buchberger vorgeschlagenen Verbesserung (vgl. z. B. [Bu 2]), die versucht, schon vor Berechnung der normalen Reduktion zu erkennen, ob sich ein S-Polynom sicher zu 0 reduzieren wird.

2.1.5 Satz: Es gelte I = (g_{1}, …, g_{s}). Sei G := (g_{1}, …, g_{s}) ∈ P^{s} und sei (i, j) ∈ 𝔹 mit ggT(t_{i}, t_{j}) = 1. Dann besitzt σ_{ij} eine Liftung in Syz(G).

Beweis: Betrachte τ_{ij} := \frac{1}{c_{i}c_{j}} (g_{j}e_{i} −g_{i}e_{j}) ∈ P^{s}. Offensichtlich ist τ_{ij} ∈ Syz(G). Da außerdem LF(τ_{ij}) = σ_{ij} gilt, ist τ_{ij} eine Liftung von σ_{ij}. □

2.1.6 Bemerkung: Betrachtet man Schritt 4 im Buchberger-Algorithmus 2.1.3 und den Satz 2.1.5, so sieht man, dass die Berechnung von S_{ij} und NR_{σ,G}(S_{ij}) gar nicht erfolgen muss, wenn ggT(t_{i}, t_{j}) = 1 gilt, da in diesem Fall NR_{σ,G}(S_{ij}) = 0 sein muss. Und auch wenn S_{ij} = 0 gilt, muss natürlich NR_{σ,G}(S_{ij}) = 0 sein, so dass man in der Praxis aus Effizienzgründen Schritt 4 in der Regel durch folgende Schritte ersetzt:

4a Gilt ggT(t_{i}, t_{j}) = 1, so fahre mit Schritt 2 fort,

andernfalls führe die Schritte 4b bis 8 durch 4b Berechne S_{ij} 4c Gilt S_{ij} = 0, so fahre mit Schritt 2 fort,

andernfalls führe die Schritte 4d bis 8 durch

4d Berechne NR_{σ,G}(S_{ij})

2.2 Die Gebauer-Möller-Installation

Bemerkung 2.1.6 entspricht einem der beiden Kriterien, die Buchberger entwickelte, um ”Nullreduktionen“ bei der Bearbeitung von S-Polynomen vorhersagen und somit vermeiden zu können (vgl. z. B. [Bu 2]). Rüdiger Gebauer und Hans Michael Möller nahmen sich dieser Kriterien an, formulierten sie in günstigerer Art und Weise um und bauten sie weiter aus, so dass drei ”neue“ Regeln entstanden (vgl. [GeMö]), die einfach zu implementieren sind.

Sei dazu P := K[x_{1}, …, x_{n}] ein Polynomring über einem Körper K, sei σ eine Termordnung auf 𝕋^{n}. Seien s ∈ ℕ_{+} und g_{1}, …, g_{s} ∈ P \ {0}. Seien I := (g_{1}, …, g_{s}) ⊆ P das von g_{1}, …, g_{s} erzeugte Ideal, G := (g_{1}, …, g_{s}) ∈ P^{s} und Σ := {σ_{ij} | (i, j) ∈ 𝔹}.

Nach Satz 1.4.5 b) ist Σ ein Erzeugendensystem von Syz(LM_{σ}(G)), das nach 1.4.5 a) aus homogenen Elementen besteht. Ist G eine σ-Gröbnerbasis von I, so besitzen nach (G_{5}) alle Elemente σ_{ij} ∈ Σ eine Liftung in Syz(G). Prinzipiell genügt es aber nach (G_{6}), dies für ein beliebiges Erzeugendensystem Σ′ ⊆ Σ zu zeigen, d. h. es reicht, NR_{σ,G}(S_{ij}) = 0 für alle Paare (i, j) ∈ 𝔹′ := {(i, j) ∈ 𝔹 | σ_{ij} ∈ Σ′} zu überprüfen. Da die Berechnung der normalen Reste erfahrungsgemäß einen großen Teil der Ausführungszeit des Buchberger-Algorithmus in Anspruch nimmt, empfiehlt es sich, ein Erzeugendensystem Σ′ ⊆ Σ von Syz(LM_{σ}(G)) zu finden, das möglichst wenige Elemente enthält – im Optimalfall also ein minimales Erzeugendensystem, das im homogenen Fall nach einer für schwach positiv graduierte Moduln gültigen Folgerung aus der graduierten Version des Lemmas von Nakayama in Σ enthalten sein muss (für Näheres siehe [KrRo 2]). Man sucht also nach effizienten und leicht zu programmierenden Kriterien, um die Menge 𝔹′ möglichst klein zu wählen, so dass aber die zugehörige Menge Σ′ noch ein Erzeugendensystem von Syz(LM_{σ}(G)) bildet. Je weniger Paare (i, j) in 𝔹′ verbleiben, desto weniger Reduktionen müssen durchgeführt werden. Die Installation von Gebauer und Möller stellt eine derartige Optimierung dar. Eine programmierfreundliche Umformulierung der drei Regeln aus [GeMö] findet sich in [CaKrRo]:

2.2.1 Satz: Sei G := (g_{1}, …, g_{s}) ∈ P^{s}. Setze B := 𝔹 und streiche Paare in B nach folgenden Regeln:

1 Streiche in B alle Paare (j, k), für die i ∈ {1, …, j − 1} existiert,

so dass t_{ki} ein Teiler von t_{kj} ist 2 Streiche in B alle Paare (i, k), für die j ∈ {i + 1, …, k − 1} existiert,

so dass t_{kj} ein echter Teiler von t_{ki} ist 3 Streiche in B alle Paare (i, j), für die k ∈ {j + 1, …, s} existiert,

so dass t_{ik} ein echter Teiler von t_{ij} und t_{jk} ein echter Teiler von t_{ji} ist

Setzt man 𝔹′ := B, so ist Σ′ := {σ_{ij} | (i, j) ∈ 𝔹′} ⊆ Σ immer noch ein Erzeugendensystem von Syz(LM_{σ}(G)). □

2.2.2 Beispiel: Sei P := ℚ[x_{1}, x_{2}, x_{3}] und seien g_{1}, g_{2}, g_{3}, g_{4} ∈ P \{0} gegeben mit den Leittermen t_{1} = x_{1}^{3}x_{3}^{2}, t_{2} = x_{1}^{3}x_{2}^{4}, t_{3} = x_{2}^{5}x_{3}^{2} und t_{4} = x_{1}^{2}x_{2}^{5}x_{3}. Damit gelten:

t_{12} = x_{2}^{4} t_{13} = x_{2}^{5} t_{14} = x_{2}^{5}  t_{23} = x_{2}x_{3}^{2} t_{24} = x_{2}x_{3} t_{34} = x_{1}^{2}
t_{21} = x_{3}^{2} t_{31} = x_{1}^{3} t_{41} = x_{1}x_{3} t_{32} = x_{1}^{3}  t_{42} = x_{1}  t_{43} = x_{3}

Mit Regel 1 aus Satz 2.2.1 wird das Paar (2, 3) aus B gestrichen, weil t_{31} = t_{32} gilt. Da t_{41} ein echtes Vielfaches von t_{42} (und auch von t_{43}) ist, wird das Paar (1, 4) mit Regel 2 gestrichen. Regel 3 würde ebenfalls das Paar (2, 3) streichen, wenn dies nicht schon bei Regel 1 passiert wäre. Betrachtet man die zu den beiden gestrichenen Paaren gehörigen Syzygien, so sieht man auch die entsprechenden Darstellungen σ_{23} = σ_{13} − x_{2} · σ_{12} sowie σ_{14} = x_{2} · σ_{12} + x_{3} · σ_{24} = σ_{13} + x_{1} · σ_{34}. Damit ist die Menge Σ′ = {σ_{12}, σ_{13}, σ_{24}, σ_{34}} ⊆ Σ immer noch ein Erzeugendensystem von Syz(LM_{σ}(G)). Allerdings handelt es sich hierbei nicht um ein minimales Erzeugendensystem wegen σ_{13} = x_{2} · σ_{12} + x_{3} · σ_{24} + x_{1} · σ_{34}.

Um diese Regeln in den Buchberger-Algorithmus 2.1.3 zu integrieren, empfiehlt es sich, diese als Funktion zu formulieren, die bei jedem Hinzufügen neuer kritischer Paare angewendet wird.

2.2.3 Korollar (Buchberger-Algorithmus mit Gebauer-Möller-Installati-on): Betrachte die folgenden Instruktionen:

1 Setze s′ := 0, G := () und B := ∅ 2 Wiederhole die Schritte 3 bis 5, solange s′ < s gilt 3 Erhöhe s′ um 1 4 Hänge g_{s′} an G an 5 Führe UpdateGM(B) durch 6 Wiederhole die Schritte 7 bis 12, solange B ≠ ∅ ist 7 Wähle ein Paar (i, j) ∈ B und streiche es aus B 8 Berechne S_{ij} und NR_{σ,G}(S_{ij})

9 Gilt NR_{σ,G}(S_{ij}) = 0, so fahre mit Schritt 6 fort,

andernfalls führe die Schritte 10 bis 12 durch

10 Erhöhe s′ um 1 11 Hänge g_{s′} := NR_{σ,G}(S_{ij}) an G an 12 Führe UpdateGM(B) durch 13 Gib G := {g_{1}, …, g_{s′}} als Ergebnis zurück

Dabei ist die Funktion UpdateGM(B) wie folgt definiert:

1 Setze C := {(1, s′), …, (s′ − 1, s′)} 2 Streiche in C alle Paare (j, s′), für die i ∈ {1, …, j − 1} existiert,

so dass t_{s′i} ein Teiler von t_{s′j} ist 3 Streiche in C alle Paare (i, s′), für die j ∈ {i + 1, …, s′ − 1} existiert,

so dass t_{s′j} ein echter Teiler von t_{s′i} ist 4 Streiche in B alle Paare (i, j), für die (i, s′), (j, s′) ∈ C gilt und für die

t_{is′} ein echter Teiler von t_{ij} und t_{js′} ein echter Teiler von t_{ji} ist 5 Hänge C an B an

Dieser Algorithmus berechnet eine σ-Gröbnerbasis des Ideals I.

Beweis: Diese Anweisungen unterscheiden sich vom Buchberger-Algorithmus 2.1.3 lediglich durch die an mehreren Stellen eingefügte Funktion UpdateGM. Da diese linear abläuft und die Menge B der abzuarbeitenden Paare im Vergleich zu 2.1.3 verkleinert, ist die Endlichkeit klar. Weiterhin ist diese Funktion genau so angelegt, dass Schritt für Schritt exakt die Paare der Menge 𝔹′ aus Satz 2.2.1 abgearbeitet werden. Also erfüllt Σ′ := {σ_{ij} | (i, j) ∈ 𝔹′} wegen Satz 2.1.1 und Satz 2.2.1 die Bedingung (G_{6}), und G ist eine Gröbnerbasis von I. □

2.3 Der Buchberger-Algorithmus im homogenen Fall

Betrachtet man den Buchberger-Algorithmus für die homogenen Erzeugenden eines homogenen Ideals, so stellt man fest, dass bei der Berechnung von S-Polynomen und normalen Reduktionen jeweils wieder homogene Polynome entstehen. Da der Grad eines homogenen Polynoms bei der normalen Reduktion erhalten bleibt, empfiehlt es sich außerdem, die zu reduzierenden Polynome gradweise aufsteigend abzuarbeiten. Dadurch wird garantiert, dass alle Gröbnerbasiselemente kleineren Grades schon berechnet wurden und somit deren Leitterme in den noch folgenden Reduktionen bereits als Teiler zur Verfügung stehen. Wäre dies nicht der Fall, so könnte es vorkommen, dass sich ein Polynom nicht zu 0 reduziert, obwohl dies einträte, wenn alle kleineren Gröbnerbasiselemente bereits vorhanden wären. Das hätte das Hinzufügen eines eigentlich überflüssigen Polynoms zur Gröbnerbasis zur Folge, wodurch etliche neue Paare entstünden, die anschließend allesamt abgearbeitet werden müssten.

Sei P := K[x_{1}, …, x_{n}] ein Polynomring über einem Körper K versehen mit der Standardgraduierung, und sei σ eine Termordnung auf 𝕋^{n}.

2.3.1 Satz: Seien s ∈ ℕ_{+} und g_{1}, …, g_{s} ∈ P \ {0} homogene Polynome sowie G := (g_{1}, …, g_{s}) ∈ P^{s}.

a) Für alle Paare (i, j) ∈ 𝔹 ist S_{ij} homogen vom Grad deg(kgV(t_{i}, t_{j})).

b) Für ein homogenes Polynom f ∈ P \ {0} ist NR_{σ,G}(f) homogen vom Grad deg(f).

Beweis: Sei (i, j) ∈ 𝔹. Außerdem seien d_{i} := deg(g_{i}) und d_{j} := deg(g_{j}) sowie d_{ij} := deg(kgV(t_{i}, t_{j})). Es gilt deg(t_{ij}) = deg(\frac{kgV(t_{i},t_{j})}{t_{i}}) = \frac{d_{ij}}{d_{i}} und entsprechend deg(t_{ji}) = \frac{d_{ji}}{d_{j}}. Somit sind t_{ij}g_{i} sowie t_{ji}g_{j} homogen vom Grad d_{ij}, also auch das S-Polynom S_{ij} = \frac{1}{c_{i}} t_{ij}g_{i} − \frac{1}{c_{j}} t_{ji}g_{j}. Sei nun f ∈ P \ {0} homogen vom Grad d ∈ ℕ. Betrachte den Divisionsalgorithmus (Theorem 1.2.1) und darin speziell das Polynom p, das am Schluss der normalen Reduktion von f bzgl. G entspricht. Anfänglich gilt p = 0 und die einzige Veränderung von p findet in Schritt 7 statt, wo LM_{σ}(h) addiert wird. Es ist also zu zeigen, dass h durchgehend homogen vom Grad d ist, was anfangs wegen h = f der Fall ist. Die Änderung von h in Schritt 8 verändert die Homogenität nicht. Dasselbe gilt auch für Schritt 6, da \frac{LM_{σ}(h)}{LM_{σ}(g_{i})} · g_{i} ebenfalls homogen vom Grad d ist. □

2.3.2 Theorem (Buchberger-Algorithmus im homogenen Fall): Seien f_{1}, …, f_{s} ∈ P \ {0} homogene Polynome und I := (f_{1}, …, f_{s}) das von f_{1}, …, f_{s} erzeugte Ideal. Betrachte die folgenden Instruktionen: 1 Setze s′ := 0, F := {f_{1}, …, f_{s}}, G := () und B := ∅ 2 Wiederhole die Schritte 3 bis 11, solange B ≠ ∅ oder F ≠ ∅ gilt 3 Setze d := min{min{deg(f) | f ∈ F }, min{deg(kgV(t_{i}, t_{j})) | (i, j) ∈ B}} 4 Setze B_{d} := {(i, j) ∈ B | deg(kgV(t_{i}, t_{j})) = d} und streiche die Elemente

von B_{d} in B 5 Setze F_{d} := {f ∈ F | deg(f) = d} und streiche die Elemente von F_{d} in F 6 Wiederhole die Schritte 7 bis 11, solange B_{d} ≠ ∅ oder F_{d} ≠ ∅ gilt 7 Ist B_{d} = ∅, so wähle f ∈ F_{d} und streiche f aus F_{d}, andernfalls

wähle ein Paar (i, j) ∈ B_{d}, streiche es aus B_{d} und setze f := S_{ij}

8 Ist NR_{σ,G}(f) = 0, so fahre mit Schritt 6 fort,

andernfalls führe die Schritte 9 bis 11 durch

9 Erhöhe s′ um 1 10 Hänge g_{s′} := NR_{σ,G}(f) an G an 11 Füge die Paare (1, s′), …, (s′ − 1, s′) zu B hinzu 12 Gib G := {g_{1}, …, g_{s′}} als Ergebnis zurück Dieser Algorithmus berechnet eine σ-Gröbnerbasis des Ideals I bestehend aus homogenen Polynomen g_{1}, …, g_{s′} mit deg(g_{1}) ≤ … ≤ deg(g_{s′}).

Beweis: vgl. [KrRo 2] □

Ein weiterer Vorteil bei der gradweisen Abarbeitung der Polynome f besteht in der Tatsache, dass nach Komplettierung eines Grades d alle weiteren Polynome f höheren Grad haben müssen, so dass zu diesem Zeitpunkt das Tupel G aus genau den Elementen der letztlich berechneten Gröbnerbasis G besteht, die höchstens Grad d haben.

2.3.3 Definition: Sei d ∈ ℕ.

a) Für eine Menge F ⊆ P sei F_{≤d} := {f ∈ F | f homogen und deg(f) ≤ d}.

b) Sei G ⊆ P \ {0} eine σ-Gröbnerbasis eines homogenen Ideals I ⊆ P bestehend aus homogenen Polynomen. Dann heißt die Menge G_{≤d} eine im Grad d abgeschnittene σ-Gröbnerbasis von I.

2.3.4 Bemerkung: Sei die Situation von Theorem 2.3.2 gegeben.

a) Die Gradkompatibilität der betrachteten Termordnung σ ist für diesen Algorithmus nicht von Bedeutung. Das rührt daher, dass immer nur Vergleiche zwischen Termen desselben Grades auftreten. Beispielsweise wären die berechneten Gröbnerbasen bzgl. der Termordnungen Lex und DegLex identisch.

b) Die Homogenität der erzeugten Gröbnerbasiselemente wird dadurch gewährleistet, dass Additionen nur zwischen homogenen Polynomen desselben Grades auftreten; insbesondere erhalten die Berechnungen von S-Polynomen und normalen Reduktionen nach Satz 2.3.1 die Homogenität.

c) Sei d_{0} ∈ ℕ. Da im Algorithmus die Grade der berechneten Gröbnerbasiselemente g_{1}, …, g_{s′} nicht abnehmend sind, erhält man eine im Grad d_{0} abgeschnittene σ-Gröbnerbasis des Ideals I, wenn man die Schritte 1 und 2 ersetzt durch

1 Setze s′ := 0, d := 0, F := {f_{1}, …, f_{s}}, G := () und B := ∅

2 Wiederhole die Schritte 3 bis 11, solange d ≤ d_{0} ist und solange B ≠ ∅ oder F ≠ ∅ gilt

Da in diesem Fall die Paare (i, j) ∈ B mit deg(kgV(t_{i}, t_{j})) > d_{0} niemals benötigt werden, kann man auch Schritt 11 wie folgt verkürzen:

11 Füge die Paare (i, s′) mit i = 1, …, s′ − 1 und deg(kgV(t_{i}, t_{s′})) ≤ d_{0} zu B hinzu

d) Auch im homogenen Fall können die Regeln von Gebauer und Möller gemäß Satz 2.2.1 angewendet werden, und zwar indem man Schritt 11 ersetzt durch

11 Führe UpdateGM(B) durch

Dabei ist UpdateGM die in Theorem 2.2.3 definierte Funktion.

2.4 Buchberger-Algorithmus mit Minimalisierung der Paare

Die in Abschnitt 2.2 vorgestellte Installation von Gebauer und Möller aus dem Jahre 1988 wurde bald zur Standardoptimierung bei den meisten Implementationen des Buchberger-Algorithmus in mathematischen Softwareapplikationen. Diese Optimierung kann viele Paare eliminieren, so dass die Berechnungszeiten der meisten Gröbnerbasen drastisch gesenkt werden, und da keine offensichtliche Verbesserung gefunden werden konnte, gingen die meisten Versuche zur Optimierung des Buchberger-Algorithmus in andere Richtungen, v. a. wurde eine Verbesserung der Reduktion (siehe Kapitel 3) angestrebt. Allerdings können die drei Regeln der Gebauer-Möller-Installation die Menge der Paare nicht in allen Fällen auf ein Minimum reduzieren, d. h. die zu den Paaren gehörigen Syzygien bilden nicht zwangsweise ein minimales Erzeugendensystem des entsprechenden Syzygienmoduls. Die letztendliche Minimierung der Paare gelang erst kürzlich: Martin Kreuzer und Lorenzo Robbiano bauten dazu in [CaKrRo] die drei bekannten Regeln (siehe Satz 2.2.1) aus, indem sie Regel 3 durch eine ”Antiregel“ ersetzten, um die mit dieser Regel gefundenen und markierten Paare später zur weiteren Minimierung verwenden zu können statt sie sofort zu streichen.

Sei P := K[x_{1}, …, x_{n}] wieder ein Polynomring über einem Körper K versehen mit der Standardgraduierung, und sei σ eine Termordnung auf 𝕋^{n}.

2.4.1 Theorem (Buchberger-Algorithmus mit Paarminimalisierung): Seien f_{1}, …, f_{s} ∈ P \ {0} und I := (f_{1}, …, f_{s}) das von f_{1}, …, f_{s} erzeugte Ideal. Betrachte die folgenden Instruktionen:

1 Setze s′ := 0, F := {f_{1}, …, f_{s}}, G := (), A := ∅, B := ∅ und B^{∗} := ∅ 2 Wiederhole die Schritte 3 bis 13, solange B ≠ ∅ oder F ≠ ∅ gilt 3 Setze d := min{min{deg(f) | f ∈ F }, min{deg(kgV(t_{i}, t_{j})) | (i, j) ∈ B}} 4 Setze B_{d} := {(i, j) ∈ B | deg(kgV(t_{i}, t_{j})) = d} und streiche die Elemente

von B_{d} in B 5 Setze B_{d}^{∗} := {(i, j) ∈ B^{∗} | deg(kgV(t_{i}, t_{j})) = d} und streiche die

Elemente von B_{d}^{∗} in B^{∗} 6 Setze F_{d} := {f ∈ F | deg(f) = d} und streiche die Elemente von F_{d} in F 7 Führe MinPairs(A, B_{d}, B_{d}^{∗}) durch 8 Wiederhole die Schritte 9 bis 13, solange B_{d} ≠ ∅ oder F_{d} ≠ ∅ gilt 9 Ist B_{d} = ∅, so wähle f ∈ F_{d} und streiche f aus F_{d},

andernfalls wähle ein Paar (i, j) ∈ B_{d}, streiche es aus B_{d}, hänge es an A an und setze f := S_{ij}

10 Ist NR_{σ,G}(f) = 0, so fahre mit Schritt 8 fort,

andernfalls führe die Schritte 11 bis 13 durch

11 Erhöhe s′ um 1 12 Hänge g_{s′} := NR_{σ,G}(f) an G an 13 Führe Update(B, B^{∗}, g_{s′}) durch 14 Gib G := {g_{1}, …, g_{s′}} als Ergebnis zurück

Dabei ist die Funktion Update(B, B^{∗}, g_{s′}) wie folgt definiert:

1 Setze C := {(1, s′), …, (s′ − 1, s′)} 2 Streiche in C alle Paare (j, s′), für die i ∈ {1, …, j − 1} existiert,

so dass t_{s′i} ein Teiler von t_{s′j} ist 3 Streiche in C alle Paare (i, s′), für die j ∈ {i + 1, …, s′ − 1} existiert,

so dass t_{s′j} ein echter Teiler von t_{s′i} ist 4 Hänge an B^{∗} alle Paare (i, j) mit 1 ≤ i < j < s′ und (i, s′), (j, s′) ∈ C an,

für die ggT(t_{is′}, t_{js′}) = 1 gilt, sofern (i, j) ∉ B^{∗} 5 Hänge C an B an

Die Funktion MinPairs(A, B_{d}, B_{d}^{∗}) ist folgendermaßen definiert:

1 Wiederhole die Schritte 2 bis 10, solange B_{d}^{∗} ≠ ∅ gilt 2 Wähle ein Paar (i, j) ∈ B_{d}^{∗} und streiche es aus B_{d}^{∗} 3 Gibt es ein Paar (i′, j) ∈ A mit t_{ji} = t_{ji′}, so fahre mit Schritt 1 fort 4 Gibt es ein Paar (i′, j) ∈ B_{d} mit t_{ji} = t_{ji′}, so streiche es aus B_{d},

hänge es an A an und fahre mit Schritt 1 fort, andernfalls führe die Schritte 5 bis 10 durch

5 Finde ein Paar (i′, j) ∈ A, so dass t_{ji} ein Vielfaches von t_{ji′} ist 6 Ist ggT(t_{ij}, t_{i′j}) ≠ 1, so fahre mit Schritt 1 fort 7 Setze k := min{i, i′} und l := max{i, i′} 8 Gibt es ein Paar (k′, l) ∈ A mit t_{lk} = t_{lk′}, so fahre mit Schritt 1 fort 9 Gibt es ein Paar (k′, l) ∈ B_{d} mit t_{lk} = t_{lk′}, so streiche es aus B_{d},

hänge es an A an und fahre mit Schritt 1 fort

10 Ist (k, l) ∈ B_{d}^{∗}, so streiche (k, l) aus B_{d}^{∗}, setze i := k, j := l und fahre mit Schritt 5 fort

Dieser Algorithmus berechnet eine σ-Gröbnerbasis des Ideals I bestehend aus homogenen Polynomen g_{1}, …, g_{s′} mit deg(g_{1}) ≤ … ≤ deg(g_{s′}). Des Weiteren bilden die zu den abgearbeiteten Paaren (i, j) gehörigen Syzygien σ_{ij} ein minimales Erzeugendensystem von Syz(LM_{σ}(G)).

Beweis: vgl. [CaKrRo] □ 2.4.2 Bemerkung: Die Funktion Update aus Theorem 2.4.1 entspricht genau der Funktion UpdateGM aus Korollar 2.2.3 – mit Ausnahme von Schritt 4; hier werden die gefundenen Paare nicht aus B gestrichen wie bei Gebauer und Möller, sondern in eine weitere Liste B^{∗} gesetzt und vorgemerkt. Diese Paare werden dann von der Funktion MinPairs für die Minimalisierung des Erzeugendensystems von Syz(LM_{σ}(G)) herangezogen.

2.4.3 Beispiel: Sei die Situation von Beispiel 2.2.2 gegeben. Dort wurde festgestellt, dass nach Anwendung der Regeln von Gebauer und Möller die Menge Σ′ = {σ_{12}, σ_{13}, σ_{24}, σ_{34}} wegen σ_{13} = x_{2} · σ_{12} + x_{3} · σ_{24} + x_{1} · σ_{34} kein minimales Erzeugendensystem ist. Im Fall von Satz 2.4.1 wird bei diesem Beispiel in Schritt 4 der Funktion Update wegen ggT(t_{24}, t_{34}) = ggT(x_{2}x_{3}, x_{1}^{2}) = 1 das Paar (2, 3) zu B^{∗} hinzugefügt. Wenn dieses Paar von der Funktion MinPairs abgearbeitet wird, gilt d = 10, d. h. wegen deg(kgV(t_{1}, t_{3})) = deg(x_{1}^{3}x_{2}^{5}x_{3}^{2}) = 10 ist das Paar (1, 3) noch nicht in A enthalten, so dass die Bedingung in Schritt 3 nicht erfüllt ist. Das Paar (1, 3) ist jedoch in B_{d} enthalten und wird wegen t_{32} = t_{31} = x_{1}^{3} in Schritt 4 gestrichen. Die dann noch verbleibenden Syzygien σ_{12}, σ_{24} und σ_{34} bilden ein minimales Erzeugendensystem von Syz(LM_{σ}(g_{1}, g_{2}, g_{3}, g_{4})).

Optimierung der Reduktion im Buchberger-Algorithmus

Die beiden bisher vorgestellten Optimierungen des Buchberger-Algorithmus (vgl. Kapitel 2) befassen sich ausschließlich mit der Eliminierung möglichst vieler kritischer Paare, um so die aufwändige Berechnung der normalen Reduktion möglichst vieler S-Polynome zu umgehen. Jetzt sollen verschiedene Abwandlungen des Buchberger-Algorithmus betrachtet werden, die eben diese Reduktion optimieren, indem sie versuchen, mehrere Paare bzw. Polynome gleichzeitig abzuarbeiten. Dazu wird die normale Reduktion jeweils durch eine andere Funktion ersetzt, die mehrere Polynome gleichzeitig behandeln kann und diese sowohl gegen die bereits bekannten Gröbnerbasiselemente als auch untereinander reduziert. Die resultierenden Reduktionen aller bei diesem Vorgang nicht verschwindenden Polynome werden anschließend – genau wie beim Buchberger-Algorithmus – als neue Gröbnerbasiselemente deklariert. Nach der Darlegung der Funktionalität der veränderten Reduktionsfunktionen soll jeweils versucht werden, diese mit den in Kapitel 2 eingeführten Optimierungen der kritischen Paare zu kombinieren, um so eine noch effizientere Symbiose zweier Optimierungen erzielen zu können. Zuerst folgt jedoch ein Abschnitt, der die Darstellbarkeit von homogenen Polynomen im Computer behandelt und den darauf folgenden Überlegungen zur Effizienzsteigerung bei der Multireduktion (vgl. Abschnitt 3.2) zugrunde liegt.

3.1 Darstellung homogener Polynome in Computersystemen

Um die Effizienz von Algorithmen zu verbessern, gilt es natürlich in erster Linie, die ”mathematischen Komponenten“ zu optimieren, wie dies bei allen hier aufgeführten Optimierungen der Fall ist. Jedoch ist es bei der Realisierung eines Algorithmus als Programm auch von Bedeutung, ob und mit welcher Effizienz die Instruktionen und Objekte in die gewählte Programmiersprache übertragen werden können. Ein wichtiger Aspekt ist beispielsweise die Speicher- und Zugriffsoptimierung für die notwendigen Daten, da gewöhnlich kein unendlicher Speicherplatz zur Verfügung steht und die Ausführungsdauer eines Programms fundamental von der Zugriffszeit auf einzelne Elemente von Listen, Matrizen usw. abhängt. Die Intention dieses Abschnitts ist es, eine Methode zu finden, mit der homogene Polynome optimal gespeichert werden können. Dazu werden alle Terme eines Grades immer in derselben Reihenfolge betrachtet, so dass jedes Polynom einfach als Koeffizientenvektor dargestellt werden kann. Eine Menge von homogenen Polynomen desselben Grades wird dann als Matrix gespeichert. In der Praxis verwendet man hierbei meist die Technik der dünn besetzten Vektoren und Matrizen, d. h. die Nulleinträge werden nicht explizit gespeichert.

Sei P := K[x_{1}, …, x_{n}] ein Polynomring über einem Körper K und sei σ eine Termordnung auf 𝕋^{n}.

3.1.1 Definition: Seien l_{1}, …, l_{m} ∈ 𝕋^{n} mit l_{1} >_{σ} … >_{σ} l_{m}. Seien außerdem L := {l_{1}, …, l_{m}} ⊆ 𝕋^{n} und L := (l_{1}, …, l_{m}) ∈ (𝕋^{n})^{m}. Dann erhält man einen K-Vektorraum-Isomorphismus

ψ_{L}: ⟨L⟩_{K} ⟶ K^{m}, l_{i} ⟼ e_{i} (i = 1, …, m)

Daraus ergibt sich dann für r ∈ ℕ_{+} ein weiterer K-Vektorraum-Isomorphismus

Ψ_{L,r}: ⟨L⟩_{K}^{r} ⟶ Mat_{r,m}(K), (f_{1}, …, f_{r}) ⟼ [ ψ_{L}(f_{1}) ; ⋮ ; ψ_{L}(f_{r}) ]

3.1.2 Beispiel: Wählt man P = ℚ[x_{1}, x_{2}, x_{3}], σ = Lex oder σ = DegLex und für L die Menge aller Monome vom Grad 2, also L = (x_{1}^{2}, x_{1}x_{2}, x_{1}x_{3}, x_{2}^{2}, x_{2}x_{3}, x_{3}^{2}), so kann man mithilfe der Abbildung Ψ_{L,r} jedes Tupel homogener Polynome vom Grad 2 als Matrix darstellen. So wird z. B. F = (2x_{1}^{2} + 3x_{1}x_{2} + x_{2}^{2}, x_{1}^{2} + 2x_{1}x_{3} + 5x_{3}^{2}, x_{1}x_{3} + 3x_{2}x_{3}) repräsentiert durch die Matrix

Ψ_{L,3}(F) = [ \begin{matrix}2 & 3 & 0 & 1 & 0 & 0 \\ 1 & 0 & 2 & 0 & 0 & 5 \\ 0 & 0 & 1 & 0 & 3 & 0 \end{matrix} ]

Für den Optimalfall wäre es sinnvoll, die Liste L der Terme entweder möglichst groß oder möglichst klein zu wählen. Im zweiten Fall empfiehlt es sich, den Träger der Menge aller betrachteten Polynome zu verwenden, wie es beispielsweise im Algorithmus F_{4} bewerkstelligt wird (vgl. Abschnitte 3.3 und 3.4). Im ersten Fall wäre es mit einer großen Liste eventuell möglich, alle Polynome zugleich zu reduzieren. Da man allerdings zu Beginn noch nicht weiß, welche Terme im Programmablauf auftreten, ist die Bestimmung einer derartigen Liste vorab nicht möglich. Verwendet man jedoch nur homogene Polynome und geht gradweise vor, so kann man jeweils alle Terme des betrachteten Grades in die Liste aufnehmen. Diese Methode wird beispielsweise beim Verfahren der Multireduktion (vgl. Abschnitt 3.2) angewandt und soll im Folgenden näher vorgestellt werden.

Sei also P von nun an mit der Standardgraduierung versehen.

3.1.3 Definition: Für d ∈ ℕ sei die Menge 𝕋_{d}^{n} aller d-gradigen Terme von P definiert als 𝕋_{d}^{n} := {t ∈ 𝕋^{n} | deg(t) = d} = 𝕋^{n} ∩ P_{d}.

3.1.4 Satz: Sei d ∈ ℕ. Es gilt

Card(𝕋_{d}^{n}) = \binom{n + d − 1}{d}

Beweis: Der Beweis erfolgt durch Induktion über n und d. Für n = 1 und d ∈ ℕ beliebig ist Card(𝕋_{d}^{1}) = Card\{x_{1}^{d}\} = 1 = \binom{1 + d − 1}{d}. Ist hingegen d = 0 und ist n ∈ ℕ_{+} beliebig, so gilt Card(𝕋_{0}^{n}) = Card\{1\} = 1 = \binom{n + 0 − 1}{0}. Seien nun n ≥ 2 und d ≥ 1, und sei die Behauptung für n − 1 und d sowie für n und d − 1 bereits gezeigt. Natürlich gilt 𝕋_{d}^{n−1} ⊊ 𝕋_{d}^{n}. Alle übrigen Terme in 𝕋_{d}^{n} \ 𝕋_{d}^{n−1} sind Vielfache von x_{n}, und wegen x_{n} · 𝕋_{d−1}^{n} ⊆ 𝕋_{d}^{n} muss sogar 𝕋_{d}^{n} \ 𝕋_{d}^{n−1} = x_{n} · 𝕋_{d−1}^{n} gelten. Insgesamt ist Card(𝕋_{d}^{n}) = Card(𝕋_{d}^{n−1} ˙∪ (x_{n} · 𝕋_{d−1}^{n})) = Card(𝕋_{d}^{n−1}) + Card(𝕋_{d−1}^{n}). Es folgt Card(𝕋_{d}^{n}) = \binom{(n − 1) + d − 1}{d} + \binom{n + (d − 1) − 1}{d − 1} = \binom{n + d − 1}{d} unter Ausnutzung der Induktionsvoraussetzung. □

3.1.5 Bemerkung: Satz 3.1.4 kann auch mithilfe der Hilbert-Funktion des Polynomrings, HF_{P} : ℤ ⟶ ℤ, i ⟼ \binom{i + n − 1}{i}, gezeigt werden (vgl. z. B. [KrRo 2]). Dabei gilt Card(𝕋_{d}^{n}) = dim_{K}(P_{d}) = HF_{P} (d) = \binom{n + d − 1}{d}.

Somit ist also die Anzahl der Terme eines bestimmten Grades d bekannt und kann aus der Anzahl n der Unbestimmten und d berechnet werden. Damit kann auch das Tupel aller Terme eines Grades wie folgt ermittelt werden.

3.1.6 Definition: Seien d ∈ ℕ sowie m := Card(𝕋_{d}^{n}) = \binom{n + d − 1}{d}. Weiter seien die Terme s_{1}, …, s_{m} ∈ 𝕋_{d}^{n} rekursiv definiert durch s_{i} := max_{σ}(𝕋_{d}^{n} \ {s_{1}, …, s_{i−1}}) für i = 1, …, m. Dann sei T_{d}^{n} := T_{σ,d}^{n} := (s_{1}, …, s_{m}) ∈ (𝕋_{d}^{n})^{m} das zu 𝕋_{d}^{n} gehörige Tupel bzgl. σ.

Da in diesem Kapitel der Vorgang der Reduktion optimiert werden soll, stellt sich nun zwangsweise die Frage, wie die (normale) Reduktion abläuft, wenn man die involvierten Polynome als Vektoren bzw. Matrizen darstellt. Hierzu ein Beispiel:

3.1.7 Beispiel: Seien P = ℚ[x_{1}, x_{2}, x_{3}], d = 3, σ = DegRevLex, g_{1} = x_{1} − x_{3}, g_{2} = x_{2}^{2} −x_{3}^{2} und G = (g_{1}, g_{2}). Das Polynom h = x_{1}^{3} −x_{2}^{2}x_{3} soll vermöge G reduziert werden. Bei der Berechnung von NR_{σ,G}(h) sucht der Divisionsalgorithmus (Theorem 1.2.1) den ersten Polynomeintrag in G, dessen Leitterm ein Teiler von LT_{σ}(h) = x_{1}^{3} ist, also g_{1}. Nun wird g′_{1} = \frac{LM_{σ}(h)}{LM_{σ}(g_{1})} · g_{1} = x_{1}^{3} − x_{1}^{2}x_{3} berechnet. Sowohl g′_{1} als auch h haben nun denselben Grad, so dass die nun zu berechnende Differenz h − g′_{1} als Vektorsubtraktion bzw. als Zeilenumformung betrachtet werden kann:

Ψ_{T_{3}^{3},2}(g′_{1}, h) = [ \begin{matrix}1 & 0 & 0 & 0 & −1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & −1 & 0 & 0 & 0 \end{matrix} ]

Ψ_{T_{3}^{3},2}(g′_{1}, h − g′_{1}) = [ \begin{matrix}1 & 0 & 0 & 0 & −1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & −1 & 0 & 0 & 0 \end{matrix} ]

Aus der zweiten Zeile ergibt sich h′ = h − g′_{1} = x_{1}^{2}x_{3} − x_{2}^{2}x_{3}. Analog erhält man im weiteren Verlauf g′′_{1} = x_{1}^{2}x_{3} − x_{1}x_{3}^{2} und h′′ = −x_{2}^{2}x_{3} + x_{1}x_{3}^{2}, g′′′_{2} = −x_{2}^{2}x_{3} + x_{3}^{3} und h′′′ = x_{1}x_{3}^{2} − x_{3}^{3} sowie g′′′′_{1} = x_{1}x_{3}^{2} − x_{3}^{3} und h′′′′ = 0 = NR_{σ,G}(h). Betrachtet man nun alle Schritte zusammen in einer einzigen Matrix

Ψ_{T_{3}^{3},5}(g′_{1}, g′′_{1}, g′′′_{2}, g′′′′_{1}, h) = [ \begin{matrix}1 & 0 & 0 & 0 & −1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & −1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & −1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & −1 \\ 1 & 0 & 0 & 0 & 0 & 0 & −1 & 0 & 0 & 0 \end{matrix} ]

so erkennt man, dass die letzte Zeile lediglich durch Zeilensubtraktionen überführt wird in einen Vektor, dessen zugehöriges Polynom (hier 0) dann die gesuchte normale Reduktion von h bzgl. G bildet.

Dies erinnert an die Gauß-Elimination, nur dass hier der erste von 0 verschiedene Eintrag nicht zwangsweise 1 sein muss und dass sich keine Dreiecksgestalt ergeben muss.

Nun liegt es natürlich nahe, im Fall des homogenen Buchberger-Algorithmus (Theorem 2.3.2) alle in einem Grad d zu reduzierenden Polynome zugleich zu betrachten, sie mit allen benötigten Vielfachen der bis zu diesem Zeitpunkt gefundenen Gröbnerbasiselemente in eine Matrix zu schreiben und mittels Gauß-Elimination geeignete Reduktionen zu finden (die Leitkoeffizienten sind irrelevant). Es wäre sogar möglich, die so entstandene Matrix mittels einfacher Umformungen auf den nächsthöheren Grad zu transformieren, so dass sie dort bereits wieder Vielfache der schon gefundenen Gröbnerbasiselemente repräsentiert, die zur Reduktion weiterer Polynome herangezogen werden können. In der Theorie scheint dies eine effiziente Alternative zur normalen Reduktion zu sein, da mehrere Polynome ”zugleich“ reduziert werden, doch die Praxis sieht leider ganz anders aus:

– Die Matrizen werden von Grad zu Grad immer größer, da ihre Breite durch einen Binomialkoeffizienten bestimmt wird, der vom Grad abhängt (siehe Satz 3.1.4); in einem Grad d ∈ ℕ_{+} beträgt sie exakt \binom{n + d − 1}{d} mehr als die Breite des vorhergehenden Grades d − 1 oder anders gesagt das \frac{n + d − 1}{d}-fache. Im Grad 15 beispielsweise hat für n = 4 eine Zeile dieser Matrix bereits 816 Einträge, und derartige Dimensionen werden nicht selten erreicht und überschritten. Und auch die Höhe der Matrix wächst natürlich mit der Breite, da in jedem Grad mehr Spalten und damit im Normalfall mehr zu reduzierende Terme zur Verfügung stehen. Das Problem bei der Implementation ist die mit dem Grad massiv ansteigende Rechenzeit, die – selbst bei einer Realisierung in Form von dünn besetzten Matrizen – nur für die Erzeugung dieser riesigen Matrizen benötigt wird, weswegen diese so klein wie möglich gehalten werden müssen.

– Man weiß vor der Abarbeitung eines Grades noch nicht, welche Vielfachen der bisher berechneten Gröbnerbasiselemente man genau benötigt. Versucht man, alle denkbaren Vielfachen zu betrachten, so dass möglichst viele Leitterme des aktuellen Grades abgedeckt werden, so hat dies zur Folge, dass die Matrix in vielen Fällen fast quadratisch wird, vor allem in höheren Graden, wenn viele Gröbnerbasiselemente für die Multiplikation mit vielen Termen zur Verfügung stehen. Eine andere denkbare Methode wäre es, nur die wirklich benötigten Vielfachen zu erzeugen und in die Matrix zu integrieren. Dies muss jedoch nach und nach geschehen, da während der Reduktion viele neue Terme entstehen können, die anfangs noch nicht in den zu reduzierenden Polynomen enthalten waren. Das bedeutet, dass während der Abarbeitung immer wieder neue Zeilen in die Mitte der bereits bestehenden Matrix eingefügt werden müssen. Dies ruft einen hohen Rechenaufwand hervor, da vor der Verschiebung der nachfolgenden Zeilen zuerst eine passende Stelle für die neue Zeile gefunden werden muss; zum möglichst schnellen Auffinden der Zeile mit dem jeweils passenden Leitterm empfiehlt es sich nämlich, die Zeilenvektoren der Vielfachen in Dreiecksgestalt anzuordnen. Ein weiteres programmiertechnisches Problem ist die hierbei notwendige Umindizierung, an die je nach Fall verschiedene Schleifenindizes angepasst werden müssen. Dabei können leicht kleine Fehler auftreteten, die nur sehr selten in Erscheinung treten und somit nur äußerst schwer erkannt werden können.

– Die erwähnte Transformation der Matrix in den nächsthöheren Grad hat unweigerlich eine Vergrößerung zur Folge, so dass mit hoher Wahrscheinlichkeit wieder Zeilen entstehen, die eigentlich nicht benötigt werden. Dieser Effekt verstärkt sich natürlich von Grad zu Grad, so dass bald viele überflüssige Zeilen die Matrix unnötig groß machen, was ja vermieden werden soll. Außerdem kommt es zuweilen vor, dass in einem betrachteten Grad d ∈ ℕ_{+} keine Polynome zu reduzieren sind. Algorithmus 2.3.2 würde diesen Grad einfach überspringen, doch wenn man mit Transformationen arbeiten möchte, muss man auch diesen Grad d betrachten, nur um die Matrix vom Grad d − 1 in den Grad d + 1 zu erheben, da die Umwandlungsvorschriften für einen Unterschied von zwei oder mehr Graden schon sehr komplex und deshalb kaum realisierbar sind.

3.2 Buchberger-Algorithmus mit Multireduktion

In diesem Abschnitt soll versucht werden, die auf den vorangegangenen Seiten entwickelte Idee doch noch zu realisieren, d. h. alle Polynome eines Grades parallel zu reduzieren. Dazu muss natürlich versucht werden, die angeführten Probleme zu lösen bzw. zu umgehen. Dies geschieht einfach dadurch, dass zwar die beschriebenen Zeilenumformungen erfolgen, jedoch niemals eine Matrix erzeugt wird. Die Operationen erfolgen direkt auf den zu den Polynomen gehörigen Vektoren, was jedoch erst bei der letztendlichen Realisierung als Programm geschieht; die Algorithmen werden hier direkt für Polynome formuliert.

Sei P := K[x_{1}, …, x_{n}] wieder ein standardgraduierter Polynomring über einem Körper K und sei σ eine Termordnung auf 𝕋^{n}.

3.2.1 Satz: Seien s ∈ ℕ_{+}, g_{1}, …, g_{s} ∈ P \ {0} homogen und G := (g_{1}, …, g_{s}). Seien außerdem d, r ∈ ℕ, f_{1}, …, f_{r} ∈ P homogen mit deg(f_{j}) = d für j = 1, …, r und F := (f_{1}, …, f_{r}). Sei weiter m := \binom{n+d−1}{d} und sei s_{k} := pr_{k}(T_{d}^{n}) ∈ 𝕋_{d}^{n} für k = 1, …, m. Betrachte die folgenden Instruktionen:

1 Setze h_{j} := f_{j} und p_{j} := 0 für j = 1, …, r 2 Wiederhole die Schritte 3 bis 7 für k = 1, …, m 3 Existiert ein i ∈ {1, …, s}, so dass s_{k} ein Vielfaches von LT_{σ}(g_{i}) ist,

so führe die Schritte 4 bis 7 durch, andernfalls ersetze p_{j} durch p_{j} + LM_{σ}(h_{j}) und h_{j} durch h_{j} − LM_{σ}(h_{j}) für alle j = 1, …, r mit h_{j} ≠ 0 und LT_{σ}(h_{j}) = s_{k} und fahre in der Ausführung von Schritt 2 fort

4 Sei i ∈ {1, …, s} der kleinste Index, für den s_{k} ein Vielfaches von

LT_{σ}(g_{i}) ist

5 Berechne g′_{i} := \frac{s_{k}}{LT_{σ}(g_{i})} · g_{i} 6 Wiederhole Schritt 7 für alle j = 1, …, r mit h_{j} ≠ 0 7 Gilt LT_{σ}(h_{j}) = s_{k}, so ersetze h_{j} durch h_{j} − \frac{LC_{σ}(h)}{LC_{σ}(g′_{i})} · g′_{i} 8 Setze Q := {p_{1}, …, p_{r}} \ {0} und l := 0 9 Wiederhole die Schritte 10 bis 16, solange Q ≠ ∅ ist 10 Setze Q′ := {q ∈ Q | LT_{σ}(q) = max_{σ}(LT_{σ}(Q))} 11 Streiche die Elemente von Q′ in Q 12 Erhöhe l um 1 13 Wähle ein Element q_{l} ∈ Q′ und streiche es in Q′ 14 Wiederhole die Schritte 15 bis 16, solange Q′ ≠ ∅ ist 15 Wähle ein Element q ∈ Q′ und streiche es in Q′ 16 Ist das Polynom q − \frac{LC_{σ}(q)}{LC_{σ}(q_{l})} · q_{l} nicht 0, so füge es zu Q hinzu 17 Gib (q_{1}, …, q_{l}) zurück

Dieser Algorithmus berechnet Polynome q_{1}, …, q_{l} mit folgenden Eigenschaften:

a) Für jedes i = 1, …, l gibt es einen Index j_{i} ∈ {1, …, r} \ {j_{1}, …, j_{i−1}} mit q_{i} = NR_{σ,(g_{1},...,g_{s},q_{1},...,q_{i−1})}(f_{j_{i}}).

b) Für die übrig gebliebenen Polynome f_{j} mit j ∈ {1, …, r} \ {j_{1}, …, j_{l}} gilt NR_{σ,(g_{1},...,g_{s},q_{1},...,q_{l})}(f_{j}) = 0.

Beweis: Die Programmabfolge besteht aus zwei Hauptteilen, die nacheinander ausgeführt werden. Der erste Teil (bis Schritt 7) umfasst nur Schleifen mit vorgegebener Wiederholungszahl. Der zweite Teil beginnt mit einer Menge Q endlicher Länge. Diese Menge Q wird in jedem Durchlauf der Wiederholungsschleife (Schritt 9 bis 16) um mindestens ein Element verkleinert, da jedesmal ein Element der Teilmenge Q′ gestrichen wird und alle anderen Elemente durch reduzierte Versionen ersetzt werden. Somit muss Q nach endlich vielen Schritten leer sein, womit die Programmabfolge abbricht, so dass die Endlichkeit gegeben ist. Der erste Teil des Algorithmus ist dem Divisionsalgorithmus (Theorem 1.2.1) nachempfunden, so dass nach 1.2.2 in Schritt 8 für j = 1, …, r immer p_{j} = NR_{σ,G}(f_{j}) gilt. Im i-ten Durchlauf der Schleife (Schritt 9 bis 16) im zweiten Teil (i = 1, …, l) wird zuerst ein Polynom q_{i} ∈ Q mit maximalem Leitterm gewählt; anschließend werden alle übrigen Polynome q ∈ Q \ {q_{i}} – wieder gemäß dem Divisionsalgorithmus – bzgl. q_{i} reduziert. Das bedeutet, für i = 1, …, l und j = 1, …, r ist p_{j}^{(i)} := NR_{σ,(q_{1},...,q_{i})}(p_{j}) nach dem i-ten Schleifendurchlauf entweder 0 oder in Q enthalten und jedes q ∈ Q besitzt eine derartige Darstellung. Also gibt es zu jedem i = 1, …, l einen Index j_{i} ∈ {1, …, r} mit

q_{i} = p_{j_{i}}^{(i−1)} = NR_{σ,(q_{1},...,q_{i−1})}(p_{j_{i}}) = NR_{σ,(g_{1},...,g_{s},q_{1},...,q_{i−1})}(f_{j_{i}})

und wegen p_{j_{i}}^{(i)} = NR_{σ,(q_{i})}(p_{j_{i}}^{(i−1)}) = NR_{σ,(q_{i})}(q_{i}) = 0 sind alle j_{i} verschieden. Für j ∈ {1, …, r} \ {j_{1}, …, j_{l}} gilt

NR_{σ,(g_{1},...,g_{s},q_{1},...,q_{l})}(f_{j}) = NR_{σ,(q_{1},...,q_{l})}(p_{j}) = p_{j}^{(l)} = 0

da Q nach dem l-ten Schleifendurchlauf leer ist. □

3.2.2 Definition: In der Situation von Satz 3.2.1 heißt MR_{σ,G}(F) := (q_{1}, …, q_{l}) die Multireduktion von F bzgl. G.

Die Multireduktion ist optimiert für eine Darstellung der homogenen Polynome als Zeilenvektoren. Stellt man sich diese untereinander geschrieben als Matrix vor (wie in Abschnitt 3.1 beschrieben), so werden im Laufe der Reduktion alle Spalten von links nach rechts abgearbeitet, indem von allen nicht einem bereits bekannten Gröbnerbasiselement entsprechenden Zeilenvektoren jeweils ein Vielfaches eines anderen Vektors abgezogen wird, der seinen ersten von Null verschiedenen Eintrag in der betrachteten Spalte besitzt. Für die zu den Vektoren gehörigen Polynome bedeutet dies nichts anderes als eine Reduktion mit einem Polynom, dessen Leitterm der der Spalte entsprechende Term ist.

3.2.3 Theorem (Buchberger-Algorithmus mit Multireduktion): Seien f_{1}, …, f_{s} ∈ P \ {0} homogene Polynome und I := (f_{1}, …, f_{s}) das von f_{1}, …, f_{s} erzeugte Ideal. Betrachte die folgenden Instruktionen:

1 Setze s′ := 0, F := {f_{1}, …, f_{s}}, G := () und B := ∅ 2 Wiederhole die Schritte 3 bis 12, solange B ≠ ∅ oder F ≠ ∅ gilt 3 Setze d := min{min{deg(f) | f ∈ F }, min{deg(kgV(t_{i}, t_{j})) | (i, j) ∈ B}} 4 Setze B_{d} := {(i, j) ∈ B | deg(kgV(t_{i}, t_{j})) = d} und streiche die Elemente

von B_{d} in B 5 Setze F_{d} := {f ∈ F | deg(f) = d} und streiche die Elemente von F_{d} in F 6 Bilde ein Tupel F aus allen Elementen von F_{d} 7 Hänge alle S-Polynome S_{ij} mit (i, j) ∈ B_{d} an F an 8 Berechne F′ := MR_{σ,G}(F) 9 Sei s′′ die Länge von F′ 10 Bilde g_{i} := pr_{i}(F′) für i = 1, …, s′′ und hänge g_{i} an G an 11 Füge die Paare (i, j) mit j = s′ + 1, …, s′ + s′′ und i = 1, …, j − 1 zu B

hinzu

12 Erhöhe s′ um s′′ 13 Gib G := {g_{1}, …, g_{s′}} als Ergebnis zurück

Dieser Algorithmus berechnet eine σ-Gröbnerbasis des Ideals I bestehend aus homogenen Polynomen g_{1}, …, g_{s′} mit deg(g_{1}) ≤ … ≤ deg(g_{s′}).

Beweis: Die Endlichkeit der Ausführung hängt einzig von der Schleifenbedingung in Schritt 2 ab. In jedem Durchlauf wird B oder F verkleinert. Da die Menge F von Anfang an endlich ist und im Laufe der Abarbeitung niemals vergrößert wird, muss lediglich überprüft werden, ob B leer wird. Eine Vergrößerung von B in Schritt 11 findet aber nur statt, wenn s′′ ≠ 0 gilt, d. h. wenn F′ = MR_{σ,G}(F) kein 0-Tupel ist. Wäre dies unendlich oft der Fall, so entstünden unendlich viele verschiedene Polynome g_{k} ≠ 0 (k ∈ ℕ_{+}) mit g_{k} = NR_{σ,(g_{1},...,g_{k−1})}(S_{ij}) für je ein Paar (i, j) mit i < j < k nach Satz 3.2.1 a). Nach Theorem 1.2.1 a) gälte für den normalen Rest g_{k} aber LT_{σ}(g_{k}) ∉ (LT_{σ}(g_{1}), …, LT_{σ}(g_{k−1})), so dass die Idealkette (LT_{σ}(g_{1})) ⊊ (LT_{σ}(g_{1}), LT_{σ}(g_{2})) ⊊ … unendlich wäre. Da dies Satz 1.1.7 b) widerspräche, muss die Programmfolge nach endlich vielen Schritten abbrechen. Am Ende des Algorithmus ist jedes Paar (i, j) mit 1 ≤ i < j ≤ s′ abgearbeitet und das zugehörige S-Polynom S_{ij} zu F hinzugefügt worden. Tritt bei der entsprechenden Multireduktion in Schritt 8 bei S_{ij} der Fall a) von Satz 3.2.1 auf, so ist die normale Reduktion von S_{ij} in F′ enthalten und wird in Schritt 10 zu G hinzugefügt, so dass am Ende des Algorithmus in beiden Fällen NR_{σ,G}(S_{ij}) = 0 gilt. Nach Satz 2.1.2 ist G somit eine σ-Gröbnerbasis von I. Die Homogenität der berechneten Polynome ist klar; die Grade sind nicht abnehmend, da der Grad d der berechneten Polynome mit jeder Schleifenwiederholung zunimmt, weil die zu den neu erzeugten Paaren gehörigen S-Polynome 0 oder mindestens vom Grad d + 1 sind. □

Vergleicht man diesen Algorithmus mit der homogenen Version des ursprünglichen Buchberger-Algorithmus (siehe 2.3.2), so besteht der Vorteil der Multireduktion darin, dass durch die sequenzielle Abarbeitung aller Terme eines Grades die Suche eines Gröbnerbasiselements mit dem entsprechenden Leitterm nur einmal für alle zu reduzierenden Polynome erfolgen muss. Die nachteilige Tatsache, dass dafür im Gegenzug jeder einzelne Term betrachtet werden muss, wird umso unbedeutender, je mehr Polynome zugleich reduziert werden. Alles in allem kann man sagen, dass die Effizienz der Multireduktion gegenüber der normalen Reduktion mit der Anzahl der zu reduzierenden Polynome ansteigt, da so deren Vorteile immer mehr die Überhand gewinnen.

3.2.4 Bemerkung: Sei die Situation von Theorem 3.2.3 gegeben.

a) Bemerkung 2.3.4 a) - c) gilt entsprechend für den Buchberger-Algorithmus mit Multireduktion.

b) Um auch hier die Regeln von Gebauer und Möller gemäß Satz 2.2.1 anzuwenden, ersetzt man die Schritte 10 bis 12 durch

10 Wiederhole die Schritte 11 und 12 für i = 1, …, s′′ 11 Bilde g_{i} := pr_{i}(F′) und hänge g_{i} an G an 12 Erhöhe s′ um 1 und führe UpdateGM(B) durch

Dabei ist UpdateGM die in Theorem 2.2.3 definierte Funktion.

c) Dementsprechend kann auch die in Theorem 2.4.1 vorgestellte Paarminimalisierung in den Buchberger-Algorithmus mit Multireduktion integriert werden, indem man die Schritte 1 sowie 10 bis 12 wie folgt abändert und die Schritte 4a bis 4c zwischen den Schritten 4 und 5 einfügt:

1 Setze s′ := 0, F := {f_{1}, …, f_{s}}, G := (), A := ∅, B := ∅ und B^{∗} := ∅

4a Setze B_{d}^{∗} := {(i, j) ∈ B^{∗} | deg(kgV(t_{i}, t_{j})) = d} und streiche die

Elemente von B_{d}^{∗} in B^{∗} 4b Führe MinPairs(A, B_{d}, B_{d}^{∗}) durch 4c Füge die Elemente von B_{d} zu A hinzu

10 Wiederhole die Schritte 11 und 12 für i = 1, …, s′′ 11 Bilde g_{i} := pr_{i}(F′) und hänge g_{i} an G an 12 Erhöhe s′ um 1 und führe Update(B, B^{∗}, g_{i}) durch

Die Funktionen Update und MinPairs sind in Theorem 2.4.1 definiert.

3.3 Faugéres Algorithmus F_{4}

Eine weitere Alternative zum Buchberger-Algorithmus stammt von Jean-Charles Faugére. In [Fa] beschreibt er den Algorithmus F_{4}, der ebenfalls eine eigene Reduktionsfunktion verwendet.

Seien P := K[x_{1}, …, x_{n}] ein Polynomring über einem Körper K und σ eine Termordnung auf 𝕋^{n}.

3.3.1 Definition: Seien m, s ∈ ℕ_{+}.

a) Ist A ∈ Mat_{s,m}(K) eine (s × m)-Matrix, so bezeichne Ã die eindeutige Zeilenstufenform von A, d.h. Ã ist von der Form

Ã = [ \begin{matrix}0 & … & 0 1 & ∗ & … & ∗ & 0 & ∗ & … & ∗ & 0 & 0 & ∗ & … & ∗ \\ 0 & … & 0 & 0 & 0 & … & 0 1 & ∗ & … & ∗ & 0 & 0 & ∗ & … & ∗ \\ 0 & … & 0 & 0 & 0 & … & 0 & 0 & 0 & … & 0 1 & 0 & ∗ & … & ∗ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & … & 0 & 0 & 0 & … & 0 & 0 & 0 & … & 0 & 0 & 1 & ∗ & … & ∗ \end{matrix} ]

Das bedeutet, Ã ist eine (s̃ × m)-Matrix mit s̃:= Rang(A) ≤ min{m, s}. b) Sei F ⊆ P endlich. Ist F = ∅, so definiere F̃ := ∅ und F̃^{+} := ∅. Andernfalls

seien s := Card(F), m := Card(Supp(F)) und F ∈ P^{s} sowie L ∈ (𝕋^{n})^{m} Tupel, die die Elemente von F bzw. Supp(F) als Einträge enthalten, wobei die Einträge von L absteigend bzgl. σ angeordnet seien. Dann definiere

s̃:= Rang(Ψ_{L,s}(F))
F̃ := Ψ_{L,s̃}^{−1}(Ψ_{L,s}(F)^{∼}) ∈ P s̃
F̃ := ⋃_{i=1}^{s̃}{pr_{i}(F̃)} ⊆ P \ {0}
F̃^{+} := {f ∈ F̃ | LT_{σ}(f) ∉ LT_{σ}{F }} ⊆ P \ {0}

Dabei heißen F̃ das zu F interreduzierte Tupel und F̃ die Interreduktion von F.

3.3.2 Beispiel: In Beispiel 3.1.2 beinhaltete L = (x_{1}^{2}, x_{1}x_{2}, x_{1}x_{3}, x_{2}^{2}, x_{2}x_{3}, x_{3}^{2}) alle Terme der Polynomeinträge von F. Die eindeutige Zeilenstufenform der Matrix Ψ_{L,3}(F) lautet

Ψ_{L,3}(F)^{∼} = [ \begin{matrix}1 & 0 & 0 & 0 & −6 & 5 \\ 0 & 1 & 0 & \frac{1}{3} & 4 & −\frac{10}{3} \\ 0 & 0 & 1 & 0 & 3 & 0 \end{matrix} ]

Also gilt F̃ = \{x_{1}^{2} − 6x_{2}x_{3} + 5x_{3}^{2}, x_{1}x_{2} + \frac{1}{3}x_{2}^{2} + 4x_{2}x_{3} − \frac{10}{3}x_{3}^{2}, x_{1}x_{3} + 3x_{2}x_{3}\} und damit F̃^{+} = \{x_{1}x_{2} + \frac{1}{3}x_{2}^{2} + 4x_{2}x_{3} − \frac{10}{3}x_{3}^{2}\}.

3.3.3 Bemerkung: In der Situation von Definition 3.3.1 b) seien y_{1}, …, y_{m} neue Variablen. Seien die Terme von Q := K[y_{1}, …, y_{m}] bzgl. Lex geordnet und sei außerdem Y := (y_{1}, …, y_{m}). Betrachtet man H := Ψ_{Y,s}^{−1}(Ψ_{L,s}(F)) ⊆ Q^{s} sowie H̃ := Ψ_{Y,s̃}^{−1}(Ψ_{L,s}(F)^{∼}) ⊆ Qs̃ und die zugehörigen Mengen H, H̃ ⊆ Q, so ist H̃ eine reduzierte Lex-Gröbnerbasis des von H in Q erzeugten Ideals (vgl. dazu auch [KrRo 1], S. 120).

3.3.4 Satz: Sei F ⊆ P eine endliche Menge und sei F′ ⊆ F eine Teilmenge mit LT_{σ}{F′} = LT_{σ}{F } und Card(F′) = Card(LT_{σ}{F }). Dann bildet B := F̃^{+} ∪ F′ eine Basis des K-Vektorraums ⟨F ⟩_{K}.

Beweis: Seien s := Card(F) und m := Card(Supp(F)). Seien F ⊆ P^{s} sowie L ⊆ (𝕋^{n})^{m} Tupel bestehend aus den Elementen von F bzw. Supp(F), wobei die Einträge von L absteigend bzgl. σ angeordnet seien. Betrachtet man nun den Polynomring Q := K[y_{1}, …, y_{m}], dessen Terme mit Lex versehen seien, sowie das Tupel Y := (y_{1}, …, y_{m}) ∈ Q^{m}, so ist ⟨F ⟩_{K} isomorph zu dem von den Einträgen von Ψ_{Y,s}^{−1}(Ψ_{L,s}(F)) erzeugten K-Vektorraum V ⊆ Q, und alle Aussagen über Leitterme und Basen gelten entsprechend in V. Deswegen genügt es, im Folgenden die Identifizierungen von F, F̃, F̃^{+}, F′ und B in V zu betrachten. Aufgrund der Definitionen von F̃^{+} und F′ sind die Leitterme in B alle paarweise verschieden. Somit sind die Elemente von B linear unabhängig. Da nach Bemerkung 3.3.3 F̃ eine reduzierte Lex-Gröbnerbasis des von F erzeugten Ideals ist, folgt dim_{K}(V) = Card(F̃) = Card(LT_{Lex}{F̃}). Für die Leitterme gilt aber LT_{Lex}{F̃} = LT_{Lex}{F̃^{+}} ∪ LT_{Lex}{F } = LT_{Lex}{F̃^{+}} ∪ LT_{Lex}{F′} = LT_{Lex}{B}. Es folgt dim_{K}(V) = Card(LT_{Lex}{B}) = Card(B). □

Mit diesem Satz sind nun alle nötigen Hilfsmittel bekannt, um F_{4} und die dafür benötigte Reduktion einführen zu können.

3.3.5 Satz: Sei G ⊆ P \ {0} endlich und seien I das von G sowie J das von LT_{σ}{G} erzeugte Ideal. Seien außerdem M ⊆ 𝕋^{n} × G eine endliche Menge und L := {tg | (t, g) ∈ M} ⊆ P. Betrachte die folgenden Instruktionen:

1 Setze F := L 2 Setze D := LT_{σ}{F } 3 Wiederhole die Schritte 4 bis 6, solange D ≠ Supp(F) gilt 4 Wähle ein m ∈ Supp(F) \ D 5 Füge m zu D hinzu 6 Gibt es ein g ∈ G, so dass LT_{σ}(g) ein Teiler von m ist,

so füge \frac{m}{LT_{σ}(g)} · g zu F hinzu 7 Berechne F̃ sowie F̃^{+} und gib das Tripel (F, F̃, F̃^{+}) als Ergebnis zurück

Die mit diesem Algorithmus berechnete Menge F̃^{+} hat folgende Eigenschaften:

a) Für alle m ∈ LT_{σ}{F̃^{+}} gilt m ∉ J.

b) Es gilt F̃^{+} ⊆ I.

c) Für alle f ∈ ⟨L⟩_{K} gilt f ⟶^{G∪F̃^{+}} 0.

Beweis: Wird in Schritt 6 ein neues Polynom zu F hinzugefügt, so hat dieses den Leitterm LT_{σ}(\frac{m}{LT_{σ}(g)} · g) = m. Da m zu D hinzugefügt wird, sind im nächsten Wiederholungsschritt alle neuen Elemente in Supp(F) \ D echt kleiner als m. Zu jedem Zeitpunkt (ab Schritt 3) gilt also max_{σ}(Supp(F) \ D) <_{σ} max_{σ}(Supp(L)). Da D in jedem Wiederholungsschritt vergrößert wird, muss nach endlich vielen Wiederhoungen D = Supp(F) gelten. Die Berechnung von F̃ aus F erfolgt nach der Gauß-Jordan-Elimination und benötigt somit auch nur endlich viele Schritte. Wäre a) nicht erfüllt, d. h. gäbe es einen Term m ∈ LT_{σ}{F̃^{+}} mit m ∈ J, so müsste es ein Polynom g ∈ G geben, dessen Leitterm m teilt. Nach den Definitionen in 3.3.1 gälte m ∈ LT_{σ}{F̃^{+}} ⊆ Supp(F̃^{+}) ⊆ Supp(F̃) = Supp(F). Also würde in Schritt 6 des Algorithmus das Polynom \frac{m}{LT_{σ}(g)} · g zu F hinzugefügt. Dessen Leitterm wäre aber m, im Widerspruch zur Definition von F̃^{+}. In Schritt 1 gilt nach Definition F = L ⊆ I. Jedes weitere in Schritt 6 zu F hinzugefügte Polynom ist stets ein Vielfaches eines Erzeugers g ∈ G, so dass am Ende des Algorithmus F ⊆ I gilt. Mit Satz 3.3.4 folgt F̃^{+} ⊆ ⟨F ⟩_{K} ⊆ I. Ebenfalls nach Satz 3.3.4 lässt sich jedes Polynom f ∈ ⟨L⟩_{K} des Untervektorraums ⟨L⟩_{K} ⊆ ⟨F ⟩_{K} als Linearkombination f = a′_{1}f′_{1} + ⋯ + a′_{k}f′_{k} + ã_{1}f̃_{1} + ⋯ + ã_{l}f̃_{l} darstellen mit f′_{i} ∈ F, f̃_{j} ∈ F̃^{+} und a′_{i}, ã_{j} ∈ K \ {0} für i = 1, …, k und j = 1, …, l. Da dabei die Polynome f′_{i} für i = 1, …, k immer von der Form f′_{i} = mg mit m ∈ 𝕋^{n}

und g ∈ G sind, gilt a′_{1}f′_{1} + ⋯ + a′_{k}f′_{k} ⟶^{G} 0. Wegen ã_{1}f̃_{1} + ⋯ + ã_{l}f̃_{l} \underrightarrow{F̃^{+}} 0 folgt

f ⟶^{G∪F̃^{+}} 0. □

3.3.6 Definition: In der Situation von Satz 3.3.5 sei FR_{σ,G}(L) := (F, F̃, F̃^{+}). Die Menge F̃^{+} heißt F-Reduktion von L bzgl. G.

Vom Ergebnistupel (F, F̃, F̃^{+}) der F-Reduktion wird nachfolgend nur die letzte Menge verwendet. Die Syntax des Ergebnisses als Tupel mit den zusätzlichen Mengen F und F̃ wurde aus Kontinuitätsgründen in Anlehnung an die im nächsten Abschnitt folgende Verbesserung von F_{4} bereits hier so gewählt, da dann alle drei Mengen benötigt werden.

3.3.7 Theorem (Algorithmus F_{4}): Seien G_{0} = {g_{1}, …, g_{s}} ⊆ P eine endliche Menge und I := (g_{1}, …, g_{s}) ⊆ P das von G_{0} erzeugte Ideal. Weiter sei Sel(M) eine (beliebige) Auswahlfunktion, die eine nichtleere Teilmenge der übergebenen nichtleeren Menge M zurückliefert. Betrachte die folgenden Instruktionen:

1 Setze G := G_{0}, s′ := s und B := {(i, j) | 1 ≤ i < j ≤ s} 2 Wiederhole die Schritte 3 bis 11, solange B ≠ ∅ ist 3 Setze C := Sel(B) 4 Ersetze B durch B \ C 5 Setze L := {t_{ij}g_{i} | (i, j) ∈ C} ∪ {t_{ji}g_{j} | (i, j) ∈ C} 6 Berechne (F, F̃, F̃^{+}) := FR_{σ,G}(L) 7 Wiederhole Schritte 8 bis 11 für jedes f ∈ F̃^{+} 8 Erhöhe s′ um 1 9 Definiere g_{s′} := f 10 Füge g_{s′} zu G hinzu 11 Füge die Paare (1, s′), …, (s′ − 1, s′) zu B hinzu 12 Gib G zurück

Dieser Algorithmus berechnet eine σ-Gröbnerbasis G von I.

Beweis: Wäre die Endlichkeit nicht gegeben, so müsste dies in der äußeren Wiederholungsschleife der Fall sein und in unendlich vielen Wiederholungsschritten müsste F̃^{+} ≠ ∅ gelten. So entstünde eine Folge (F̃_{i}^{+})_{i∈ℕ} nichtleerer Mengen und eine entsprechende Folge (G_{i})_{i∈ℕ} aufsteigender Mengen G. Nun könnte man für jedes i ∈ ℕ_{+} ein f_{i} ∈ F̃_{i}^{+} wählen und mit I_{0} := (0) und I_{i} := I_{i−1} + (LT_{σ}(f_{i})) für i ∈ ℕ_{+} eine aufsteigende Idealkette konstruieren. Es gälte stets I_{i−1} ⊆ (LT_{σ}{G_{i−1}}), aber f_{i} ∉ (LT_{σ}{G_{i−1}}) wegen Satz 3.3.5 a), und damit I_{i−1} ⊊ I_{i}. Die Idealkette wäre somit nicht stationär, im Widerspruch zur Noether-Eigenschaft von P. Da anfänglich G = G_{0} gilt und zu G in Schritt 10 immer nur Elemente von F̃^{+} hinzugefügt werden, gilt wegen Satz 3.3.5 b) stets G_{0} ⊆ G ⊆ I. Jedes Paar (i, j) mit 1 ≤ i < j ≤ s′ ist genau einmal in der Menge C enthalten. Im entsprechenden Wiederholungsschritt muss also t_{ij} · g_{i}, t_{ji} · g_{j} ∈ L und damit S_{ij} ∈ ⟨L⟩_{K} gelten, womit nach Satz 3.3.5 c) nach diesem Wiederholungsdurchlauf S_{ij} ⟶^{G} 0 gilt. Damit ist nach Satz 2.1.1 Bedingung (G_{6}) erfüllt, und G ist eine Gröbnerbasis. □

Die Funktion Sel im Algorithmus F_{4} ist eine Auswahlfunktion, die keinen Einfluss auf die Korrektheit des Algorithmus hat. Gibt Sel beispielsweise immer nur ein Element der übergebenen Menge zurück, so entspricht dies der Auswahlstrategie im Buchberger-Algorithmus. Ratsam wäre z. B. eine Selektionsfunktion, die alle Polynome minimalen Grades zurückliefert.

3.4 Optimierung von F_{4}

Faugére stellt in [Fa] auch eine Verbesserung von F_{4} vor, die eine zusätzliche Funktion verwendet, um die Darstellung der zurückgegebenen Polynome zu optimieren. Dies soll gewährleisten, dass die erzeugten Polynome derart gewählt werden, dass sie aus bereits bekannten Polynomen durch Multiplikation mit einem möglichst kleinen Term hervorgehen.

Seien P := K[x_{1}, …, x_{n}] ein Polynomring über einem Körper K und σ eine Termordnung auf 𝕋^{n}.

3.4.1 Satz: Seien t ∈ 𝕋^{n}, f ∈ P \{0}, d ∈ ℕ sowie F_{k} ⊆ P endlich für k = 1, …, d. Weiterhin seien die Tupel F := (F_{1}, …, F_{d}) und F̃ := (F̃_{1}, …, F̃_{d}) gegeben.

1 Setze t′ := t und f′ := f 2 Setze M := {m ∈ 𝕋^{n} | m teilt t′} \ {1} 3 Schreibe M = {m_{1}, …, m_{s}} mit s = Card(M) und t′ = m_{1} >_{σ} … >_{σ} m_{s} >_{σ} 1 4 Wiederhole die Schritte 5 bis 7 für alle j = 1, …, s und k = 1, …, d 5 Gilt m_{j} · f′ ∈ F_{k}, so führe die Schritte 6 und 7 durch 6 Suche f′′ ∈ F̃_{k} mit LT_{σ}(f′′) = LT_{σ}(m_{j}f′) 7 Ist j = 1, so gib (1, f′′) zurück, andernfalls ersetze t′ durch \frac{t′}{m_{j}} und

f′ durch f′′ und starte wieder bei Schritt 2

8 Gib (t′, \frac{f′}{LC_{σ}(f′)}) zurück

Dieser Algorithmus berechnet ein Paar (t̂, f̂) ∈ 𝕋^{n} × P, für das gilt:

a) LT_{σ}(t̂f̂) = LT_{σ}(tf).

b) Ist I ⊆ P das von ⋃_{k = 1}^{d} F_{k} erzeugte Ideal, so gibt es ein Polynom r ∈ I mit

LT_{σ}(r) <_{σ} LT_{σ}(tf), so dass tf = LC_{σ}(f) · t̂f̂+ r gilt.

c) Das Paar (t̂, f̂) wird so gewählt, dass t̂ bzgl. σ minimal ist mit den Eigenschaften a) und b).

Beweis: Die Menge M ist endlich und effektiv berechenbar, so dass nur endlich viele Wiederholungen auftreten können. Kommt es in Schritt 7 zu einer Rekursion, so gilt \frac{t′}{m_{j}} <_{σ} t′, so dass t′ in jedem Rekursionsschritt verkleinert wird, womit nur endlich viele Rekursionsschritte auftreten können. Somit wird nach endlich vielen Schritten ein Paar (t̂, f̂) zurückgegeben. Die Gleichheit der Leitterme ist nur fraglich, falls ein rekursiver Aufruf stattfindet. In diesem Fall gilt LT_{σ}(\frac{t′}{m_{j}} · f′′) = \frac{t′}{m_{j}} · LT_{σ}(m_{j}f′) = LT(t′f′), so dass auch im nächsten (und in jedem noch folgenden) Rekursionsschritt LT_{σ}(t′f′) gleich bleibt. Es genügt, Behauptung b) für den Fall eines Rekursionsaufrufes zu zeigen, also mit t̂ = \frac{t′}{m_{j}} und f̂ = f′′. Da im entsprechenden Schritt m_{j}f′ ∈ F_{k} gelten muss, kann man eine Menge F′_{k} ⊆ F_{k} bilden mit m_{j}f′ ∈ F′_{k}, LT_{σ}{F′_{k}} = LT_{σ}{F_{k}} und Card(F′_{k}) = Card(LT_{σ}{F_{k}}). Nach Satz 3.3.4 bildet B := F′_{k} ∪ F̃_{k}^{+} eine Basis von ⟨F ⟩_{K} ⊆ I. Schreibt man B = {b_{1}, …, b_{l}} mit l = Card(B) und b_{1} = m_{j}f′, so gibt es wegen f̂ = f′′ ∈ F̃_{k} eine Darstellung f̂ = ∑_{i = 1}^{l} a_{i}b_{i} mit a_{i} ∈ K für i = 1, …, l. Mit r′ := ∑_{i = 2}^{l} a_{i}b_{i} muss LT(r′) <_{σ} LT(f̂) gelten und somit folgt f̂ = a_{1}m_{j}f′ + r′. Wegen LC_{σ}(f̂) = 1 gilt a_{1} = \frac{1}{LC_{σ}(f′)} und mit m_{j} = \frac{t′}{t̂} folgt

t′f′ = LC_{σ}(f′)·t̂f̂−LC_{σ}(f′)·t̂r′. Damit liefert r := − LC_{σ}(f′)·t̂r′ die Behauptung. Die Minimalität von t̂ ist klar, da die Teiler m_{j} ∈ M in absteigender Reihenfolge abgearbeitet werden und jeweils \frac{t′}{m_{j}} betrachtet wird. □

3.4.2 Definition: Das Ergebnis des in Satz 3.4.1 beschriebenen Algorithmus werde mit Simp(t, f, F, F̃) := (t̂, f̂) bezeichnet. Für Teilmengen T ⊆ 𝕋^{n} und F ⊆ P \ {0}

bezeichne Simp(T, F, F, F̃) := ⋃_{t ∈ T} ⋃_{f ∈ F}{Simp(t, f, F, F̃)}.

Die Mengen T ⊆ 𝕋^{n} und F ⊆ P \{0} in Definition 3.4.2 müssen dabei nicht zwangsweise endlich sein. Die Menge Simp(T, F, F, F̃) kann somit im Fall der Unendlichkeit von T oder F nicht mit dem Algorithmus aus Satz 3.4.1 berechnet werden.

3.4.3 Lemma: Seien d ∈ ℕ und F_{k} ⊆ P endlich für k = 1, …, d. Seien G ⊆ P \{0} endlich mit G ⊇ F̃_{1}^{+} ∪ … ∪ F̃_{d}^{+}. Für k = 1, …, d sei

L_{k} := {tf | (t, f) ∈ Simp(𝕋^{n}, G, (F_{1}, …, F_{k−1}), (F̃_{1}, …, F̃_{k−1}))}

und es gelte F_{k} ⊆ L_{k}. Weiter seien Tupel F := (F_{1}, …, F_{d}) und F̃ := (F̃_{1}, …, F̃_{d}) gegeben. Seien g ∈ G, t ∈ 𝕋^{n} und (t̂, ĝ) := Simp(t, g, F, F̃). Dann besitzt ĝ eine LT_{σ}(ĝ)-Repräsentation bzgl. G (vgl. Definition 1.5.1).

Beweis: Der Beweis erfolgt durch Induktion nach d. Für d = 0 ist ĝ = \frac{1}{LC_{σ}(g)} · g bereits eine LT_{σ}(ĝ)-Repräsentation. Ist d > 0 und gilt ĝ ≠ \frac{1}{LC_{σ}(g)} · g, so ist nach

dem Algorithmus ĝ ∈ F̃_{k} für einen Index k ∈ {1, …, d}. Nach Satz 3.3.4 muss es eine eindeutige Linearkombination ĝ = a_{1}f_{1} + ⋯ + a_{l}f_{l} + ã_{1}f̃_{1} + ⋯ + ã_{m}f̃_{m} mit f_{i} ∈ F_{k}, f̃_{j} ∈ F̃_{k}^{+} ⊆ G und a_{i}, ã_{j} ∈ K \ {0} für i = 1, …, l und j = 1, …, m geben, die keine Terme größer LT_{σ}(ĝ) aufweist. Die Polynome f_{i} besitzen aber für i = 1 …, l wegen F_{k} ⊆ L_{k} nach Induktionsannahme eine LT_{σ}(f_{i})-Repräsentation bzgl. G, und wegen LT_{σ}(f_{i}) ≤_{σ} LT_{σ}(ĝ) folgt die Behauptung. □

3.4.4 Lemma: In der Situation von Lemma 3.4.3 seien g_{1}, g_{2} ∈ G mit g_{1} ≠ g_{2}. Außerdem seien (t̂_{12}, ĝ_{1}) := Simp(t_{12}, g_{1}, F, F̃) und (t̂_{21}, ĝ_{2}) := Simp(t_{21}, g_{2}, F, F̃) sowie f_{1} := t̂_{12}ĝ_{1} und f_{2} := t̂_{21}ĝ_{2}. Das S-Polynom S von f_{1} und f_{2} habe eine t′-Repräsentation für t′ ∈ 𝕋^{n} mit t′ <_{σ} LT_{σ}(f_{1}) = LT_{σ}(f_{2}) = kgV(t_{1}, t_{2}). Dann besitzt das S-Polynom S_{12} von g_{1} und g_{2} eine t-Repräsentation bzgl. G für einen Term t ∈ 𝕋^{n} mit t <_{σ} kgV(t_{1}, t_{2}).

Beweis: Das S-Polynom von ĝ_{1} und ĝ_{2} ist ebenfalls S. Es gilt

S_{12} = \frac{1}{c_{1}} t_{12}g_{1} − \frac{1}{c_{2}} t_{21}g_{2} = \underbrace{\frac{1}{c_{1}} t_{12}g_{1} − t̂_{12}ĝ_{1}}_{=: r_{1}} + \underbrace{t̂_{12}ĝ_{1} − t̂_{21}ĝ_{2}}_{S} + \underbrace{t̂_{21}ĝ_{2} − \frac{1}{c_{2}} t_{21}g_{2}}_{=: r_{2}}

Nach Satz 3.4.1 b) gilt LT_{σ}(r_{1}), LT_{σ}(r_{2}) <_{σ} LT_{σ}(t_{12}g_{1}) = LT_{σ}(t_{21}g_{2}) = kgV(t_{1}, t_{2}). Mit Lemma 3.4.3 folgt, dass S_{12} für t := max_{σ}{LT_{σ}(r_{1}), LT_{σ}(r_{2}), t′} <_{σ} kgV(t_{1}, t_{2}) eine t-Repräsentation besitzt. □

Der Algorithmus der F-Reduktion (vgl. Satz 3.3.5) wird nun für den verbesserten Algorithmus F_{4} wie folgt verändert:

3.4.5 Satz: Seien d ∈ ℕ und F_{k} ⊆ P endlich für k = 1, …, d und seien die Tupel F = (F_{1}, …, F_{d}) und F̃ = (F̃_{1}, …, F̃_{d}) gegeben. Sei G ⊆ P \ {0} endlich mit G ⊇ F̃_{1}^{+} ∪ … ∪ F̃_{d}^{+} und sei M ⊆ 𝕋^{n} × G eine endliche Menge. Seien außerdem L′ := {Simp(t, g, F̃, F̃^{+}) | (t, g) ∈ M} ⊆ 𝕋^{n} × P und L := {tg | (t, g) ∈ L′} ⊆ P. Betrachte die folgenden Instruktionen: 1 Setze F := L 2 Setze D := LT_{σ}{F } 3 Wiederhole die Schritte 4 bis 6, solange D ≠ Supp(F) gilt 4 Wähle ein m ∈ Supp(F) \ D 5 Füge m zu D hinzu 6 Gibt es ein g ∈ G, so dass LT_{σ}(g) ein Teiler von m ist, so berechne

(t, f) := Simp(\frac{m}{LT_{σ}(g)}, g, F, F̃) und füge tf zu F hinzu 7 Berechne F̃ sowie F̃^{+} und gib das Tripel (F, F̃, F̃^{+}) als Ergebnis zurück Dies ist ein Algorithmus und mit der Definition von L_{d} ⊆ P gemäß Lemma 3.4.3 gilt F ⊆ L_{d}.

Beweis: Da sich diese Instruktionen gegenüber Satz 3.3.5 nur durch die Anwendung der Funktion Simp unterscheiden, ergibt sich die Endlichkeit aus der Endlichkeit der Algorithmen in den Sätzen 3.3.5 und 3.4.1. In Schritt 1 gilt F = L ⊆ L_{d}. Für jedes weitere in Schritt 6 zu F hinzugefügte Polynom tf gilt ebenfalls tf ∈ L_{d}. Somit ist F ⊆ L_{d}. □

3.4.6 Definition: In der Situation von 3.4.5 sei FR_{σ,G}(L, F, F̃) := (F, F̃, F̃^{+}). Die Menge F̃^{+} heißt erweiterte F-Reduktion von L bzgl. G.

3.4.7 Theorem (Verbesserter Algorithmus F_{4}): Seien g_{1}, …, g_{s} ∈ P \ {0} und I := (g_{1}, …, g_{s}) ⊆ P das von diesen Polynomen erzeugte Ideal. Weiter sei Sel(M) eine (beliebige) Auswahlfunktion, die eine nichtleere Teilmenge der übergebenen nichtleeren Menge M zurückliefert. Betrachte die folgenden Instruktionen: 1 Setze d := 0, s′ := s, G := {g_{1}, …, g_{s}} und B := {(i, j) | 1 ≤ i < j ≤ s} 2 Wiederhole die Schritte 3 bis 14, solange B ≠ ∅ ist 3 Erhöhe d um 1 4 Setze C := Sel(B) 5 Ersetze B durch B \ C 6 Setze F := (F_{1}, …, F_{d−1}) und F̃ := (F̃_{1}, …, F̃_{d−1}) 7 Setze L′ := {Simp(t_{ij}, g_{i}, F, F̃) | (i, j) ∈ C} ∪ {Simp(t_{ji}, g_{j}, F, F̃) | (i, j) ∈ C}

8 Setze L := {tf | (t, f) ∈ L′} 9 Berechne (F_{d}, F̃_{d}, F̃_{d}^{+}) := FR_{σ,G}(L, F, F̃) 10 Wiederhole die Schritte 11 bis 14 für jedes Polynom f ∈ F̃_{d}^{+} 11 Erhöhe s′ um 1 12 Definiere g_{s′} := f 13 Füge g_{s′} zu G hinzu 14 Füge die Paare (1, s′), …, (s′ − 1, s′) zu B hinzu 15 Gib G als Ergebnis zurück Dieser Algorithmus berechnet eine σ-Gröbnerbasis G von I.

Beweis: Die Endlichkeit folgt genau wie in der ursprünglichen Version von F_{4} (Theorem 3.3.7). Für i, j ∈ {1, …, s′} mit i ≠ j sei (t̂_{ij}, ĝ_{i}) := Simp(t_{ij}, g_{i}, F, F̃). Definiert man Polynome f_{ij} := t̂_{ij}ĝ_{i}, so gilt LT_{σ}(f_{ij}) = LT_{σ}(t_{ij}g_{i}) = t_{ij}t_{i} = kgV(t_{i}, t_{j}) nach Satz 3.4.1 a). Es folgt kgV(LT_{σ}(f_{ij}), LT_{σ}(f_{ji})) = kgV(t_{i}, t_{j}). Für das S-Polynom S′_{ij} von f_{ij} und f_{ji} gilt damit

S′_{ij} = \frac{kgV(LT_{σ}(f_{ij}), LT_{σ}(f_{ji}))}{LT_{σ}(f_{ij})} · f_{ij} − \frac{kgV(LT_{σ}(f_{ij}), LT_{σ}(f_{ji}))}{LT_{σ}(f_{ji})} · f_{ji}
= f_{ij} − f_{ji}
= t̂_{ij}ĝ_{i} − t̂_{ji}ĝ_{j}

Jedes der S-Polynome S′_{ij} besitzt eine LT_{σ}(S′_{ij})-Repräsentation bzgl. G und mit I ≠ P gilt jeweils LT_{σ}(S′_{ij}) <_{σ} LT_{σ}(f_{i}) = LT_{σ}(f_{j}) = kgV(t_{i}, t_{j}). Da nach Satz 3.4.5 die Voraussetzungen von Lemma 3.4.4 erfüllt sind, hat auch jedes der S-Polynome S_{ij} eine t-Repräsentation bzgl. G mit t <_{σ} kgV(t_{i}, t_{j}). Weil dies (G_{1}) erfüllt, ist G eine σ-Gröbnerbasis von I. □

Zum Abschluss soll nun der Algorithmus F_{4} speziell auf den homogenen Fall zugeschnitten werden.

3.4.8 Lemma: Seien d ∈ ℕ und F_{k} ⊆ P endliche Mengen homogener Polynome vom Grad k für k = 1, …, d. Seien außerdem die beiden Tupel F := (F_{1}, …, F_{d}) und F̃ := (F̃_{1}, …, F̃_{d}) gegeben. Sei G ⊆ P \ {0} eine endliche Menge homogener Polynome mit G ⊇ F̃_{1}^{+} ∪ … ∪ F̃_{d}^{+} und sei M ⊆ 𝕋^{n} × G eine endliche Menge mit deg(tg) = d + 1 für alle (t, g) ∈ M. Seien L′ := {Simp(t, g, F̃, F̃^{+}) | (t, g) ∈ M} und L := {t̂ĝ | (t̂, ĝ) ∈ L′} ⊆ P.

a) Für jedes Paar (t̂, ĝ) ∈ L′ ist das Polynom t̂ĝ ∈ L homogen vom Grad d + 1.

b) Ist (F, F̃, F̃^{+}) := FR_{σ,G}(L, F, F̃), so sind alle in F, F̃ und F̃^{+} enthaltenen Polynome homogen vom Grad d + 1.

Beweis: Teil a) folgt wegen deg(tg) = d + 1 direkt aus Satz 3.4.1 a). Bei der Berechnung von FR_{σ,G}(L, F, F̃) gemäß Satz 3.4.5 gilt anfangs F = L. Jedes anschließend in Schritt 6 zu F hinzugefügte Polynom ist von der Form f = t̂ĝ mit (t̂, ĝ) = Simp(\frac{m}{LT_{σ}(g)}, g, F, F̃) für ein Polynom g ∈ G und einen Term m ∈ Supp(F), der von LT_{σ}(g) geteilt wird. Also ist \frac{m}{LT_{σ}(g)} · g homogen vom Grad deg(m) = d + 1

und nach a) gilt dies ebenfalls für f. Wegen Supp(F̃^{+}) ⊆ Supp(F̃) ⊆ Supp(F) sind auch alle Polynome in F̃ und F̃^{+} homogen vom Grad d + 1. □

3.4.9 Korollar (Homogene Version von F_{4}): Seien f_{1}, …, f_{s} ∈ P \ {0} homogene Polynome und I := (f_{1}, …, f_{s}) das von f_{1}, …, f_{s} erzeugte Ideal. Betrachte die folgenden Instruktionen:

1 Setze k := 0, s′ := 0, F := {f_{1}, …, f_{s}}, G := ∅ und B := ∅ 2 Wiederhole die Schritte 3 bis 20, solange B ≠ ∅ oder F ≠ ∅ gilt 3 Setze d := min{min{deg(f) | f ∈ F }, min{deg(kgV(t_{i}, t_{j})) | (i, j) ∈ B}} 4 Setze B_{d} := {(i, j) ∈ B | deg(kgV(t_{i}, t_{j})) = d} und streiche die Elemente

von B_{d} in B 5 Setze F′ := {f ∈ F | deg(f) = d} und streiche die Elemente von F′ in F 6 Wiederhole die Schritte 7 bis 20, solange B_{d} ≠ ∅ oder F′ ≠ ∅ gilt 7 Ist F′ = ∅, so führe die Schritte 8 bis 13 durch,

andernfalls fahre mit Schritt 14 fort

8 Erhöhe k um 1 9 Setze F := (F_{1}, …, F_{k−1}) und F̃ := (F̃_{1}, …, F̃_{k−1}) 10 Setze L′ := {Simp(t_{ij}, g_{i}, F, F̃) | (i, j) ∈ B_{d}} ∪ {Simp(t_{ji}, g_{j}, F, F̃) | (i, j) ∈ B_{d}}

11 Setze L := {tf | (t, f) ∈ L′} und B_{d} := ∅ 12 Berechne (F_{k}, F̃_{k}, F̃_{k}^{+}) := FR_{σ,G}(L, F, F̃) 13 Setze F′ := F̃_{k}^{+} 14 Wiederhole die Schritte 15 bis 18 für jedes Polynom f ∈ F′ 15 Erhöhe s′ um 1 16 Definiere g_{s′} := f 17 Füge g_{s′} zu G hinzu 18 Füge die Paare (1, s′), …, (s′ − 1, s′) zu B hinzu 19 Füge die Paare (i, j) ∈ B mit deg(kgV(t_{i}, t_{j})) = d zu B_{d} hinzu und

streiche sie in B

20 Setze F′ := ∅ 21 Gib G als Ergebnis zurück

Dieser Algorithmus berechnet eine σ-Gröbnerbasis des Ideals I bestehend aus homogenen Polynomen g_{1}, …, g_{s′} mit deg(g_{1}) ≤ … ≤ deg(g_{s′}).

Beweis: Da nur endliche Mengen und Einzeloperationen Verwendung finden, müssen zum Beweis der Endlichkeit lediglich die beiden großen Wiederholungsschleifen (Schritte 2 bis 20 bzw. 6 bis 20) geprüft werden. Für jede der beiden Schleifen kann man die Endlichkeitsargumentation aus dem Beweis zu Theorem 3.3.7 in entsprechender Weise übernehmen. Die Instruktionsabfolge wurde gegenüber derjenigen in Theorem 3.4.7 lediglich um die gradweise Abarbeitung der Startpolynome erweitert und die beliebige Auswahlfunktion Sel wurde ersetzt durch eine bestimmte, nämlich durch die Auswahl aller Paare, die Polynome vom Grad d hervorbringen. Somit bildet G nach wie vor eine Gröbnerbasis und mit Lemma 3.4.8 folgt die Homogenität der Gröbnerbasiselemente g_{1}, …, g_{s′}, die aufgrund der gradweisen Abarbeitung nichtabsteigende Grade besitzen müssen. □

3.4.10 Bemerkung: Sei die Situation von Korollar 3.4.9 gegeben.

a) Sei d_{0} ∈ ℕ. Da im Algorithmus die Grade der berechneten Gröbnerbasiselemente g_{1}, …, g_{s′} nicht abnehmend sind, erhält man eine im Grad d_{0} abgeschnittene σ-Gröbnerbasis des Ideals I, wenn man nach Schritt 3 abbricht und G als Ergebnis zurückgibt, sobald d > d_{0} gilt. Da in diesem Fall die Paare (i, j) ∈ B mit deg(kgV(t_{i}, t_{j})) > d_{0} niemals benötigt werden, kann man auch Schritt 18 wie folgt verkürzen:

18 Füge die Paare (i, s′) mit i = 1, …, s′ − 1 und deg(kgV(t_{i}, t_{s′})) ≤ d_{0} zu B hinzu

b) Auch im Algorithmus F_{4} können die in Kapitel 2 vorgestellten Optimierungen der kritischen Paare verwendet werden. Für die Optimierung nach Gebauer und Möller (vgl. Abschnitt 2.2) ersetze Schritt 18 durch

18 Führe UpdateGM(B) durch

und für die Optimierung mit Paarminimalisierung (vgl. Abschnitt 2.4) ändere die Schritte 1 und 18 wie folgt ab und füge die Schritte 4a bis 4c zwischen den Schritten 4 und 5 sowie die Schritte 19a bis 19c zwischen den Schritten 19 und 20 ein:

1 Setze k := 0, s′ := 0, F := {f_{1}, …, f_{s}}, G := ∅, A := ∅, B := ∅ und B^{∗} := ∅

4a Setze B_{d}^{∗} := {(i, j) ∈ B^{∗} | deg(kgV(t_{i}, t_{j})) = d} und streiche die

Elemente von B_{d}^{∗} in B^{∗} 4b Führe MinPairs(A, B_{d}, B_{d}^{∗}) durch 4c Füge die Elemente von B_{d} zu A hinzu

18 Führe Update(B, B^{∗}, g_{s′}) durch

19a Setze B_{d}^{∗} := {(i, j) ∈ B^{∗} | deg(kgV(t_{i}, t_{j})) = d} und streiche die

Elemente von B_{d}^{∗} in B^{∗} 19b Führe MinPairs(A, B_{d}, B_{d}^{∗}) durch 19c Füge die Elemente von B_{d} zu A hinzu

Hierbei ist jedoch zu beachten, dass trotz der Verwendung der ”Optimierung mit Paarminimalisierung“ nicht zwangsweise auch eine Paarminimalisierung stattfindet, wie dies bei der entsprechend optimierten Version des homogenen Buchberger-Algorithmus (vgl. Theorem 2.4.1) der Fall ist. Der Grund hierfür ist die Möglichkeit einer Erzeugung von Paaren (i, j), so dass deg(kgV(t_{i}, t_{j})) = d gilt, d. h. dass Paare erzeugt werden, die eigentlich im gerade behandelten Grad abgearbeitet werden hätten müssen.

Effizienzvergleiche zwischen verschiedenen Algorithmen und Optimierungen

Nun sollen zum Abschluss noch die in den beiden vorangegangenen Kapiteln vorgestellten Algorithmen bzgl. ihrer Effizienz verglichen werden, um herauszufinden, ob der erhöhte Programmieraufwand in den unterschiedlichen Optimierungen letztendlich wirklich in einer schnelleren Berechnung der Gröbnerbasen resultiert oder nicht und ob einer der Algorithmen besser geeignet (d. h. effizienter) ist als die anderen. Die drei zu vergleichenden Algorithmen sind der Buchberger-Algorithmus (vgl. Theorem 2.3.2) mit normaler Auswahlstrategie, der Buchberger-Algorithmus mit Multireduktion (vgl. Theorem 3.2.3) und der homogene Algorithmus F_{4} (vgl. Theorem 3.4.9). Alle drei Algorithmen sollen in drei Optimierungsstufen getestet werden, die für jeden Algorithmus gleich implementiert werden. Dies sind die jeweils unoptimierte Version des entsprechenden Algorithmus, die Gebauer-Möller-Installation (vgl. Korollar 2.2.3) sowie die Paarminimalisierung (vgl. Theorem 2.4.1). Um die Tabellen in den nächsten Abschnitten übersichtlicher zu halten, sollen dort die verschiedenen Kombinationen von Algorithmus und Optimierung wie folgt abgekürzt werden:

Optimierungsstufe

Algorithmus unoptimiert Gebauer-Möller Paarminimalisierung

Buchberger-Algorithmus  B  BG  BP

Buchberger-Algorithmus mit Multireduktion M MG

MP

F_{4}  F  FG  FP

Um ein neutrales Umfeld für alle Algorithmen zu gewährleisten, wurde eine entsprechende Umgebung in C++ implementiert, die alle notwendigen Voraussetzungen zur Verfügung stellt, aber keinen Algorithmus bevorzugt behandelt, d. h. in den Basisklassen wurden keinerlei Optimierungen verwendet, die einen oder mehrere der Algorithmen begünstigen. Für die Effizienztests wurden einige bekannte Beispiele ausgewählt, die größtenteils aus dem Symbolic-Data-Projekt [SDP] stammen. Die folgende Tabelle stellt alle in den Tests dieses Kapitels verwendeten Beispiele vor:

Beispielname Abk. Unbestimmte homogene Erzeuger

Trivial 1  T1 x, y  {x^{2} \atop xy + y^{2}}

Trivial 2  T2 x_{0}, x_{1}, x_{2}, x_{3}  {x_{0}^{3}x_{1} − x_{3}^{4} \atop x_{0}^{4}x_{2} − x_{3}^{5}}

Neff-89^{1)}  Nef h, x, y, z  {2yz +2y^{2} +xz +x^{2} −3hz −hy −2hx \atop z^{2} −8yz −4y^{2} +4xz +3x^{2} −4hx+h^{2}}

Bronstein-86^{2)} Bro

h, r, x, y, z

xy + z^{2} − h^{2} ; x^{2} + y^{2} + z^{2} − r^{2} ; xyz − hx^{2} − hy^{2} − h^{2}z + h^{3}

Buchberger-87^{3)} Buc

h, r, t, x, y, z

hx − rt ; hz − r^{2} ; h^{2}y − rt^{2}

Czapor-86a^{4)}  Cza h, x, y, z  5x^{2} + 8xy + 9y^{2} + 4xz − 6yz − z^{2} ; + 8hx + 2hy − 7hz + 5h^{2} ; 8x^{2} − 2xy + 3y^{2} − 6xz − 7yz + 10z^{2} ; + 3hx + 10hy − 8hz − 4h^{2} ; 10x^{2} − 2xy + 9y^{2} + 6xz − yz − 2z^{2} ; − 6hx − 4hy + 5hz − 9h^{2}

Katsura 3^{5)}  Ka3 h, u_{0}, u_{1}, u_{2}, u_{3} u_{0} + 2u_{1} + 2u_{2} + 2u_{3} − h ; u_{1}^{2} + 2u_{0}u_{2} + 2u_{1}u_{3} − hu_{2} ; 2u_{0}u_{1} + 2u_{1}u_{2} + 2u_{2}u_{3} − hu_{1} ; u_{0}^{2} + 2u_{1}^{2} + 2u_{2}^{2} + 2u_{3}^{2} − hu_{0}

Gerdt-93^{6)}  Ger h, l, s, x, y, z  hl − l^{2} − 4ls + hy ; h^{2}s − 6ls^{2} + h^{2}z ; xh^{2} − l^{2}s − h^{3}

Sym3 3^{7)}  S33 h, x, y, z  yz^{3} + h^{3}x − 2h^{4} ; x^{3}z + h^{3}y − 2h^{4} ; xy^{3} + h^{3}z − 2h^{4}

Liu^{8)}  Liu a, h, t, x, y, z  yz − ty − hx + ah ; tz − xz − hy + ah ; tx − ty − hz + ah ; xy − xz − ht + ah

Sym1 411^{9)}  S14 h, x, y, z  z^{4} + h^{3}x + h^{3}y − 3h^{4} ; y^{4} + h^{3}x + h^{3}z − 3h^{4} ; x^{4} + h^{3}y + h^{3}z − 3h^{4}

1)Quelle: http://www.SymbolicData.org/SD HTML/Data/INTPS/Homog/Neff-89.html 2)Quelle: http://www.SymbolicData.org/SD HTML/Data/INTPS/Homog/Bronstein-86.html 3)Quelle: http://www.SymbolicData.org/SD HTML/Data/INTPS/Homog/Buchberger-87.html 4)Quelle: http://www.SymbolicData.org/SD HTML/Data/INTPS/Homog/Czapor-86a.html 5)Quelle: http://www.SymbolicData.org/SD HTML/Data/INTPS/Homog/Katsura 3.html 6)Quelle: http://www.SymbolicData.org/SD HTML/Data/INTPS/Homog/Gerdt-93.html 7)Quelle: http://www.SymbolicData.org/SD HTML/Data/INTPS/Homog/Sym3 3.html 8)Quelle: http://posso.lip6.fr/~jcf/Benchs/@benchs/liu.fgb 9)Quelle: http://www.SymbolicData.org/SD HTML/Data/INTPS/Homog/Sym1 411.html

Beispielname Abk. Unbestimmte homogene Erzeuger

Sym3 4^{10)}  S34 h, x, y, z  yz^{4} + h^{4}x − 2h^{5} ; x^{4}z + h^{4}y − 2h^{5} ; xy^{4} + h^{4}z − 2h^{5}

Cyclic 5^{11)}  Cyc h, v, w, x, y, z  v + w + x + y + z ; vw + wx + xy + vz + yz ; vwx + wxy + vwz + vyz + xyz ; vwxy + vwxz + vwyz + vxyz + wxyz ; vwxyz − h^{5}

Noonburg-89^{12)} Noo

c, h, x, y, z

x^{2}z + y^{2}z − chz + h^{3} ; xy^{2} + xz^{2} − chx + h^{3} ; x^{2}y + yz^{2} − chy + h^{3}

Katsura 4^{13)}  Ka4 {h, u_{0}, u_{1}, u_{2}, u_{3}, \atop u_{4}} u_{0} + 2u_{1} + 2u_{2} + 2u_{3} + 2u_{4} − h ; 2u_{1}u_{2} + 2u_{0}u_{3} + 2u_{1}u_{4} − hu_{3} ; u_{1}^{2} + 2u_{0}u_{2} + 2u_{1}u_{3} + 2u_{2}u_{4} − hu_{2} ; 2u_{0}u_{1} +2u_{1}u_{2} +2u_{2}u_{3} +2u_{3}u_{4} −hu_{1} ; u_{0}^{2} + 2u_{1}^{2} + 2u_{2}^{2} + 2u_{3}^{2} + 2u_{4}^{2} − hu_{0}

Wang-89^{14)}  Wan h, w, x, y, z  wz − wx + hy ; yz − 2x^{2} − wx − h^{2} ; wz^{2} −wxz +hz^{2} −hxz +hwx+3h^{2}x

Pavelle^{15)}  Pav {a, b, c, d, h, t, x, \atop y, z} tx + ty + tz − dh ; xz + yz + tz − ch ; xy + yz + ty − bh ; xy + xz + tx − ah

Trinks^{16)}  Tri b, h, p, t, s, w, z 35p − 27s + 25t + 40z ; 45p + 35s − 165b − 36h ; 3b^{2} − 11bs + 99hw ; 25ps − 165b^{2} + 15hw + 30hz − 18ht ; 15pt + 20sz − 9hw ; hpw + 2htz − 11b^{3}

Vermeer 2^{17)}  Ver h, t, u, x, y, z  t^{2} + x^{2} − 2ty + y^{2} − 2xz + z^{2} − h^{2} ; ht^{2} − z^{3} ; 3uz^{2} − h^{3} ; 2h^{2}tx − 3tz^{3} + 3yz^{3} − 2h^{2}tz

Uteshev Bikker^{18)}

UB h, t, x, y, z

t^{2} + x^{2} − 2ty + y^{2} − 2xz + z^{2} − h^{2} ; ht^{2} − z^{3} ; 3uz^{2} − h^{3} ; 2h^{2}tx − 3tz^{3} + 3yz^{3} − 2h^{2}tz

10)Quelle: http://www.SymbolicData.org/SD HTML/Data/INTPS/Homog/Sym3 4.html 11)Quelle: http://www.SymbolicData.org/SD HTML/Data/INTPS/Homog/Cyclic 5.html 12)Quelle: http://www.SymbolicData.org/SD HTML/Data/INTPS/Homog/Noonburg-89.html 13)Quelle: http://www.SymbolicData.org/SD HTML/Data/INTPS/Homog/Katsura 4.html 14)Quelle: http://www.SymbolicData.org/SD HTML/Data/INTPS/Homog/Wang-89.html 15)Quelle: http://www.SymbolicData.org/SD HTML/Data/INTPS/Homog/Pavelle.html 16)Quelle: http://www.SymbolicData.org/SD HTML/Data/INTPS/Homog/Trinks.html 17)Quelle: http://www.SymbolicData.org/SD HTML/Data/INTPS/Homog/Vermeer 2.html 18)Quelle: http://posso.lip6.fr/~jcf/Benchs/@benchs/Uteshev Bikker.fgb

Beispielname Abk. Unbestimmte homogene Erzeuger

Weispfen- ning-94^{19)}

Wei h, x, y, z

y^{4}+xy^{2}z+h^{2}x^{2}−2h^{2}xy+h^{2}y^{2}+h^{2}z^{2} ; xy^{4} + yz^{4} − 2h^{2}x^{2}y − 3h^{5} ; hy^{4} − x^{3}y^{2} + xyz^{3} + hxy^{2}z − 2h^{3}xy

Lichtblau^{20)} Lic

h, t, x, y

h^{10}x − 110h^{9}t^{2} + 495h^{8}t^{3} − 1320h^{7}t^{4} ; + 2772h^{6}t^{5} − 5082h^{5}t^{6} + 7590h^{4}t^{7} ; − 8085h^{3}t^{8} + 5555h^{2}t^{9} − 2189ht^{10} ; + 374t^{11} ; h^{10}y − 22h^{10}t + 110h^{9}t^{2} − 330h^{8}t^{3} ; + 1848h^{6}t^{5} − 3696h^{5}t^{6} + 3300h^{4}t^{7} ; − 1650h^{3}t^{8}+550h^{2}t^{9}−88ht^{10}−22t^{11}

Um alle Beispiele unter möglichst identischen Bedingungen testen zu können, wurden stets die Termordnung DegRevLex sowie derselbe endliche Grundkörper ℤ/(p) mit der zufällig gewählten Primzahl p = 7583 verwendet.

4.1 Lohnen sich Optimierungen?

Zunächst soll untersucht werden, ob sich der Mehraufwand für die vorgestellten Optimierungen der Paarmenge (Gebauer-Möller und Paarminimalisierung) lohnt, d. h. ob die Berechnung der Gröbnerbasis dann wirklich schneller erfolgt. Hierfür genügt es bereits, zwei sehr einfache Beispiele anzuführen:

Algorithmus

Test Indikator  B BG BP M MG MP F FG FP
abgearbeitete Paare 3 2 2 3  2  2  6 3 3
T1 höchster Grad  5 4 4 5  4  4  5 4 4
abgearbeitete Paare 15 8 8 15  8  8 28 8 8
T2 höchster Grad  16 12 12 16 12 12 20 12 12
Dauer [\frac{1}{100} s]  11 0 6 0  0  0 116 5 11

Man sieht deutlich an der Anzahl der mit Optimierung ”eingesparten“ Paare sowie am maximalen Grad der verwendeten Paare (d. h. derer S-Polynome), dass bereits bei sehr einfachen Gröbnerbasisberechnungen (die Berechnungsdauer bei T1 liegt sogar immer unterhalb der Messgenauigkeit) eine Paaroptimierung sinnvoll ist. Besonders effektiv tritt dies beim Algorithmus F_{4} zutage, da bei diesem grundsätzlich wesentlich mehr Gröbnerbasiselemente und somit auch Paare auftreten. Aus der wesentlich längeren Berechnungsdauer von T2 in der unoptimierten Version von F_{4} lässt sich auch bereits erahnen, dass F_{4} ohne Optimierung bei nichttrivialen Berechnungen wegen der hohen Anzahl der erzeugten Paare keinerlei Sinn macht. Man kann also festhalten, dass beide Optimierungen bei allen drei Algorithmen die Effizienz gegenüber der jeweiligen unoptimierten Version steigern, da selbst bei trivialen Berechnungen fast immer Paare gestrichen und dadurch genauso viele Reduktionen vermieden werden können, die einen Großteil der Berechnungsdauer in Anspruch nehmen. Aus diesem Grund werden in den nachfolgenden Abschnitten nur noch die optimierten Algorithmen betrachtet.

19)Quelle: http://www.SymbolicData.org/SD HTML/Data/INTPS/Homog/Weispfenning-94.html 20)Quelle: http://posso.lip6.fr/~jcf/Benchs/@benchs/lichtblau.fgb

4.2 Ist F_{4} konkurrenzfähig?

Während sich die Vorgehensweisen beim Buchberger-Algorithmus ohne sowie mit Multireduktion sehr ähnlich sind, wird bei F_{4} ein anderer Weg eingeschlagen: Da bei der F-Reduktion keine S-Polynome verwendet werden, entstehen mehr Gröbnerbasiselemente, die jedoch in der Regel weniger Terme beinhalten. Dies bringt jedoch wiederum eine höhere Anzahl an kritischen Paaren mit sich, die abgearbeitet oder zumindest im Laufe einer Optimierung untersucht und gestrichen werden müssen. Die Frage nach der Rentabilität dieser Strategie soll anhand folgender Testergebnisse untersucht werden:

Algorithmus

Test Indikator  BG BP MG MP FG FP
Gröbnerbasiselemente  3 3  3  3  11  11
kritische Paare  3 3  3  3  55  55
Nef abgearbeitete Paare  2 2  2  2  10  10
Dauer [\frac{1}{100} s]  5 0  0  5  44  50
Gröbnerbasiselemente  4 4  4  4  21  21
kritische Paare  6 6  6  6 210 210
Bro abgearbeitete Paare  5 5  5  5  22  22
Dauer [\frac{1}{100} s]  6 0  5  0 121 115
Gröbnerbasiselemente  8 8  8  8  14  14
kritische Paare  28 28 28 28  91  91
Buc abgearbeitete Paare  14 14 14 14  20  20
Dauer [\frac{1}{100} s]  11 11  5  5  55  44
Gröbnerbasiselemente  6 6  8  8  29  29
kritische Paare  15 15 28 28 406 406
Cza abgearbeitete Paare  8 8 10 10  31  31
Dauer [\frac{1}{100} s]  21 22 28 27 286 292
Gröbnerbasiselemente  8 8  8  8  58  58
kritische Paare  28 28 28 28 1653 1653
Ka3 abgearbeitete Paare  17 17 17 17  67  67
Dauer [\frac{1}{100} s]  22 22 22 22 1450 1461
Gröbnerbasiselemente  9 9  9  9  61  61
kritische Paare  36 36 36 36 1830 1830
Ger abgearbeitete Paare  15 15 15 15  67  67
Dauer [\frac{1}{100} s]  100 99 55 50 3938 3987
Gröbnerbasiselemente 10 10 12 12  70  70
kritische Paare  45 45 66 66 2415 2415
S33 abgearbeitete Paare  15 15 17 17  75  75
Dauer [\frac{1}{100} s]  44 44 38 39 4201 4295

Algorithmus

Test Indikator  BG BP MG MP FG FP
Gröbnerbasiselemente 12 12 15 15  69  69
kritische Paare  66 66 105 105 2346 2346
Liu abgearbeitete Paare  26 26 29 29  83  83
Dauer [\frac{1}{100} s]  94 93 82 83 3851 3910
Gröbnerbasiselemente 11 11 13 13  81  79
kritische Paare  55 55 78 78 3240 3081
S14 abgearbeitete Paare  17 16 19 18  87  84
Dauer [\frac{1}{100} s]  127 121 126 132 9898 9282

Wie man bei allen Testbeispielen deutlich erkennen kann, ist bei beiden Optimierungen die Anzahl der kritischen Paare bei F_{4} immer wesentlich höher als bei den anderen beiden Algorithmen. Dadurch entstehen zweierlei Effizienzverluste: Zuerst müssen all diese Paare im Zuge der Paaroptimierung untersucht werden. Hierbei wird zwar ein großer Anteil an Paaren eliminiert, jedoch bleiben immer noch wesentlich mehr Paare übrig als bei den anderen Algorithmen. Diese restlichen Paare müssen wiederum reduziert werden, was in der Regel einen noch erheblicheren Zeitverlust darstellt. Letzterer legt sich auch klar erkennbar in den Berechnungszeiten nieder. Zusammenfassend kann man sagen, dass der Algorithmus F_{4} – zumindest in der hier in Theorem 3.4.9 vorgestellten homogenen Version – zur Berechnung von Gröbnerbasen aus Effizienzgründen ungeeignet ist. Der Buchberger-Algorithmus mit normaler oder Multireduktion sollte in jedem Fall bevorzugt werden.

4.3 Normale Reduktion oder Multireduktion? Was bringt die Paarminimalisierung?

Unter Berücksichtigung der vorhergehenden Abschnitte bleiben lediglich vier Algorithmus-Optimierungs-Kombinationen zur Untersuchung übrig: Der Buchberger-Algorithmus mit normaler bzw. Multireduktion zusammen mit der Gebauer-Möller-Installation oder der Paarminimalisierung. Diese vier Kombinationen sind von Entstehung und Funktionalität her relativ ähnlich. Um ihre Effizienz zu vergleichen, sollen noch weitere Testbeispiele hinzugezogen werden:

Algorithmus

Test Indikator  BG BP MG MP
Gröbnerbasiselemente 10 10 12 12
kritische Paare  45 45 66 66
Paare in B  15 16 17 17
S34 abgearbeitete Paare  15 15 17 17
Reduktionsschritte  228 228 185 185
Dauer [\frac{1}{100} s]  76 72 50 49

KAPITEL 4. EFFIZIENZVERGLEICHE 46

Algorithmus

Test Indikator  BG BP MG MP
Gröbnerbasiselemente 11 11 13 13
kritische Paare  55 55 78 78
Paare in B  17 18 19 19
S14 abgearbeitete Paare  17 16 19 18
Reduktionsschritte  213 202 252 250
Dauer [\frac{1}{100} s]  127 121 126 132
Gröbnerbasiselemente 12 12 12 12
kritische Paare  66 66 66 66
Paare in B  38 38 38 38
Cyc abgearbeitete Paare  38 38 38 38
Reduktionsschritte  228 228 200 200
Dauer [\frac{1}{100} s]  165 159 83 94
Gröbnerbasiselemente 15 15 17 17
kritische Paare  105 105 136 136
Paare in B  33 37 35 36
Noo abgearbeitete Paare  33 33 35 35
Reduktionsschritte  366 366 363 363
Dauer [\frac{1}{100} s]  203 203 127 132
Gröbnerbasiselemente 13 13 13 13
kritische Paare  78 78 78 78
Paare in B  38 38 38 38
Ka4 abgearbeitete Paare  38 38 38 38
Reduktionsschritte  598 598 820 820
Dauer [\frac{1}{100} s]  198 208 165 165
Gröbnerbasiselemente 10 10 10 10
kritische Paare  45 45 45 45
Paare in B  22 22 22 22
Wan abgearbeitete Paare  22 22 22 22
Reduktionsschritte  589 589 634 634
Dauer [\frac{1}{100} s]  225 220 109 104
Gröbnerbasiselemente 15 15 15 15
kritische Paare  105 105 105 105
Paare in B  35 36 35 35
Pav abgearbeitete Paare  35 35 35 35
Reduktionsschritte  376 376 365 365
Dauer [\frac{1}{100} s]  962 862 159 164

Algorithmus

Test Indikator  BG BP MG MP
Gröbnerbasiselemente  15  15  15  15
kritische Paare  105 105 105 105
Paare in B  58  58  58  58
Tri abgearbeitete Paare  58  58  58  58
Reduktionsschritte  786 786 818 818
Dauer [\frac{1}{100} s]  544 544 236 236
Gröbnerbasiselemente  26  26  26  26
kritische Paare  325 325 325 325
Paare in B  80  81  80  80
Ver abgearbeitete Paare  80  80  80  80
Reduktionsschritte  625 625 613 613
Dauer [\frac{1}{100} s]  934 933 478 484
Gröbnerbasiselemente  17  17  18  18
kritische Paare  136 136 153 153
Paare in B  40  40  41  41
UB abgearbeitete Paare  40  40  41  41
Reduktionsschritte  1406 1406 1401 1401
Dauer [\frac{1}{100} s]  813 851 714 725
Gröbnerbasiselemente  20  20  20  20
kritische Paare  190 190 190 190
Paare in B  40  41  40  40
Wei abgearbeitete Paare  40  40  40  40
Reduktionsschritte  1093 1093 1008 1008
Dauer [\frac{1}{100} s]  945 978 786 797
Gröbnerbasiselemente  12  12  12  12
kritische Paare  66  66  66  66
Paare in B  11  11  11  11
Lic abgearbeitete Paare  11  11  11  11
Reduktionsschritte  2331 2331 2412 2412
Dauer [\frac{1}{100} s]  3625 3483 2110 2121

Vergleicht man die Spalten für den normalen Buchberger-Algorithmus (BG und BP) mit denjenigen des Buchberger-Algorithmus mit Multireduktion (MG und MP), so fällt sofort auf, dass die Berechnungsdauern bei letzterem meist deutlich geringer ausfallen. Bei näherer Betrachtung stellt man jedoch fest, dass dafür die Zahlen der Gröbnerbasiselemente und somit auch der Paare gelegentlich (S34, S14, Noo, UB) etwas höher sind, was daher rührt, dass die Optimierung hier nicht sofort nach jedem einzelnen neuen Gröbnerbasiselement erfolgen kann, da der gesamte Grad zugleich abgearbeitet wird und erst nachher die neuen Gröbnerbasiselemente feststehen, so dass Paare, die im anderen Fall eliminiert würden, bereits abgearbeitet sind. Allerdings wird diese eventuell höhere Anzahl an Paaren durch die Organisation der Multireduktion mehr als kompensiert, so dass die effektiv erfolgenden Reduktionsschritte nicht so rechenintensiv sind (d. h. die Polynome haben weniger Terme), auch wenn mehr Reduktionsschritte erfolgen wie beim normalen Buchberger-Algorithmus, was aber – wie man sieht – auch nicht immer der Fall sein muss. Ein weiterer Grund für diese Effizienzsteigerung ist auch die Einsparung der Suchvorgänge nach Gröbnerbasiselementen mit geeignetem Leitterm im Zuge der Reduktion, da nicht für jeden einzelnen Reduktionsschritt nach einem passenden Polynom gesucht werden muss, sondern umgekehrt dieses Polynom bereits festgelegt ist und mit diesem mehrere Reduktionsschritte nacheinander vollzogen werden. Will man also die Rechenzeit gering halten und nimmt minimal längere Gröbnerbasen in Kauf, so ist auf jeden Fall zur Multireduktion zu raten.

Untersucht man nun die Vor- und Nachteile der Paarminimalisierung gegenüber der Gebauer-Möller-Installation bei beiden Algorithmen, so stellt man fest, dass die Berechnungszeiten machmal ein wenig besser und manchmal ein wenig schlechter, aber doch immer relativ ähnlich ausfallen. Bei etlichen Beispielen (S34, Noo, Pav, Ver, Wei) fällt anhand der ”Paare in B“ auf, dass zwar der gegenüber der Gebauer-Möller-Installation abgeänderte Schritt in der Funktion Update in Effekt tritt, dies aber nicht wirklich eine Verkleinerung der Paarmenge verursacht. Hierbei ist interessant zu beobachten, dass dies in vier der genannten fünf Fälle nur beim normalen Buchberger-Algorithmus, nicht aber mit Multireduktion auftritt; im fünften Fall (Noo) sinkt die Anzahl der betroffenen Paare ebenfalls (von vier auf eins). Das einzige der aufgeführten Testbeispiele, bei dem gegenüber Gebauer-Möller wirklich ein Paar und damit auch einige Reduktionsschritte eingespart werden können, ist S14. Zusammenfassend kann man sagen, dass die Verwendung der Paarminimalisierung zu empfehlen ist, da sie keine wesentlichen Effizienzverluste gegenüber der Gebauer-Möller-Installation aufweist. Plant man nur einfache Berechnungen, so ist sie zwar nicht unbedingt notwendig, da hier eine ”Paarminimalisierung“ häufig auch schon mit Gebauer-Möller erreicht wird. Bei komplexeren Gröbnerbasisberechnungen jedoch ist dies häufig nicht mehr gegeben, da mit einer höheren Anzahl an Paaren auch die Chance auf Paare steigt, die von UpdateGM nicht gestrichen werden, deren Syzygien aber nicht dem minimalen Erzeugendensystem angehören (vgl. dazu die Tests in [CaKrRo]).

Bezeichnungen

Die folgene Liste stellt ein Verzeichnis der wichtistgen verwendeten Funktions-, Mengen- und sonstigen Bezeichner dar. Die angegebene Seitenzahl verweist auf die jeweilige Definition.

Symbol  Beschreibung  Seite
𝔹  Menge der kritischen Paare im Buchberger-Algorithmus  10
c_{i}  Leitkoeffizient von g_{i}  10
Card  Anzahl der Elemente einer Menge (Kardinalzahl)  –
deg  Grad von homogenen Elementen  9
deg  Grad von Polynomen oder Termen  5
deg_{σ,G}  σ-Grad  10
DegLex  graduiert-lexikographische Termordnung  6

DegRevLex graduiert-umgekehrt-lexikographische Termordnung 6

FR_{σ,G}  F-Reduktion einer Polynommenge bzgl. einer Menge G  33
HF_{P}  Hilbert-Funktion des Polynomrings  26
LC_{σ}  Leitkoeffizient eines Polynoms bzgl. der Termordnung σ  7
Lex  lexikographische Termordnung  6
LF  Abbildung, die LF_{σ,G} ergänzt  11
LF_{σ,G}  σ-Leitform  10
LM_{σ}  LM_{σ}(f) = LC_{σ}(f) · LT_{σ}(f) für ein Polynom f  7
log  Logarithmus, log: 𝕋^{n} ⟶ ℕ^{n}, x_{1}^{a_{1}} … x_{n}^{a_{n}} ⟼ (a_{1}, …, a_{n})  5
LT_{σ}  Leitterm eines Polynoms bzgl. der Termordnung σ  7
Mat_{m,n}  Menge der (m × n)-Matrizen über einem Körper  –

max_{σ} Maximum einer Menge von Termen bzgl. der Termordnung σ 6 min_{σ} Minimum einer Menge von Termen bzgl. der Termordnung σ 6 MinPairs Paaroptimierung beim Buchb.-Alg. mit Paarminimalisierung 22

MR_{σ,G}  Multireduktion eines Polynomtupels bzgl. eines Tupels G  29
ℕ  Menge der natürlichen Zahlen, ℕ = {0, 1, 2, …}  –
ℕ_{+}  Menge der positiven natürlichen Zahlen, ℕ_{+} = {1, 2, 3, …}  –

NF_{σ}, NF_{σ,I} Normalform eines Polynoms bzgl. eines Ideals I 13

NR_{σ,G}  normaler Rest eines Polynoms bzgl. eines Tupels G  8
pr_{k}  Projektion auf die k-te Komponente  –

ψ_{L} Funktion zur Umwandlung von Polynomen in Zeilenvektoren 25 Ψ_{L,r} Funktion zur Umwandlung von Polynommengen in Matrizen 25

Rang  Rang einer Matrix  –
S_{ij}  S-Polynom von g_{i} und g_{j}  10
σ_{ij}  zum Paar (i, j) gehörige Syzygie  10
Sel  Auswahlfunktion im Algorithmus F_{4}  34
Simp  Vereinfachungsfunktion beim (optimierten) Algorithmus F_{4}  35
Supp  Träger von Polynomen  5
Syz  Syzygienmodul  10

t_{i}  Leitterm von g_{i}  10
t_{ij}  t_{ij} := \frac{kgV(t_{i},t_{j})}{t_{i}}  10
𝕋^{n}  Menge der Terme in n Unbekannten  5
𝕋_{d}^{n}  Menge der Terme in n Unbekannten mit Grad d  25

T_{d}^{n}, T_{σ,d}^{n} zu 𝕋_{d}^{n} gehöriges Tupel von absteigend angeordneten Termen 26 Update Paaraktualisierung beim Buchb.-Alg. mit Paarminimalisierung 22 UpdateGM Paaraktualisierung bei der Gebauer-Möller-Installation 19

ℤ  Menge der ganzen Zahlen, ℤ = {…, −2, −1, 0, 1, 2, …}  –

Literaturverzeichnis

[BeWe] T. Becker, V. Weispfenning Gröbner Bases Springer, Berlin, 1993

[Bu 1] B. Buchberger Ein Algorithmus zum Auffinden der Basiselemente des Restklassenrings nach einem nulldimensionalen Polynomideal Dissertation, Universität Innsbruck, 1965

[Bu 2] B. Buchberger Groebner Bases: An Algorithmic Method in Polynomial Ideal Theory in: N. K. Bose (Hrsg.), Multidimensional Systems Theory, S. 184-232 Reidel, Dordrecht, 1985

[CaKrRo] M. Caboara, M. Kreuzer, L. Robbiano Minimal Sets of Critical Pairs in: Journal of Symbolic Computation Academic Press, London, erscheint demnächst

[Fa] J.-C. Faugére A New Efficient Algorithm for Computing Gröbner Bases (F4) in: Journal of Pure and Applied Algebra, Bd. 139, Nr. 1-3, S. 61-88 North-Holland, Amsterdam, 1999

[GeMö] R. Gebauer, H. M. Möller On an Installation of Buchberger’s Algorithm in: Journal of Symbolic Computation, Bd. 6, Nr. 2-3, S. 257-286 Academic Press, London, 1988

[KrRo 1] M. Kreuzer, L. Robbiano Computational Commutative Algebra 1 Springer, Heidelberg, 2000

[KrRo 2] M. Kreuzer, L. Robbiano Computational Commutative Algebra 2 Springer, Heidelberg, in Vorbereitung

[SDP] The SymbolicData Project

http://www.SymbolicData.org/

2000–2002

Stichwortverzeichnis

Auswahlstrategie normale, 16

Buchberger-Algorithmus, 16 im homogenen Fall, 20 mit Gebauer-Möller, 18 mit Multireduktion, 29 mit Paarminimalisierung, 22

Buchberger-Kriterium, 15

deg, 5, 9, 10 DegLex, 6 DegRevLex, 6 Divisionsalgorithmus, 8

Ersetzungsregel, 8

F_{4}, 34 homogen, 38 verbessert, 37

FR, 33, 37 F-Reduktion, 33

erweiterte, 37

Gebauer-Möller-Installation, 18 Gröbnerbasis, 12, 15

abgeschnittene, 20 reduzierte, 12, 32

Grad σ-Grad, 10 von homogenen Elementen, 9 von homogenen Polynomen, 9 von Polynomen, 5 von Termen, 5

gradkompatibel, 6, 20 Graduierung, 8, 10

HF, 26 Hilbert-Funktion, 26 homogen, 9

Ideal homogenes, 9 monomiales, 7

Idealmitgliedschaftstest, 13 Interreduktion, 32 interreduziertes Tupel, 32 irreduzibel, 8

Komponente homogene, 9

LC, 7 Leitform, 10 Leitkoeffizient, 7 Leitterm, 7 Leittermideal, 7 Lex, 6 LF, 10, 11 Liftung, 11, 15, 17 LM, 7 log, 5 Logarithmus, 5 LT, 7

max, 6 Maximum, 6 min, 6 Minimum, 6 Modul

graduierter, 9 Monoideal, 7 Monom, 5 MR, 29 Multireduktion, 29

NF, 13 Normalform, 13 normiert, 7 NR, 8

Polynom homogenes, 9 normiertes, 7

Reduktionsschritt, 8 reduzieren, 8 Rest

normaler, 8 Ring

graduierter, 9 Sel, 34, 37 Simp, 35 S-Polynom, 11 Standardgraduierung, 9 Supp, 5 Syz, 10 Syzygie, 10 Syzygienmodul, 10

Term, 5 Termordnung, 6

graduiert-lexikographische, 6 graduiert-umgekehrt-lexikogr., 6 lexikographische, 6

Träger, 5 t-Repräsentation, 12

Untermodul graduierter, 9

Zeilenstufenform, 31

Erklärung

Hiermit erkläre ich, dass ich die vorliegende Diplomarbeit ”Optimierung des Buchberger-Algorithmus im homogenen Fall“ eigenständig verfasst und keine anderen als die angegebenen Quellen und Hilfsmittel verwendet habe.

Regensburg, den 16. Juli 2002 \overline{Jens Schmidbauer}