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.
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
-
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.
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.
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
-
Die Totalgradordnung oder graduierte lexikalische Ordnung ist definiert durch
-
Grad-revers-lex-Ordnung (Degree reverse lexicographical order)
Bearbeiten
Hier gilt[2]:
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
-
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.
- 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 .
- ↑ D. A. Cox, J. B. Little, D. O’Shea: Ideals, Varieties, and Algorithms. 2007, 2.2. Definition 1, Lemma 2.
- ↑ Winfried Bruns: Computer-Algebra. (PDF) Abgerufen am 31. Juli 2019.
- ↑ M. Roczen, H. Wolter, W. Pohl, D. Popescu, R. Laza: Lineare Algebra individuell – Kapitel 2: Algebraische Gleichungen. (PDF) Abgerufen am 31. Juli 2019.
- ↑ D. A. Cox, J. B. Little, D. O’Shea: Ideals, Varieties, and Algorithms. 2007, 2.2. Definition 7.