Eine Monomordnung oder Termordnung ist eine lineare Ordnung auf der Menge der Monome über einer endlichen Variablenmenge. Monomordnungen werden zur Definition der Division mit Rest von Polynomen in mehreren Variablen benötigt. Eine Gröbnerbasis bzgl. definiert den Rest dieser Division eindeutig.

Definition

Bearbeiten

Eine lineare Ordnung   auf der Menge

 

der Monome in den Variablen   heißt Monomordnung, falls gilt

(1) Für alle Monome   gilt

 

(2) Das Monom   ist das kleinste Monom, also

 

Äquivalente Definitionen

Bearbeiten

Es sind auch andere äquivalente Definitionen üblich. So ist es etwa möglich die Bedingung (2) durch eine andere Bedingung auszutauschen. In der Literatur[1] finden sich zum Beispiel:

(2') Die Ordnung   ist eine Wohlordnung

oder auch äquivalenten dazu

(2*) Bezüglich der Ordnung   gibt es keine unendlichen absteigenden Ketten   von Monomen.

Die Eigenschaft (2*) ist Grundlage vieler Terminierungsbeweise für Algorithmen im Zusammenhang mit Gröbnerbasen.

Beispiele für Monomordnungen

Bearbeiten

Monome in einer Variablen

Bearbeiten

Falls wir nur eine Variable haben, also   gilt, gibt es nur eine Monomordnung  . Aus der Definition einer Monomordnung folgt nämlich direkt, dass in diesem Fall   sein muss.

(Rein) Lexikalische Ordnung

Bearbeiten

Bezüglich der lexikalischen oder lexikographischen Ordnung   gilt   genau dann, wenn der am weitesten links stehende, von Null verschiedene Eintrag von   negativ ist. Das heißt, es kann rekursiv definiert werden

 

Totalgradordnung

Bearbeiten

Die Totalgradordnung oder graduierte lexikalische Ordnung   ist definiert durch

 

Grad-revers-lex-Ordnung (Degree reverse lexicographical order)

Bearbeiten

Hier gilt[2]:

 

Matrix-Ordnungen

Bearbeiten

Sei  invertierbar mit der Eigenschaft, dass in jeder Spalte der erste von Null verschiedene Eintrag positiv ist. Dann gilt[3]:

 

Insbesondere kann man jede beliebige Monomordnung als Matrixordnung in  darstellen. So ergibt sich beispielsweise für die Totalordnung (graduiert lexikographische Ordnung) folgende Matrix:  . Die Grad-revers-lex-Ordnung kann folgendermaßen in eine Matrix umgesetzt werden:  .

Blockordnungen oder Eliminationsordnungen

Bearbeiten

Jedes Monom   über einer Variablenmenge   kann auf eindeutige Weise in ein Produkt   zerlegt werden, so dass in   nur Variablen aus   und in   nur Variablen aus   vorkommen. Mit dieser Schreibweise wird für gegebene Monomordnungen   und   auf Monomen über den Variablen aus   bzw.   die Blockordnung   auf Monomen in   definiert als

 

Begriffe im Zusammenhang mit Polynomen

Bearbeiten

Eine Monomordnung erlaubt es die Monome in einem Polynom anzuordnen. Für ein Polynom   kann dann zum Beispiel der Multigrad  , der Leitkoeffizient  , das Leitmonom   oder der Leitterm   von   bezüglich der Monomordnung   definiert werden.[4] Es gilt

 

Für den Polynomring in einer Variablen ergeben sich daraus die üblichen Definitionen für den Grad des Polynoms, seinen Leitkoeffizienten und seinen Leitterm.

Literatur

Bearbeiten
  • T. Becker, V. Weispfenning: Gröbner Bases, a computational approach to commutative algebra. Springer-Verlag, 1993, ISBN 3-540-97971-9.
  • David A. Cox, John B. Little, Donal O’Shea: Ideals, Varieties, and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra (= Undergraduate Texts in Mathematics). 3. Auflage. Springer, New York 2007, ISBN 978-0-387-35650-1, 2.2. Orderings on the Monomials in  .

Einzelnachweise

Bearbeiten
  1. D. A. Cox, J. B. Little, D. O’Shea: Ideals, Varieties, and Algorithms. 2007, 2.2. Definition 1, Lemma 2.
  2. Winfried Bruns: Computer-Algebra. (PDF) Abgerufen am 31. Juli 2019.
  3. M. Roczen, H. Wolter, W. Pohl, D. Popescu, R. Laza: Lineare Algebra individuell – Kapitel 2: Algebraische Gleichungen. (PDF) Abgerufen am 31. Juli 2019.
  4. D. A. Cox, J. B. Little, D. O’Shea: Ideals, Varieties, and Algorithms. 2007, 2.2. Definition 7.