ブッフベルガーアルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/02/14 17:10 UTC 版)
「グレブナー基底」の記事における「ブッフベルガーアルゴリズム」の解説
グレブナー基底はブッフベルガーアルゴリズム (英: Buchberger's algorithm) と呼ばれるアルゴリズムで計算ができる。これはブッフベルガー (英: Bruno Buchberger) により発見された。グレブナー基底の計算はユークリッドの互除法を多変数多項式に一般化したようなアルゴリズムになっている。大まかには以下のようになる。 G {\displaystyle G} ← F {\displaystyle F} 任意の多項式の組 f 1 , f 2 ∈ G {\displaystyle f_{1},f_{2}\in G} について、 f 1 , f 2 {\displaystyle f_{1},f_{2}} のS-多項式 (S-polynomial) を G {\displaystyle G} で簡約化したものを h {\displaystyle h} とする。 h ≠ 0 ならば G ← G ∪ h {\displaystyle G\leftarrow G\cup h} として繰り返し h ＝ 0 ならば次の組を処理する この操作は有限回で止まり、得られた G は F に同値なグレブナー基底である。 ここで「S-多項式」は f1 と f2 の先頭項（項順序の最も高い項）を相殺させた式で、以下の例のように計算する。この例は次数付き逆辞書式順序。 f 1 = x y + 2 y , f 2 = 2 y 2 + x 2 {\displaystyle f_{1}=xy+2y,f_{2}=2y^{2}+x^{2}} の場合、先頭項を相殺できるような多項式 y {\displaystyle y} と 1 2 x {\displaystyle {\tfrac {1}{2}}x} をそれぞれに掛け、 S-polynomial ( f 1 , f 2 ) = y f 1 − 1 2 x f 2 = − x 3 2 + 2 y 2 {\displaystyle {\text{S-polynomial}}(f_{1},f_{2})=yf_{1}-{\frac {1}{2}}xf_{2}=-{\frac {x^{3}}{2}}+2y^{2}} これは、多項式の先頭項について最小公倍数の多項式を求めそれらを引くことで相殺していることになる。直観的には、S-多項式による計算は f1, f2 共通の簡約化と見ることができる。この場合の f1, f2 はクヌース・ベンディックス完備化アルゴリズムでの危険対 (critical pair) に相当し、本来は別々の簡約化の流れをS-多項式で合流させていくことで、簡約化の順序によらず結果が一致するという合流性 (confluence) を保証しているととらえられる。 ただし、ブッフベルガーアルゴリズムで求まるグレブナー基底には冗長な要素が含まれており、そのままでは一意にならない。冗長な要素を取り除き、先頭項の係数を 1 になるようにした基底を被約グレブナー基底 (reduced Gröbner basis) と呼ぶ。被約グレブナー基底は項順序が決まれば一意に決まる。
※この「ブッフベルガーアルゴリズム」の解説は、「グレブナー基底」の解説の一部です。
「ブッフベルガーアルゴリズム」を含む「グレブナー基底」の記事については、「グレブナー基底」の概要を参照ください。
- ブッフベルガーアルゴリズムのページへのリンク
