Direkt zum Inhalt

Lexikon der Mathematik: Buchberger-Algorithmus

Algorithmus zur Berechnung einer Gröbner-Basis eines Ideals I im Polynomring über einem Körper.

Um den Algorithmus zu beschreiben, benutzen wir folgende Abkürzungen:

Seien f, g Polynome und S eine endliche Menge von Polynomen. \(\text{NF}(f|S)\) ist die Normalform von f bezüglich S. spoly\((f,g)\) ist das spolynom von f und g.

S = Buchberger(F)

Input: Eine Menge F von Polynomen

Output: Eine Gröbner-Basis für das von F erzeugte Ideal

\begin{eqnarray}S=F\\ P=\{(f,g):f,g\in S\}\\ \text{while}\text{\hspace{0.17em}}P\ne \varnothing \text{DO}\\ \text{choose}\text{\hspace{0.17em}}(f,g)\in P\\ P=P\backslash \{(f,g)\}\\ h=\text{NF}(\text{spoly}(f,g)|S)\\ \text{if}\text{\hspace{0.17em}}h\ne 0\\ P=P\cup \{(h,g):g\in S\}\\ S=S\cup \{h\}\end{eqnarray}

Return S.
  • Die Autoren
- Prof. Dr. Guido Walz

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.