Effiziente Berechnung von Gröbnerbasen

Martin Kreuzer Fachbereich Mathematik Universität Dortmund

Situation.

P = K[x_{1}, …, x_{n}] Polynomring über einem Körper K P sei graduiert durch eine Matrix W ∈ Mat_{m,n}(ℤ) in deren Spalten die Multigrade von x_{1}, …, x_{n} stehen. Die Graduierung sei positiv, d.h. der oberste von Null verschiedene Eintrag in jeder Spalte ist positiv. Beispiel. W = (1, …, 1) definiert die Standardgraduierung. F = ⨁_{i=1}^{r} P (−δ_{i}) sei ein graduiert-freier P -Modul, d.h. ein freier P -Modul dessen i-tes Basiselement e_{i} den Multigrad δ_{i} ∈ ℤ^{m} besitzt. M ⊆ F sei ein graduierter Untermodul, gegeben durch ein Erzeugendensystem V = (v_{1}, …, v_{s}) bestehend aus homogenen Vektoren von Polynomen. Beispiel. Ist F = P, so ist M ein homogenes Ideal in P. σ sei eine Modultermordnung auf 𝕋(e_{1}, …, e_{r}).

Ziele. Berechne eine σ-Gröbner Basis von M möglichst effizient. Ggf. berechne auch den Syzygienmodul von V. Dabei gilt

Syz(V) = {(f_{1}, …, f_{s}) | f_{1}v_{1} + ⋯ + f_{s}v_{s} = 0}

Notation. Wenn ein Vektor g_{i} ∈ F vorkommt, schreibe

LM_{σ}(g_{i}) = c_{i} t_{i} e_{γ_{i}}

mit c_{i} ∈ K Leitkoeffizient, t_{i} Potenzprodukt, 1 ≤ γ_{i} ≤ r. (i, j) mit i < j und γ_{i} = γ_{j} heisst kritisches Paar. Setze t_{ij} = \frac{kgV(t_{i},t_{j})}{t_{i}} für alle i, j. σ_{ij} = \frac{1}{c_{i}} t_{ij} e_{i} − \frac{1}{c_{j}} t_{ji} e_{j} heisst fundamentale Syzygie. S_{ij} = \frac{1}{c_{i}} t_{ij} g_{i} − \frac{1}{c_{j}} t_{ji} g_{j} heisst S-Vektor. Σ sei die Menge aller fundamentalen Syzygien.

Der Multihomogene Buchberger Algorithmus 1) Sei B = ∅, W = V, G = ∅ und s′ = 0.

2) Sei d der Lex-kleinste Multigrad in B oder in W. Bilde B_{d} = {(i, j) ∈ B | deg_{W} (σ_{ij}) = d} und W_{d} und streiche ihre Elemente in B bzw. W.

3) Ist B_{d} = ∅, so fahre mit 6) fort. Andernfalls wähle (i, j) ∈ B_{d} und steiche es in B_{d}.

4) Berechne den normalen Rest S′_{ij} = NR_{σ,G}(S_{ij}) des S-Vektors. Ist S′_{ij} = 0, so fahre mit 3) fort.

5) Erhöhe s′ um eins, füge g_{s′} = S′_{ij} zu G hinzu und füge {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}} zu B hinzu. Fahre mit 3) fort.

6) Ist W_{d} = ∅, so fahre mit 9) fort. Andernfalls wähle v ∈ W_{d} und streiche es in W_{d}.

7) Finde v′ = NR_{σ,G}(v). Ist v′ = 0, so fahre mit 6) fort.

8) Erhöhe s′ um eins, füge g_{s′} = v′ zu G hinzu und füge {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}} zu B hinzu. Fahre mit 6) fort.

9) Ist B = ∅ und W = ∅, so gib G aus und stoppe. Andernfalls fahre mit 2) fort. Dies ist ein Algorithmus, der ein multihomogenes, gradaufsteigendes Tupel G = (g_{1}, …, g_{s′}) berechnet welches eine σ-Gröbner Basis von M darstellt.

Optimierungen.

1) Es genügt in 3) – 5) eine Menge von kritischen Paaren (i, j) abzuarbeiten für die die zugehörigen fundamentalen Syzygien σ_{ij} den Modul S = Syz(LM_{σ}(g_{1}), …, LM_{σ}(g_{s′})) erzeugen.

2) Von manchen Paaren kann man vielleicht von vorneherein wissen, dass sich NR_{σ,G}(S_{ij}) = 0 ergibt. (Z.B. triviale Syzygien im Fall r = 1.)

3) Verwende einen anderen Algorithmus, um die Gröbner Basis zu berechnen!

Probleme.

1) Es ist keine einfache Art bekannt, wie man eine Teilmenge von Σ findet die S minimal erzeugt.

Die Regeln von Buchberger und Gebauer-Möller zur Entdeckung nicht-minimaler fundamentaler Syzygien liefern im Allgemeinen nur ein fast minimales Erzeugendensystem.

2) Welche Paare man als überflüssig betrachtet hängt stark vom Kontext der Berechnung ab (siehe unten). Über 1) hinausgehende allgemein anwendbare Regeln sind unbekannt.

3) Nur für spezielle Arten von Gröbner-Basis-Berech-nungen sind effiziente Algorithmen bekannt.

Beispiel 1. In P = ℚ[x, y, z] betrachte f_{1} = x^{2}−y^{2} und f_{2} = y^{2} − xz − z^{2}. Verwende die Termordnung σ = DegRevLex. Wegen LT_{σ}(f_{1}) = x^{2} und LT_{σ}(f_{2}) = y^{2} und ggT(x^{2}, y^{2}) = 1 ist das Paar (1, 2) überflüssig (triviale Syzygie).

Beispiel 2. Sei P = ℚ[x, y, z] standard graduiert und sei F = P ⊕ P (−2). In F betrachte v_{1} = (x^{2} − y^{2}, 0) und v_{2} = (y^{2} − xz − z^{2}, 1). Verwende die Modultermordnung

σ = DegRevLexPos.

Dann gilt LT_{σ}(v_{1}) = x^{2}e_{1} und LT_{σ}(v_{2}) = y^{2}e_{1}, aber das kritische Paar (1, 2) ist nicht überflüssig, denn es liefert das neue Gröbner-Basiselement

y^{2}v_{1} −x^{2}v_{2} = (−y^{4} +x^{3}z +x^{2}z^{2}, −x^{2}) ⟶^{v_{1},v_{2}} (0, −x^{2} +y^{2})

In Fall von Idealen überflüssige Paare können im Fall von Moduln unverzichtbar sein!

Beispiel 3. Sei P = ℚ[x, y, z] standard graduiert. Betrachte die Polynome f_{1} = x^{2} − y^{2} − z^{2} und f_{2} = xy − xz + z^{2}. Verwende die Termordnung σ = Lex.

Wegen LT_{σ}(f_{1}) = x^{2} und LT_{σ}(f_{2}) = xy liefert das Paar (1, 2) ein neues Gröbner-Basiselement f_{3} = xz^{2} + y^{3} − y^{2}z + yz^{2} − z^{3} und neue Paare (1, 3) sowie (2, 3). Die Berechnung geht wie folgt weiter:

Grad 1 2 3 4
3 −y x  ⟶ f_{3}
4 −z^{2}  x  ⟶ 0 fundamentale Syzygie
4  −z^{2} y  ⟶ f_{4}
5  −y^{3}  x ⟶ 0  total überflüssig
6 −y^{4}  x^{2} Regel 1
7 −y^{4} xz^{2} Regel 1

mit f_{4} = y^{4} − 2y^{3}z + 2y^{2}z^{2} − 2yz^{3}.

Die in Grad 4 berechnete Syzygie ist die fundamentale Syzygie (−f_{2}, f_{1}) von (f_{1}, f_{2}). Sie ist überflüssig für die Berechnung der Gröbner-Basis aber wesentlich für die Berechnung des Syzygienmoduls. Die in Grad 5 berechnete Syzygie ist in jeder Hinsicht überflüssig.

Für die Berechnung der Gröbner-Basis überflüssige Paare können für die Syzygienberechnung unverzichtbar sein!

Die Regeln von Gebauer-Möller

Regel 1. Streiche in Σ alle Elemente σ_{jk} für die es einen Index i ∈ {1, …, j − 1} gibt so dass t_{ki} den Term t_{kj} teilt. Die verbleibende Menge heisse Σ′.

Regel 2. Streiche in Σ′ alle Elemente σ_{ik} für die es einen Index j ∈ {i + 1, …, k − 1} gibt so dass t_{kj} ein echter Teiler von t_{ki} ist. Die verbleibende Menge heisse Σ′′.

Regel 3. Streiche in Σ′′ alle Elemente σ_{ij} für die es einen Index k ∈ {j + 1, …, s} gibt so dass t_{ik} ein echter Teiler von t_{ij} ist und t_{jk} ist ein echter Teiler von t_{ji}. Die verbleibende Menge heisse Σ′′′.

Dann erzeugt die Menge Σ′′′ immer noch den Modul S = Syz(t_{1}e_{γ_{1}}, …, t_{s}e_{γ_{s}}).

Ist Σ′′′ stets ein minimales Erzeugendensystem von S?

Was ist die tiefere mathematische Bedeutung dieser Regeln?

Beispiel 4. Sei P = ℚ[x, y, z] standard graduiert, sei σ = DegLex, und sei I das homogene Ideal das erzeugt wird von

f_{1} = x^{3}z^{2} + x^{2}y^{2}z

f_{2} = x^{3}y^{8}, und
f_{3} = y^{10}z^{2}.

Die Leitterme sind t_{1} = x^{3}z^{2}, t_{2} = x^{3}y^{8} und t_{3} = y^{10}z^{2}.

Grad 1 2 3 4
13 −y^{8} z^{2}  ⟶ f_{4}
14  −y^{2}z  x  ⟶ 0
14  −x^{2} z  ⟶ 0
15 −y^{10}  x^{3}  NICHT von GM entdeckt
15  −z^{2}y^{2} x^{3}  von GM entdeckt
15 −y^{10}  xz  von GM entdeckt

wobei f_{4} = x^{2}y^{10}z. Das Paar (1, 3) wird von den Gebauer-Möller Regeln nicht entdeckt, ist aber überflüssig wegen

σ_{13} = z σ_{24} − x σ_{34} + y^{2} σ_{12}

Kann man alle überflüssigen Paare entdecken und dabei genauso schnell sein wie die GM-Regeln?

Die erste Idee wäre die Menge Σ während der Berechnung der Gröbner-Basis mit einem Standardverfahren zu minimalisieren. Dies ist zu ineffizient.

Der Buchberger Algorithmus mit Minimalisierung 1) Sei B = ∅, W = V, G = ∅, s′ = 0 und V_{min} = ∅.

2) Sei d der Lex-kleinste Multigrad in B oder in W. Bilde B_{d} = {(i, j) ∈ B | deg_{W} (σ_{ij}) = d} und W_{d} und streiche ihre Elemente in B bzw. W.

3) Ist B_{d} = ∅, so fahre mit 6) fort. Andernfalls wähle (i, j) ∈ B_{d} und steiche es in B_{d}.

4) Berechne den normalen Rest S′_{ij} = NR_{σ,G}(S_{ij}) des S-Vektors. Ist S′_{ij} = 0, so fahre mit 3) fort.

5) Erhöhe s′ um eins, füge g_{s′} = S′_{ij} zu G hinzu und füge {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}} zu B hinzu. Fahre mit 3) fort.

6) Ist W_{d} = ∅, so fahre mit 9) fort. Andernfalls wähle v ∈ W_{d} und streiche es in W_{d}.

7) Finde v′ = NR_{σ,G}(v). Ist v′ = 0, so fahre mit 6) fort.

8) Erhöhe s′ um eins, füge g_{s′} = v′ zu G und v zu V_{min} hinzu und füge {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}} zu B hinzu. Fahre mit 6) fort.

9) Ist B = ∅ und W = ∅, so gib (G, V_{min} ) aus und stoppe. Andernfalls fahre mit 2) fort. Dies ist ein Algorithmus, der eine Gröbner-Basis G und ein in V enthaltenes minimales Erzeugendensystem V_{min} von M berechnet.

Definition. Auf der Menge 𝕋(e_{1}, …, e_{s}) definieren wir eine Relation τ durch

t e_{i} ≥_{τ} t′ e_{j} ⇔ \{ \begin{matrix}LT_{σ}(t t_{i} e_{γ_{i}}) >_{σ} LT_{σ}(t′ t_{j} e_{γ_{j}}), oder \\ LT_{σ}(t t_{i} e_{γ_{i}}) = LT_{σ}(t′ t_{j} e_{γ_{j}}) und i ≥ j \end{matrix}

für Potenzprodukte t, t′ und i, j ∈ {1, …, s}.

Die Relation τ ist eine Modultermordnung. Sie heisst die von G induzierte Modultermordnung.

Satz. Sei Σ′′ ⊆ Σ die nach Anwendung der Regeln 1) und 2) von Gebauer-Möller verbleibende Menge.

Dann ist Σ̃ = {−c_{j} · σ_{ij} | σ_{ij} ∈ Σ′′} die reduzierte τ-Gröbner Basis des Moduls

Syz_{P} (LM_{σ}(G)) = Syz_{P} (c_{1}t_{1}e_{γ_{1}}, …, c_{s}t_{s}e_{γ_{s}})

Folgerung. Wir müssen eine reduzierte Gröbner-Basis minimalisieren. Dazu kann man den Buchberger Algorithmus stark verbessern.

Minimalisierung einer Reduzierten Gröbner Basis Sei V die reduzierte σ-Gröbner Basis von M.

1) Sei B = ∅, W = V, G = ∅, s′ = 0 und V_{min} = ∅.

2) Sei d der kleinste Grad eines Elements von B oder W. Bilde B_{d} und W_{d} und streiche ihre Elemente aus B bzw. W.

3) Ist B_{d} = ∅, so fahre mit 6) fort. Andernfalls wähle (i, j) ∈ B_{d} und streiche es in B_{d}.

4) Sei S′_{ij} = NR_{σ,G}(S_{ij}). Ist S′_{ij} = 0, so fahre mit 3) fort.

5) Erhöhe s′ um eins, füge g_{s′} = S′_{ij} zu G hinzu und füge {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}} zu B hinzu. Fahre mit 3) fort.

6) Ist W_{d} = ∅, so fahre mit 9) fort. Andernfalls wähle v ∈ W_{d} und streiche es in W_{d}.

7) Ist LT_{σ}(v) = LT_{σ}(g) für ein g ∈ G, so ersetze g in G durch v. Fahre mit 6) fort.

8) Erhöhe s′ um eins, füge g_{s′} = v zu G und V_{min} hinzu und füge {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}} zu B hinzu. Fahre mit 6) fort.

9) Ist B = ∅ und W = ∅, so gib V_{min} aus und stoppe. Andernfalls fahre mit 2) fort. Die ist ein Algorithmus der ein in V enthaltenes minimales Erzeugendensystem V_{min} von M berechnet.

Folgerungen. a) Wendet man diesen Algorithmus auf die reduzierte τ-Gröbner Basis Σ̃ von Syz(LM_{σ}(G)) an, so kann man ihn noch weiter beschleunigen.

b) Man kann die so erhaltene Minimalisierung der kritischen Paare in den multihomogenen Buchberger Algorithmus einbauen. Das Resultat ist der optimierte Buchberger Algorithmus (siehe unten).

c) Die Minimalisierung der kritischen Paare ist dabei ebenso schnell und effizient wie die Anwendung der Regeln von Gebauer-Möller. Sie findet aber alle nicht-minimalen kritischen Paare.

Der Optimierte Buchberger-Algorithmus

1) Sei W = V, A = ∅, B = ∅, B^{∗} = ∅, G = ∅ und s′ = 0.

2) Sei d der Lex-kleinste Grad eines Elements von B oder W. Bilde B_{d}, B_{d}^{∗}, W_{d}, und streiche ihre Elemente aus B, B^{∗}, und W.

3) Wende MinPairs(A, B_{d}, B_{d}^{∗}) an.

4) Ist B_{d} = ∅, so fahre mit 7) fort. Andernfalls wähle (i, j) ∈ B_{d}, streiche es in B_{d}, und füge es zu A hinzu.

5) Berechne S_{ij} und S′_{ij} = NR_{σ,G}(S_{ij}). Ist S′_{ij} = 0, so fahre mit 4) fort.

6) Erhöhe s′ um eins, füge g_{s′} = S′_{ij} zu G hinzu, führe Update(B, B^{∗}, g_{s′}) durch und fahre mit 4) fort.

7) Ist W_{d} = ∅ so fahre mit 10) fort. Andernfalls wähle v ∈ W_{d} und steiche es aus W_{d}.

8) Berechne v′ = NR_{σ,G}(v). Ist v′ = 0, so fahre mit 7) fort.

9) Erhöhe s′ um eins, füge g_{s′} = v′ zu G hinzu und führe Update(B, B^{∗}, g_{s′}) durch. Dann fahre mit 7) fort.

10) Ist B = ∅ und W = ∅, so gib G aus und stoppe. Andernfalls fahre mit 2) fort.

Hierbei ist die Prozedur Update(B, B^{∗}, g_{s′}) wie folgt definiert.

U1) Bilde die Menge C = {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}}. U2) Streiche in C alle Paare (j, s′) für die es ein i ∈ {1, …, j−

1} gibt so dass t_{s′i} das Monom t_{s′j} teilt. U3) Streiche in C alle Paare (i, s′) für die es ein j ∈ {i +

1, …, s′ − 1} gibt so dass t_{s′j} das Monom t_{s′i} echt teilt. U4) Finde in C alle Paare (i, s′) und (j, s′) so dass 1 ≤ i <

j < s′ und gcd(t_{is′}, t_{js′}) = 1 gilt. Prüfe jeweils ob (i, j) schon in B^{∗} liegt und füge es evtl. an.

U5) Füge alle Elemente von C zu B hinzu und stoppe.

Ferner sei MinPairs(A, B_{d}, B_{d}^{∗}) die folgende Prozedur. M1) Ist B_{d}^{∗} = ∅, so stoppe. Andernfalls wähle ein Paar (i, j)

in B_{d}^{∗} und streiche es aus B_{d}^{∗}. M2) Ist t_{ji} = t_{ji′} für (i′, j) ∈ A, so fahre mit M1) fort. M3) Ist t_{ji} = t_{ji′} für ein Paar (i′, j) ∈ B_{d}, so streiche dieses

Paar in B_{d} und füge es zu A hinzu. Fahre mit M1) fort. M4) Finde (i′, j) ∈ A so dass t_{ji′} das Monom t_{ji} teilt. Sei

(k, ℓ) = (min{i, i′}, max{i, i′}). Ist gcd(t_{ij}, t_{i′j}) ≠ 1, so fahre mit M1) fort.

M5) Ist t_{ℓk} = t_{ℓk′} für (k′, ℓ) ∈ A, so fahre mit M1) fort. M6) Ist t_{ℓk} = t_{ℓk′} für ein Paar (k′, ℓ) ∈ B_{d}, so streiche dieses

Paar in B_{d}, füge es zu A hinzu und fahre mit M1) fort. M7) Ist (k, ℓ) ∈ B_{d}^{∗}, so streiche (k, ℓ) in B_{d}^{∗} und fahre mit M4),

angewendet auf dieses Paar, fort. M8) Fahre mit M1) fort.

Dies ist ein Algorithmus der ein gradweise aufsteigend geordnetes Tupel G = {g_{1}, …, g_{s′}) homogener Vektoren berechnet dessen Elemente eine homogene σ-Gröbner-Basis von M darstellen.

Ferner entsprechen die Paare, die irgendwann in den Schritten 4)–6) abgearbeitet werden, einem minimalen Erzeugendensystem des Moduls Syz_{P} (c_{1}t_{1}e_{γ_{1}}, …, c_{s′}t_{s′}e_{γ_{s′}}).

Der Buchberger-Möller Algorithmus

Sei φ : P ⟶ K^{s} eine K-lineare Abbildung, deren Kern ein Ideal von P ist. Die Abbildung φ sei effizient berechenbar. Ferner sei σ eine Termordnung auf 𝕋^{n}.

Frage. Kann man den Kern von φ effizient berechnen?

Beispiel 1 (Multivariate Interpolation). Seien Punkte P_{1}, …, P_{s} ∈ K^{n} gegeben durch ihre Koordinaten

P_{i} = (p_{i1}, …, p_{in})

Die Abbildung φ sei die Auswertung

φ(f) = (f(P_{1}), …, f(P_{s}))

Dann ist ker(φ) das Verschwindungsideal von {P_{1}, …, P_{s}}, d.h. das Ideal aller Polynome, die an allen Punkten verschwinden.

Beispiel 2 (Hermite Interpolation). Seien wieder Punkte P_{1}, …, P_{s} ∈ K^{n} durch ihre Koordinaten gegeben. Ferner seien positive ganze Zahlen d_{1}, …, d_{s} gegeben. Die Abbildung φ : P ⟶ K^{t} mit t = \binom{d_{1}+n−1}{n−1} + ⋯ + \binom{d_{s}+n−1}{n−1} sei dadurch gegeben dass man für i = 1, …, s ein Polynom f an der Stelle P_{i} bis zum Grad d_{i} − 1 in eine Potenzreihe entwickelt und die Koeffizienten (bzgl. der Basis 𝕋^{n}) aneinanderreiht.

Der Kern von φ besteht aus der Lösung des Hermiteschen Interpolationsproblems zu den Exponenten (d_{1}, …, d_{s}), d.h. aus dem Ideal aller Polynome, die in P_{i} von mindestens d_{i}- ter Ordnung verschwinden. Die Abbildung φ ist durch eine geeignete Variante des Horner-Schemas effizient berechenbar.

Beispiel 3 (Projektive Punkte). Gegeben seien Punkte P_{1}, …, P_{s} im projektiven Raum ℙ^{n}(K) über K. Für jeden Punkt wähle ein festes Koordinatentupel P_{i} = (p_{i0}, …, p_{in}).

Gesucht ist das homogene Verschwindungsideal I dieser Punkte, d.h. das Ideal das erzeugt wird von allen homogenen Polynomen, die an diesen Punkten verschwinden. Für jedes d ≥ 0 betrachte

φ_{d} : P_{d} ⟶ K^{s} mit φ_{d}(f) = (f(P_{1}), …, f(P_{s}))

Berechnet man ker(φ_{d}) Grad für Grad nach dem Schema des Buchberger-Möller Algorithmus, so benötigt man ein Stoppkriterium dafür, dass man ein Erzeugendensystem von ganz I gefunden hat.

Beispiel 4 (Homogene Implizitisierung). Gegeben sind homogene Polynome f_{1}, …, f_{m} ∈ P vom gleichen Grad δ. Gesucht ist das Ideal der algebraischen Relationen zwischen diesen Polynomen, also das Ideal

I = {g(y_{1}, …, y_{m}) | g(f_{1}, …, f_{m}) = 0} ⊆ K[y_{1}, …, y_{m}]

Offenbar ist I ein homogenes Ideal und man kann es Grad für Grad berechnen. In jedem Grad d ist

φ_{d} : K[y_{1}, …, y_{m}]_{d} ⟶ K^{s} ≅ P_{δ d}

mit φ_{d}(g) = g(f_{1}, …, f_{m}) eine lineare Abbildung mit Kern I_{d}. Wiederum braucht man ein Stoppkriterium, das im vorliegenden Fall z.B. aus der Kenntnis der Hilbert-Funktion von I abgeleitet sein könnte.

Der Buchberger-Möller Algorithmus Sei σ eine Termordnung auf 𝕋^{n} und seien P_{1}, …, P_{s} ∈ K^{n} mit P_{i} = (p_{i1}, …, p_{in}) gegeben.

1) Sei G = ∅, S = ∅, L = (1) und M = (m_{ij}) eine 0 × s Matrix.

2) Ist L = ∅ so gib G aus und stoppe. Andernfalls wähle t = min_{σ}(L) und streiche es in L.

3) Berechne φ(t) = (t(P_{1}), …, t(P_{s})) und reduziere es gegen die Zeilen von M. Erhalte

(v_{1}, …, v_{s}) = (t(P_{1}), …, t(P_{s})) − ∑_{i} a_{i}(m_{i1}, …, m_{is})

mit a_{i} ∈ K.

4) Ist (v_{1}, …, v_{s}) = (0, …, 0) so füge t − ∑_{i} a_{i}s_{i} zu G hinzu, wobei s_{i} das i-te Element von S ist. Streiche in L die Vielfachen von t. Fahre mit 2) fort.

5) Ist (v_{1}, …, v_{s}) ≠ (0, …, 0) so füge (v_{1}, …, v_{s}) als neue Zeile zu M hinzu und t−∑_{i} a_{i}s_{i} als neues Element zu S. Füge zu L alle Terme in {x_{1}t, …, x_{n}t} hinzu, die weder Vielfaches eines Elements aus L noch aus LT_{σ}(G) sind. Fahre mit 2) fort.

Dies ist ein Algorithmus, der die reduzierte σ-Gröbner Basis des Ideals I = ker(φ) berechnet.

ProjektiveVersion des BM-Algorithmus

Sei σ eine Termordnung auf 𝕋^{n+1} und seien P_{1}, …, P_{s} ∈ ℙ^{n}(K) mit P_{i} = (p_{i0}, p_{i1}, …, p_{in}) gegeben.

1) Sei G = ∅, S = ∅ und L = (1). Sei d = 0.

2) Gilt Stoppkriterium(G)=TRUE, so gib G aus und stoppe. Andernfalls erhöhe d um eins. Sei M = (m_{ij}) eine 0×s Matrix und L = 𝕋_{d}^{n} \ LT_{σ}(G).

2) Ist L = ∅ so fahre mit 2) fort. Andernfalls wähle t = min_{σ}(L) und streiche es in L.

3) Berechne φ(t) = (t(P_{1}), …, t(P_{s})) und reduziere es gegen die Zeilen von M. Erhalte a_{i} ∈ K mit

(v_{1}, …, v_{s}) = (t(P_{1}), …, t(P_{s})) − ∑_{i} a_{i}(m_{i1}, …, m_{is})

4) Ist (v_{1}, …, v_{s}) = (0, …, 0) so füge t − ∑_{i} a_{i}s_{i} zu G hinzu, wobei s_{i} das i-te Element von S ist. Streiche in L die Vielfachen von t. Fahre mit 3) fort.

5) Ist (v_{1}, …, v_{s}) ≠ (0, …, 0) so füge (v_{1}, …, v_{s}) als neue Zeile zu M hinzu und t−∑_{i} a_{i}s_{i} als neues Element zu S. Fahre mit 3) fort.

Dies ist ein Algorithmus, der die reduzierte σ-Gröbner Basis des homogenen Verschwindungsideals von {P_{1}, …, P_{s}} berechnet.

Problem. Wir brauchen ein möglichst gutes Stoppkriterium.

Das naive Stoppkriterium d > s ist viel zu schwach. Wir bräuchten eine Gradschranke für die reduzierte Gröbner-Basis eines 1-dimensionalen Cohen-Macaulay Ideals.

Definition. Zwei Monome t, t′ ∈ 𝕋_{d}^{n+1} heissen verbunden in einer Teilmenge Q, wenn es eine Kette

t = t_{0}, t_{1}, …, t_{r} = t′

in Q gibt mit t_{i} = t_{i−1} · x_{α}/x_{β} für i = 1, …, r. Auf diese Weise zerfällt Q in Zusammenhangskomponenten.

Satz. Für P_{1}, …, P_{s} ∈ ℙ^{n}(K) gebe es einen Grad d so dass Folgendes gilt:

a) In Q = 𝕋_{d}^{n+1} \ LT_{σ}(I)_{d} liegen genau s Monome.

b) Für i = 0, …, n ist jedes Monom in der Zusammenhangskomponente von x_{i}^{d} in Q durch x_{i} teilbar.

Dann haben alle Elemente der reduzierten σ-Gröbner-Basis von I einen Grad ≤ d.

Computeralgebrasystem CoCoA

• momentante Version 4.2, graphisches Interface, toplevel Programmierung

• in einigen Wochen: Version 5, C++ Bibliothek, Source Code verfügbar

Dritte Int. Schule der Computeralgebra

• 2. – 5. Juni 2003 in Cadiz (Spanien)

• Zwei Kurse und ein Minikurs:

– Computational Invariant Theory (G. Kemper)

– Computing in Multigraded Structures (M. Kreuzer)

– Computational Aspects of D-Modules (J-M. Ucha)

Konferenz CoCoA 8

• 5. – 7. Juni 2003 in Cadiz (Spanien)

Buch “Computational Commutative Algebra”

• Autoren M. Kreuzer und L. Robbiano

• Band 1: Springer, Heidelberg 2000 (Yellow Sale!)

• Band 2: erscheint 2004