Google

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

項順序の設定

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

基本的な項順序型として次の 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 で表されていることからこのような極端な結果となったわけである. 実際に現れる計算においては, このように選ぶべき変数順序が明らかである ことは少なく, 試行錯誤が必要な場合もある.

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