グレブナ基底の計算
*********

分散表現多項式
=======

分散表現多項式とは, 多項式の内部形式の一つである. 通常の多項式 (type が 2) は, 再帰表現と呼ばれる形式で表現されている. すなわち, 特定の変数を主変数とする 1 変数多項式で, その他の変数は, その 1 変数多項式の係数に, 主変数を含まない多項式として現れる. この係数が, また, ある変数を主変数とする多項式となっていることから再帰表現と呼ばれる.

     (x+y+z)^2 = 1 x^2 + (2 y + (2 z)) x + ((2 z) y + (1 z^2 ))

これに対し, 多項式を, 変数の冪積と係数の積の和として表現したものを分散表現と呼ぶ.

     (x+y+z)^2 = 1 x^2 + 2 xy + 2 xz + 1 y^2 + 2 yz +1 z^2$

グレブナ基底計算においては, 単項式に注目して操作を行うため多項式が分散表現されている方がより効率のよい演算が可能になる. このため, 分散表現多項式が, 識別子 9 の型として Asir のトップレベルから利用可能となっている. ここで, 後の説明のために, いくつかの言葉を定義しておく.

項 (term)
     変数の冪積. すなわち, 係数 1 の単項式のこと. Asir においては,

          <<0,1,2,3,4>>

     という形で表示され, また, この形で入力可能である. この例は, 5 変数の項を示す. 各変数を a, b, c, d, e とするとこの項は b*c^2*d^3*e^4 を表す.

項順序 (term order)
     分散表現多項式における項は, 次の性質を満たす全順序により整列される.

      1. 任意の項 t に対し t > 1

      2. t, s, u を項とする時, t > s ならば tu > su

     この性質を満たす全順序を項順序と呼ぶ. この順序は変数順序 (変数のリスト) と項順序型 (数, リストまたは行列) により指定される.

単項式 (monomial)
     項と係数の積.

          2*<<0,1,2,3,4>>

     という形で表示され, また, この形で入力可能である.

頭単項式 (head monomial)

頭項 (head term)
頭係数 (head coefficient)
     分散表現多項式における各単項式は, 項順序により整列される. この時順序最大の単項式を頭単項式, それに現れる項, 係数をそれぞれ頭項, 頭係数と呼ぶ.

ファイルの読み込み
=========

グレブナ基底を計算するための基本的な函数は dp_gr_main() および dp_gr_mod_main() なる 2 つの組み込み函数であるが, 通常は, パラメタ設定などを行ったのちこれらを呼び出すユーザ函数を用いるのが便利である. これらのユーザ函数は, ファイル gr を load() により読み込むことにより使用可能となる. gr は, Asir の標準ライブラリディレクトリに置かれている. よって, 環境変数 ASIR_LIBDIR を特に異なるパスに設定しない限り, ファイル名のみで読み込むことができる.

     [0] load("gr")$

基本的な函数
======

gr では数多くの函数が定義されているが, 直接グレブナ基底を計算するためのトップレベルは次の 3 つである. 以下で, PLIST は多項式のリスト, VLIST は変数 (不定元) のリスト, ORDER は変数順序型, P は 2^27 未満の素数である.

gr(PLIST,VLIST,ORDER)

     Gebauer-Moeller による useless pair elimination criteria, sugar strategy および Traverso による trace-lifting を用いた Buchberger アルゴリズムによる有理数係数グレブナ基底計算函数. 一般にはこの函数を用いる.

hgr(PLIST,VLIST,ORDER)

     入力多項式を斉次化した後 gr() のグレブナ基底候補生成部により候補生成し, 非斉次化, interreduce したものを gr() のグレブナ基底チェック部でチェックする. 0 次元システム (解の個数が有限個の方程式系) の場合, sugar strategy が係数膨張を引き起こす場合がある. このような場合, strategy を斉次化による strategy に置き換えることにより係数膨張を抑制することができる場合が多い.

gr_mod(PLIST,VLIST,ORDER,P)

     Gebauer-Moeller による useless pair elimination criteria, sugar strategy および Buchberger アルゴリズムによる GF(p) 係数グレブナ基底計算函数.

計算および表示の制御
==========

グレブナ基底の計算において, さまざまなパラメタ設定を行うことにより計算, 表示を制御することができる. これらは, 組み込み函数 dp_gr_flags() により設定参照することができる. 無引数で dp_gr_flags() を実行すると, 現在設定されているパラメタが, 名前と値のリストで返される.

     [100] dp_gr_flags();
     [Demand,0,NoSugar,0,NoCriB,0,NoGC,0,NoMC,0,NoRA,0,NoGCD,0,Top,0,ShowMag,1,
     Print,1,Stat,0,Reverse,0,InterReduce,0,Multiple,0]
     [101]

以下で, 各パラメタの意味を説明する. on の場合とは, パラメタが 0 でない場合をいう. これらのパラメタの初期値は全て 0 (off) である.

NoSugar
     on の場合, sugar strategy の代わりに Buchbergerの normal strategy が用いられる.

NoCriB
     on の場合, 不必要対検出規準のうち, 規準 B を適用しない.

NoGC
     on の場合, 結果がグレブナ基底になっているかどうかのチェックを行わない.

NoMC
     on の場合, 結果が入力イデアルと同等のイデアルであるかどうかのチェックを行わない.

NoRA
     on の場合, 結果を reduced グレブナ基底にするための interreduce を行わない.

NoGCD
     on の場合, 有理式係数のグレブナ基底計算において, 生成された多項式の, 係数の content をとらない.

Top
     on の場合, normal form 計算において頭項消去のみを行う.

Interreduce
     on の場合, 多項式を生成する毎に, それまで生成された基底をその多項式による normal form で置き換える.

Reverse
     on の場合, normal form 計算の際の reducer を, 新しく生成されたものを優先して選ぶ.

Print
     on の場合, グレブナ基底計算の途中におけるさまざまな情報を表示する.

Stat
     on で Print が off ならば, Print が on のとき表示されるデータの内, 集計データのみが表示される.

ShowMag
     on で Print が on ならば, 生成が生成される毎に, その多項式の係数のビット長の和を表示し, 最後に, それらの和の最大値を表示する.

Multiple
     0 でない整数の時, 有理数上の正規形計算において, 係数のビット長の和が Multiple 倍になるごとに係数全体の GCD が計算され, その GCD で割った多項式を簡約する. Multiple が 1 ならば, 簡約するごとに GCD 計算が行われ一般には効率が悪くなるが, Multiple を 2 程度とすると, 巨大な整数が係数に現れる場合, 効率が良くなる場合がある.

Demand
     正当なディレクトリ名 (文字列) を値に持つとき, 生成された多項式はメモリ中におかれず, そのディレクトリ中にバイナリデータとして置かれ, その多項式を用いる normal form 計算の際, 自動的にメモリ中にロードされる. 各多項式は, 内部でのインデックスをファイル名に持つファイルに格納される. ここで指定されたディレクトリに書かれたファイルは自動的には消去されないため, ユーザが責任を持って消去する必要がある.

Print が 0 でない場合次のようなデータが表示される.

     [93] gr(cyclic(4),[c0,c1,c2,c3],0)$
     mod= 99999989, eval = []
     (0)(0)<<0,2,0,0>>(2,3),nb=2,nab=5,rp=2,sugar=2,mag=4
     (0)(0)<<0,1,2,0>>(1,2),nb=3,nab=6,rp=2,sugar=3,mag=4
     (0)(0)<<0,1,1,2>>(0,1),nb=4,nab=7,rp=3,sugar=4,mag=6
     .
     (0)(0)<<0,0,3,2>>(5,6),nb=5,nab=8,rp=2,sugar=5,mag=4
     (0)(0)<<0,1,0,4>>(4,6),nb=6,nab=9,rp=3,sugar=5,mag=4
     (0)(0)<<0,0,2,4>>(6,8),nb=7,nab=10,rp=4,sugar=6,mag=6
     ....gb done
     reduceall
     .......
     membercheck
     (0,0)(0,0)(0,0)(0,0)
     gbcheck total 8 pairs
     ........
     UP=(0,0)SP=(0,0)SPM=(0,0)NF=(0,0)NFM=(0.010002,0)ZNFM=(0.010002,0)PZ=(0,0)
     NP=(0,0)MP=(0,0)RA=(0,0)MC=(0,0)GC=(0,0)T=40,B=0 M=8 F=6 D=12 ZR=5 NZR=6
     Max_mag=6
     [94]

最初に表示される mod, eval は, trace-lifting で用いられる法である. mod は素数, eval は有理式係数の場合に用いられる数のリストである.

計算途中で多項式が生成される毎に次の形のデータが表示される.

     (TNF)(TCONT)HT(INDEX),nb=NB,nab=NAB,rp=RP,sugar=S,mag=M

それらの意味は次の通り.

TNF
     normal form 計算時間 (秒)

TCONT
     content 計算時間 (秒)

HT
     生成された多項式の頭項

INDEX
     S-多項式を構成する多項式のインデックスのペア

NB
     現在の, 冗長性を除いた基底の数

NAB
     現在までに生成された基底の数

RP
     残りのペアの数

S
     生成された多項式の sugar の値

M
     生成された多項式の係数のビット長の和 (ShowMag が on の時に表示される. )

最後に, 集計データが表示される. 意味は次の通り. (時間の表示において, 数字が 2 つあるものは, 計算時間と GC 時間のペアである.)

UP
     ペアのリストの操作にかかった時間

SP
     有理数上の S-多項式計算時間

SPM
     有限体上の S-多項式計算時間

NF
     有理数上の normal form 計算時間

NFM
     有限体上の normal form 計算時間

ZNFM
     NFM の内, 0 への reduction にかかった時間

PZ
     content 計算時間

NP
     有理数係数多項式の係数に対する剰余演算の計算時間

MP
     S-多項式を生成するペアの選択にかかった時間

RA
     interreduce 計算時間

MC
     trace-lifting における, 入力多項式のメンバシップ計算時間

GC
     結果のグレブナ基底候補のグレブナ基底チェック時間

T
     生成されたペアの数

B, M, F, D
     各 criterion により除かれたペアの数

ZR
     0 に reduce されたペアの数

NZR
     0 でない多項式に reduce されたペアの数

Max_mag
     生成された多項式の, 係数のビット長の和の最大値

項順序の設定
======

項は内部では, 各変数に関する指数を成分とする整数ベクトルとして表現される. 多項式を分散表現多項式に変換する際, 各変数がどの成分に対応するかを指定するのが, 変数リストである. さらに, それら整数ベクトルの全順序を指定するのが項順序の型である. 項順序型は, 数, 数のリストあるいは行列で表現される.

基本的な項順序型として次の 3 つがある.

0 (DegRevLex; 全次数逆辞書式順序)

     一般に, この順序によるグレブナ基底計算が最も高速である. ただし, 方程式を解くという目的に用いることは, 一般にはできない. この順序によるグレブナ基底は, 解の個数の計算, イデアルのメンバシップや, 他の変数順序への基底変換のためのソースとして用いられる.

1 (DegLex; 全次数辞書式順序)

     この順序も, 辞書式順序に比べて高速にグレブナ基底を求めることができるが, DegRevLex と同様直接その結果を用いることは困難である. しかし, 辞書式順序のグレブナ基底を求める際に, 斉次化後にこの順序でグレブナ基底を求めている.

2 (Lex; 辞書式順序)

     この順序によるグレブナ基底は, 方程式を解く場合に最適の形の基底を与えるが計算時間がかかり過ぎるのが難点である. 特に, 解が有限個の場合, 結果の係数が極めて長大な多倍長数になる場合が多い. この場合, gr(), hgr() による計算が極めて有効になる場合が多い.

これらを組み合わせてリストで指定することにより, 様々な消去順序が指定できる. これは,

[[O1,L1],[O2,L2],...]

で指定される. Oi は 0, 1, 2 のいずれかで, Li は変数の個数を表す. この指定は, 変数を先頭から L1, L2 , ...個ずつの組に分け, それぞれの変数に関し, 順に O1, O2, ...の項順序型で大小が決定するまで比較することを意味する. この型の順序は一般に消去順序と呼ばれる.

さらに, 行列により項順序を指定することができる. 一般に, n 行 m 列の実数行列 M が次の性質を持つとする.

 1. 長さ m の整数ベクトル v に対し Mv=0 と v=0 は同値.

 2. 非負成分を持つ長さ m の 0 でない整数ベクトル v に対し, Mv の 0 でない最初の成分は非負.

この時, 2 つのベクトル t, s に対し, t>s を, M(t-s) の 0 でない最初の成分が非負, で定義することにより項順序が定義できる.

項順序型は, gr() などの引数として指定される他, 組み込み函数 dp_ord() で指定され, さまざまな函数の実行の際に参照される.

これらの順序の具体的な定義およびグレブナ基底に関する更に詳しい解説は [Becker,Weispfenning] などを参照のこと.

項順序型の設定の他に, 変数の順序自体も計算時間に大きな影響を与える.

     [90] B=[x^10-t,x^8-z,x^31-x^6-x-y]$
     [91] gr(B,[x,y,z,t],2);
     [x^2-2*y^7+(-41*t^2-13*t-1)*y^2+(2*t^17-12*t^14+42*t^12+30*t^11-168*t^9
     -40*t^8+70*t^7+252*t^6+30*t^5-140*t^4-168*t^3+2*t^2-12*t+16)*z^2*y
     +(-12*t^16+72*t^13-28*t^11-180*t^10+112*t^8+240*t^7+28*t^6-127*t^5
     -167*t^4-55*t^3+30*t^2+58*t-15)*z^4,
     (y+t^2*z^2)*x+y^7+(20*t^2+6*t+1)*y^2+(-t^17+6*t^14-21*t^12-15*t^11+84*t^9
     +20*t^8-35*t^7-126*t^6-15*t^5+70*t^4+84*t^3-t^2+5*t-9)*z^2*y+(6*t^16-36*t^13
     +14*t^11+90*t^10-56*t^8-120*t^7-14*t^6+64*t^5+84*t^4+27*t^3-16*t^2-30*t+7)*z^4,
     (t^3-1)*x-y^6+(-6*t^13+24*t^10-20*t^8-36*t^7+40*t^5+24*t^4-6*t^3-20*t^2-6*t-1)*y
     +(t^17-6*t^14+9*t^12+15*t^11-36*t^9-20*t^8-5*t^7+54*t^6+15*t^5+10*t^4-36*t^3
     -11*t^2-5*t+9)*z^2,
     -y^8-8*t*y^3+16*z^2*y^2+(-8*t^16+48*t^13-56*t^11-120*t^10+224*t^8+160*t^7
     -56*t^6-336*t^5-112*t^4+112*t^3+224*t^2+24*t-56)*z^4*y+(t^24-8*t^21+20*t^19
     +28*t^18-120*t^16-56*t^15+14*t^14+300*t^13+70*t^12-56*t^11-400*t^10-84*t^9
     +84*t^8+268*t^7+84*t^6-56*t^5-63*t^4-36*t^3+46*t^2-12*t+1)*z,
     2*t*y^5+z*y^2+(-2*t^11+8*t^8-20*t^6-12*t^5+40*t^3+8*t^2-10*t-20)*z^3*y+8*t^14
     -32*t^11+48*t^8-t^7-32*t^5-6*t^4+9*t^2-t,
     -z*y^3+(t^7-2*t^4+3*t^2+t)*y+(-2*t^6+4*t^3+2*t-2)*z^2,
     2*t^2*y^3+z^2*y^2+(-2*t^5+4*t^2-6)*z^4*y+(4*t^8-t^7-8*t^5+2*t^4-4*t^3+5*t^2-t)*z,
     z^3*y^2+2*t^3*y+(-t^7+2*t^4+t^2-t)*z^2,
     -t*z*y^2-2*z^3*y+t^8-2*t^5-t^3+t^2,
     -t^3*y^2-2*t^2*z^2*y+(t^6-2*t^3-t+1)*z^4,
     z^5-t^4]
     [93] gr(B,[t,z,y,x],2);
     [x^10-t,x^8-z,x^31-x^6-x-y]

変数順序 [x,y,z,t] におけるグレブナ基底は, 基底の数も多く, それぞれの式も大きい. しかし, 順序 [t,z,y,x] にもとでは, B がすでにグレブナ基底となっている. 大雑把にいえば, 辞書式順序でグレブナ基底を求めることは, 左側の (順序の高い) 変数を, 右側の (順序の低い) 変数で書き表すことであり, この例の場合は, t,  z, y が既に x で表されていることからこのような極端な結果となったわけである. 実際に現れる計算においては, このように選ぶべき変数順序が明らかであることは少なく, 試行錯誤が必要な場合もある.

有理式を係数とするグレブナ基底計算
=================

gr() などのトップレベル函数は, いずれも, 入力多項式リストに現れる変数 (不定元) と, 変数リストに現れる変数を比較して, 変数リストにない変数が入力多項式に現れている場合には, 自動的に, その変数を, 係数体の元として扱う.

     [64] gr([a*x+b*y-c,d*x+e*y-f],[x,y],2);
     [(-e*a+d*b)*x-f*b+e*c,(-e*a+d*b)*y+f*a-d*c]

この例では, a, b, c, d が係数体の元として扱われる. すなわち, 有理函数体 F = Q(a,b,c,d) 上の 2 変数多項式環 F[x,y] におけるグレブナ基底を求めることになる. 注意すべきことは, 係数が体として扱われていることである. すなわち, 係数の間に多項式としての共通因子があった場合には, 結果からその因子は除かれているため, 有理数体上の多項式環上の問題として考えた場合の結果とは一般には異なる. また, 主として計算効率上の問題のため, 分散表現多項式の係数として実際に許されるのは多項式までである. すなわち, 分母を持つ有理式は分散表現多項式の係数としては許されない.

基底変換
====

辞書式順序のグレブナ基底を求める場合, 直接 gr() などを起動するより, 一旦他の順序 (例えば全次数逆辞書式順序) のグレブナ基底を計算して, それを入力として辞書式順序のグレブナ基底を計算する方が効率がよい場合がある. また, 入力が何らかの順序でのグレブナ基底になっている場合, 基底変換と呼ばれる方法により, Buchberger アルゴリズムによらずに効率良く辞書式順序のグレブナ基底が計算できる場合がある. このような目的のための函数が, ユーザ定義函数として gr にいくつか定義されている. 以下の 2 つの函数は, 変数順序 VLIST1, 項順序型 ORDER で既にグレブナ基底となっている多項式リスト GBASE を, 変数順序 VLIST2 における辞書式順序のグレブナ基底に変換する函数である.

tolex(GBASE,VLIST1,ORDER,VLIST2)

     この函数は, GBASE が有理数体上のシステムの場合にのみ使用可能である. この函数は, 辞書式順序のグレブナ基底を, 有限体上で計算されたグレブナ基底を雛型として, 未定係数法および Hensel 構成により求めるものである.

tolex_tl(GBASE,VLIST1,ORDER,VLIST2,HOMO)

     この函数は, 辞書式順序のグレブナ基底を Buchberger アルゴリズムにより求めるものであるが, 入力がある順序におけるグレブナ基底である場合の trace-liftingにおけるグレブナ基底候補の頭項, 頭係数の性質を利用して, 最終的なグレブナ基底チェック, イデアルメンバシップチェックを省略しているため, 単にBuchberger アルゴリズムを繰り返すより効率よく計算できる. 更に, 入力が 0 次元システムの場合, 自動的にもう 1 つの中間的な項順序を経由して辞書式順序のグレブナ基底を計算する. 多くの場合, この方法は, 直接辞書式順序の計算を行うより効率がよい. (もちろん例外あり. ) 引数 HOMO が 0 でない時, hgr() と同様に斉次化を経由して計算を行う.

その他, 0 次元システムに対し, 与えられた多項式の最小多項式を求める函数, 0 次元システムの解を, よりコンパクトに表現するための函数などが gr で定義されている. これらについては個々の函数の説明を参照のこと.

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

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 で定義されている.

  * いずれも, 多項式リスト PLIST の, 変数順序 VLIST, 項順序型 ORDER に関するグレブナ基底を求める. gr(), hgr() は 有理数係数, gr_mod() は GF(P) 係数として計算する.

  * VLIST は不定元のリスト. VLIST に現れない不定元は, 係数体に属すると見なされる.

  * gr(), trace-lifting (モジュラ演算を用いた高速化) および sugar strategy による計算, hgr() は trace-lifting および斉次化による 矯正された sugar strategy による計算を行う.

  * dgr() は, gr(), dgr() を子プロセスリスト PROCS の 2 つのプロセスにより同時に計算させ, 先に結果を返した方の結果を返す. 結果は同一であるが, どちらの方法が高速か一般には不明のため, 実際の経過時間を短縮するのに有効である.

  * dgr() で表示される時間は, この函数が実行されているプロセスでの CPU 時間であり, この函数の場合はほとんど通信のための時間である.

     [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_ord.

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_ord, 分散計算

lex_hensel_gsl, tolex_gsl, tolex_gsl_d
--------------------------------------

lex_hensel_gsl(PLIST,VLIST1,ORDER,VLIST2,HOMO)
     :: GSL 形式のイデアル基底の計算

tolex_gsl(PLIST,VLIST1,ORDER,VLIST2,HOMO)
tolex_gsl_d(PLIST,VLIST1,ORDER,VLIST2,HOMO,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 は, 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, 分散計算

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.

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.

dp_gr_main, dp_gr_mod_main
--------------------------

dp_gr_main(PLIST,VLIST,HOMO,MODULAR,ORDER)
dp_gr_mod_main(PLIST,VLIST,HOMO,MODULAR,ORDER)
     :: グレブナ基底の計算 (組み込み函数)

return
     リスト

plist, vlist
     リスト

order
     数, リストまたは行列

homo
     フラグ

modular
     フラグまたは素数

  * これらの函数は, グレブナ基底計算の基本的組み込み函数であり, gr(), hgr(), gr_mod() などはすべてこれらの函数を呼び出して計算を行っている.

  * フラグ 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, 計算および表示の制御.

dp_f4_main, dp_f4_mod_main
--------------------------

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

return
     リスト

plist, vlist
     リスト

order
     数, リストまたは行列

  * F4 アルゴリズムによりグレブナ基底の計算を行う.

  * F4 アルゴリズムは, J.C. Faugere により提唱された新世代グレブナ基底算法であり, 本実装は, 中国剰余定理による線形方程式求解を用いた試験的な実装である.

  * 引数および動作はそれぞれ dp_gr_main(), dp_gr_mod_main() と同様である.

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

dp_gr_flags, dp_gr_print
------------------------

dp_gr_flags([LIST])
dp_gr_print([0|1])
     :: 計算および表示用パラメタの設定, 参照

return
     設定値

list
     リスト

  * dp_gr_main(), dp_gr_mod_main() 実行時におけるさまざまなパラメタを設定, 参照する.

  * 引数がない場合, 現在の設定が返される.

  * 引数は, ["Print",1,"NoSugar",1,...] なる形のリストで, 左から順に設定される. パラメタ名は文字列で与える必要がある.

  * dp_gr_print() は, 特にパラメタ Print の値を直接設定, 参照できる. これは, dp_gr_main() などをサブルーチンとして用いるユーザ函数において, Print の値を見て, そのサブルーチンが中間情報の表示を行う際に, 迅速にフラグを見ることができるように用意されている.

参照
     計算および表示の制御

dp_ord
------

dp_ord([ORDER])
     :: 変数順序型の設定, 参照

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

order
     数, リストまたは行列

  * 引数がある時, 変数順序型を ORDER に設定する. 引数がない時, 現在設定されている変数順序型を返す.

  * 分散表現多項式に関する函数, 演算は引数として変数順序型をとるものととらないものがあり, とらないものに関しては, その時点で設定されている値を用いて計算が行われる.

  * gr() など, 引数として変数順序型をとるものは, 内部で dp_ord() を呼び出し, 変数順序型を設定する. この設定は, 計算終了後も生き残る.

  * 分散表現多項式の四則演算も, 設定されている値を用いて計算される. 従って, その多項式が生成された時点における変数順序型が, 四則演算時に正しく設定されていなければならない. また, 演算対象となる多項式は, 同一の変数順序型に基づいて生成されたものでなければならない.

  * トップレベル函数以外の函数を直接呼び出す場合には, この函数により変数順序型を正しく設定しなければならない.

     [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>>

参照
     項順序の設定

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.

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

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.

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.

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.

dp_nf, dp_nf_mod, dp_true_nf, dp_true_nf_mod
--------------------------------------------

dp_nf(INDEXLIST,DPOLY,DPOLYARRAY,FULLREDUCE)

dp_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 の正規形を求める.

  * 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);
     -1138087976845165778088612297273078520347097001020471455633353049221045677593
     0005716505560062087150928400876150217079820311439477560587583488*u4^15+...
     [79] dp_dtop(dp_nf([4,3,2,1,0],T,DP2,1),V);
     -1138087976845165778088612297273078520347097001020471455633353049221045677593
     0005716505560062087150928400876150217079820311439477560587583488*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.

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>>

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

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.

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.

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.

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>>

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.

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.

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.

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.

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.

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]

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

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.