実験的仕様の関数: 2.3 グレブナー基底

2.3 グレブナー基底

2.3.1 `dp_gr_main`

dp_gr_main(f | v=vv, order=oo, homo=n, matrix=m, block=b, sugarweight=sw): :: dp_gr_main の新しいインタフェース.

return: リスト (グレブナ基底. 再帰表現多項式か分散表現多項式のリスト)
f: リスト (入力多項式系. 再帰表現多項式か分散表現多項式のリスト)
vv: リスト (変数のリスト)
oo: リスト (順序をあらわすリスト)
n: 0 か1 (homogenization をするか)
m: 順序を matrix で表現する場合 (cf. dp_ord).
b: ???
sw: Sugar strategy を適用するときの weight vector. 全ての要素は非負.

dp_gr_main(f) は, f のグレブナ基底を計算する. グレブナ基底は順序を変えるとその形が変わる. asir ではいままで順序の指定方法が系統だっていなかった. dp_gr_main の新しいインタフェースでは順序をある文法に従い指定する.
順序 order は次の文法で定義する. {, } は 0 回以上の繰り返しを意味する.
```
  order         : '[' orderElement { ',' orderElement } ']'
  orderElement   :  weightVec | builtinOrder
  weightVec     : '[' weightElement { ',' weightElement } ']'
  builtiniOrder : '[' orderName  ',' setOfVariables ']'
  weightElement :   NUMBER | setOfVariables ',' NUMBER
  setOfVariables:  V | range(V,V)
  orderName    : @grlex | @glex | @lex
```
ここで V は変数名, NUMBER は整数をあわらす. 例1: v=[x,y,z,u,v], order=[[x,10,y,5,z,1],[@grlex,range(x,v)]] は x,y,z がそれぞれ weight 10, 5, 1 をもつ順序で比較したあと, [x,y,z,u,v] についての graded reverse lexicographic order を tie-breaker として用いることを意味する. 参考書: B.Sturmfels: Gr\"obner Bases and Convex Polytopes (1995). M.Saito, B.Sturmfels, N.Takayama: Gr\"obner Deformations of Hypergeometric Differential Equations (2000).
順序要素 (orderElement) の指定方法は (1) 変数名または rangeで指定された変数の集合と重みの値の繰り返し (2) 重みの値を変数リストの順番に並べる方法 (3) 変数名または rangeで指定された変数の集合と順序名の組の三通りの基礎的方法がある. 似た指定方法が Macaulay, Singular, CoCoA, Kan/sm1 等の環論システムで使用されていた. Risa/Asir の指定方法はこれらのシステムの指定方法を参考にさらに改良を加えたもので柔軟性が高い.
order の tie-breaker は grlex がデフォールト.
分散表現多項式を引数としたときは結果も分散表現多項式として戻る. order 指定にもちいるデフォールトの変数名はこのとき x0, x1, x2, ... となる.
オプションの値は option_list キーワードを用いてリストで与えてもよい. 下の例を参照.

[218] load("cyclic");
[219] V=vars(cyclic(4));
[c0,c1,c2,c3]
[220]dp_gr_main(cyclic(4) | v=V, order=[[c0,10,c1,1],[c2,5],[@grlex,range(c0,c3)]]);
[ 10 1 0 0 ]
[ 0 0 5 0 ]
[ R R R R ]
[(-c3^6+c3^2)*c2^2+c3^4-1,c3^2*c2^3+c3^3*c2^2-c2-c3,
 (c3^4-1)*c1+c3^5-c3,(c2-c3)*c1+c3^4*c2^2+c3*c2-2*c3^2,-c1^2-2*c3*c1-c3^2,
 c0+c1+c2+c3]

[1151]  F=map(dp_ptod,katsura(4), vars(katsura(4)));
[(1)*<<1,0,0,0,0>>+(2)*<<0,1,0,0,0>>+ ... ]
[1152] dp_gr_main(F | order=[[range(x0,x3),1]]);
[ 1 1 1 1 0 ]
[ R R R R R ]
[(47774098944)*<<0,0,0,0,13>>+ ... ]

[1153] Opt=[["v",[x,y]], ["order",[[x,5,y,1]]]];
[[v,[x,y]],[order,[[x,5,y,1]]]]
[1154]  dp_gr_main([x^2+y^2-1,x*y-1] | option_list=Opt);
[ 5 1 ]
[ R R ]
[-y^4+y^2-1,x+y^3-y]

ChangeLog

この関数は 2003-12 から 2004-2 の始めに大きな修正が行われた.
setOfVariablesの表現のために range オブジェクトが導入された.
グレブナ基底は順序を変えるとその形が変わる. asir ではいままで順序の指定方法が系統だっていなかった. dp_gr_main の新しいインタフェースでは順序をある文法に従い指定する.
OpenXM_contrib2/asir2000 の下の次の各ファイルが修正をうけた. builtin/gr.c 1.56–1.57, builtin/dp-supp.c 1.27–1.31 (create_composite_order_spec), builtin/dp.c 1.46–1.48 (parse_gr_option), engine/Fgfs.c 1.20, engine/dist.c 1.27–1.28 engine/nd.c 1.89, include/ca.h 1.42–1.43, io/pexpr.c 1.28, io/sexpr.c 1.26, parse/arith.c 1.11, parse/glob.c 1.44-1.45, parse/lex.c 1.29, parse/parse.h 1.23–1.26
Todo: return キーワードで戻り値のデータを quote のリストにできるように. attribute, ring 構造体.

2.3.2 `dp_weyl_gr_main`

dp_weyl_gr_main(f | v=vv, order=oo, homo=n, matrix=m, block=b, sugarweight=sw): :: dp_weyl_gr_main の新しいインタフェース. dp_gr_main と同じ形式である.

return: リスト (グレブナ基底. 再帰表現多項式か分散表現多項式のリスト)
f: リスト (入力多項式系. 再帰表現多項式か分散表現多項式のリスト)
vv: リスト (変数のリスト)
oo: リスト (順序をあらわすリスト)
n: 0 か1 (homogenization をするか). [テストまだ]
m: 順序を matrix で表現する場合 (cf. dp_ord). [テストまだ]
b: ???
sw: Sugar strategy を適用するときの weight vector. 全ての要素は非負. [テストまだ]

dp_weyl_gr_main(f) は, f のグレブナ基底を計算する. グレブナ基底は順序を変えるとその形が変わる. asir ではいままで順序の指定方法が系統だっていなかった. dp_weyl_gr_main の新しいインタフェースでは順序をある文法に従い指定する. 指定方法については dp_gr_main のマニュアルを参照.
分散表現多項式の各モノミアルの長さが偶数のときはワイル代数 K[x_1, ..., x_n, d_1, ..., d_n] で計算がおこなわれる. ワイル代数では x_i と d_i は非可換な掛け算規則 d_i x_i = x_i d_i +1 をみたし, x_i と x_j や d_i と d_j は可換である. また i と j が異なる場合は x_i と d_j も可換である.
分散表現多項式の各モノミアルの長さが奇数のときは同次化ワイル代数 K[x_1, ..., x_n, d_1, ..., d_n, h] で計算がおこなわれる. 同次化ワイル代数では x_i と d_i は非可換な掛け算規則 d_i x_i = x_i d_i + h^2 をみたし, h は任意の元と可換, その他の変数もワイル代数と同様な可換性の規則をみたす. 詳しくは dp_gr_main で参照した Saito, Sturmfels, Takayama の教科書をみよ.

[1220] F=sm1.gkz([ [[1,1,1,1],[0,1,3,4]], [0,0]]);  /* Command in asir-contrib*/
[[x4*dx4+x3*dx3+x2*dx2+x1*dx1,4*x4*dx4+3*x3*dx3+x2*dx2,-dx1*dx4+dx2*dx3,-dx2^2*dx4+dx1*dx3^2,dx1^2*dx3-dx2^3,-dx2*dx4^2+dx3^3],[x1,x2,x3,x4]]
[1221] V=[x1,x2,x3,x4,dx1,dx2,dx3,dx4]$
[1222] dp_weyl_gr_main(F[0] | v=V, order=[[dx1,1,dx2,1,dx3,1,dx4,1]]);
...
[1238] FF=map(dp_ptod,F[0],V);
[(1)*<<1,0,0,0,1,0,0,0>>+(1)*<<0,1,0,0,0,1,0,0>>+(1)*<<0,0,1,0,0,0,1,0>>+(1)*<<0,0,0,1,0,0,0,1>>,(1)*<<0,1,0,0,0,1,0,0>>+(3)*<<0,0,1,0,0,0,1,0>>+(4)*<<0,0,0,1,0,0,0,1>>,0,0,0,0]

[1244] FF=map(dp_ptod,F[0],V);
[(1)*<<1,0,0,0,1,0,0,0>>+(1)*<<0,1,0,0,0,1,0,0>>+(1)*<<0,0,1,0,0,0,1,0>>+(1)*<<0,0,0,1,0,0,0,1>>,(1)*<<0,1,0,0,0,1,0,0>>+(3)*<<0,0,1,0,0,0,1,0>>+(4)*<<0,0,0,1,0,0,0,1>>,(1)*<<0,0,0,0,0,1,1,0>>+(-1)*<<0,0,0,0,1,0,0,1>>,(1)*<<0,0,0,0,1,0,2,0>>+(-1)*<<0,0,0,0,0,2,0,1>>,(-1)*<<0,0,0,0,0,3,0,0>>+(1)*<<0,0,0,0,2,0,1,0>>,(1)*<<0,0,0,0,0,0,3,0>>+(-1)*<<0,0,0,0,0,1,0,2>>]

dp_weyl_gr_main(FF | v=V, order=[[0,0,0,0,1,1,1,1]]);

[1246] dp_weyl_gr_main(FF | v=V, order=[[dx1,1,dx2,1,dx3,1,dx4,1]]);
[ 0 0 0 0 1 1 1 1 ]
[ R R R R R R R R ]
 ...

参照: dp_gr_main

ChangeLog

dp_gr_main のインタフェースが dp_weyl_gr_main へも導入された.
OpenXM_contrib2/asir2000 の下の次の各ファイルが修正をうけた. builtin/dp-supp.c 1.32–1.33 builtin/dp.c 1.49–1.50

2.3.3 `dp_initial_term`

dp_initial_term(f | v=vv, order=oo): :: dp_initial_term は与えられた weight に対する先頭項の和を戻す.

return: 分散表現多項式または分散表現多項式のリスト.
f: 分散表現多項式か分散表現多項式のリスト.
vv: リスト (変数のリスト)
oo: リスト (順序をあらわすリスト)

dp_initial_term は与えられた weight w に対する先頭項の和を戻す. これは多くの教科書でと書かれている.
順序を表すリストは dp_gr_main で定義した文法に従う. このリストの先頭が weight vector で無い場合はエラーとなる. たとえば order=[[@lex,...]] はエラーとなる.
結果は与えられた順序に関してソートされてるわけではない.

[1220] F=<<2,0,0>>+<<1,1,0>>+<<0,0,1>>;
(1)*<<2,0,0>>+(1)*<<1,1,0>>+(1)*<<0,0,1>>
[1220] dp_initial_term(F | order=[[1,1,1]]);
[ 1 1 1 ]
[ R R R ]
(1)*<<2,0,0>>+(1)*<<1,1,0>>
[1221] dp_initial_term(F | v=[x,y,z], order=[[x,1]]);
[ 1 0 0 ]
[ R R R ]
(1)*<<2,0,0>>

参照: dp_gr_main, dp_weyl_gr_main, dp_order, @ref{dp_hm}

ChangeLog

OpenXM_contrib2/asir2000 の下の次の各ファイルが修正をうけた. builtin/dp-supp.c 1.32 builtin/dp.c 1.49

2.3.4 `dp_order`

dp_order(f | v=vv, order=oo): :: dp_order は与えられた weight に対する次数の最大値を戻す.

return: 数か数のリスト
f: 分散表現多項式か分散表現多項式のリスト.
vv: リスト (変数のリスト)
oo: リスト (順序をあらわすリスト)

順序を表すリストは dp_gr_main で定義した文法に従う. このリストの先頭が weight vector で無い場合はエラーとなる. たとえば order=[[@lex,...]] はエラーとなる.
dp_order は与えられた weight w に対する次数の最大値を戻す. これをと書く論文や教科書もある.
引数がリストの場合各要素の次数が計算される.

[1220] F=<<2,0,0>>+<<1,1,0>>+<<0,0,1>>;
(1)*<<2,0,0>>+(1)*<<1,1,0>>+(1)*<<0,0,1>>
[1222] dp_order(F | order=[[1,1,1]]);
[ 1 1 1 ]
[ R R R ]
2
[1223] dp_order(F | v=[x,y,z], order=[[x,1]]);
[ 1 0 0 ]
[ R R R ]

参照: dp_gr_main, dp_weyl_gr_main, dp_initial_term, @ref{dp_hm}

ChangeLog

OpenXM_contrib2/asir2000 の下の次の各ファイルが修正をうけた. builtin/dp-supp.c 1.32 builtin/dp.c 1.49

2.3.5 `nd_sba`, `nd_sba_f4`

nd_sba(gen,vars,char,ord)
nd_sba_f4(gen,vars,char,ord): :: signature based algorithm によるグレブナー基底の計算

gen: 多項式リスト
ord: 項順序型
var: 変数リスト
return: 多項式リスト

signature based algorithm (SBA) によるグレブナー基底計算の実験的実装である.
signature based algorithm とは, イデアルの各元に, その元をもとの生成系から生成する係数ベクトル (加群の元) の先頭項 (signature) を付随させ, 単項式除算を, signature が真に小さいものによる除算に限定して Buchberger algorithm 類似の手続きを実行する.
Buchberger algorithm における useless pair elimination criteria の代わりに, syzygy を用いた criterion や, 同一 signature の S-ペアを 1 つに絞るなどの S-ペア消去手法により, Buchberger algorithm より効率よくグレブナー基底を計算できる場合がある.
nd_sba は signature 付き Buchberger algorithm を実行する. 引数, オプション, dp_gr_flags() で設定されるスイッチは nd_gr と同一である.
nd_sba_f4 は nd_sba において, 複数のS-ペアをまとめて簡約できるような reducer を symbolic preprocessing で集め, 行列上で簡約操作を行う実装である. しかし, 通常の F4 と異なり, SBA の実行は S-ペアを選ぶ順序に鋭敏であり, どのような基準で複数のS-ペアを選ぶかについて実験中である.

[0] load("katsura")$
[4] F=katsura(10)$
[5] V=[u0,u1,u2,u3,u4,u5,u6,u7,u8,u9,u10]$
[6] cputime(1)$
1.7e-05sec(1.502e-05sec)
[7] G=nd_gr(F,V,31991,0)$
83.04sec(83.2sec)
[8] Gs=nd_sba(F,V,31991,0)$
12.9sec(12.92sec)
[9] G4=nd_f4(F,V,31991,0)$ 
12.56sec(12.58sec)
[10] G4s=nd_sba_f4(F,V,31991,0)$
5.534sec(5.538sec)

参照: Risa/Asir ユーザーズマニュアルの「グレブナ基底の計算」

2.3.6 `nd_gr`, `nd_gr_trace` (加群)

nd_gr(gen,vars,char,ord)
nd_gr_trace(gen,vars,homo,char,ord)
nd_weyl_gr(gen,vars,char,ord)
nd_weyl_gr_trace(gen,vars,homo,char,ord): :: 部分加群のグレブナー基底の計算

gen: リストのリスト
ord: [IsPOT,Ord] なるリスト
return: リストのリスト

多項式環あるいはワイル代数上の自由加群の部分加群のグレブナー基底を計算する. 結果はリストのリストである. 各要素リストは, 自由加群の元であるベクトルとみなす.
ord として [IsPOT,Ord] という2要素リストが指定された場合, 加群のグレブナー基底計算を実行する. この場合, gen は, 多項式のリストのリストとして与える必要がある.
IsPOT が 1 の場合, POT (position over term), 0 の場合 TOP (term over position) で比較する. 基礎環での項比較は Ord で行う.
説明されていない引数は, イデアルの場合の解説を参照のこと.

[0] Gen=[[x,y,z],[y^2+x,x^2,z],[y^2,z^3+x,x+z]];
[[x,y,z],[x+y^2,x^2,z],[y^2,x+z^3,x+z]]
[1]  nd_gr(Gen,[x,y,z],0,[0,0]);
[[x,y,z],[y^2,x^2-y,0],[y^2,x+z^3,x+z],[y^3+z^3*y^2,y^3*x-y^3,
-x^3-z*x^2+(z*y^2+y)*x-z*y^2+z*y],[0,0,x^4+z*x^3+(-z*y^2-y)*x^2
+(-y^3+z*y^2-z*y)*x+z^4*y^2]]

参照: @ref{nd_gr}, @ref{nd_gr_trace}

2.3.7 `nd_gr`, `nd_gr_trace` (option)

nd_gr(...[|opt,opt,…])
nd_gr_trace(...[|opt,opt,…])
nd_weyl_gr(...[|opt,opt,…])
nd_weyl_gr_trace(...[|opt,opt,…]): :: グレブナー基底計算に関する種々のオプションの説明

opt: key=value なるオプション設定
return: オプションにより異なる

グレブナー基底計算をオプションにより制御する.
現状では次の 3 つのオプションを受け付ける.

gentrace

value が 0 でないとき, グレブナー基底の計算経過情報を出力する.

gensyz

value が 0 でないとき, 計算されたグレブナー基底に対する syzygy の生成系を出力する.

nora

value が 0 でないとき, 最終ステップで相互簡約を行わない.
gentrace が指定された場合, 出力は, [GB,Homo,Trace,IntRed,Ind,InputRed,SpairTrace] なるリストである. 各要素の意味は次の通りである.

GB

グレブナー基底

Homo

中間基底が斉次化されている場合 1, そうでない場合 0.

Trace

全中間基底に対する計算経過情報

IntRed

相互簡約に対する計算経過情報

Ind

簡約グレブナー基底の各要素の, 全中間基底のにおけるインデックス

InputRed

各入力多項式をグレブナー基底で簡約して剰余 0 を得るまでの計算経過情報 (gensyz が指定された場合)

SpairTrace

簡約グレブナー基底に対する S 多項式を簡約して剰余 0 を得るまでの計算経過情報 (syzygy 加群の生成系の要素のみ; gensyz が指定された場合)
詳細は, 入力多項式集合とグレブナー基底の相互変換行列, および syzygy 計算関数の項で説明する予定.

[0] C=[c3*c2*c1*c0-1,((c2+c3)*c1+c3*c2)*c0+c3*c2*c1,...]
[1] D=nd_gr_trace(C,[c0,c1,c2,c3,c4],0,1,0|gentrace=1,gensyz=1)$
[2] D[0];
[c0+c1+c2+c3,-c1^2-2*c3*c1-c3^2,...]
[3] D[2];
[[[0,0,1],[1,1,1],[2,2,1],[3,3,1]],[4,[[1,2,(1)*<<0,0,0,0>>,1],...]
[4] D[6];
[[-1,[[1,0,(1)*<<0,0,2,4>>,1],[1,6,(-1)*<<1,0,0,0>>,1],...]

参照: @ref{nd_gr}, @ref{nd_gr_trace}

この文書は3月 16, 2025にtexi2html 5.0を用いて生成されました。

2.3 グレブナー基底

2.3.1 dp_gr_main

2.3.2 dp_weyl_gr_main

2.3.3 dp_initial_term

2.3.4 dp_order

2.3.5 nd_sba, nd_sba_f4

2.3.6 nd_gr, nd_gr_trace (加群)

2.3.7 nd_gr, nd_gr_trace (option)

2.3.1 `dp_gr_main`

2.3.2 `dp_weyl_gr_main`

2.3.3 `dp_initial_term`

2.3.4 `dp_order`

2.3.5 `nd_sba`, `nd_sba_f4`

2.3.6 `nd_gr`, `nd_gr_trace` (加群)

2.3.7 `nd_gr`, `nd_gr_trace` (option)