Gröbner Basen für polynomiale Ideale

Ordnen und Reduzieren von Termen in mehreren Variablen

Definition eines Ideals:

Ist R ein kommutativer Ring und eine Teilmenge von R, so heißt I ein Ideal, wenn

Jede endliche Menge von Polynomen erzeugt ein Ideal:

P heißt Basis des Ideals.

Bezeichnungen:

F[x] Polynomring
x (geordnete) Menge von Variablen
Tx Menge der Terme in x:

 

Ordnen von Termen

Für jede zulässige totale Ordnung in Tx muß gelten:

für alle , wobei gilt.

 

Die lexikographische Ordnung ist definiert durch:

 

Die graduelle Ordnung (degree term ordering) ist definiert durch:

 

Das führende Monom (leading monomial) von bezüglich einer Ordnung ist der maximale Term in p.

Schreibweisen:

MT(p) = M(p) führendes Monom
hterm(p) der maximale Term (head term) in p
hcoeff(p) der zugehörige Koeffizient

Konvention:

hcoeff(0) = 0, hterm(0) = 1

 

Reduktion von Termen in mehreren Variablen

Für von Null verschiedene Polynome sagt man, p läßt sich modulo q reduzieren (bezüglich einer festen Termordnung), wenn es in p ein Monom gibt, das durch hterm(q) teilbar ist.

Man sagt, ein Polynom p läßt sich modulo einer Menge von Polynomen reduzieren, wenn sich p modulo qi für (mindestens) ein i reduzieren läßt.

Schreibweise:

Andernfalls heißt p irreduzibel oder reduziert modulo Q.

Konvention: 0 ist stets irreduzibel

 

Satz 1: Für eine feste Menge Q und Ordnung gibt es keine unendliche Sequenz von Reduktionen

 

Weitere Bezeichnungen:

bezeichnet die reflexive, transitive Hülle von

D.h.

Wenn und q irreduzibel ist, schreibt man: .

 

Ein Algorithmus zur vollen Reduktion von p modulo Q

Gegeben:Polynom p, Menge von Polynomen Q aus F[x]

Gesucht:Polynom q mit

Grundidee: Zuerst Reduktion der höherwertigen Monome, dadurch werden die niederen Monome auch verändert

Bezeichnung R(p, Q):

Menge aller möglichen Reduktionspolynome in Q, die das höchstwertigste Monom in p reduzieren können

Es wird aus dieser Menge der möglichen Reduktionspolynome durch die Funktion SelectPoly(R(p, Q)) ein beliebiges ausgewählt.

 

Schematische Beschreibung des Algorithmus

procedure Reduziere(p, Q)
r = p  // r: noch zu reduzierendes Polynom
q = 0  // q: Ergebnispolynom
while do {
while do {
f = SelectPoly(R(r, Q)) // f: Reduktionspolynom
}
q = q + M(r); r = r - M(r)
}
return q
end

 

Ein Beispiel zum Algorithmus

Zu reduzierendes Polynom:

Zugrundeliegende Termordnung: <L (lexikographisch)

Reduktionspolynome:

Der Algorithmus liefert:

Dies ist die vollständige Reduktion von p modulo Q.

 

Ein weiteres Beispiel zum Algorithmus

Zugrundeliegende Termordnung: <G (graduell)

Reduktionspolynome:

Zu reduzierende Polynome:

Aber: ist irreduzibel modulo Q.

D.h. p1 und p2 lassen sich modulo Q zu 0 reduzieren, ihre Summe ist aber irreduzibel modulo Q.

 

Nachteile des Algorithmus, Verbesserungen

  • Größtes Problem: Reduktion ist nicht eindeutig, da die Auswahl des nächsten Reduktionspolynoms aus Q nicht determiniert erfolgt, sondern zufällig
  • Lassen sich zwei Polynome p, q jeweils zu 0 reduzieren, so muß dies nicht für ihre Summe p + q zutreffen
  • Algorithmus kann terminieren, wenn alle Terme in r reduziert wurden, die größer sind als der kleinste "head term" in Q (nur minimale Verbesserung)
  • Verbesserung in der innersten Schleife kann erreicht werden, wenn vor dem Algorithmus jedes Polynom in Q durch seinen head term dividiert wird (nur arithmetische, keine prinzipielle Verbesserung)

 

Weitere Sätze über Reduktionen

Satz 2: Sind p, q und r Polynome aus F[x] und und gilt , dann existieren Polynome und , so daß gilt.

Satz 3: Sind p, q Polynome aus F[x] mit für , dann gibt es ein , so daß und gilt.

Satz 4: Sind p1, p2 Polynome mit , dann existiert für jedes Polynom r ein Polynom s mit .

 

Literatur

[1] Geddes, Gabor, Algorithms for Computer Algebra, Kluwer Academic Publ. 1992

 

Zurück zur Übersicht über alle Publikationen