ブッフバーガーのアルゴリズム

多変数多項式理論において、ブッフバーガーのアルゴリズムは、与えられた多項式の集合をグレブナー基底に変換する手法である。グレブナー基底とは、同じ共通零点を持ち、これらの共通零点に関する情報を抽出するのに便利な別の多項式の集合である。このアルゴリズムは、グレブナー基底の定義と同時に ブルーノ・ブッフバーガーによって導入された。

多項式の最大公約数を計算するユークリッドのアルゴリズムと線形システムのガウス消去法は、変数の数または多項式の次数がそれぞれ 1 に等しい場合の Buchberger アルゴリズムの特殊なケースです。

その他のグレブナー基底アルゴリズムについては、グレブナー基底 § アルゴリズムと実装を参照してください。

多項式環RのイデアルIの基底を見つけるこのアルゴリズムの大まかなバージョンは、次のように進行します。

入力Iを生成する多項式Fの集合

Iのグレブナー基底 Gを出力する

1. G  := F
2. G内のすべてのf _i、f _jについて、与えられた単項式順序に関するf _iの主要項をg _iで表し、g _iとg _jの最小公倍数をa _ijで表します。
3. G内の2つの多項式を選択し、S _ij = ⁠ア・_イジ/ ギ_​⁠ f _i − ⁠ア・_イジ/ グー_​⁠ f _j (ここでの主要な項は構文上消去されることに注意してください)。
4. 多変量除算アルゴリズムを使用して、結果がそれ以上減算できなくなるまで、集合Gに対してS _{ij を}減算します。結果がゼロ以外の場合は、それをGに追加します。
5. 手順 4 で追加された新しい多項式を含むすべての可能なペアが考慮されるまで、手順 2 ～ 4 を繰り返します。
6. 出力G

多項式S _{ij は}一般にS多項式と呼ばれます。ここで、S は減算(Buchberger) またはシジジー(その他)を表します。これに関連付けられた多項式のペアは一般に臨界ペアと呼ばれます。

このアルゴリズムを改良する方法は、上記以外にも数多くあります。たとえば、Fのすべての新しい要素を、追加する前に互いに相対的に縮約することができます。f i と f j の主要項に共通の変数がない場合、 S ij_は常に0に_縮約されます(縮約にf _iとf _jのみを使用する場合)。そのため、これを計算する必要はありません。

このアルゴリズムは、集合Fの主要な項によって生成される単項式イデアルのサイズを一貫して増加させているため終了し、ディクソンの補題(またはヒルベルト基底定理) により、このような上昇チェーンは最終的に定数になることが保証されます。

ブッフバーガーのアルゴリズムの計算量は、計算時間を劇的に変える可能性のある選択肢の数が多いため、見積もるのが非常に難しい。しかし、TWデュベは^[1]、縮小グレブナー基底の要素の次数が常に

${\displaystyle 2\left({\frac {d^{2}}{2}}+d\right)^{2^{n-2}}}$、

ここで、nは変数の数、d は入力多項式の最大総次数です。これにより、理論的には、この値で制限される次数の多項式のベクトル空間上で線型代数を使用して、複雑度のアルゴリズムを取得できます 。 ${\displaystyle d^{2^{n+o(1)}}}$

一方、グレブナー基底に次数の要素が含まれる 例^{[2]もある。}

${\displaystyle d^{2^{\Omega (n)}}}$、

そして、上記の複雑さの上限は最適です。しかし、そのような例は非常にまれです。

発見されて以来、ブッフベルガーのアルゴリズムの多くの変種が効率性を改善するために導入されてきました。現在、フォジェールの F4 アルゴリズムと F5 アルゴリズムは、グレブナー基底を計算するための最も効率的なアルゴリズムであり、数百の項と数百桁の係数を持つ数百の多項式で構成されるグレブナー基底を日常的に計算できます。

• クヌース・ベンディックス補完アルゴリズム
• クワイン・マクラスキーアルゴリズム– ブール代数の類似アルゴリズム

• Buchberger, B. (1976 年 8 月). 「多項式から標準形への縮約の理論的基礎」. ACM SIGSAM 速報. 10 (3). ACM: 19–29. doi :10.1145/1088216.1088219. MR  0463136. S2CID  15179417.
• David Cox、John Little、Donald O'Shea (1997)。『イデアル、多様体、アルゴリズム：計算代数幾何学と可換代数の入門』、Springer。ISBN 0-387-94680-2。 
• Vladimir P. Gerdt、Yuri A. Blinkov (1998)。多項式イデアルの反転基底、シミュレーションにおける数学とコンピュータ、45:519ff

• 「ブッフバーガーアルゴリズム」、数学百科事典、EMS Press、2001 [1994]
• Scholarpedia の Buchberger のアルゴリズム
• ワイスタイン、エリック W.「ブッフベルガーのアルゴリズム」。マスワールド。