Monomordnung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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.

Definition[Bearbeiten]

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 erhält man durch wiederholte Anwendung von (1) die absteigende Kette

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

Beispiele für Monomordnungen[Bearbeiten]

(Rein) Lexikalische Ordnung[Bearbeiten]

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[Bearbeiten]

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_{i=1}^n e_i < \sum_{i=1}^n f_i\right)\mbox{ oder }\left(\sum_{i=1}^n e_i = \sum_{i=1}^n 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[Bearbeiten]

Jedes Monom m über einer Variablenmenge X \cup Y kann auf eindeutige Weise in ein Produkt m_x m_y zerlegt werden, so dass in m_x nur Variablen aus X und in m_y 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[Bearbeiten]

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