を 前節で考えた順序
か
とする.
を
変数多項式環
に属する多項式としよう.
の部分集合
例として,
1 変数多項式で 順序
の場合を考える.
の GCD を
とすると,
はグレブナ基底である.
グレブナ基底は余分な元をふくんでいてよくて,
たとえば,
も
のグレブナ基底となる.
問題(代数学既習者向け): ヒルベルトの基底定理を用いてグレブナ基底の存在を証明せよ.
グレブナ基底の構成をおこなうアルゴリズムが Buchberger アルゴリズムである.
まず, S 多項式の計算について簡単に説明する. 二つの多項式 ,
に対し,
,
の initial term をそれぞれ
,
とするとき,
の S 多項式は
def spolynomial(F,G) { DF = multi_degree(F); DG = multi_degree(G); Mx = DF[0]>DG[0]?DF[0]:DG[0]; My = DF[1]>DG[1]?DF[1]:DG[1]; Mz = DF[2]>DG[2]?DF[2]:DG[2]; return x^(Mx-DF[0])*y^(My-DF[1])*z^(Mz-DF[2])*F/DF[3] -x^(Mx-DG[0])*y^(My-DG[1])*z^(Mz-DG[2])*G/DG[3]; }
このプログラムで
A?B:C
なる表現があるが, これは,
A が 0 なら C を戻し, A が 0 でないならば,
B を戻す.
この定理の証明は, 例えば [2, 2章6節 定理 6] にある. これよりただちに次の Buchberger アルゴリズムを得る.
グレブナ基底の応用はいろいろなものがあるが, たとえば グレブナ基底により, ある多項式がイデアルに属するかどうか が割算により判定できる.
さらに, グレブナ基底の重要な性質として, どのように割算を行なっても結果 が一意的である, ということがある. これも, 上の定理によりすぐにわかる であろう.
3 変数の場合の Buchberger アルゴリズムを実行するプログラムを 書いてみる.
プログラム
def buchberger(F) { N = length(F); Pairs = []; for ( I = N-1; I >= 0; I-- ) for ( J = N-1; J > I; J-- ) Pairs = cons([I,J],Pairs); G = F; while ( Pairs != [] ) { P = car(Pairs); Pairs = cdr(Pairs); Sp = spolynomial(G[P[0]],G[P[1]]); Rem = reduction(Sp,G); if ( Rem ) { G = append(G,[Rem]); for ( I = 0; I < N; I++ ) Pairs = cons([I,N],Pairs); N++; } } return G; }
|
Buchberger アルゴリズムは, イデアルの基底 G に属する
二つの多項式からつくられる S 多項式に対し,
reduction 関数により剰余を計算して, G に追加していく.
実行例 [218] F=[x-y*z,y-z*x, z-x*y]; [219] G=buchberger(F); [x-z*y,-z*x+y,-y*x+z,-x^2+y^2, -y*x^3+y*x,-x^5+x^3,-x^4+x^2, x^3-x,-y*x^2+y] [220] reduction(x^2+y^2+z^2,G); 3*x^2 [221] reduction(x^2+y^2+z^2, reverse(G)); 3*x^2この実行例は, 前節で例に用いたイデアルの グレブナ基底を計算してみたものである. 順序を変えて reduction しても, 今度は同じ結果になって いることに注目してほしい. |
上のプログラムは Buchberger アルゴリズムのもっともシンプルな 形である. 残念ながら, このままでは, ごく簡単な例しか計算できない. 次のような点から種々の改良が行なわれており, それらを実装して はじめて実用的に使えるものが得られる.
これらについては [3] でくわしく解説されている.
Asir に組み込まれている函数 gr は与えらた多項式と順序に対して,
グレブナ基底を戻す. もちろん, 上に挙げたようなさまざまな改良が
実装されている.
(OpenXM 版でない Asir では, load("gr");
でまずグレブナ基底用のライブラリをロードしておく必要がある.)
gr([x^2+y^2-1, x*y-1],[y,x], 2);
順序は 0 が graded reverse lexicographic order,
1 が graded lexicographic order,
2 が lexicographic order である.
行列を用いた一般の順序の指定も可能だが, それはマニュアルを見よ.
上の例では, と
で生成されるイデアルの
なる lexicographic order に関するグレブナ基底
を戻す.
答えは,
まず, ブレブナ基底の initial term が ,
なので,
これらで割れないモノミアルで係数 1 のものは,
[713] G = gr([x^2+y^2-1,x*y-1],[y,x],2)$ [714] G; [-x^4+x^2-1,y+x^3-x] [715] p_true_nf(x^4,G,[y,x],2); [-x^2+1,-1] [716] p_true_nf(x^5,G,[y,x],2); [-x^3+x,-1] [717] p_true_nf(x^6,G,[y,x],2); [-1,1]
以上の出力より, での次の乗法表を得る.
![]() |
![]() |
![]() |
![]() |
|
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
|
![]() |
![]() |
![]() |
||
![]() |
![]() |
[284] F = [-3*x^3+4*y^2+(-2*z-3)*y+3*z^2,(-8*y-4)*x+(2*z+3)*y, -2*x^2-3*x-2*y^2+2*z*y-z^2]$ [285] V = [x,y,z]$ [286] cputime(1)$ 2.3e-05sec(1.895e-05sec) [287] buchberger(F)$ 10.38sec + gc : 0.6406sec(11.41sec) [288] gr(F,V,2)$ 0.05449sec(0.05687sec)この例では gr が圧倒的に高速である. しかし, 入力を ほんの少し変更すると次のようなことが起こる.
[289] F = [-3*x^3+4*y^2+(-2*z-3)*y+3*z^2,(-8*y-4)*x^2+(2*z+3)*y, -2*x^2-3*x-2*y^2+2*z*y-z^2]$ 8.7e-05sec(7.892e-05sec) [290] buchberger(F)$ 49.02sec + gc : 3.573sec(53.4sec) [291] gr(F,V,2)$ 163.1sec + gc : 4.694sec(168.2sec) [292] hgr(F,V,2)$ 0.02296sec(0.02374sec)これでわかるように, gr に実装されている改良も, あらゆる 入力に対して有効なわけではなく, かえって悪影響を及ぼす場合もある. hgr というのは, gr にある前処理, 後処理を付け加えた もので, おおむね安定だが, やはり遅くなる場合もある. 計算効率の 点では, グレブナ基底計算はまだ発展途上であり, 改良や新しい アルゴリズムも発表され続けている.