Groebner[Basis]に用いられている算法
|
使い方
|
|
Basis(J, tord, method=meth)
|
|
パラメータ
|
|
J
|
-
|
多項式のリストか集合、あるいは PolynomialIdeal
|
tord
|
-
|
単項式順序の一般的な記述か短い記述あるいは名前
|
meth
|
-
|
以下で説明する計算手法のいづれか
|
|
|
|
|
説明
|
|
•
|
Groebner[Basis] コマンドは様々な単項式順序、ドメインについての 5 つの異なる Groebner 基底計算アルゴリズムを組み合わせて計算しています。このヘルプページでは各アルゴリズムについて効率面での特徴を解説し、ユーザに、どのアルゴリズムを用いるのがよいか、選択する指針を示します。アルゴリズムはオプションのパラメータとして method=meth を入力することで指定します。
|
•
|
method=fgb という入力は、J.C. Faugere によって書かれた F4 アルゴリズムのソースをコンパイルしたもの (FGb) を用いて計算することを指定します。FGb は有理数体、p 進数体 (ただし p は p < 2^(kernelopts(wordsize)/2) 、32-bit 機では 65536) を扱うことができます。FGb は全次数逆辞書式順序 (tdeg) と変数を二つに分けた消去順序 (lexdeg) を扱うことができます。係数にパラメータを含む場合 (つまり、有理関数体系数の場合) や、 output=extended をサポートしていません。
|
•
|
method=maplef4 は F4 アルゴリズムの Maple による実装を用いて計算することを指定します。この実装では非可換 Ore 代数の計算で使える全ての単項式順序と係数体を用いることができます。この実装はモジュラー手法を用いない計算のため、もし可能ならば FGb を用いる方が効率面で好ましい結果になります。output=extended は現在サポートされていません。
|
•
|
method=buchberger は以前からある Maple の Buchberger アルゴリズムの実装です。このアルゴリズムは全てのドメイン、単項式順序、output=extended といったオプションをサポートしています。この実装はほとんどの場合効率面では F4 に劣りますが、多項式が追加され、Broebner 基底を再計算するような場合は、この実装では Gebauer と Moller の理論に基づいた計算を正規戦略を用いて実行するため、この限りではありません。
|
•
|
method=fglm は Faugere, Gianni, Lazard, Mora による Groebner 基底変換のアルゴリズムを用います。このアルゴリズムでは全ての可環なドメインをサポートしますが、入力のイデアルが 0 次元イデアルである必要があります。詳細な情報は
Groebner[FGLM] をご参照ください。このアルゴリズムによる計算では、Groebner[Basis] コマンドは既にわかっている Groebner 基底のうちの一つを選び (わかっているものがない場合は適当な順序で Groebner 基底を計算して) Groebner[FGLM] コマンドを実行します。
|
•
|
method=walk は Collart, Kalkbrener, Mall による Groebner Walk 基底変換アルゴリズムを用います。このアルゴリズムでは全ての可環なドメインと単項式順序を用いることができます。詳細な情報は Groebner[Walk] の項をご参照ください。このアルゴリズムによる計算では Groebner[Basis] コマンドは既にわかっている Groebner 基底のうちの一つを選び (わかっているものがない場合は適当な順序で Groebner 基底を計算して) Groebner[Walk] コマンドを実行します。0 次元イデアルに対しては、一般に Groebner walk は FGLM より効率面で劣ります。
|
•
|
以上のアルゴリズム以外にも、method=... によって、計算する戦略を指定し、Groebner[Basis] コマンドがいづれのアルゴリズムを用いるのが適当か選択する基準を定めることができます。その戦略とは以下のものを指します :
|
•
|
method=direct と入力すると、直接計算する汎用の手法の中で最も速いものを用います。それは現在では FGb か、FGb が使えない場合は Maple の実装による F4 アルゴリズムとなります。現在よりよいアルゴリズムが実装されれば、この戦略に用いられるアルゴリズムは最新の手法を反映したものに更新されます。つまり将来 Maple がアップデートされても、この指定を用いて書かれたコードは最も速い直接計算法を使っていると考える事ができます。
|
•
|
method=convert は適用可能な基底変換手法の中で最も速いアルゴリズム、つまり FGLM か Groebner Walk のいづれか速い方を選択し、計算に用います。この選択は単項式順序と、イデアルが 0 次元であるかどうかによります。この戦略を用いることは単項式順序が消去順序である場合に推奨されます。この戦略は 'plex', 'lexdeg', 'prod' に対して、もし可能であれば FGLM アルゴリズムを用います。それ以外の順序か、あるいは 0 次元イデアルでない場合は計算には Groebner Walk が用いられます。
|
•
|
method=default は標準の戦略を用いますが、これは将来変更されます。現在この指定では 'tdeg', 'wdeg', 'grlex', 'matrix' と非可換多項式環の場合では method=direct を、可換な場合で 'plex', 'lexdeg', 'prod' 順序の場合は method=convert を指定したことと同じになります。
|
•
|
infolevel[GroebnerBasis] を 1 から 5 の間で指定すると、各計算手法は計算の進行状況と計算効率を出力するようになります。
|
|
|
例
|
|
>
|
infolevel[GroebnerBasis] := 2:
|
>
|
F := [x^2-2*x*z+5, x*y^2+y*z^3, 3*y^2-8*z^3];
|
| (4.1) |
-> FGb
total time: 0.016 sec
| |
| (4.2) |
>
|
Basis(F, grlex(x,y,z));
|
-> F4 algorithm
total time: 0.008 sec
| |
| (4.3) |
-> FGLM algorithm
total monomials : 23
total time (sec) .8e-2
| |
| (4.4) |
| (4.5) |
>
|
Basis(F, lexdeg([x], [y,z]), method=walk);
|
-> Groebner Walk
total time: 0.000 sec
| |
| (4.6) |
>
|
Basis(F, lexdeg([x,y], [z]), method=direct);
|
-> FGb
total time: 0.012 sec
| |
| (4.7) |
>
|
Basis(F, plex(z,y,x), method=direct);
|
-> F4 algorithm
total time: 0.036 sec
| |
| (4.8) |
>
|
Basis(F, wdeg([1,2,3], [x,y,z]), method=convert);
|
-> Groebner Walk
total time: 0.028 sec
| |
| (4.9) |
非可環な場合の計算例 (詳細な情報については Basis_details をご参照ください)
>
|
infolevel[GroebnerBasis] := 4:
|
>
|
A := diff_algebra(seq([D[i], x[i]], i=1..N), comm={a, b, seq(c[i], i=1..N)}, polynom={seq(x[i], i=1..N)}):
|
>
|
S := `+`(seq(x[i]*D[i], i=1..N)):
|
>
|
P := skew_product(S+a, S+b, A):
|
>
|
F := [seq(skew_product(D[i], x[i]*D[i]+c[i]-1, A) - P, i=1..N)];
|
| (4.10) |
>
|
tord := tdeg(seq(D[i],i=1..N), seq(x[i],i=1..N));
|
| (4.11) |
>
|
T := MonomialOrder(A, tord):
|
-> F4 algorithm
domain: SkewAlgebra coeffs: rat_fcn
basis: 2 of 3, syzygies: 1 of 2, degree: 4
4 x 4 with 1 rhs
basis: 3 of 4, syzygies: 2 of 2, degree: 5
5 x 5 with 2 rhs
basis: 5 of 6, syzygies: 4 of 5, degree: 6
14 x 14 with 4 rhs
basis: 8 of 9, syzygies: 12 of 13, degree: 7
42 x 42 with 12 rhs
basis: 10 of 11, syzygies: 10 of 10, degree: 8
83 x 83 with 10 rhs
basis: 12 of 13, syzygies: 7 of 7, degree: 9
104 x 104 with 7 rhs
symbolic prc 0.272 sec
inter reduce 0.032 sec
update pairs 0.020 sec
reduce basis 0.028 sec
total time: 0.356 sec
-----------------------------
| |
>
|
Groebner:-LeadingMonomial(G, T);
|
| (4.12) |
|
|
参考文献
|
|
B. Buchberger. "Grobner Bases: An algorithmic method in polynomial ideal theory." in Multidimensional systems theory, pp. 184-232, Reidel, 1985.
S. Collart, M. Kalkbrener, D. Mall. "Converting Bases with the Grobner Walk." J. Symbolic Comput., 3/4 (1997), 465-469.
J. Faugere. "A New Efficient Algorithm for Computing Gr"obner Bases (F4)." Journal of Pure and Applied Algebra, 139, 1-3, pp. 61-88, 1999.
J. Faugere, P. Gianni, D. Lazard and T. Mora. "Efficient computation of zero-dimensional Grobner bases by change of ordering." J. Symbolic Comput., 16 (1993), 329-344.
R. Gebauer, H. Moller. "On an installation of Buchberger's algorithm." J. Symbolic Comput, 6, pp. 275-286, 1988.
R. Pearce, M. Monagan. "A Sparse Algorithm for Polynomial Division with Application to F4." in preparation, 2006.
|
|