@node グレブナ基底の計算,,, Top
@chapter グレブナ基底の計算

@menu
* 分散表現多項式::
* ファイルの読み込み::
* 基本的な函数::
* 計算および表示の制御::
* 項順序の設定::
* 有理式を係数とするグレブナ基底計算::
* 基底変換::
* グレブナ基底に関する函数::
@end menu

@node 分散表現多項式,,, グレブナ基底の計算
@section 分散表現多項式

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


@iftex
@tex
$(x+y+z)^2 = 1 \cdot x^2 + (2 \cdot y + (2 \cdot z)) \cdot x + ((2 \cdot z) \cdot y + (1 \cdot z^2 ))$
@end tex
@end iftex
@ifinfo
@example
(x+y+z)^2 = 1 x^2 + (2 y + (2 z)) x + ((2 z) y + (1 z^2 ))
@end example
@end ifinfo

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

@iftex
@tex
$(x+y+z)^2 = 1 \cdot x^2 + 2 \cdot xy + 2 \cdot xz + 1 \cdot y^2 + 2 \cdot yz +1 \cdot z^2$
@end tex
@end iftex
@ifinfo
@example
(x+y+z)^2 = 1 x^2 + 2 xy + 2 xz + 1 y^2 + 2 yz +1 z^2$
@end example
@end ifinfo

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

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

@example
<<0,1,2,3,4>>
@end example

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

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

@enumerate
@item
任意の項 @code{t} に対し @code{t} > 1

@item
@code{t}, @code{s}, @code{u} を項とする時, @code{t} > @code{s} ならば
@code{tu} > @code{su}
@end enumerate

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

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

@example
2*<<0,1,2,3,4>>
@end example

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

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

@node ファイルの読み込み,,, グレブナ基底の計算
@section ファイルの読み込み

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

@example
[0] load("gr")$
@end example

@node 基本的な函数,,, グレブナ基底の計算
@section 基本的な函数

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

@table @code
@item gr(@var{plist},@var{vlist},@var{order})

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

@item hgr(@var{plist},@var{vlist},@var{order})

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

@item gr_mod(@var{plist},@var{vlist},@var{order},@var{p})

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

@end table

@node 計算および表示の制御,,, グレブナ基底の計算
@section 計算および表示の制御

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

@example
[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]
@end example

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

@example
[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]
@end example

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

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

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

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

@table @code
@item TNF
normal form 計算時間 (秒)

@item TCONT
content 計算時間 (秒)

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

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

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

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

@item RP
残りのペアの数

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

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

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


@table @code
@item UP
ペアのリストの操作にかかった時間

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

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

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

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

@item ZNFM
@code{NFM} の内, 0 への reduction にかかった時間

@item PZ
content 計算時間

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

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

@item RA
interreduce 計算時間

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

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

@item T
生成されたペアの数

@item B, M, F, D
各 criterion により除かれたペアの数
      
@item ZR
0 に reduce されたペアの数

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

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

@end table

@node 項順序の設定,,, グレブナ基底の計算
@section 項順序の設定

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

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

@table @code
@item 0 (DegRevLex; @b{全次数逆辞書式順序})

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

@item 1 (DegLex; @b{全次数辞書式順序})

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

@item 2 (Lex; @b{辞書式順序})

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

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

@code{[[O1,L1],[O2,L2],...]}

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

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

@enumerate
@item
長さ @code{m} の整数ベクトル @code{v} に対し @code{Mv=0} と @code{v=0} は同値. 

@item
非負成分を持つ長さ @code{m} の 0 でない整数ベクトル @code{v} に対し, 
@code{Mv} の 0 でない最初の成分は非負.
@end enumerate

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

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

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

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

@example
[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]
@end example

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

@node 有理式を係数とするグレブナ基底計算,,, グレブナ基底の計算
@section 有理式を係数とするグレブナ基底計算

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

@example
[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]
@end example

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

@node 基底変換,,, グレブナ基底の計算
@section 基底変換

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

@table @code
@item tolex(@var{gbase},@var{vlist1},@var{order},@var{vlist2})

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

@item tolex_tl(@var{gbase},@var{vlist1},@var{order},@var{vlist2},@var{homo})

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

@end table

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

@node グレブナ基底に関する函数,,, グレブナ基底の計算
@section グレブナ基底に関する函数

@menu
* gr hgr gr_mod::
* lex_hensel lex_tl tolex tolex_d tolex_tl::
* lex_hensel_gsl tolex_gsl tolex_gsl_d::
* gr_minipoly minipoly::
* tolexm minipolym::
* dp_gr_main dp_gr_mod_main::
* dp_f4_main dp_f4_mod_main::
* dp_gr_flags dp_gr_print::
* dp_ord::
* dp_ptod::
* dp_dtop::
* dp_mod dp_rat::
* dp_homo dp_dehomo::
* dp_ptozp dp_prim::
* dp_nf dp_nf_mod dp_true_nf dp_true_nf_mod::
* dp_hm dp_ht dp_hc dp_rest::
* dp_td dp_sugar::
* dp_lcm::
* dp_redble::
* dp_subd::
* dp_mbase::
* dp_mag::
* dp_red dp_red_mod::
* dp_sp dp_sp_mod::
* p_nf p_nf_mod p_true_nf p_true_nf_mod ::
* p_terms::
* gb_comp::
* katsura hkatsura cyclic hcyclic::
* dp_vtoe dp_etov::
* lex_hensel_gsl tolex_gsl tolex_gsl_d::
@end menu

@node gr hgr gr_mod,,, グレブナ基底に関する函数
@subsection @code{gr}, @code{hgr}, @code{gr_mod}, @code{dgr}
@findex gr
@findex hgr
@findex gr_mod
@findex dgr

@table @t
@item gr(@var{plist},@var{vlist},@var{order})
@itemx hgr(@var{plist},@var{vlist},@var{order})
@itemx gr_mod(@var{plist},@var{vlist},@var{order},@var{p})
@itemx dgr(@var{plist},@var{vlist},@var{order},@var{procs})
:: グレブナ基底の計算
@end table

@table @var
@item return
リスト
@item plist, vlist, procs
リスト
@item order
数, リストまたは行列
@item p
2^27 未満の素数
@end table

@itemize @bullet
@item
標準ライブラリの @samp{gr} で定義されている. 
@item
いずれも, 多項式リスト @var{plist} の, 変数順序 @var{vlist}, 項順序型
@var{order} に関するグレブナ基底を求める. @code{gr()}, @code{hgr()}
は 有理数係数, @code{gr_mod()} は GF(@var{p}) 係数として計算する. 
@item
@var{vlist} は不定元のリスト. @var{vlist} に現れない不定元は, 
係数体に属すると見なされる. 
@item
@code{gr()}, trace-lifting (モジュラ演算を用いた高速化) および sugar
strategy による計算, @code{hgr()} は trace-lifting および
斉次化による 矯正された sugar strategy による計算を行う. 
@item
@code{dgr()} は, @code{gr()}, @code{dgr()} を
子プロセスリスト @var{procs} の 2 つのプロセスにより同時に計算させ, 
先に結果を返した方の結果を返す. 結果は同一であるが, どちらの方法が
高速か一般には不明のため, 実際の経過時間を短縮するのに有効である. 
@item
@code{dgr()} で表示される時間は, この函数が実行されているプロセスでの
CPU 時間であり, この函数の場合はほとんど通信のための時間である. 
@end itemize

@example
[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
@end example

@table @t
@item 参照
@comment @fref{dp_gr_main dp_gr_mod_main},
@fref{dp_gr_main dp_gr_mod_main},
@fref{dp_ord}.
@end table

@node lex_hensel lex_tl tolex tolex_d tolex_tl,,, グレブナ基底に関する函数
@subsection @code{lex_hensel}, @code{lex_tl}, @code{tolex}, @code{tolex_d}, @code{tolex_tl}
@findex lex_hensel
@findex lex_tl
@findex tolex
@findex tolex_d
@findex tolex_tl

@table @t
@item lex_hensel(@var{plist},@var{vlist1},@var{order},@var{vlist2},@var{homo})
@itemx lex_tl(@var{plist},@var{vlist1},@var{order},@var{vlist2},@var{homo})
:: 基底変換による辞書式順序グレブナ基底の計算
@item tolex(@var{plist},@var{vlist1},@var{order},@var{vlist2})
@itemx tolex_d(@var{plist},@var{vlist1},@var{order},@var{vlist2},@var{procs})
@itemx tolex_tl(@var{plist},@var{vlist1},@var{order},@var{vlist2},@var{homo})
:: グレブナ基底を入力とする, 基底変換による辞書式順序グレブナ基底の計算
@end table

@table @var
@item return
リスト
@item plist, vlist1, vlist2, procs
リスト
@item order
数, リストまたは行列
@item homo
フラグ
@end table

@itemize @bullet
@item
標準ライブラリの @samp{gr} で定義されている. 
@item
@code{lex_hensel()}, @code{lex_tl()} は, 
多項式リスト @var{plist} の, 変数順序 @var{vlist1}, 項順序型
@var{order} に関するグレブナ基底を求め, それを, 変数順序 @var{vlist2}
の辞書式順序グレブナ基底に変換する. 
@item
@code{tolex()}, @code{tolex_tl()} は, 
変数順序 @var{vlist1}, 項順序型 @var{order} に関するグレブナ基底である
多項式リスト @var{plist} を変数順序 @var{vlist2} の辞書式順序グレブナ
基底に変換する. 
@code{tolex_d()} は, @code{tolex()} における, 各基底の計算を, 子プロセス
リスト @var{procs} の各プロセスに分散計算させる. 
@item
@code{lex_hensel()}, @code{lex_tl()} においては, 辞書式順序グレブナ基底の
計算は次のように行われる. (@code{[Noro,Yokoyama]} 参照.)

@enumerate
@item
@var{vlist1}, @var{order} に関するグレブナ基底 @var{G0} を計算する. 
(@code{lex_hensel()} のみ. )
@item
@var{G0} の各元の @var{vlist2} に関する辞書式順序における頭係数を割らない
ような素数 @var{p} を選び, GF(@var{p}) 上での辞書式順序グレブナ基底
@var{Gp} を計算する. 
@item
@var{Gp} に現れるすべての項の, @var{G0} に関する正規形 @var{NF} を計算する. 
@item
@var{Gp} の各元 @var{f} につき, @var{f} の係数を未定係数で, 
@var{f} の各項を対応する @var{NF} の元で置き換え, 各項の係数を 0 と置いた,
未定係数に関する線形方程式系 @var{Lf} を作る. 
@item
@var{Lf} が, 法 @var{p} で一意解を持つことを用いて @var{Lf} の解を
法 @var{p}の解から Hensel 構成により求める. 
@item
すべての @var{Gp} の元につき線形方程式が解けたらその解全体が求める
辞書式順序でのグレブナ基底. もしどれかの線形方程式の求解に失敗したら, 
@var{p} をとり直してやり直す. 
@end enumerate

@item
@code{lex_tl()}, @code{tolex_tl()} においては, 辞書式順序グレブナ基底の
計算は次のように行われる. 

@enumerate
@item
@var{vlist1}, @var{order} に関するグレブナ基底 @var{G0} を計算する. 
(@code{lex_hensel()} のみ. )
@item
@var{G0} が 0 次元システムでないとき, @var{G0} を入力として, 
@var{G0} の各元の @var{vlist2} に関する辞書式順序における頭係数を割らない
ような素数 @var{p} を選び, @var{p} を用いた trace-lifting により辞書式
順序のグレブナ基底候補を求め, もし求まったならチェックなしにそれが求める
グレブナ基底となる. もし失敗したら, @var{p} をとり直してやり直す. 
@item
@var{G0} が 0 次元システムのとき, @var{G0} を入力として, 
まず, @var{vlist2} の最後の変数以外を消去する消去順序により
グレブナ基底 @var{G1} を計算し, それから辞書式順序のグレブナ基底を
計算する. その際, 各ステップでは, 入力の各元の, 求める順序における
頭係数を割らない素数を用いた trace-lifting でグレブナ基底候補を求め, 
もし求まったらチェックなしにそれがその順序でのグレブナ基底となる. 
@end enumerate

@item
有理式係数の計算は, @code{lex_tl()}, @code{tolex_tl()} のみ受け付ける. 
@item
@code{homo} が 0 でない場合, 内部で起動される Buchberger アルゴリズムに
おいて, 斉次化が行われる.
@item
@code{tolex_d()} で表示される時間は, この函数が実行されているプロセスに
おいて行われた計算に対応していて, 子プロセスにおける時間は含まれない. 
@end itemize

@example
[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
@end example

@table @t
@item 参照
@fref{dp_gr_main dp_gr_mod_main},
@fref{dp_ord}, @fref{分散計算}
@end table

@node lex_hensel_gsl tolex_gsl tolex_gsl_d,,, グレブナ基底に関する函数
@subsection @code{lex_hensel_gsl}, @code{tolex_gsl}, @code{tolex_gsl_d}
@findex lex_hensel_gsl
@findex tolex_gsl
@findex tolex_gsl_d

@table @t
@item lex_hensel_gsl(@var{plist},@var{vlist1},@var{order},@var{vlist2},@var{homo})
:: GSL 形式のイデアル基底の計算
@item tolex_gsl(@var{plist},@var{vlist1},@var{order},@var{vlist2},@var{homo})
@itemx tolex_gsl_d(@var{plist},@var{vlist1},@var{order},@var{vlist2},@var{homo},@var{procs})
:: グレブナ基底を入力とする, GSL 形式のイデアル基底の計算
@end table

@table @var
@item return
リスト
@item plist, vlist1, vlist2, procs
リスト
@item order
数, リストまたは行列
@item homo
フラグ
@end table

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

@example
[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-...]
@end example

@table @t
@item 参照
@fref{lex_hensel lex_tl tolex tolex_d tolex_tl},
@fref{分散計算}
@end table

@node gr_minipoly minipoly,,, グレブナ基底に関する函数
@subsection @code{gr_minipoly}, @code{minipoly}
@findex gr_minipoly
@findex minipoly

@table @t
@item gr_minipoly(@var{plist},@var{vlist},@var{order},@var{poly},@var{v},@var{homo})
:: 多項式の, イデアルを法とした最小多項式の計算
@item minipoly(@var{plist},@var{vlist},@var{order},@var{poly},@var{v})
:: グレブナ基底を入力とする, 多項式の最小多項式の計算
@end table

@table @var
@item return
多項式
@item plist, vlist
リスト
@item order
数, リストまたは行列
@item poly
多項式
@item v
不定元
@item homo
フラグ
@end table

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

@example
[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
@end example

@table @t
@item 参照
@fref{lex_hensel lex_tl tolex tolex_d tolex_tl}.
@end table

@node tolexm minipolym,,, グレブナ基底に関する函数
@subsection @code{tolexm}, @code{minipolym}
@findex tolexm
@findex minipolym

@table @t
@item tolexm(@var{plist},@var{vlist1},@var{order},@var{vlist2},@var{mod})
:: 法 @var{mod} での基底変換によるグレブナ基底計算
@item minipolym(@var{plist},@var{vlist1},@var{order},@var{poly},@var{v},@var{mod})
:: 法 @var{mod} でのグレブナ基底による多項式の最小多項式の計算
@end table

@table @var
@item return
@code{tolexm()} : リスト, @code{minipolym()} : 多項式
@item plist, vlist1, vlist2
リスト
@item order
数, リストまたは行列
@item mod
素数
@end table

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

@example
[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+...
@end example

@table @t
@item 参照
@fref{lex_hensel lex_tl tolex tolex_d tolex_tl},
@fref{gr_minipoly minipoly}.
@end table

@node dp_gr_main dp_gr_mod_main,,, グレブナ基底に関する函数
@subsection @code{dp_gr_main}, @code{dp_gr_mod_main}
@findex dp_gr_main
@findex dp_gr_mod_main

@table @t
@item dp_gr_main(@var{plist},@var{vlist},@var{homo},@var{modular},@var{order})
@itemx dp_gr_mod_main(@var{plist},@var{vlist},@var{homo},@var{modular},@var{order})
:: グレブナ基底の計算 (組み込み函数)
@end table

@table @var
@item return
リスト
@item plist, vlist
リスト
@item order
数, リストまたは行列
@item homo
フラグ
@item modular
フラグまたは素数
@end table

@itemize @bullet
@item
これらの函数は, グレブナ基底計算の基本的組み込み函数であり, @code{gr()},
@code{hgr()}, @code{gr_mod()} などはすべてこれらの函数を呼び出して計算
を行っている. 
@item
フラグ @var{homo} が 0 でない時, 入力を斉次化してから Buchberger アルゴリズム
を実行する. 
@item
@code{dp_gr_mod_main()} に対しては, @var{modular} は, GF(@var{modular}) 上
での計算を意味する. 
@code{dp_gr_main()} に対しては, @var{modular} は次のような意味を持つ. 
@enumerate
@item
@var{modular} が 1 の時, trace-lifting による計算を行う. 素数は
@code{lprime(0)} から順に成功するまで @code{lprime()} を呼び出して生成する. 
@item
@var{modular} が 2 以上の自然数の時, その値を素数とみなして trace-lifting
を行う. その素数で失敗した場合, 0 を返す. 
@item
@var{modular} が負の場合, 
@var{-modular} に対して上述の規則が適用されるが, trace-lifting の最終
段階のグレブナ基底チェックとイデアルメンバシップチェックが省略される. 
@end enumerate

@item
@code{gr(P,V,O)} は @code{dp_gr_main(P,V,0,1,O)}, @code{hgr(P,V,O)} は
@code{dp_gr_main(P,V,1,1,O)}, @code{gr_mod(P,V,O,M)} は
@code{dp_gr_mod_main(P,V,0,M,O)} をそれぞれ実行する. 
@item
@var{homo}, @var{modular} の他に, @code{dp_gr_flags()} で設定される
さまざまなフラグにより計算が制御される. 
@end itemize

@table @t
@item 参照
@fref{dp_ord},
@fref{dp_gr_flags dp_gr_print},
@fref{gr hgr gr_mod},
@fref{計算および表示の制御}.
@end table

@node dp_f4_main dp_f4_mod_main,,, グレブナ基底に関する函数
@subsection @code{dp_f4_main}, @code{dp_f4_mod_main}
@findex dp_f4_main
@findex dp_f4_mod_main

@table @t
@item dp_f4_main(@var{plist},@var{vlist},@var{order})
@itemx dp_f4_mod_main(@var{plist},@var{vlist},@var{order})
:: F4 アルゴリズムによるグレブナ基底の計算 (組み込み函数)
@end table

@table @var
@item return
リスト
@item plist, vlist
リスト
@item order
数, リストまたは行列
@end table

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

@table @t
@item 参照
@fref{dp_ord},
@fref{dp_gr_flags dp_gr_print},
@fref{gr hgr gr_mod},
@fref{計算および表示の制御}.
@end table

@node dp_gr_flags dp_gr_print,,, グレブナ基底に関する函数
@subsection @code{dp_gr_flags}, @code{dp_gr_print}
@findex dp_gr_flags
@findex dp_gr_print

@table @t
@item dp_gr_flags([@var{list}])
@itemx dp_gr_print([@var{0|1}])
:: 計算および表示用パラメタの設定, 参照
@end table

@table @var
@item return
設定値
@item list
リスト
@end table

@itemize @bullet
@item
@code{dp_gr_main()}, @code{dp_gr_mod_main()} 実行時におけるさまざま
なパラメタを設定, 参照する. 
@item
引数がない場合, 現在の設定が返される. 
@item
引数は, @code{["Print",1,"NoSugar",1,...]} なる形のリストで, 左から順に
設定される. パラメタ名は文字列で与える必要がある. 
@item
@code{dp_gr_print()} は, 特にパラメタ @code{Print} の値を直接設定, 参照
できる. これは, @code{dp_gr_main()} などをサブルーチンとして用いるユーザ
函数において, @code{Print} の値を見て, そのサブルーチンが中間情報の表示
を行う際に, 迅速にフラグを見ることができるように用意されている. 
@end itemize

@table @t
@item 参照
@fref{計算および表示の制御}
@end table

@node dp_ord,,, グレブナ基底に関する函数
@subsection @code{dp_ord}
@findex dp_ord

@table @t
@item dp_ord([@var{order}])
:: 変数順序型の設定, 参照
@end table

@table @var
@item return
変数順序型 (数, リストまたは行列)
@item order
数, リストまたは行列
@end table

@itemize @bullet
@item
引数がある時, 変数順序型を @var{order} に設定する. 引数がない時, 
現在設定されている変数順序型を返す. 

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

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

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

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

@example
[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>>
@end example

@table @t
@item 参照
@fref{項順序の設定}
@end table

@node dp_ptod,,, グレブナ基底に関する函数
@subsection @code{dp_ptod}
@findex dp_ptod

@table @t
@item dp_ptod(@var{poly},@var{vlist})
:: 多項式を分散表現多項式に変換する. 
@end table

@table @var
@item return
分散表現多項式
@item poly
多項式
@item vlist
リスト
@end table

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

@example
[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>>
@end example

@table @t
@item 参照
@fref{dp_dtop},
@fref{dp_ord}.
@end table

@node dp_dtop,,, グレブナ基底に関する函数
@subsection @code{dp_dtop}
@findex dp_dtop

@table @t
@item dp_dtop(@var{dpoly},@var{vlist})
:: 分散表現多項式を多項式に変換する. 
@end table

@table @var
@item return
多項式
@item dpoly
分散表現多項式
@item vlist
リスト
@end table

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

@example
[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
@end example

@node dp_mod dp_rat,,, グレブナ基底に関する函数
@subsection @code{dp_mod}, @code{dp_rat}
@findex dp_mod
@findex dp_rat

@table @t
@item dp_mod(@var{p},@var{mod},@var{subst})
:: 有理数係数分散表現多項式の有限体係数への変換
@item dp_rat(@var{p})
:: 有限体係数分散表現多項式の有理数係数への変換
@end table

@table @var
@item return
分散表現多項式
@item p
分散表現多項式
@item mod
素数
@item subst
リスト
@end table

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

@example
@end example

@table @t
@item 参照
@fref{dp_nf dp_nf_mod dp_true_nf dp_true_nf_mod},
@fref{subst psubst},
@fref{setmod}.
@end table

@node dp_homo dp_dehomo,,, グレブナ基底に関する函数
@subsection @code{dp_homo}, @code{dp_dehomo}
@findex dp_homo
@findex dp_dehomo

@table @t
@item dp_homo(@var{dpoly})
:: 分散表現多項式の斉次化
@item dp_dehomo(@var{dpoly})
:: 斉次分散表現多項式の非斉次化
@end table

@table @var
@item return
分散表現多項式
@item dpoly
分散表現多項式
@end table

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

@example
[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>>
@end example

@table @t
@item 参照
@fref{gr hgr gr_mod}.
@end table

@node dp_ptozp dp_prim,,, グレブナ基底に関する函数
@subsection @code{dp_ptozp}, @code{dp_prim}
@findex dp_ptozp
@findex dp_prim

@table @t
@item dp_ptozp(@var{dpoly})
:: 定数倍して係数を整数係数かつ係数の整数 GCD を 1 にする. 
@itemx dp_prim(@var{dpoly})
:: 有理式倍して係数を整数係数多項式係数かつ係数の多項式 GCD を 1 にする. 
@end table

@table @var
@item return
分散表現多項式
@item dpoly
分散表現多項式
@end table

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

@example
[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>>
@end example

@table @t
@item 参照
@fref{ptozp}.
@end table

@node dp_nf dp_nf_mod dp_true_nf dp_true_nf_mod,,, グレブナ基底に関する函数
@subsection @code{dp_nf}, @code{dp_nf_mod}, @code{dp_true_nf}, @code{dp_true_nf_mod}
@findex dp_nf
@findex  dp_true_nf
@findex dp_nf_mod
@findex  dp_true_nf_mod

@table @t
@item dp_nf(@var{indexlist},@var{dpoly},@var{dpolyarray},@var{fullreduce})
@item dp_nf_mod(@var{indexlist},@var{dpoly},@var{dpolyarray},@var{fullreduce},@var{mod})
:: 分散表現多項式の正規形を求める. (結果は定数倍されている可能性あり)

@item dp_true_nf(@var{indexlist},@var{dpoly},@var{dpolyarray},@var{fullreduce})
@item dp_true_nf_mod(@var{indexlist},@var{dpoly},@var{dpolyarray},@var{fullreduce},@var{mod})
:: 分散表現多項式の正規形を求める. (真の結果を @code{[分子, 分母]} の形で返す)
@end table

@table @var
@item return
@code{dp_nf()} : 分散表現多項式, @code{dp_true_nf()} : リスト
@item indexlist
リスト
@item dpoly
分散表現多項式
@item dpolyarray
配列
@item fullreduce
フラグ
@item mod
素数
@end table

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

@end itemize

@example
[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
@end example

@table @t
@item 参照
@fref{dp_dtop},
@fref{dp_ord},
@fref{dp_mod dp_rat},
@fref{p_nf p_nf_mod p_true_nf p_true_nf_mod}.
@end table

@node dp_hm dp_ht dp_hc dp_rest,,, グレブナ基底に関する函数
@subsection @code{dp_hm}, @code{dp_ht}, @code{dp_hc}, @code{dp_rest}
@findex dp_hm
@findex dp_ht
@findex dp_hc
@findex dp_rest

@table @t
@item dp_hm(@var{dpoly})
:: 頭単項式を取り出す. 
@item dp_ht(@var{dpoly})
:: 頭項を取り出す. 
@item dp_hc(@var{dpoly})
:: 頭係数を取り出す. 
@item dp_rest(@var{dpoly})
:: 頭単項式を取り除いた残りを返す. 
@end table

@table @var
@item return
@code{dp_hm()}, @code{dp_ht()}, @code{dp_rest()} : 分散表現多項式,
@code{dp_hc()} : 数または多項式
@item dpoly
分散表現多項式
@end table

@itemize @bullet
@item
これらは, 分散表現多項式の各部分を取り出すための函数である. 
@item
分散表現多項式 @var{p} に対し次が成り立つ. 
@table @code
@item @var{p} = dp_hm(@var{p}) + dp_rest(@var{p})
@item dp_hm(@var{p}) = dp_hc(@var{p}) dp_ht(@var{p})
@end table
@end itemize

@example
[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>>
@end example

@node dp_td dp_sugar,,, グレブナ基底に関する函数
@subsection @code{dp_td}, @code{dp_sugar}
@findex dp_td
@findex dp_sugar

@table @t
@item dp_td(@var{dpoly})
:: 頭項の全次数を返す. 
@item dp_sugar(@var{dpoly})
:: 多項式の @code{sugar} を返す. 
@end table

@table @var
@item return
自然数
@item dpoly
分散表現多項式
@item onoff
フラグ
@end table

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

@example
[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
@end example

@node dp_lcm,,, グレブナ基底に関する函数
@subsection @code{dp_lcm}
@findex dp_lcm

@table @t
@item dp_lcm(@var{dpoly1},@var{dpoly2})
:: 最小公倍項を返す. 
@end table

@table @var
@item return
分散表現多項式
@item dpoly1, dpoly2
分散表現多項式
@end table

@itemize @bullet
@item
それぞれの引数の頭項の最小公倍項を返す. 係数は 1 である. 
@end itemize

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

@table @t
@item 参照
@fref{p_nf p_nf_mod p_true_nf p_true_nf_mod}.
@end table

@node dp_redble,,, グレブナ基底に関する函数
@subsection @code{dp_redble}
@findex dp_redble

@table @t
@item dp_redble(@var{dpoly1},@var{dpoly2})
:: 頭項どうしが整除可能かどうか調べる. 
@end table

@table @var
@item return
整数
@item dpoly1, dpoly2
分散表現多項式
@end table

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

@example
[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
@end example

@table @t
@item 参照
@fref{dp_red dp_red_mod}.
@end table

@node dp_subd,,, グレブナ基底に関する函数
@subsection @code{dp_subd}
@findex dp_subd

@table @t
@item dp_subd(@var{dpoly1},@var{dpoly2})
:: 頭項の商単項式を返す. 
@end table

@table @var
@item return
分散表現多項式
@item dpoly1, dpoly2
分散表現多項式
@end table

@itemize @bullet
@item
@code{dp_ht(@var{dpoly1})/dp_ht(@var{dpoly2})} を求める. 結果の係数は 1 
である. 
@item
割り切れることがあらかじめわかっている必要がある.
@end itemize

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

@table @t
@item 参照
@fref{dp_red dp_red_mod}.
@end table

@node dp_vtoe dp_etov,,, グレブナ基底に関する函数
@subsection @code{dp_vtoe}, @code{dp_etov}
@findex dp_vtoe
@findex dp_etov

@table @t
@item dp_vtoe(@var{vect})
:: 指数ベクトルを項に変換
@item dp_etov(@var{dpoly})
:: 頭項を指数ベクトルに変換
@end table

@table @var
@item return
@code{dp_vtoe} : 分散表現多項式, @code{dp_etov} : ベクトル
@item vect
ベクトル
@item dpoly
分散表現多項式
@end table

@itemize @bullet
@item
@code{dp_vtoe()} は, ベクトル @var{vect} を指数ベクトルとする項を生成する. 
@item
@code{dp_etov()} は, 分散表現多項式 @code{dpoly} の頭項の指数ベクトルを
ベクトルに変換する. 
@end itemize

@example
[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>>
@end example

@node dp_mbase,,, グレブナ基底に関する函数
@subsection @code{dp_mbase}
@findex dp_mbase

@table @t
@item dp_mbase(@var{dplist})
:: monomial 基底の計算
@end table

@table @var
@item return
分散表現多項式のリスト
@item dplist
分散表現多項式のリスト
@end table

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

@example
[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]
@end example

@table @t
@item 参照
@fref{gr hgr gr_mod}.
@end table

@node dp_mag,,, グレブナ基底に関する函数
@subsection @code{dp_mag}
@findex dp_mag

@table @t
@item dp_mag(@var{p})
:: 係数のビット長の和を返す
@end table

@table @var
@item return
数
@item p
分散表現多項式
@end table

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

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

@table @t
@item 参照
@fref{dp_gr_flags dp_gr_print}.
@end table

@node dp_red dp_red_mod,,, グレブナ基底に関する函数
@subsection @code{dp_red}, @code{dp_red_mod}
@findex dp_red
@findex dp_red_mod

@table @t
@item dp_red(@var{dpoly1},@var{dpoly2},@var{dpoly3})
@item dp_red_mod(@var{dpoly1},@var{dpoly2},@var{dpoly3},@var{mod})
:: 一回の簡約操作
@end table

@table @var
@item return
リスト
@item dpoly1, dpoly2, dpoly3
分散表現多項式
@item vlist
リスト
@item mod
素数
@end table

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

@example
[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>>]
@end example

@table @t
@item 参照
@fref{dp_mod dp_rat}.
@end table

@node dp_sp dp_sp_mod,,, グレブナ基底に関する函数
@subsection @code{dp_sp}, @code{dp_sp_mod}
@findex dp_sp
@findex dp_sp_mod

@table @t
@item dp_sp(@var{dpoly1},@var{dpoly2})
@item dp_sp_mod(@var{dpoly1},@var{dpoly2},@var{mod})
:: S-多項式の計算
@end table

@table @var
@item return
分散表現多項式
@item dpoly1, dpoly2
分散表現多項式
@item mod
素数
@end table

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

@example
[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>>
@end example

@table @t
@item 参照
@fref{dp_mod dp_rat}.
@end table
@node p_nf p_nf_mod p_true_nf p_true_nf_mod,,, グレブナ基底に関する函数
@subsection @code{p_nf}, @code{p_nf_mod}, @code{p_true_nf}, @code{p_true_nf_mod}
@findex p_nf
@findex p_nf_mod
@findex p_true_nf
@findex p_true_nf_mod

@table @t
@item p_nf(@var{poly},@var{plist},@var{vlist},@var{order})
@itemx p_nf_mod(@var{poly},@var{plist},@var{vlist},@var{order},@var{mod})
:: 表現多項式の正規形を求める. (結果は定数倍されている可能性あり)
@item p_true_nf(@var{poly},@var{plist},@var{vlist},@var{order})
@itemx p_true_nf_mod(@var{poly},@var{plist},@var{vlist},@var{order},@var{mod})
:: 表現多項式の正規形を求める. (真の結果を @code{[分子, 分母]} の形で返す)
@end table

@table @var
@item return
@code{p_nf} : 多項式, @code{p_true_nf} : リスト
@item poly
多項式
@item plist,vlist
リスト
@item order
数, リストまたは行列
@item mod
素数
@end table

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

@example
[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
@end example

@table @t
@item 参照
@fref{dp_ptod},
@fref{dp_dtop},
@fref{dp_ord},
@fref{dp_nf dp_nf_mod dp_true_nf dp_true_nf_mod}.
@end table

@node p_terms,,, グレブナ基底に関する函数
@subsection @code{p_terms}
@findex p_terms

@table @t
@item p_terms(@var{poly},@var{vlist},@var{order})
:: 多項式にあらわれる単項をリストにする. 
@end table

@table @var
@item return
リスト
@item poly
多項式
@item vlist
リスト
@item order
数, リストまたは行列
@end table

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

@example
[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]
@end example

@node gb_comp,,, グレブナ基底に関する函数
@subsection @code{gb_comp}
@findex gb_comp

@table @t
@item gb_comp(@var{plist1}, @var{plist2})
:: 多項式リストが, 符号を除いて集合として等しいかどうか調べる. 
@end table

@table @var
@item return 0 または 1
@item plist1, plist2
@end table

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

@example
[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
@end example

@node katsura hkatsura cyclic hcyclic,,, グレブナ基底に関する函数
@subsection @code{katsura}, @code{hkatsura}, @code{cyclic}, @code{hcyclic}
@findex katsura
@findex hkatsura
@findex cyclic
@findex hcyclic

@table @t
@item katsura(@var{n})
@item hkatsura(@var{n})
@item cyclic(@var{n})
@item hcyclic(@var{n})
:: 多項式リストの生成
@end table

@table @var
@item return
リスト
@item n
整数
@end table

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

@example
[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]
@end example

@table @t
@item 参照
@fref{dp_dtop}.
@end table