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

参照

section dp_gr_main, dp_gr_mod_main, section dp_ord, section 分散計算

Go to the first, previous, next, last section, table of contents.