Monomordnung

Monomordnung

Eine Monomordnung oder Termordnung \leq 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. \leq definiert den Rest dieser Division eindeutig.

Inhaltsverzeichnis

Definition

Eine lineare Ordnung \leq auf der Menge

M := \{ x_1^{e_1}\cdots x_n^{e_n}: e_1,\ldots,e_n \geq 0\}

der Monome in den Variablen x_1,\dots,x_n heißt Monomordnung, falls gilt


1. Für alle Monome r,m,n \in M gilt

m \leq n \Rightarrow rm \leq rn

2. Das Monom 1 ist das kleinste Monom:

\forall m \in M: 1 \leq m

Bedingung (2) ist, sofern (1) erfüllt ist, äquivalent dazu, dass \leq eine Wohlordnung ist, es also keine unendlichen absteigenden Ketten

m_1 > m_2 > m_3 > \cdots

von Monomen gibt. Diese Eigenschaft ist Grundlage vieler Terminierungsbeweise für Algorithmen im Zusammenhang mit Gröbnerbasen. Falls (2) verletzt ist, etwa m < 1, dann erhalten wird durch wiederholte Anwendung von (1) die absteigende Kette

1 > m > m^2 > m^3 > \cdots.

Beispiele für Monomordnungen

(Rein) Lexikalische Ordnung

Die lexikalische oder lexikographische Ordnung \leq_\mathrm{lex} ist definiert durch

 x_1^{e_1}\cdots x_n^{e_n} \leq_\mathrm{lex} x_1^{f_1}\cdots x_n^{f_n}
\Leftrightarrow
(e_1 < f_1)\mbox{ oder }(e_1 = f_1\mbox{ und } x_2^{e_2}\cdots x_n^{e_n} \leq_\mathrm{lex} x_2^{f_2}\cdots x_n^{f_n})

Totalgradordnung

Die Totalgradordnung oder graduierte lexikalische Ordnung \leq_\mathrm{tdeg} ist definiert durch

x_1^{e_1}\cdots x_n^{e_n} \leq_\mathrm{tdeg} x_1^{f_1}\cdots x_n^{f_n} \Leftrightarrow\left(\sum e_i < \sum f_i\right)\mbox{ oder }\left(\sum e_i = \sum f_i\mbox{ und } x_1^{e_1}\cdots x_n^{e_n} \leq_\mathrm{lex} x_1^{f_1}\cdots x_n^{f_n}\right)

Blockordnungen

Jedes Monom m über einer Variablenmenge X \cup Y kann auf eindeutige Weise in ein Produkt mxmy zerlegt werden, so dass in mx nur Variablen aus X und in my nur Variablen aus Y vorkommen. Mit dieser Schreibweise wird für gegebene Monomordnungen \leq_x und \leq_y auf Monomen über den Variablen aus X bzw. Y die Blockordnung \leq_{x > y} auf Monomen in X \cup Y definiert als

m \leq_{x > y} n \mbox{ genau dann, wenn }(m_x \leq_x n_x)\mbox{ oder }
(m_x = n_x\mbox{ und } m_y \leq_y n_y)

Literatur

  • Becker T., Weispfenning V.: Gröbner Bases, Springer-Verlag 1993.

Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Gröbnerbasis — Eine Gröbnerbasis (nach Bruno Buchberger, 1965) bzw. Standardbasis (nach Heisuke Hironaka, 1964) ist ein endliches Erzeugendensystem zu einem Ideal I im Polynomring über dem (kommutativen) Körper K, das besonders gut dafür geeignet ist, zu… …   Deutsch Wikipedia

  • Gröbner-Basis — Eine Gröbnerbasis (nach Bruno Buchberger, 1965) bzw. Standardbasis (nach Heisuke Hironaka, 1964) ist eine endliche Idealbasis zu einem Ideal I im Polynomring über dem (kommutativen) Körper K, die besonders gut dafür geeignet ist, zu entscheiden,… …   Deutsch Wikipedia

  • Buchberger-Algorithmus — Der Buchberger Algorithmus (nach Bruno Buchberger) ist in der Algebra ein Verfahren zur Berechnung einer Gröbnerbasis von einem Ideal in einem Polynomring. Durch die Möglichkeit, Gröbnerbasen algorithmisch zu bestimmen sind viele damit lösbare… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”