グレブナー基底とは何？わかりやすく解説 Weblio辞書

グレブナー基底

概要

多変数多項式環の基底の一種で，多項式の集合．多変数多項式環の単項式順序 $<$ を固定する．このとき，有限個の $0$ でない多変数多項式の集合であるグレブナー基底 $G$ は，任意の $0$ でない多変数多項式 $f$ を $G$ の元で割ったときに，割り算の順序によらず余りが一意となる良い性質をもつ．グレブナー基底は，ブッフバーガーアルゴリズムと呼ばれる解法で計算される．

詳説

　グレブナー基底 (Gröbner basis) は，体上の多変数多項式環の上で定義される「性質の良い」多項式の集合で，多変数からなる連立代数方程式の求解等に適用される．多項式環のイデアルのグレブナー基底の概念は，1960年代，オーストリアの大学院生であったブッフバーガー (Bruno Buchberger) によって発表された．ブッフバーガーは指導教官のグレブナー(Wolfgang Gröbner) に敬意を表しグレブナー基底と名付けている．ブッフバーガーは，学位論文で多項式環の剰余類環を計算する未解決問題に対し，グレブナー基底の概念とグレブナー基底を求める算法であるブッフバーガー算法 (Buchberger's algorithm) を示して解決を図った．なお，同時期に広中平祐が，局所環のイデアルに対して同様の概念 (標準基底) を独立に導入している．

　グレブナー基底に関する研究は，コンピュータの飛躍的な進歩と計算代数の研究の発展と共に盛んになり今日に至る．現在，グレブナー基底は可換代数，代数幾何，微分方程式等の純粋数学のみならず，組合せ論，凸多面体の三角形分割，符号，統計，整数計画等の情報科学や応用分野にも影響を及ぼしている．Mathematica, Maple, Risa/Asir, Singular, Macaulay 2 等の数式処理システムには，標準でグレブナー基底を計算するパッケージが組み込まれており，さらに，複数の研究者グループがグレブナー基底計算を含む計算機代数システムの開発を手掛けている．

　多変数の連立代数方程式を解くには，等価でかつ解きやすい形の別の連立方程式を求める必要があり，そこに表れる多項式がグレブナー基底である．多変数代数方程式の解の存在の判定には，多項式イデアル (以後イデアルと呼ぶ) という多項式集合が用いられる．イデアルは，多変数多項式の連立代数方程式の一般化で，多項式環の任意のイデアルに対してグレブナー基底が存在する事が知られている．グレブナー基底を計算する際には，多項式中の各単項式の「全順序」を考慮する必要があるため，ここで単項式順序について触れる． $1\,$ 変数多項式内の各単項式の全順序は,変数の次数を用いて順序付け出来る．しかし, $2\,$ 変数以上の多項式で各単項式に全順序を定義するには,順序規則を導入しなければならない．この規則は単項式順序 (monomial order)，項順序(term order)等と呼ばれる．（グレブナー基底に関する用語や記号は，統一されていないものが多いことに注意されたい．）一般に, 単項式順序は以下の二つの条件を満たすものと定義される．すなわち，「(1) 任意の単項式 $u (\neq 1)\,$ は $1<u\,$ を満たす」，「(2) 単項式 $u\,$ と $v\,$ が $u<v\,$ であるならば，任意の単項式 $w\,$ について， $uw<vw\,$ である」というものである．単項式順序には，辞書式順序，次数付き辞書式順序，次数付き逆辞書式順序等がある．

　ブッフバーガー算法は，任意のイデアルの生成系のグレブナー基底を計算するアルゴリズムで，ユークリッドの互除法の一般化のような算法である．入力として「イデアルの基底」と呼ばれる多項式の集合と，多項式中の各単項式に対する「単項式順序」が与えられると，単項式順序に関するグレブナー基底が出力されるのである．

　ブッフバーガー算法を説明する前に,算法中で用いる操作等を定義する．多項式 $f\,$ を多項式 $g\,$ で簡約するとは,「 $f\,$ 中の単項式」から「 $g\,$ 中の単項式順序の一番大きな項で割り切れるもの」を消すことである．多項式 $f\,$ を多項式の集合 $G\,$ で簡約するとは, $G\,$ の各元を前出の $g\,$ として $f\,$ に適用することである． $f\,$ を $G\,$ のどの元でも簡約出来ない時, $f\,$ は正規形であるといい, 簡約を繰り返して正規形を得ることを正規化という．

　以下にブッフバーガー算法の概略を述べる．

ブッフバーガー算法 (Buchberger's Algorithm)

入力：イデアル $I\,$ の基底 $F=\{g_1,g_2,\ldots,g_s\}\,$ ,単項式順序 $<\, \,$

出力：単項式順序 $<\,$ に関する,イデアル $I\,$ のグレブナー基底 $G\, \,$

$G \; \leftarrow \; F\, \, \,$

$\mathbf {repeat}\,$

$G' \; \leftarrow \; G\,$

$\mathbf {for}\, \,$ 各 $u,v \; (u \neq v) \in G' \; \mathbf {do}\,$

$\mbox{S-poly} \; \leftarrow \; u\,$ と $v\,$ から順序の一番大きな項を打ち消して作られる多項式

$r \; \leftarrow \; \mbox{S-poly}\, \,$ を $G\,$ で正規化して得られた正規形

$\mathbf {if} \; r \neq 0 \; \mathbf {then} \; G \leftarrow G \cup \{r\} \,$

$\mathbf {until} \; G=G' \,$

$\mathbf {return} \; G\,$

　算法中の $\mbox{S-poly}\,$ の正確な定義は紙面の都合割愛する．詳細は参考文献を参照されたい．グレブナー基底は単項式順序に依存し，単項式順序が異なると,求まるグレブナー基底も異なるかもしれない．一般に，多項式 $f\,$ を複数の多項式 $G=\{g_1,\dots,g_s\}\,$ で正規化する場合， $g_i\,$ を選ぶ順序によって正規形が異なるが， $G\,$ がグレブナー基底であれば $g_i\,$ を選ぶ順序によらず正規形の一意性が保証される．

　ブッフバーガー算法では，計算途中で生成元が膨れ上がり，最終的にグレブナー基底として選ばれる元は，計算途中で求めた生成元の一部である．ブッフバーガー算法で求まるグレブナー基底には一意性がなく，冗長な元が含まれているが，不要な元を取り除く等の操作を施すことにより被約グレブナー基底 (reduced Gröbner basis)と呼ばれる一意なグレブナー基底を求めることが出来る．

　ブッフバーガー算法によるグレブナー基底の計算時間は，単項式順序に依存する．例えば，辞書式順序のグレブナー基底を求める場合，他の単項式順序のグレブナー基底を計算してから，「基底変換」操作を行って，辞書式順序のグレブナー基底を求める方が，直接辞書式順序のグレブナー基底を計算するよりも効率が良い場合があることが経験的に知られている．そのため，近年，基底変換に関する算法研究が注目されている．

　ここで，グレブナー基底を用いた整数計画問題の求解の概要について触れる．まず問題を標準化し，等式制約から多変数多項式系を生成する．次に，目的関数のコストベクトルから単項式順序 $<\,$ を決定する．この多変数多項式系と単項式順序 $<\,$ を入力とし，グレブナー基底 $G\,$ を計算する．すると，整数計画問題の制約式の右辺項ベクトルから生成される単項式を $G\,$ で正規化して得られた正規形から,容易に最適解を導くことが出来る．

　グレブナー基底は，列挙やサンプリングとも密接な関係がある．グレブナー基底を利用して，逆探索法の枠組みで整数計画問題の実行可能領域中の実行可能解 (整数点) の列挙や，マルコフ連鎖構築による整数点のサンプリングが実現出来ることが知られている[9]．そのため，今後，グレブナー基底と凸多面体との関連研究の発展が期待される．

　グレブナー基底に関する文献は代数の予備知識を仮定したものが多いが，文献 [6] は非数学者向けにグレブナー基底とその周辺知識が記述され，初学者に適している．実際に計算機でグレブナー基底を計算する際には，文献 [8] が参考になる．

参考文献

[1] W. Adams and P. Loustaunau, An Introduction to Gröbner Bases, Graduate Studies in Mathematics, 3, American Mathematical Society, Providence, RI, 1994.

[2] P. Conti and C. Traverso, "Buchberger algorithm and integer progamming," in Applied Algebra, Algebraic Algorithms and Error-correcting codes(AAECC-9), H. Mattson, T. Mora and T. Rao, eds., Lecture Notes inComputer Science 539, Springer-Verlag, New York, 130-139, 1991.

[3] D. Cox, J. Little and D. O'Shea, "Ideals,Varieties, and Algorithms," Springer-Verlag, New York, 1992. 落合啓之, 示野信一, 西山享, 室政和, 山本敦子共訳,『グレブナー基底と代数多様体入門上，下』, シュプリンガー・フェアラーク東京, 2000.

[4] D. Cox, J. Little and D. O'Shea, "Using Algebraic Geometry," Springer-Verlag, New York, 1998. 大杉英史, 北村知徳,日比孝之共訳,『グレブナー基底１，２』, シュプリンガー・フェアラーク東京, 2000.

[5] 日比孝之,『グレブナー基底』, 野海正俊・日比孝之編, すうがくの風景 8, 朝倉書店, 2003.

[6] 平林隆一,『工学基礎　代数系とその応用』, 数理工学社, 2006.

[7] S. Hosten and R. R. Thomas, "Gröbner Bases and Integer Programming, in Gröbner Bases and Applications, Proc. of 33 Years of Groebner Bases Conference, B. Buchberger and F. Winkler, eds., London Mathematical Society Lecture Note Series 251, Cambridge University Press, Cambridge, 144-158, 1998.

[8] 野呂正行，横山和弘,『グレブナー基底の計算　基礎篇　計算代数入門』, 東京大学出版会, 2003.

[9] B. Sturmfels, Gröbner Bases and Convex Polytopes, University Lecture Notes Series, 8, American Mathematical Society, Providence, RI, 1995.

[10] R. R. Thomas, "Gröbner Bases in Integer Programming," in Handbook of Combinatorial Optimization Vol.1, D. -Z. Du and P. M. Pardalos, eds., Kluer Academic Publishers, 1998.

「OR事典」の他の用語

組合せ最適化：

クラスNC クラスR グラフ彩色問題グレブナー基底データ構造ナップサック問題ネットワークフロー問題

ウィキペディア

索引トップ用語の索引ランキングカテゴリー

グレブナー基底

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/12/14 20:49 UTC 版)

グレブナー基底（グレブナーきてい、英: Gröbner basis）は、多変数多項式の簡約化が一意に行える多項式の集合である。多変数の連立代数方程式の解を求める際などに利用される（#計算例参照）。

グレブナー基底を求めるアルゴリズムとしては、ブッフベルガーアルゴリズム（英: Buchberger's algorithm）があり、数式処理の分野での連立代数方程式の解法として使われている。また、可換環論、代数幾何、微分方程式論、整数計画問題などに出てくる様々な数学的対象物を構成するための基礎となっている。

概要

グレブナー基底の基本的な考え方は、多項式の集合 F を以下の特性を持つ "性質の良い"（グレブナー基底と呼ばれる）多項式の集合 G に変換することである^[1]。

F と G は "等価"（つまり同じイデアルを生成する）

さらに、グレブナー基底についての理論から以下のことが分かっている。

グレブナー基底の "性質の良さ" のため、F で解くのが難しい多くの問題をグレブナー基底 G で解くことができる。
任意の F を等価なグレブナー基底 G に変換するアルゴリズム（ブッフベルガーアルゴリズム）が存在する。
G での問題の解法は、多くの場合、簡単に F での問題の解法に変換できる。

例えば、数式処理システムで多変数の連立代数方程式を解く場合、直接解くのは多くの場合難しい。その際に与えられた方程式のグレブナー基底を計算しそれらを解くことで、元の連立代数方程式の解を求めることができる。

歴史

多項式環上のグレブナー基底の理論はオーストリアの大学院生であったブルーノ・ブッフベルガー（英語版）によって1965年に発表され、その当時のブッフベルガーの指導教授ヴォルフガンク・グレブナー（英語版）の名前からグレブナー基底と名付けられた。これと独立して1964年に局所環上での同様の理論が広中平祐によって発見され、標準基底（standard basis、あるいはHironaka's standard basis）とも呼ばれる。自由リー代数の枠組みでの同様の理論はA. I. Shirshovによって1962年に発見されたが、ソ連の外には広く知られなかった。

定義

イデアル

F を n 変数の多項式の集合 {f₁, f₂, ... , f_r} とするとき、多項式イデアル ⟨F⟩ = ⟨f₁, f₂, ... , f_r⟩ とは、

h_{1}f_{1}+h_{2}f_{2}+\cdots +h_{r}f_{r}

全般

FAST

国立図書館

その他

IdRef

11	ケセラセラ
12	爪先立って
13	季語一覧
14	警動
15	インスパイア
16	互礼会
17	ご愛顧
18	ツイ廃
19	つまさきだち
20	邁進

21	定義
22	尽力
23	凡事徹底
24	罹患
25	真野響子
26	巳年
27	爪立ち
28	遅ればせながら
29	つま先
30	権禰宜

グレブナー基底とは？わかりやすく解説

グレブナー基底

概要

詳説

グレブナー基底

概要

歴史

定義

イデアル

グレブナー基底

「グレブナー基底」の関連用語


	Copyright (C) 2024 （社）日本オペレーションズ・リサーチ学会 All rights reserved.
	All text is available under the terms of the GNU Free Documentation License. この記事は、ウィキペディアのグレブナー基底 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
	Text is available under GNU Free Documentation License (GFDL). Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaのクヌース・ベンディックス完備化アルゴリズム (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

グレブナー基底とは？ わかりやすく解説

グレブナー基底

概要

詳説

グレブナー基底

概要

歴史

定義

イデアル

グレブナー基底

「グレブナー基底」の関連用語

グレブナー基底とは？わかりやすく解説