ブフラーのアルゴリズム - 百科事典

多元多項式理論において、Buchbergerのアルゴリズムは、与えられた多項式の集合をGröbner基底に変換する方法であり、同じ共通の零点を持つ別の多項式の集合で、これらの共通の零点に関する情報を抽出するのに便利です。それは、Gröbner基底の定義と同時にBruno Buchbergerによって紹介されました。

多項式の最大公約数を計算するユークリッドアルゴリズムは、Buchbergerのアルゴリズムの特別な場合であり、単一変数の多項式に制限されています。線形方程式のガウス消去法も、すべての多項式の度数が1である特別な場合です。

他のGröbner基底アルゴリズムについては、Gröbner基底 § アルゴリズムと実装を参照してください。

アルゴリズム
このアルゴリズムの原始的なバージョンは、多項式環Rの理想Iの基底を探すために以下のように進行します：

入力 Aを生成する多項式の集合F
出力 IのGröbner基底G
G := F
Gの中のすべてのfi、fjに対して、giを与えられたモノマ数順序に関するfiの先頭項と、aijをgiとgjの最小公倍数とする。
Gの中の2つの多項式を選び、Sij = aij/gi fi - aij/gj fj（ここでの先頭項は構造上消えることに注意）とする。
Sijを多項式の除法アルゴリズムに基づいてGに対して減少させ、結果がさらに減少できないまで減少させる。
結果が0でない場合、それをGに追加する。
ステップ2から4までをすべての可能な対（ステップ4で追加された新しい多項式を含む）について繰り返す。
Gを出力する
多項式Sijは通常S-多項式と呼ばれ、Sは減法（Buchberger）または共軛（他のもの）を意味します。関連する多項式のペアは通常批判的対と呼ばれます。

上記のもの以上に、このアルゴリズムを改善する多くの方法があります。例えば、Fのすべての新しい要素を互いに対して減少させることができます。fiとfjの先頭項が共通の変数を持たない場合、Sijは常に0に減少します（減少にfiとfjのみを使用する場合）、したがってそれを計算する必要はありません。

このアルゴリズムは、先頭項のモノマ理想の大きさを一貫して増加させるため、終了します。ディクソンの補題（またはヒルバート基底定理）は、このようなような昇順の連鎖が最終的に一定になることを保証します。

繁雑さ
Buchbergerのアルゴリズムの計算複雑さは非常に難しい估计であり、計算時間を劇的に変える可能性のある選択の数のために難しいです。それにもかかわらず、T. W. Dubéは、減少されたGröbner基底の要素の度数が常に以下で制限されることを証明しました：



2


(




d

2


2


+
d

)



2

n
−
2






、ここでnは変数の数、dは入力多項式の最大の総度数です。これにより、理論的には、この値に制限された度数を持つ多項式のベクトル空間に対して線形代数を使用して、複雑さのアルゴリズムを得ることができます：





d


2

n
+
o
(
1
)






、ここでnは変数の数、dは入力多項式の最大の総度数です。これにより、理論的には、この値に制限された度数を持つ多項式のベクトル空間に対して線形代数を使用して、複雑さのアルゴリズムを得ることができます：





d


2

n
+
o
(
1
)






、ここでnは変数の数、dは入力多項式の最大の総度数です。

一方、Gröbner基底に度数が以下を持つ例があります：





d


2

Ω
(
n
)






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

Buchbergerのアルゴリズムが発見されて以来、その効率を向上させるための多くのバリエーションが導入されました。FaugèreのF4とF5アルゴリズムは、現在、Gröbner基底を計算する最も効率的なアルゴリズムであり、数百の多項式からなるGröbner基底を計算することが通常可能です。各多項式には数百の項と数百の桁の係数があります。

実装
PythonのSymPyライブラリでは、(改善された)Buchbergerのアルゴリズムがsympy.polys.polytools.groebner()として実装されています。

Coqの証明助手内で正しさが証明されたBuchbergerのアルゴリズムの実装があります。

参考資料
Knuth–Bendix completion algorithm
Quine–McCluskey algorithm – Boolean algebraに対する類似のアルゴリズム


参考文献
Buchberger, B. (August 1976). "Theoretical Basis for the Reduction of Polynomials to Canonical Forms". ACM SIGSAM Bulletin. 10 (3). ACM: 19–29. doi:10.1145/1088216.1088219. MR 0463136. S2CID 15179417.
David Cox, John Little, and Donald O'Shea (1997). Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, Springer. ISBN 0-387-94680-2.
Vladimir P. Gerdt, Yuri A. Blinkov (1998). Involutive Bases of Polynomial Ideals, Mathematics and Computers in Simulation, 45:519ff


外部リンク
"Buchberger algorithm", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
Buchberger's algorithm on Scholarpedia
Weisstein, Eric W. "Buchberger's Algorithm". MathWorld.