8.10 グレブナ基底に関する函数

8.10.1 gr, hgr, gr_mod, dgr

gr(plist,vlist,order)

hgr(plist,vlist,order)

gr_mod(plist,vlist,order,p)

dgr(plist,vlist,order,procs)

:: グレブナ基底の計算

return

リスト

plist vlist procs

リスト

order

数, リストまたは行列

p

2^27 未満の素数

• 標準ライブラリの ‘gr’ で定義されている.
• gr を名前に含む関数は現在メンテされていない. nd_gr系の関数を代わりに利用すべきである(nd_gr, nd_gr_trace, nd_f4, nd_f4_trace, nd_weyl_gr, nd_weyl_gr_trace).
• いずれも, 多項式リスト plist の, 変数順序 vlist, 項順序型 order に関するグレブナ基底を求める. gr(), hgr() は 有理数係数, gr_mod() は GF(p) 係数として計算する.
• vlist は不定元のリスト. vlist に現れない不定元は, 係数体に属すると見なされる.
• gr(), trace-lifting (モジュラ演算を用いた高速化) および sugar strategy による計算, hgr() は trace-lifting および 斉次化による 矯正された sugar strategy による計算を行う.
• dgr() は, gr(), hgr() を 子プロセスリスト procs の 2 つのプロセスにより同時に計算させ, 先に結果を返した方の結果を返す. 結果は同一であるが, どちらの方法が 高速か一般には不明のため, 実際の経過時間を短縮するのに有効である.
• dgr() で表示される時間は, この函数が実行されているプロセスでの CPU 時間であり, この函数の場合はほとんど通信のための時間である.
• 多項式リスト plist の要素が分散表現多項式の場合は 結果も分散表現多項式のリストである. この場合, 引数の分散多項式は与えられた順序に従い dp_sort で ソートされてから計算される. 多項式リストの要素が分散表現多項式の場合も 変数の数分の不定元のリストを vlist 引数として与えないといけない (ダミー).

[0] load("gr")$
[64] load("cyclic")$
[74] G=gr(cyclic(5),[c0,c1,c2,c3,c4],2);
[c4^15+122*c4^10-122*c4^5-1,...]
[75] GM=gr_mod(cyclic(5),[c0,c1,c2,c3,c4],2,31991)$
24628*c4^15+29453*c4^10+2538*c4^5+7363
[76] (G[0]*24628-GM[0])%31991;
0

参照

dp_gr_main, dp_gr_mod_main, dp_gr_f_main, dp_weyl_gr_main, dp_weyl_gr_mod_main, dp_weyl_gr_f_main, dp_ord.

8.10.2 lex_hensel, lex_tl, tolex, tolex_d, tolex_tl

lex_hensel(plist,vlist1,order,vlist2,homo)

lex_tl(plist,vlist1,order,vlist2,homo)

:: 基底変換による辞書式順序グレブナ基底の計算

tolex(plist,vlist1,order,vlist2)

tolex_d(plist,vlist1,order,vlist2,procs)

tolex_tl(plist,vlist1,order,vlist2,homo)

:: グレブナ基底を入力とする, 基底変換による辞書式順序グレブナ基底の計算

return

リスト

plist vlist1 vlist2 procs

リスト

order

数, リストまたは行列

homo

フラグ

• 標準ライブラリの ‘gr’ で定義されている.
• lex_hensel(), lex_tl() は, 多項式リスト plist の, 変数順序 vlist1, 項順序型 order に関するグレブナ基底を求め, それを, 変数順序 vlist2 の辞書式順序グレブナ基底に変換する.
• tolex(), tolex_tl() は, 変数順序 vlist1, 項順序型 order に関するグレブナ基底である 多項式リスト plist を変数順序 vlist2 の辞書式順序グレブナ 基底に変換する. tolex_d() は, tolex() における, 各基底の計算を, 子プロセス リスト procs の各プロセスに分散計算させる.
• lex_hensel(), lex_tl() においては, 辞書式順序グレブナ基底の 計算は次のように行われる. ([Noro,Yokoyama] 参照.)
  1. vlist1, order に関するグレブナ基底 G0 を計算する. (lex_hensel() のみ. )
  2. G0 の各元の vlist2 に関する辞書式順序における頭係数を割らない ような素数 p を選び, GF(p) 上での辞書式順序グレブナ基底 Gp を計算する.
  3. Gp に現れるすべての項の, G0 に関する正規形 NF を計算する.
  4. Gp の各元 f につき, f の係数を未定係数で, f の各項を対応する NF の元で置き換え, 各項の係数を 0 と置いた, 未定係数に関する線形方程式系 Lf を作る.
  5. Lf が, 法 p で一意解を持つことを用いて Lf の解を 法 pの解から Hensel 構成により求める.
  6. すべての Gp の元につき線形方程式が解けたらその解全体が求める 辞書式順序でのグレブナ基底. もしどれかの線形方程式の求解に失敗したら, p をとり直してやり直す.
• lex_tl(), tolex_tl() においては, 辞書式順序グレブナ基底の 計算は次のように行われる.
  1. vlist1, order に関するグレブナ基底 G0 を計算する. (lex_hensel() のみ. )
  2. G0 が 0 次元システムでないとき, G0 を入力として, G0 の各元の vlist2 に関する辞書式順序における頭係数を割らない ような素数 p を選び, p を用いた trace-lifting により辞書式 順序のグレブナ基底候補を求め, もし求まったならチェックなしにそれが求める グレブナ基底となる. もし失敗したら, p をとり直してやり直す.
  3. G0 が 0 次元システムのとき, G0 を入力として, まず, vlist2 の最後の変数以外を消去する消去順序により グレブナ基底 G1 を計算し, それから辞書式順序のグレブナ基底を 計算する. その際, 各ステップでは, 入力の各元の, 求める順序における 頭係数を割らない素数を用いた trace-lifting でグレブナ基底候補を求め, もし求まったらチェックなしにそれがその順序でのグレブナ基底となる.
• 有理式係数の計算は, lex_tl(), tolex_tl() のみ受け付ける.
• homo が 0 でない場合, 内部で起動される Buchberger アルゴリズムに おいて, 斉次化が行われる.
• tolex_d() で表示される時間は, この函数が実行されているプロセスに おいて行われた計算に対応していて, 子プロセスにおける時間は含まれない.

[78] K=katsura(5)$ 
30msec + gc : 20msec
[79] V=[u5,u4,u3,u2,u1,u0]$
0msec
[80] G0=hgr(K,V,2)$
91.558sec + gc : 15.583sec
[81] G1=lex_hensel(K,V,0,V,0)$
49.049sec + gc : 9.961sec
[82] G2=lex_tl(K,V,0,V,1)$
31.186sec + gc : 3.500sec
[83] gb_comp(G0,G1);
1
10msec
[84] gb_comp(G0,G2);
1

参照

dp_gr_main, dp_gr_mod_main, dp_gr_f_main, dp_weyl_gr_main, dp_weyl_gr_mod_main, dp_weyl_gr_f_main, dp_ord, 分散計算

8.10.3 lex_hensel_gsl, tolex_gsl, tolex_gsl_d

lex_hensel_gsl(plist,vlist1,order,vlist2,homo)

:: GSL 形式のイデアル基底の計算

tolex_gsl(plist,vlist1,order,vlist2)

tolex_gsl_d(plist,vlist1,order,vlist2,procs)

:: グレブナ基底を入力とする, GSL 形式のイデアル基底の計算

return

リスト

plist vlist1 vlist2 procs

リスト

order

数, リストまたは行列

homo

フラグ

• lex_hensel_gsl() は lex_hensel() の, tolex_gsl() は tolex() の変種で, 結果のみが異なる. tolex_gsl_d() は, 基底計算を, procs で指定される子プロセスに 分散計算させる.
• 入力が 0 次元システムで, その辞書式順序グレブナ基底が [f0,x1-f1,...,xn-fn] (f0,...,fn は x0 の 1 変数多項式) なる形 (これを SL 形式と呼ぶ) を持つ場合, [[x1,g1,d1],...,[xn,gn,dn],[x0,f0,f0']] なるリスト (これを GSL 形式と呼ぶ) を返す. ここで, gi は, di*f0'*fi-gi が f0 で割り切れるような x0 の1 変数多項式で, 解は f0(x0)=0 なる x0 に対し, [x1=g1/(d1*f0'),...,xn=gn/(dn*f0')] となる. 辞書式順序グレブナ基底が上のような形でない場合, tolex() に よる通常のグレブナ基底を返す.
• GSL 形式により表される基底はグレブナ基底ではないが, 一般に係数が SL 形式 のグレブナ基底より非常に小さいため計算も速く, 解も求めやすい. tolex_gsl_d() で表示される時間は, この函数が実行されているプロセスに おいて行われた計算に対応していて, 子プロセスにおける時間は含まれない.

[103] K=katsura(5)$
[104] V=[u5,u4,u3,u2,u1,u0]$
[105] G0=gr(K,V,0)$
[106] GSL=tolex_gsl(G0,V,0,V)$ 
[107] GSL[0];
[u1,8635837421130477667200000000*u0^31-...]
[108] GSL[1];
[u2,10352277157007342793600000000*u0^31-...]
[109] GSL[5];
[u0,11771021876193064124640000000*u0^32-...,
376672700038178051988480000000*u0^31-...]

参照

lex_hensel, lex_tl, tolex, tolex_d, tolex_tl, 分散計算

8.10.4 gr_minipoly, minipoly

gr_minipoly(plist,vlist,order,poly,v,homo)

:: 多項式の, イデアルを法とした最小多項式の計算

minipoly(plist,vlist,order,poly,v)

:: グレブナ基底を入力とする, 多項式の最小多項式の計算

return

多項式

plist vlist

リスト

order

数, リストまたは行列

poly

多項式

v

不定元

homo

フラグ

• gr_minipoly() はグレブナ基底の計算から行い, minipoly() は 入力をグレブナ基底とみなす.
• イデアル I が体 K 上の多項式環 K[X] の 0 次元イデアルの時, K[v] の元 f(v) に f(p) mod I を対応させる 環準同型の核は 0 でない多項式により生成される. この生成元を p の, 法 I での最小多項式と呼ぶ.
• gr_minipoly(), minipoly() は, 多項式 p の最小多項式 を求め, v を変数とする多項式として返す.
• 最小多項式は, グレブナ基底の 1 つの元として計算することもできるが, 最小多項式のみを求めたい場合, minipoly(), gr_minipoly() は グレブナ基底を用いる方法に比べて効率がよい.
• gr_minipoly() に指定する項順序としては, 通常全次数逆辞書式順序を 用いる.

[117] G=tolex(G0,V,0,V)$      
43.818sec + gc : 11.202sec
[118] GSL=tolex_gsl(G0,V,0,V)$
17.123sec + gc : 2.590sec
[119] MP=minipoly(G0,V,0,u0,z)$
4.370sec + gc : 780msec

参照

lex_hensel, lex_tl, tolex, tolex_d, tolex_tl.

8.10.5 tolexm, minipolym

tolexm(plist,vlist1,order,vlist2,mod)

:: 法 mod での基底変換によるグレブナ基底計算

minipolym(plist,vlist1,order,poly,v,mod)

:: 法 mod でのグレブナ基底による多項式の最小多項式の計算

return

tolexm() : リスト, minipolym() : 多項式

plist vlist1 vlist2

リスト

order

数, リストまたは行列

mod

素数

• 入力 plist はいずれも 変数順序 vlist1, 項順序型 order, 法 mod におけるグレブナ基底でなければならない.
• minipolym() は minipoly に対応する計算を法 modで行う.
• tolexm() は FGLM 法による基底変換により vlist2, 辞書式順序によるグレブナ基底を計算する.

[197] tolexm(G0,V,0,V,31991);
[8271*u0^31+10435*u0^30+816*u0^29+26809*u0^28+...,...]
[198] minipolym(G0,V,0,u0,z,31991);
z^32+11405*z^31+20868*z^30+21602*z^29+...

参照

lex_hensel, lex_tl, tolex, tolex_d, tolex_tl, gr_minipoly, minipoly.

8.10.6 dp_gr_main, dp_gr_mod_main, dp_gr_f_main, dp_weyl_gr_main, dp_weyl_gr_mod_main, dp_weyl_gr_f_main

dp_gr_main(plist,vlist,homo,modular,order)

dp_gr_mod_main(plist,vlist,homo,modular,order)

dp_gr_f_main(plist,vlist,homo,order)

dp_weyl_gr_main(plist,vlist,homo,modular,order)

dp_weyl_gr_mod_main(plist,vlist,homo,modular,order)

dp_weyl_gr_f_main(plist,vlist,homo,order)

:: グレブナ基底の計算 (組み込み函数)

return

リスト

plist vlist

リスト

order

数, リストまたは行列

homo

フラグ

modular

フラグまたは素数

• これらの函数は, グレブナ基底計算の基本的組み込み函数であり, gr(), hgr(), gr_mod() などはすべてこれらの函数を呼び出して計算 を行っている. 関数名に weyl が入っているものは, Weyl 代数上の計算 のための関数である.
• dp_gr_f_main(), dp_weyl_f_main() は, 種々の有限体上のグレブナ基底を計算する 場合に用いる. 入力は, あらかじめ, simp_ff() などで, 考える有限体上に射影されている必要がある.
• フラグ homo が 0 でない時, 入力を斉次化してから Buchberger アルゴリズム を実行する.
• dp_gr_mod_main() に対しては, modular は, GF(modular) 上 での計算を意味する. dp_gr_main() に対しては, modular は次のような意味を持つ.
  1. modular が 1 の時, trace-lifting による計算を行う. 素数は lprime(0) から順に成功するまで lprime() を呼び出して生成する.
  2. modular が 2 以上の自然数の時, その値を素数とみなして trace-lifting を行う. その素数で失敗した場合, 0 を返す.
  3. modular が負の場合, -modular に対して上述の規則が適用されるが, trace-lifting の最終 段階のグレブナ基底チェックとイデアルメンバシップチェックが省略される.
• gr(P,V,O) は dp_gr_main(P,V,0,1,O), hgr(P,V,O) は dp_gr_main(P,V,1,1,O), gr_mod(P,V,O,M) は dp_gr_mod_main(P,V,0,M,O) をそれぞれ実行する.
• homo, modular の他に, dp_gr_flags() で設定される さまざまなフラグにより計算が制御される.

参照

dp_ord, dp_gr_flags, dp_gr_print, gr, hgr, gr_mod, dgr, setmod_ff, 計算および表示の制御.

8.10.7 dp_f4_main, dp_f4_mod_main, dp_weyl_f4_main, dp_weyl_f4_mod_main

dp_f4_main(plist,vlist,order)

dp_f4_mod_main(plist,vlist,order)

dp_weyl_f4_main(plist,vlist,order)

dp_weyl_f4_mod_main(plist,vlist,order)

:: F4 アルゴリズムによるグレブナ基底の計算 (組み込み函数)

return

リスト

plist vlist

リスト

order

数, リストまたは行列

• F4 アルゴリズムによりグレブナ基底の計算を行う.
• F4 アルゴリズムは, J.C. Faugere により提唱された新世代グレブナ基底 算法であり, 本実装は, 中国剰余定理による線形方程式求解を用いた 試験的な実装である.
• 斉次化の引数がないことを除けば, 引数および動作はそれぞれ dp_gr_main(), dp_gr_mod_main(), dp_weyl_gr_main(), dp_weyl_gr_mod_main() と同様である.

参照

dp_ord, dp_gr_flags, dp_gr_print, gr, hgr, gr_mod, dgr, 計算および表示の制御.

8.10.8 nd_gr, nd_gr_trace, nd_f4, nd_f4_trace, nd_weyl_gr, nd_weyl_gr_trace

nd_gr(plist,vlist,p,order[|option=value,...])

nd_gr_trace(plist,vlist,homo,p,order[|option=value,...])

nd_f4(plist,vlist,modular,order[|option=value,...])

nd_f4_trace(plist,vlist,homo,p,order[|option=value,...])

nd_weyl_gr(plist,vlist,p,order[|option=value,...])

nd_weyl_gr_trace(plist,vlist,homo,p,order[|option=value,...])

:: グレブナ基底の計算 (組み込み函数)

return

リスト

plist vlist

リスト

order

数, リストまたは行列

homo

フラグ

modular

フラグまたは素数

• これらの函数は, グレブナ基底計算組み込み関数の新実装である.
• nd_gr は, p が 0 のとき有理数体上の Buchberger アルゴリズムを実行する. p が 2 以上の自然数のとき, GF(p) 上の Buchberger アルゴリズムを実行する.
• nd_gr_trace および nd_f4_trace は有理数体上で trace アルゴリズムを実行する. p が 0 または 1 のとき, 自動的に選ばれた素数を用いて, 成功する まで trace アルゴリズムを実行する. p が 2 以上のとき, trace はGF(p) 上で計算される. trace アルゴリズム が失敗した場合 0 が返される. p が負の場合, グレブナ基底チェックは 行わない. この場合, p が -1 ならば自動的に選ばれた素数が, それ以外は指定された素数を用いてグレブナ基底候補の計算が行われる. nd_f4_trace は, 各全次数について, ある有限体上で F4 アルゴリズム で行った結果をもとに, その有限体上で 0 でない基底を与える S-多項式のみを 用いて行列生成を行い, その全次数における基底を生成する方法である. 得られる 多項式集合はやはりグレブナ基底候補であり, nd_gr_trace と同様の チェックが行われる.
• nd_f4 は modular が 0 のとき有理数体上の, modular が マシンサイズ素数のとき有限体上の F4 アルゴリズムを実行する.
• plist が多項式リストの場合, plistで生成されるイデアルのグレブナー基底が 計算される. plist が多項式リストのリストの場合, 各要素は多項式環上の自由加群の元と見なされ, これらが生成する部分加群のグレブナー基底が計算される. 後者の場合, 項順序は加群に対する項順序を 指定する必要がある. これは [s,ord] の形で指定する. s が 0 ならば TOP (Term Over Position), 1 ならば POT (Position Over Term) を意味し, ord は多項式環の単項式に対する項順序である.
• nd_weyl_gr, nd_weyl_gr_trace は Weyl 代数用である.
• f4 系関数以外はすべて有理関数係数の計算が可能である.
• 一般に dp_gr_main, dp_gr_mod_main より高速であるが, 特に有限体上の場合顕著である.
• 以下のオプションが指定できる.

  homo

  1 のとき, 斉次化を経由して計算する. (nd_gr, nd_f4 のみ)

  dp

  1 のとき, 分散表現多項式 (加群の場合には加群多項式) を結果として返す.

  nora

  1 のとき, 結果の相互簡約を行わない.

[38] load("cyclic")$
[49] C=cyclic(7)$
[50] V=vars(C)$
[51] cputime(1)$
[52] dp_gr_mod_main(C,V,0,31991,0)$
26.06sec + gc : 0.313sec(26.4sec)
[53] nd_gr(C,V,31991,0)$
ndv_alloc=1477188
5.737sec + gc : 0.1837sec(5.921sec)
[54] dp_f4_mod_main(C,V,31991,0)$  
3.51sec + gc : 0.7109sec(4.221sec)
[55] nd_f4(C,V,31991,0)$
1.906sec + gc : 0.126sec(2.032sec)

参照

dp_ord, dp_gr_flags, dp_gr_print, 計算および表示の制御.

8.10.9 nd_gr_postproc, nd_weyl_gr_postproc

nd_gr_postproc(plist,vlist,p,order,check)

nd_weyl_gr_postproc(plist,vlist,p,order,check)

:: グレブナ基底候補のチェックおよび相互簡約

return

リスト または 0

plist vlist

リスト

p

素数または 0

order

数, リストまたは行列

check

0 または 1

• グレブナ基底(候補)の相互簡約を行う.
• nd_weyl_gr_postproc は Weyl 代数用である.
• check=1 の場合, plist が, vlist, p, order で指定される多項式環, 項順序でグレブナー基底になっているか のチェックも行う.
• 斉次化して計算したグレブナー基底を非斉次化したものを相互簡約を行う, CRT で計算したグレブナー基底候補のチェックを行うなどの場合に用いる.

afo

8.10.10 dp_gr_flags, dp_gr_print

dp_gr_flags([list])

dp_gr_print([i])

:: 計算および表示用パラメタの設定, 参照

return

設定値

list

リスト

i

整数

• dp_gr_main(), dp_gr_mod_main(), dp_gr_f_main() 実行時におけるさまざま なパラメタを設定, 参照する.
• 引数がない場合, 現在の設定が返される.
• 引数は, ["Print",1,"NoSugar",1,...] なる形のリストで, 左から順に 設定される. パラメタ名は文字列で与える必要がある.
• dp_gr_print() は, 特にパラメタ Print, PrintShort の値を直接設定, 参照 できる. 設定される値は次の通りである。

  i=0

  Print=0, PrintShort=0

  i=1

  Print=1, PrintShort=0

  i=2

  Print=0, PrintShort=1

  これは, dp_gr_main() などをサブルーチンとして用いるユーザ 函数において, そのサブルーチンが中間情報の表示 を行う際に, 迅速にフラグを見ることができるように用意されている.

参照

計算および表示の制御

8.10.11 dp_ord

dp_ord([order])

:: 変数順序型の設定, 参照

return

変数順序型 (数, リストまたは行列)

order

数, リストまたは行列

• 引数がある時, 変数順序型を order に設定する. 引数がない時, 現在設定されている変数順序型を返す.
• 分散表現多項式に関する函数, 演算は引数として変数順序型をとるものととらないもの があり, とらないものに関しては, その時点で設定されている値を用いて計算が 行われる.
• gr() など, 引数として変数順序型をとるものは, 内部で dp_ord() を呼び出し, 変数順序型を設定する. この設定は, 計算終了後も生き残る.
• 分散表現多項式の四則演算も, 設定されている値を用いて計算される. 従って, その多項式が生成された時点における変数順序型が, 四則演算時に正しく設定 されていなければならない. また, 演算対象となる多項式は, 同一の変数順序 型に基づいて生成されたものでなければならない.
• トップレベル函数以外の函数を直接呼び出す場合には, この函数により 変数順序型を正しく設定しなければならない.
• 引数がリストの場合, 自由加群における項順序型を設定する. 引数が[0,Ord] の場合, 多項式環上で Ord で指定される項順序に基づく TOP 順序, 引数が [1,Ord] の場合 OPT 順序を設定する.

[19] dp_ord(0)$          
[20] <<1,2,3>>+<<3,1,1>>;
(1)*<<1,2,3>>+(1)*<<3,1,1>>
[21] dp_ord(2)$          
[22] <<1,2,3>>+<<3,1,1>>;
(1)*<<3,1,1>>+(1)*<<1,2,3>>

参照

項順序の設定

8.10.12 dp_set_weight, dp_set_top_weight, dp_weyl_set_weight

dp_set_weight([weight])

:: sugar weight の設定, 参照

dp_set_top_weight([weight])

:: top weight の設定, 参照

dp_weyl_set_weight([weight])

:: weyl weight の設定, 参照

return

ベクトル

weight

整数のリストまたはベクトル

• dp_set_weight は sugar weight を weight に設定する. 引数がない時, 現在設定されている sugar weight を返す. sugar weight は正整数を成分とするベクトルで, 各変数の重みを表す. 次数つき順序において, 単項式の次数を計算する際に用いられる. 斉次化変数用に, 末尾に 1 を付け加えておくと安全である.
• dp_set_top_weight は top weight を weight に設定する. 引数がない時, 現在設定されている top weight を返す. top weight が設定されているとき, まず top weight による単項式比較を先に行う. tie breaker として現在設定されている 項順序が用いられるが, この比較には top weight は用いられない.
• dp_weyl_set_weight は weyl weight を weight に設定する. 引数がない時, 現在設定されている weyl weight を返す. weyl weight w を設定すると, 項順序型 11 での計算において, (-w,w) を top weight, tie breaker を graded reverse lex とした項順序が設定される.

参照

Weight

8.10.13 dp_ptod

dp_ptod(poly,vlist)

:: 多項式を分散表現多項式に変換する.

return

分散表現多項式

poly

多項式

vlist

リスト

• 変数順序 vlist および現在の変数順序型に従って分散表現多項式に変換する.
• vlist に含まれない不定元は, 係数体に属するとして変換される.

[50] dp_ord(0);
1
[51] dp_ptod((x+y+z)^2,[x,y,z]);
(1)*<<2,0,0>>+(2)*<<1,1,0>>+(1)*<<0,2,0>>+(2)*<<1,0,1>>+(2)*<<0,1,1>>
+(1)*<<0,0,2>>
[52] dp_ptod((x+y+z)^2,[x,y]);  
(1)*<<2,0>>+(2)*<<1,1>>+(1)*<<0,2>>+(2*z)*<<1,0>>+(2*z)*<<0,1>>
+(z^2)*<<0,0>>

参照

dp_dtop, dp_ord.

8.10.14 dpm_dptodpm

dpm_dptodpm(dpoly,pos)

:: 分散表現多項式を加群多項式に変換する.

return

加群多項式

dpoly

分散表現多項式

pos

正整数

• 分散表現多項式を加群多項式に変換する.
• 出力は加群多項式 dpoly e_pos である.

[50] dp_ord([0,0])$
[51] D=dp_ptod((x+y+z)^2,[x,y,z]);
(1)*<<2,0,0>>+(2)*<<1,1,0>>+(1)*<<0,2,0>>+(2)*<<1,0,1>>+(2)*<<0,1,1>>
+(1)*<<0,0,2>>
[52] dp_dptodpm(D,2);
(1)*<<2,0,0:2>>+(2)*<<1,1,0:2>>+(1)*<<0,2,0:2>>+(2)*<<1,0,1:2>>
+(2)*<<0,1,1:2>>+(1)*<<0,0,2:2>>

参照

dp_ptod, dp_ord.

8.10.15 dpm_ltod

dpm_dptodpm(plist,vlist)

:: 多項式リストを加群多項式に変換する.

return

加群多項式

plist

多項式リスト

vlist

変数リスト

• 多項式リストを加群多項式に変換する.
• [p1,...,pm] は p1 e1+...+pm em に変換される.

[2126] dp_ord([0,0])$
[2127] dpm_ltod([x^2+y^2,x,y-z],[x,y,z]);
(1)*<<2,0,0:1>>+(1)*<<0,2,0:1>>+(1)*<<1,0,0:2>>+(1)*<<0,1,0:3>>
+(-1)*<<0,0,1:3>>

参照

dpm_dtol, dp_ord.

8.10.16 dpm_dtol

dpm_dptodpm(poly,vlist)

:: 加群多項式を多項式リストに変換する.

return

多項式リスト

poly

加群多項式

vlist

変数リスト

• 加群多項式を多項式リストに変換する.
• p1 e1+...+pm em は [p1,...,pm] に変換される.
• 出力リストの長さは, poly に含まれる標準基底の最大インデックスとなる.

[2126] dp_ord([0,0])$
[2127] D=(1)*<<2,0,0:1>>+(1)*<<0,2,0:1>>+(1)*<<1,0,0:2>>+(1)*<<0,1,0:3>>
+(-1)*<<0,0,1:3>>$
[2128] dpm_dtol(D,[x,y,z]);
[x^2+y^2,x,y-z]

参照

dpm_ltod, dp_ord.

8.10.17 dp_dtop

dp_dtop(dpoly,vlist)

:: 分散表現多項式を多項式に変換する.

return

多項式

dpoly

分散表現多項式

vlist

リスト

• 分散表現多項式を, 与えられた不定元リストを用いて多項式に変換する.
• 不定元リストは, 長さ分散表現多項式の変数の個数と一致していれば何でもよい.

[53] T=dp_ptod((x+y+z)^2,[x,y]);
(1)*<<2,0>>+(2)*<<1,1>>+(1)*<<0,2>>+(2*z)*<<1,0>>+(2*z)*<<0,1>>
+(z^2)*<<0,0>>
[54] P=dp_dtop(T,[a,b]);
z^2+(2*a+2*b)*z+a^2+2*b*a+b^2

8.10.18 dp_mod, dp_rat

dp_mod(p,mod,subst)

:: 有理数係数分散表現多項式の有限体係数への変換

dp_rat(p)

:: 有限体係数分散表現多項式の有理数係数への変換

return

分散表現多項式

p

分散表現多項式

mod

素数

subst

リスト

• dp_nf_mod(), dp_true_nf_mod() は, 入力として有限体係数の 分散表現多項式を必要とする. このような場合, dp_mod() により 有理数係数分散表現多項式を変換して用いることができる. また, 得られた 結果は, 有限体係数多項式とは演算できるが, 有理数係数多項式とは演算できない ため, dp_rat() により変換する必要がある.
• 有限体係数の演算においては, あらかじめ setmod() により有限体の元の 個数を指定しておく必要がある.
• subst は, 係数が有理式の場合, その有理式の変数にあらかじめ数を代入 した後有限体係数に変換するという操作を行う際の, 代入値を指定するもので, [[var,value],...] の形のリストである.

参照

dp_nf, dp_nf_mod, dp_true_nf, dp_true_nf_mod, subst, psubst, setmod.

8.10.19 dp_homo, dp_dehomo

dp_homo(dpoly)

:: 分散表現多項式の斉次化

dp_dehomo(dpoly)

:: 斉次分散表現多項式の非斉次化

return

分散表現多項式

dpoly

分散表現多項式

• dp_homo() は, dpoly の 各項 t について, 指数ベクトルの長さを 1 伸ばし, 最後の成分の値を d-deg(t) (d は dpoly の全次数) とした分散表現多項式を返す.
• dp_dehomo() は, dpoly の各項について, 指数ベクトルの最後の成分 を取り除いた分散多項式を返す.
• いずれも, 生成された多項式を用いた演算を行う場合, それらに適合する項順序を 正しく設定する必要がある.
• hgr() などにおいて, 内部的に用いられている.

[202] X=<<1,2,3>>+3*<<1,2,1>>;
(1)*<<1,2,3>>+(3)*<<1,2,1>>
[203] dp_homo(X);
(1)*<<1,2,3,0>>+(3)*<<1,2,1,2>>
[204] dp_dehomo(@);
(1)*<<1,2,3>>+(3)*<<1,2,1>>

参照

gr, hgr, gr_mod, dgr.

8.10.20 dp_ptozp, dp_prim

dp_ptozp(dpoly)

:: 定数倍して係数を整数係数かつ係数の整数 GCD を 1 にする.

dp_prim(dpoly)

:: 有理式倍して係数を整数係数多項式係数かつ係数の多項式 GCD を 1 にする.

return

分散表現多項式

dpoly

分散表現多項式

• dp_ptozp() は, ptozp() に相当する操作を分散表現多項式に 対して行う. 係数が多項式を含む場合, 係数に含まれる多項式共通因子は 取り除かない.
• dp_prim() は, 係数が多項式を含む場合, 係数に含まれる多項式共通因子 を取り除く.

[208] X=dp_ptod(3*(x-y)*(y-z)*(z-x),[x]);
(-3*y+3*z)*<<2>>+(3*y^2-3*z^2)*<<1>>+(-3*z*y^2+3*z^2*y)*<<0>>
[209] dp_ptozp(X);                       
(-y+z)*<<2>>+(y^2-z^2)*<<1>>+(-z*y^2+z^2*y)*<<0>>
[210] dp_prim(X);                        
(1)*<<2>>+(-y-z)*<<1>>+(z*y)*<<0>>

参照

ptozp.

8.10.21 dp_nf, dp_nf_mod, dp_true_nf, dp_true_nf_mod

dp_nf(indexlist,dpoly,dpolyarray,fullreduce)

dp_weyl_nf(indexlist,dpoly,dpolyarray,fullreduce)

dp_nf_mod(indexlist,dpoly,dpolyarray,fullreduce,mod)

dp_weyl_nf_mod(indexlist,dpoly,dpolyarray,fullreduce,mod)

:: 分散表現多項式の正規形を求める. (結果は定数倍されている可能性あり)

dp_true_nf(indexlist,dpoly,dpolyarray,fullreduce)

dp_true_nf_mod(indexlist,dpoly,dpolyarray,fullreduce,mod)

:: 分散表現多項式の正規形を求める. (真の結果を [分子, 分母] の形で返す)

return

dp_nf() : 分散表現多項式, dp_true_nf() : リスト

indexlist

リスト

dpoly

分散表現多項式

dpolyarray

配列

fullreduce

フラグ

mod

素数

• 分散表現多項式 dpoly の正規形を求める.
• 名前に weyl を含む関数はワイル代数における正規形計算を行う. 以下の説明は weyl を含むものに対しても同様に成立する.
• dp_nf_mod(), dp_true_nf_mod() の入力は, dp_mod() など により, 有限体上の分散表現多項式になっていなければならない.
• 結果に有理数, 有理式が含まれるのを避けるため, dp_nf() は 真の値の定数倍の値を返す. 有理式係数の場合の dp_nf_mod() も同様 であるが, 係数体が有限体の場合 dp_nf_mod() は真の値を返す.
• dp_true_nf(), dp_true_nf_mod() は, [nm,dn] なる形のリストを返す. ただし, nm は係数に分数, 有理式を含まない分散表現多項式, dn は 数または多項式で nm/dn が真の値となる.
• dpolyarray は分散表現多項式を要素とするベクトル, indexlist は正規化計算に用いる dpolyarray の要素のインデックス のリスト.
• fullreduce が 0 でないとき全ての項に対して簡約を行う. fullreduce が 0 のとき頭項のみに対して簡約を行う.
• indexlist で指定された多項式は, 前の方のものが優先的に使われる.
• 一般には indexlist の与え方により函数の値は異なる可能性があるが, グレブナ基底に対しては一意的に定まる.
• 分散表現でない固定された多項式集合による正規形を多数求める必要がある場合 に便利である. 単一の演算に関しては, p_nf, p_true_nf を 用いるとよい.

[0] load("gr")$
[64] load("katsura")$
[69] K=katsura(4)$
[70] dp_ord(2)$
[71] V=[u0,u1,u2,u3,u4]$
[72] DP1=newvect(length(K),map(dp_ptod,K,V))$
[73] G=gr(K,V,2)$
[74] DP2=newvect(length(G),map(dp_ptod,G,V))$
[75] T=dp_ptod((u0-u1+u2-u3+u4)^2,V)$
[76] dp_dtop(dp_nf([0,1,2,3,4],T,DP1,1),V);
u4^2+(6*u3+2*u2+6*u1-2)*u4+9*u3^2+(6*u2+18*u1-6)*u3+u2^2
+(6*u1-2)*u2+9*u1^2-6*u1+1
[77] dp_dtop(dp_nf([4,3,2,1,0],T,DP1,1),V);
-5*u4^2+(-4*u3-4*u2-4*u1)*u4-u3^2-3*u3-u2^2+(2*u1-1)*u2-2*u1^2-3*u1+1
[78] dp_dtop(dp_nf([0,1,2,3,4],T,DP2,1),V);
-11380879768451657780886122972730785203470970010204714556333530492210
456775930005716505560062087150928400876150217079820311439477560587583
488*u4^15+...
[79] dp_dtop(dp_nf([4,3,2,1,0],T,DP2,1),V);
-11380879768451657780886122972730785203470970010204714556333530492210
456775930005716505560062087150928400876150217079820311439477560587583
488*u4^15+...
[80] @78==@79;
1

参照

dp_dtop, dp_ord, dp_mod, dp_rat, p_nf, p_nf_mod, p_true_nf, p_true_nf_mod.

8.10.22 dpm_nf, dpm_nf_and_quotient

dpm_nf([indexlist,]dpoly,dpolyarray,fullreduce)

:: 加群多項式の正規形を求める. (結果は定数倍されている可能性あり)

dpm_nf_and_quotient([indexlist,]dpoly,dpolyarray)

:: 加群多項式の正規形と商を求める.

return

dpm_nf() : 加群多項式, dpm_nf_and_quotient() : リスト

indexlist

リスト

dpoly

加群多項式

dpolyarray

配列

• 加群多項式 dpoly の正規形を求める.
• 結果に有理数, 有理式が含まれるのを避けるため, dpm_nf() は 真の値の定数倍の値を返す.
• dpolyarray は加群多項式を要素とするベクトル, indexlist は正規化計算に用いる dpolyarray の要素のインデックス
• indexlist が与えられている場合, dpolyarray の中で, indexlist で指定されたもののみが, 前の方から優先的に使われる. indexlist が与えられていない場合には, dpolyarray の中の全ての多項式が前の方から優先的に使われる.
• dpm_nf_and_quotient() は, [nm,dn,quo] なる形のリストを返す. ただし, nm は係数に分数を含まない加群多項式, dn は 数または多項式で nm/dn が真の値となる. quo は除算の商を表す配列で, dndpoly=nm+quo[0]dpolyarray[0]+... が成り立つ. のリスト.
• fullreduce が 0 でないとき全ての項に対して簡約を行う. fullreduce が 0 のとき頭項のみに対して簡約を行う.

[2126] dp_ord([1,0])$
[2127] S=ltov([(1)*<<0,0,2,0:1>>+(1)*<<0,0,1,1:1>>+(1)*<<0,0,0,2:1>>
+(-1)*<<3,0,0,0:2>>+(-1)*<<0,0,2,1:2>>+(-1)*<<0,0,1,2:2>>
+(1)*<<3,0,1,0:3>>+(1)*<<3,0,0,1:3>>+(1)*<<0,0,2,2:3>>,
(-1)*<<0,1,0,0:1>>+(-1)*<<0,0,1,0:1>>+(-1)*<<0,0,0,1:1>>
+(-1)*<<3,0,0,0:3>>+(1)*<<0,1,1,1:3>>,(1)*<<0,1,0,0:2>>
+(1)*<<0,0,1,0:2>>+(1)*<<0,0,0,1:2>>+(-1)*<<0,1,1,0:3>>
+(-1)*<<0,1,0,1:3>>+(-1)*<<0,0,1,1:3>>])$
[2128] U=dpm_sp(S[0],S[1]);
(1)*<<0,0,3,0:1>>+(-1)*<<0,1,1,1:1>>+(1)*<<0,0,2,1:1>>
+(-1)*<<0,1,0,2:1>>+(1)*<<3,1,0,0:2>>+(1)*<<0,1,2,1:2>>
+(1)*<<0,1,1,2:2>>+(-1)*<<3,1,1,0:3>>+(1)*<<3,0,2,0:3>>
+(-1)*<<3,1,0,1:3>>+(-1)*<<0,1,3,1:3>>+(-1)*<<0,1,2,2:3>>
[2129] dpm_nf(U,S,1);
0
[2130] L=dpm_nf_and_quotient(U,S)$
[2131] Q=L[2]$
[2132] D=L[1]$
[2133] D*U-(Q[1]*S[1]+Q[2]*S[2]);
0

参照

dpm_sp, dp_ord.

8.10.23 dp_hm, dp_ht, dp_hc, dp_rest

dp_hm(dpoly)

:: 頭単項式を取り出す.

dp_ht(dpoly)

:: 頭項を取り出す.

dp_hc(dpoly)

:: 頭係数を取り出す.

dp_rest(dpoly)

:: 頭単項式を取り除いた残りを返す.

return

dp_hm(), dp_ht(), dp_rest() : 分散表現多項式, dp_hc() : 数または多項式

dpoly

分散表現多項式

• これらは, 分散表現多項式の各部分を取り出すための函数である.
• 分散表現多項式 p に対し次が成り立つ.

  p = dp_hm(p) + dp_rest(p)

  dp_hm(p) = dp_hc(p) dp_ht(p)

[87] dp_ord(0)$
[88] X=ptozp((a46^2+7/10*a46+7/48)*u3^4-50/27*a46^2-35/27*a46-49/216)$
[89] T=dp_ptod(X,[u3,u4,a46])$                                        
[90] dp_hm(T);                                                        
(2160)*<<4,0,2>>
[91] dp_ht(T);
(1)*<<4,0,2>>
[92] dp_hc(T);
2160
[93] dp_rest(T);
(1512)*<<4,0,1>>+(315)*<<4,0,0>>+(-4000)*<<0,0,2>>+(-2800)*<<0,0,1>>
+(-490)*<<0,0,0>>

8.10.24 dpm_hm, dpm_ht, dpm_hc, dpm_hp, dpm_rest

dpm_hm(dpoly)

:: 加群多項式の頭単項式を取り出す.

dpm_ht(dpoly)

:: 加群多項式の頭項を取り出す.

dpm_hc(dpoly)

:: 加群多項式の頭係数を取り出す.

dpm_hp(dpoly)

:: 加群多項式の頭位置を取り出す.

dpm_rest(dpoly)

:: 加群多項式の頭単項式を取り除いた残りを返す.

return

dp_hm(), dp_ht(), dp_rest() : 加群多項式, dp_hc() : 数または多項式

dpoly

加群多項式

• これらは, 加群多項式の各部分を取り出すための函数である.
• dpm_hc() は, dpm_hm() の, 標準基底に関する係数である単項式を返す. スカラー係数を取り出すには, さらに dp_hc() を実行する.
• dpm_hp() は, 頭加群単項式に含まれる標準基底のインデックスを返す.

[2126] dp_ord([1,0]); 
[1,0]
[2127] F=2*<<1,2,0:2>>-3*<<1,0,2:3>>+<<2,1,0:2>>;
(1)*<<2,1,0:2>>+(2)*<<1,2,0:2>>+(-3)*<<1,0,2:3>>
[2128] M=dpm_hm(F);
(1)*<<2,1,0:2>>
[2129] C=dpm_hc(F);
(1)*<<2,1,0>>
[2130] R=dpm_rest(F);
(2)*<<1,2,0:2>>+(-3)*<<1,0,2:3>>
[2131] dpm_hp(F);
2

8.10.25 dp_td, dp_sugar

dp_td(dpoly)

:: 頭項の全次数を返す.

dp_sugar(dpoly)

:: 多項式の sugar を返す.

return

自然数

dpoly

分散表現多項式

onoff

フラグ

• dp_td() は, 頭項の全次数, すなわち各変数の指数の和を返す.
• 分散表現多項式が生成されると, sugar と呼ばれるある整数が付与 される. この値は 仮想的に斉次化して計算した場合に結果が持つ全次数の値となる.
• sugar は, グレブナ基底計算における正規化対の選択のストラテジを 決定するための重要な指針となる.

[74] dp_ord(0)$
[75] X=<<1,2>>+<<0,1>>$
[76] Y=<<1,2>>+<<1,0>>$
[77] Z=X-Y;
(-1)*<<1,0>>+(1)*<<0,1>>
[78] dp_sugar(T);
3

8.10.26 dp_lcm

dp_lcm(dpoly1,dpoly2)

:: 最小公倍項を返す.

return

分散表現多項式

dpoly1 dpoly2

分散表現多項式

• それぞれの引数の頭項の最小公倍項を返す. 係数は 1 である.

[100] dp_lcm(<<1,2,3,4,5>>,<<5,4,3,2,1>>);
(1)*<<5,4,3,4,5>>

参照

p_nf, p_nf_mod, p_true_nf, p_true_nf_mod.

8.10.27 dp_redble

dp_redble(dpoly1,dpoly2)

:: 頭項どうしが整除可能かどうか調べる.

return

整数

dpoly1 dpoly2

分散表現多項式

• dpoly1 の頭項が dpoly2 の頭項で割り切れれば 1, 割り切れなければ 0 を返す.
• 多項式の簡約を行う際, どの項を簡約できるかを探すのに用いる.

[148] C;
(1)*<<1,1,1,0,0>>+(1)*<<0,1,1,1,0>>+(1)*<<1,1,0,0,1>>+(1)*<<1,0,0,1,1>>
[149] T;
(3)*<<2,1,0,0,0>>+(3)*<<1,2,0,0,0>>+(1)*<<0,3,0,0,0>>+(6)*<<1,1,1,0,0>>
[150] for ( ; T; T = dp_rest(T)) print(dp_redble(T,C));
0
0
0
1

参照

dp_red, dp_red_mod.

8.10.28 dpm_redble

dpm_redble(dpoly1,dpoly2)

:: 頭項どうしが整除可能かどうか調べる.

return

整数

dpoly1 dpoly2

加群多項式

• dpoly1 の頭項が dpoly2 の頭項で割り切れれば 1, 割り切れなければ 0 を返す.
• 多項式の簡約を行う際, どの項を簡約できるかを探すのに用いる.

8.10.29 dp_subd

dp_subd(dpoly1,dpoly2)

:: 頭項の商単項式を返す.

return

分散表現多項式

dpoly1 dpoly2

分散表現多項式

• dp_ht(dpoly1)/dp_ht(dpoly2) を求める. 結果の係数は 1 である.
• 割り切れることがあらかじめわかっている必要がある.

[162] dp_subd(<<1,2,3,4,5>>,<<1,1,2,3,4>>);
(1)*<<0,1,1,1,1>>

参照

dp_red, dp_red_mod.

8.10.30 dp_vtoe, dp_etov

dp_vtoe(vect)

:: 指数ベクトルを項に変換

dp_etov(dpoly)

:: 頭項を指数ベクトルに変換

return

dp_vtoe : 分散表現多項式, dp_etov : ベクトル

vect

ベクトル

dpoly

分散表現多項式

• dp_vtoe() は, ベクトル vect を指数ベクトルとする項を生成する.
• dp_etov() は, 分散表現多項式 dpoly の頭項の指数ベクトルを ベクトルに変換する.

[211] X=<<1,2,3>>;
(1)*<<1,2,3>>
[212] V=dp_etov(X);
[ 1 2 3 ]
[213] V[2]++$
[214] Y=dp_vtoe(V);
(1)*<<1,2,4>>

8.10.31 dp_mbase

dp_mbase(dplist)

:: monomial 基底の計算

return

分散表現多項式のリスト

dplist

分散表現多項式のリスト

• ある順序でグレブナ基底となっている多項式集合の, その順序に関する分散表現 である dplist について, dplist が K[X] 中で生成するイデアル I が 0 次元の時, K 上有限次元線形空間である K[X]/I の monomial による基底を求める.
• 得られた基底の個数が, K[X]/I の K-線形空間としての次元に等しい.

[215] K=katsura(5)$
[216] V=[u5,u4,u3,u2,u1,u0]$
[217] G0=gr(K,V,0)$
[218] H=map(dp_ptod,G0,V)$
[219] map(dp_ptod,dp_mbase(H),V)$
[u0^5,u4*u0^3,u3*u0^3,u2*u0^3,u1*u0^3,u0^4,u3^2*u0,u2*u3*u0,u1*u3*u0,
u1*u2*u0,u1^2*u0,u4*u0^2,u3*u0^2,u2*u0^2,u1*u0^2,u0^3,u3^2,u2*u3,u1*u3,
u1*u2,u1^2,u4*u0,u3*u0,u2*u0,u1*u0,u0^2,u4,u3,u2,u1,u0,1]

参照

gr, hgr, gr_mod, dgr.

8.10.32 dp_mag

dp_mag(p)

:: 係数のビット長の和を返す

return

数

p

分散表現多項式

• 分散表現多項式の係数に現れる有理数につき, その分母分子 (整数の場合は分子) のビット長の総和を返す.
• 対象となる多項式の大きさの目安として有効である. 特に, 0 次元システムにおいては 係数膨張が問題となり, 途中生成される多項式が係数膨張を起こしているかどうか の判定に役立つ.
• dp_gr_flags() で, ShowMag, Print を on にすることにより 途中生成される多項式にたいする dp_mag() の値を見ることができる.

[221] X=dp_ptod((x+2*y)^10,[x,y])$
[222] dp_mag(X);
115

参照

dp_gr_flags, dp_gr_print.

8.10.33 dp_red, dp_red_mod

dp_red(dpoly1,dpoly2,dpoly3)

dp_red_mod(dpoly1,dpoly2,dpoly3,mod)

:: 一回の簡約操作

return

リスト

dpoly1 dpoly2 dpoly3

分散表現多項式

vlist

リスト

mod

素数

• dpoly1 + dpoly2 なる分散表現多項式を dpoly3 で 1 回簡約する.
• dp_red_mod() の入力は, 全て有限体係数に変換されている必要がある.
• 簡約される項は dpoly2 の頭項である. 従って, dpoly2 の 頭項が dpoly3 の頭項で割り切れることがあらかじめわかっていなければ ならない.
• 引数が整数係数の時, 簡約は, 分数が現れないよう, 整数 a, b, 項 t により a(dpoly1 + dpoly2)-bt dpoly3 として計算される.
• 結果は, [a dpoly1,a dpoly2 - bt dpoly3] なるリストである.

[157] D=(3)*<<2,1,0,0,0>>+(3)*<<1,2,0,0,0>>+(1)*<<0,3,0,0,0>>;
(3)*<<2,1,0,0,0>>+(3)*<<1,2,0,0,0>>+(1)*<<0,3,0,0,0>>
[158] R=(6)*<<1,1,1,0,0>>;                                    
(6)*<<1,1,1,0,0>>
[159] C=12*<<1,1,1,0,0>>+(1)*<<0,1,1,1,0>>+(1)*<<1,1,0,0,1>>; 
(12)*<<1,1,1,0,0>>+(1)*<<0,1,1,1,0>>+(1)*<<1,1,0,0,1>>
[160] dp_red(D,R,C);                                         
[(6)*<<2,1,0,0,0>>+(6)*<<1,2,0,0,0>>+(2)*<<0,3,0,0,0>>,
(-1)*<<0,1,1,1,0>>+(-1)*<<1,1,0,0,1>>]

参照

dp_mod, dp_rat.

8.10.34 dp_sp, dp_sp_mod

dp_sp(dpoly1,dpoly2)

dp_sp_mod(dpoly1,dpoly2,mod)

:: S-多項式の計算

return

分散表現多項式

dpoly1 dpoly2

分散表現多項式

mod

素数

• dpoly1, dpoly2 の S-多項式を計算する.
• dp_sp_mod() の入力は, 全て有限体係数に変換されている必要がある.
• 結果に有理数, 有理式が入るのを避けるため, 結果が定数倍, あるいは多項式 倍されている可能性がある.

[227] X=dp_ptod(x^2*y+x*y,[x,y]);
(1)*<<2,1>>+(1)*<<1,1>>
[228] Y=dp_ptod(x*y^2+x*y,[x,y]);
(1)*<<1,2>>+(1)*<<1,1>>
[229] dp_sp(X,Y);
(-1)*<<2,1>>+(1)*<<1,2>>

参照

dp_mod, dp_rat.

8.10.35 dpm_sp

dpm_sp(dpoly1,dpoly2[|coef=1])

:: S-多項式の計算

return

加群多項式またはリスト

dpoly1 dpoly2

加群多項式 分散表現多項式

• dpoly1, dpoly2 の S-多項式を計算する.
• オプション coef=1 が指定されている場合, [S,t1,t2] なるリストを返す. ここで, t1, t2 はS-多項式を作る際の係数単項式で S=t1 dpoly1-t2 dpoly2 を満たす.

8.10.36 dpm_schreyer_base

dpm_schreyer_base(G)

:: szygy 加群のグレブナー基底の計算

return

加群多項式リスト

G

加群多項式リスト

• 加群多項式で表された簡約グレブナー基底 G に対し, syz(G) の極小グレブナー基底を計算して返す.
• 得られる結果は, G の先頭項から定まる Schreyer 順序に関するグレブナー基底である. 副作用として, この Schreyer 順序が自動的に設定される.

8.10.37 dpm_schreyer_frame

dpm_schreyer_frame(G)

:: Schreyer フレームの計算

return

加群単項式リストのリスト

G

加群多項式リスト

• G の先頭項からスタートして, Schreyer フレーム, すなわち Schreyer の自由分解に現れるグレブナー基底の, Schreyer 順序に関する先頭単項式を計算する.
• 得られる結果は, 自由分解における F_i の標準基底の像の先頭単項式のリスト M_i のリスト [M_m,...,M_1] である.
• 副作用として, 各レベルにおける Schreyer 順序を設定するためのデータが作られる. このデータは dpm_set_schreyer_level により, 各レベルの Schreyer 順序を設定する際に用いられる.

8.10.38 dpm_set_schreyer_level

dpm_set_schreyer_level(L)

:: 指定されたレベルの Schreyer ordering の設定

return

非負整数

G

非負整数

• G の先頭項からスタートして, Schreyer フレーム, すなわち Schreyer の自由分解に現れるグレブナー基底の, Schreyer 順序に関する先頭単項式を計算する.
• 得られる結果は, 自由分解における F_i の標準基底の像の先頭単項式のリスト M_i のリスト [M_m,...,M_1] である.
• 副作用として, 各レベルにおける Schreyer 順序を設定するためのデータが作られる. このデータは dpm_set_schreyer_level により, 各レベルの Schreyer 順序を設定する際に用いられる.

8.10.39 dpm_sp_nf

dpm_sp_nf(C,Z,P,Q)

:: S-多項式を多項式配列で割った余りの計算

return

加群単項式のリスト

C

加群多項式配列

Z

整数リストの配列

P

Q

整数

• C[P], C[Q] の S-多項式を C で割った余り f が ct C[P]-c’t’C[Q]=g_1C[1]+...+g_LC[L]+f と表されるとき g’=ct e_P-c’t’ e_Q-(g_1 e_1+...+g_L e_L) に対し [g’,f] を返す.
• 配列 Z の第 I 成分は, 先頭項の位置が I であるような C の元の配列インデックスのリストである.

8.10.40 p_nf, p_nf_mod, p_true_nf, p_true_nf_mod

p_nf(poly,plist,vlist,order)

p_nf_mod(poly,plist,vlist,order,mod)

:: 表現多項式の正規形を求める. (結果は定数倍されている可能性あり)

p_true_nf(poly,plist,vlist,order)

p_true_nf_mod(poly,plist,vlist,order,mod)

:: 表現多項式の正規形を求める. (真の結果を [分子, 分母] の形で返す)

return

p_nf : 多項式, p_true_nf : リスト

poly

多項式

plist vlist

リスト

order

数, リストまたは行列

mod

素数

• ‘gr’ で定義されている.
• 多項式の, 多項式リストによる正規形を求める.
• dp_nf(), dp_true_nf(), dp_nf_mod(), dp_true_nf_mod に対するインタフェースである.
• poly および plist は, 変数順序 vlist および 変数順序型 otype に従って分散表現多項式に変換され, dp_nf(), dp_true_nf(), dp_nf_mod(), dp_true_nf_mod() に渡される.
• dp_nf(), dp_true_nf(), dp_nf_mod(), dp_true_nf_mod() は fullreduce が 1 で呼び出される.
• 結果は多項式に変換されて出力される.
• p_true_nf(), p_true_nf_mod() の出力に関しては, dp_true_nf(), dp_true_nf_mod() の項を参照.

[79] K = katsura(5)$
[80] V = [u5,u4,u3,u2,u1,u0]$
[81] G = hgr(K,V,2)$
[82] p_nf(K[1],G,V,2);
0
[83] L = p_true_nf(K[1]+1,G,V,2);
[-1503...,-1503...]
[84] L[0]/L[1];
1

参照

dp_ptod, dp_dtop, dp_ord, dp_nf, dp_nf_mod, dp_true_nf, dp_true_nf_mod.

8.10.41 p_terms

p_terms(poly,vlist,order)

:: 多項式にあらわれる単項をリストにする.

return

リスト

poly

多項式

vlist

リスト

order

数, リストまたは行列

• ‘gr’ で定義されている.
• 多項式を単項に展開した時に現れる項をリストにして返す. vlist および order により定まる項順序により, 順序の高いもの がリストの先頭に来るようにソートされる.
• グレブナ基底はしばしば係数が巨大になるため, 実際にどの項が現れて いるのかを見るためなどに用いる.

[233] G=gr(katsura(5),[u5,u4,u3,u2,u1,u0],2)$
[234] p_terms(G[0],[u5,u4,u3,u2,u1,u0],2);
[u5,u0^31,u0^30,u0^29,u0^28,u0^27,u0^26,u0^25,u0^24,u0^23,u0^22,
u0^21,u0^20,u0^19,u0^18,u0^17,u0^16,u0^15,u0^14,u0^13,u0^12,u0^11,
u0^10,u0^9,u0^8,u0^7,u0^6,u0^5,u0^4,u0^3,u0^2,u0,1]

8.10.42 gb_comp

gb_comp(plist1, plist2)

:: 多項式リストが, 符号を除いて集合として等しいかどうか調べる.

return 0 または 1

plist1 plist2

• plist1, plist2 について, 符号を除いて集合として等しいかどうか 調べる.
• 異なる方法で求めたグレブナ基底は, 基底の順序, 符号が異なる場合があり, それらが等しいかどうかを調べるために用いる.

[243] C=cyclic(6)$
[244] V=[c0,c1,c2,c3,c4,c5]$
[245] G0=gr(C,V,0)$
[246] G=tolex(G0,V,0,V)$
[247] GG=lex_tl(C,V,0,V,0)$
[248] gb_comp(G,GG);
1

8.10.43 katsura, hkatsura, cyclic, hcyclic

katsura(n)

hkatsura(n)

cyclic(n)

hcyclic(n)

:: 多項式リストの生成

return

リスト

n

整数

• katsura() は ‘katsura’, cyclic() は ‘cyclic’ で定義されている.
• グレブナ基底計算でしばしばテスト, ベンチマークに用いられる katsura, cyclic およびその斉次化を生成する.
• cyclic は Arnborg, Lazard, Davenport などの 名で呼ばれることもある.

[74] load("katsura")$
[79] load("cyclic")$ 
[89] katsura(5);
[u0+2*u4+2*u3+2*u2+2*u1+2*u5-1,2*u4*u0-u4+2*u1*u3+u2^2+2*u5*u1,
2*u3*u0+2*u1*u4-u3+(2*u1+2*u5)*u2,2*u2*u0+2*u2*u4+(2*u1+2*u5)*u3
-u2+u1^2,2*u1*u0+(2*u3+2*u5)*u4+2*u2*u3+2*u1*u2-u1,
u0^2-u0+2*u4^2+2*u3^2+2*u2^2+2*u1^2+2*u5^2]
[90] hkatsura(5);
[-t+u0+2*u4+2*u3+2*u2+2*u1+2*u5,
-u4*t+2*u4*u0+2*u1*u3+u2^2+2*u5*u1,-u3*t+2*u3*u0+2*u1*u4+(2*u1+2*u5)*u2,
-u2*t+2*u2*u0+2*u2*u4+(2*u1+2*u5)*u3+u1^2,
-u1*t+2*u1*u0+(2*u3+2*u5)*u4+2*u2*u3+2*u1*u2,
-u0*t+u0^2+2*u4^2+2*u3^2+2*u2^2+2*u1^2+2*u5^2]
[91] cyclic(6);
[c5*c4*c3*c2*c1*c0-1,
((((c4+c5)*c3+c5*c4)*c2+c5*c4*c3)*c1+c5*c4*c3*c2)*c0+c5*c4*c3*c2*c1,
(((c3+c5)*c2+c5*c4)*c1+c5*c4*c3)*c0+c4*c3*c2*c1+c5*c4*c3*c2,
((c2+c5)*c1+c5*c4)*c0+c3*c2*c1+c4*c3*c2+c5*c4*c3,
(c1+c5)*c0+c2*c1+c3*c2+c4*c3+c5*c4,c0+c1+c2+c3+c4+c5]
[92] hcyclic(6);
[-c^6+c5*c4*c3*c2*c1*c0,
((((c4+c5)*c3+c5*c4)*c2+c5*c4*c3)*c1+c5*c4*c3*c2)*c0+c5*c4*c3*c2*c1,
(((c3+c5)*c2+c5*c4)*c1+c5*c4*c3)*c0+c4*c3*c2*c1+c5*c4*c3*c2,
((c2+c5)*c1+c5*c4)*c0+c3*c2*c1+c4*c3*c2+c5*c4*c3,
(c1+c5)*c0+c2*c1+c3*c2+c4*c3+c5*c4,c0+c1+c2+c3+c4+c5]

参照

dp_dtop.

8.10.44 primadec, primedec

primadec(plist,vlist)

primedec(plist,vlist)

:: イデアルの分解

return

plist

多項式リスト

vlist

変数リスト

• ここで解説されているイデアル分解については, 新しいパッケージ ‘noro_pd.rr’ においてより高速な実装が利用できる.
• primadec(), primedec は ‘primdec’ で定義されている.
• primadec(), primedec() はそれぞれ有理数体上でのイデアルの 準素分解, 根基の素イデアル分解を行う.
• 引数は多項式リストおよび変数リストである. 多項式は有理数係数のみが許される.
• primadec は [準素成分, 付属素イデアル] のリストを返す.
• primadec は 素因子のリストを返す.
• 結果において, 多項式リストとして表示されている各イデアルは全て グレブナ基底である. 対応する項順序は, それぞれ 変数 PRIMAORD, PRIMEORD に格納されている.
• primadec は [Shimoyama,Yokoyama] の準素分解アルゴリズム を実装している.
• もし素因子のみを求めたいなら, primedec を使う方がよい. これは, 入力イデアルが根基イデアルでない場合に, primadec の計算に余分なコストが必要となる場合があるからである.

[84] load("primdec")$
[102] primedec([p*q*x-q^2*y^2+q^2*y,-p^2*x^2+p^2*x+p*q*y,
(q^3*y^4-2*q^3*y^3+q^3*y^2)*x-q^3*y^4+q^3*y^3,
-q^3*y^4+2*q^3*y^3+(-q^3+p*q^2)*y^2],[p,q,x,y]);
[[y,x],[y,p],[x,q],[q,p],[x-1,q],[y-1,p],[(y-1)*x-y,q*y^2-2*q*y-p+q]]
[103] primadec([x,z*y,w*y^2,w^2*y-z^3,y^3],[x,y,z,w]);
[[[x,z*y,y^2,w^2*y-z^3],[z,y,x]],[[w,x,z*y,z^3,y^3],[w,z,y,x]]]

参照

fctr, sqfr, 項順序の設定.

8.10.45 primedec_mod

primedec_mod(plist,vlist,ord,mod,strategy)

:: イデアルの分解

return

plist

多項式リスト

vlist

変数リスト

ord

数, リストまたは行列

mod

正整数

strategy

整数

• primedec_mod() は ‘primdec_mod’ で定義されている. [Yokoyama] の素イデアル分解アルゴリズム を実装している.
• primedec_mod() は有限体上でのイデアルの 根基の素イデアル分解を行い, 素イデアルのリストを返す.
• primedec_mod() は, GF(mod) 上での分解を与える. 結果の各成分の生成元は, 整数係数多項式である.
• 結果において, 多項式リストとして表示されている各イデアルは全て [vlist,ord] で指定される項順序に関するグレブナ基底である.
• strategy が 0 でないとき, incremental に component の共通 部分を計算することによる early termination を行う. 一般に, イデアルの次元が高い場合に有効だが, 0 次元の場合など, 次元が小さい 場合には overhead が大きい場合がある.
• 計算途中で内部情報を見たい場合には、 前もって dp_gr_print(2) を実行しておけばよい.

[0] load("primdec_mod")$
[246] PP444=[x^8+x^2+t,y^8+y^2+t,z^8+z^2+t]$
[247] primedec_mod(PP444,[x,y,z,t],0,2,1);
[[y+z,x+z,z^8+z^2+t],[x+y,y^2+y+z^2+z+1,z^8+z^2+t],
[y+z+1,x+z+1,z^8+z^2+t],[x+z,y^2+y+z^2+z+1,z^8+z^2+t],
[y+z,x^2+x+z^2+z+1,z^8+z^2+t],[y+z+1,x^2+x+z^2+z+1,z^8+z^2+t],
[x+z+1,y^2+y+z^2+z+1,z^8+z^2+t],[y+z+1,x+z,z^8+z^2+t],
[x+y+1,y^2+y+z^2+z+1,z^8+z^2+t],[y+z,x+z+1,z^8+z^2+t]]
[248] 

参照

modfctr, dp_gr_main, dp_gr_mod_main, dp_gr_f_main, dp_weyl_gr_main, dp_weyl_gr_mod_main, dp_weyl_gr_f_main, 項順序の設定. dp_gr_flags, dp_gr_print.

8.10.46 bfunction, bfct, generic_bfct, ann, ann0

bfunction(f)

bfct(f)

generic_bfct(plist,vlist,dvlist,weight)

:: b 関数の計算

ann(f)

ann0(f)

:: 多項式のベキの annihilator の計算

return

多項式またはリスト

f

多項式

plist

多項式リスト

vlist dvlist

変数リスト

• ‘bfct’ で定義されている.
• bfunction(f), bfct(f) は多項式 f の global b 関数 b(s) を 計算する. b(s) は, Weyl 代数 D 上の一変数多項式環 D[s] の元 P(x,s) が存在して, P(x,s)f^(s+1)=b(s)f^s を満たすような 多項式 b(s) の中で, 次数が最も低いものである.
• generic_bfct(f,vlist,dvlist,weight) は, plist で生成される D の左イデアル I の, ウェイト weight に関する global b 関数を計算する. vlist は x-変数, vlist は対応する D-変数 を順に並べる.
• bfunction と bfct では用いているアルゴリズムが 異なる. どちらが高速かは入力による.
• ann(f) は, f^s の annihilator ideal の生成系を返す. ann(f) は, [a,list] なるリストを返す. ここで, a は f の b 関数の最小整数根, list は ann(f) の結果の s$ に, a を 代入したものである.
• 詳細については, [Saito,Sturmfels,Takayama] を見よ.

[0] load("bfct")$
[216] bfunction(x^3+y^3+z^3+x^2*y^2*z^2+x*y*z);
-9*s^5-63*s^4-173*s^3-233*s^2-154*s-40
[217] fctr(@);
[[-1,1],[s+2,1],[3*s+4,1],[3*s+5,1],[s+1,2]]
[218] F = [4*x^3*dt+y*z*dt+dx,x*z*dt+4*y^3*dt+dy,
x*y*dt+5*z^4*dt+dz,-x^4-z*y*x-y^4-z^5+t]$
[219] generic_bfct(F,[t,z,y,x],[dt,dz,dy,dx],[1,0,0,0]);
20000*s^10-70000*s^9+101750*s^8-79375*s^7+35768*s^6-9277*s^5
+1278*s^4-72*s^3
[220] P=x^3-y^2$
[221] ann(P);
[2*dy*x+3*dx*y^2,-3*dx*x-2*dy*y+6*s]
[222] ann0(P);
[-1,[2*dy*x+3*dx*y^2,-3*dx*x-2*dy*y-6]]

参照

Weyl 代数.

この文書は4月 18, 2024にtexi2html 5.0を用いて生成されました。