数理解析研究所講究録
第 1572 巻 2007 年 131-141

131

Risa/Asir CGB 関連パッケージの整備
倉田陽介

鈴木晃

YOSUKE KURATA

AKIRA SUZUKI

神戸大学自然科学研究科

神戸大学情報管理室 \dag er*

鍋島克輔
KATSUSUKE NABESHIMA

RISC-Linz, Johannes Kepler Universit\"at \dager

1

Introduction
Comprehensive G\"obner Systems (CGS), あるいは, Comprehensive Gr\"obner Bases (CGB) とはパラメー

タを含む多項式イデアルに対する Gr\"obner Bases を与える. CGS&CGB の概念は 1992 年に Weispfenning[19] によって示され, その後, Weispfenning 自身による [20] (CCGB), Manubens-Montes $[8, 7]$ (DISPGB),
鈴木佐藤 $[16, 15]$ (ACGB) などにより, 新しいアルゴリズムが発展している.
また, 2006 年に鈴木・佐藤 [17] (SS-CGS) によりまったく新しい CGS&CGB 計算のアルゴリズムが示され,これまでのアルゴリズム, 実装では計算できなかった問題が高速に計算できるようになり, CGS ア

ルゴリズムの研究者のみならず注目を集めるところとなっている.
パラメータ付き多項式集合$F\subset K[\overline{A},\overline{X}]$

また $\overline{A}=\{A_{1}, \ldots, A_{m}\}$ をパラメータ,

1.

$K(\overline{A})$上の多項式環2. $K$ 上の多項式環のCGS&CGB の計算は, $K$ を体とし,$\overline{X}=\{X_{1}, \ldots, X_{n}\}$$L$をその代数的閉包,を変数とすると,$K(\overline{A})[\overline{X}]$$K[\overline{A},\overline{X}]$3. von Neumann regular ring$R$上の多項式環$R[\overline{X}]$のどれかの観点から計算をすることになる. Weispfenning の CGB や $Manubens- Mont\infty$ の DISPGB は本多項式と単項簡約を定義している. 鈴木・佐藤の ACGB はやや趣が変わり, 3. による方法である. この方法はどちらかというと計算効率における改良というよりは, CGS&CGB の理論的な定式化といえる. 最新の鈴木・佐藤の SS-CGS アルゴリズムは 2. による計算法であり,既存の体 $K$ 上の多項式環における Gr6bner 基底計算をそのまま流用できることから, 新たに CGS&CGB
質的には 1. の上に CGS 計算に特化した$S$

プログラムを開発する場合の敷居の低さもこの方法の大きな特徴になっている.
現在の CGS &CGB アルゴリズム研究は, 上記で紹介した Weispfenning グループ, Montes $fKs$ -プ,

佐藤グループが主流となって開発が行われている. それぞれのシステムは,
lkurata@math.kobe-u.ac.jp$\dagger_{8akira\emptyset kobe\cdot u}$$*Kat_{8}u\epsilon uke$. ac.jp.

.Nab\infty hima\copyright risc. uni-linz. $ac$ at

132

.

.
$\bullet$$\bullet$

Weispfenning (CGB) : 計算機代数システム REDUCE.
http: $//students.f$ im. uni-passau. $de/\sim reduce/cgb/$

Montes (DISPGB) : 数式処理システム Maple.

.

http: $//www^{-}ma2$ upc. $es/-montes/$

鈴木佐藤 (ACGB) : 計算機代数システム $Risa/Asir$ .

(未公開)

鈴木佐藤 (SS-CGS) : 計算機代数システム $Risa/Asir$ .

http: $//kurt$ . scitec. kobe-u. ac. $jp/\sim_{sakira}/CGBusingGB/$の上で構築されている. 特に SS-CGS 計算とその周辺に関する研究は倉田野呂 [6] や鍋島 [10] により進ん

日本人研究者の活躍するところが大きい. そこで鈴木, 鍋島, 倉田のそれぞれの SS-CGS アルゴ
リズムに関連した研究成果を統合し, 計算機代数システム $Risa/Asir[12]$ 上のパッケージとして提供するこ

でおり,

とにした.

2

鈴木・佐藤の CGS アルゴリズムの復習 (SS-CGS)CGB の定義を与えておく. $<x$ で最初に, アルゴリズムに無関係な CGS および,$T(\overline{X})$上の項順序を表すとする.

定義 1 (Comprehensive Gr\"obner System)$F$をの部分集合とし,$K[\overline{A},\overline{X}]$$S_{1},$$S\iota$$\ldots,$$T_{1},$$T\downarrow$$\ldots,$

有限集合 $\mathcal{G}=\{(S_{1}, T_{1}, G_{1}), \ldots, (S_{l}, T_{t}, G_{t})\}$ がであるとは,

に対して

$F$

をそれぞれ

の項順序

$(V(S_{1})\backslash V(T_{1}))\cup\cdots\cup(V(S_{l})\backslash V(T_{l}))=L^{m}$$\sigma_{\overline{a}}(c_{:})$

が$L[\overline{X}]$のイデアル$\langle\sigma_{a}(F)\rangle$の$<_{\overline{X}}$た, 各 $(S_{1}, T_{i}, G_{i})$ あるいは $(V(S_{i})\backslash V(T_{i}), G_{i})$ を$<_{\overline{X}}$$K[\overline{A}]$の有限部分集合とする.

このとき.

に関する comprehensive Gr\"obner system

かつ, 任意の $\overline{a}\in V(S_{i})\backslash V(T_{1}),$ $(i=1, \ldots, l)$に関する Gr\"obner basis となるときのことを言う. ま$\mathcal{G}$の segment と呼ぶ.

定韓 2 (Comprehensive Gr\"obner Bases)$G\subset K[\overline{A},\overline{X}]$$\sigma_{\overline{a}}(G)$がが $F$ の$<\overline{x}$$\langle a_{a}(F)\rangle\subset L[\overline{X}]$に関する comprehensive Gr\"obner basis であるとは, 任意のの$<\overline{x}$$\overline{a}\in L^{m}$に対してに関する Gr\"obner basis となるときのことを言う.

SS-CGS アルゴリズムを支えるのは, Kalkbrener [5] による以下の定理である.
定理 3 (Kalkbrener 1997)
の項順序
有限集合
$F\subset K(\overline{A})[\overline{X}]$$<\overline{x}$に関する Gr\"obner 基底を $G=\{g_{1}, \ldots,g_{l}\}$ とし, 任意の対応する sPecialization homomorphism$K(\overline{A})arrow L$を$\sigma_{\delta}$

とする.

ここで,

ある

$\overline{a}\in L^{m}$$\overline{a}\in L^{m}$

に

に対して.

$G_{\delta}=\{g\in G|\sigma_{\overline{a}}(HC<R(g))\neq 0\}$とするとき,\mbox{\boldmath $\sigma$}社$G_{\delta}$)が$\langle\sigma_{\delta}(F)\rangle$の$<\overline{x}$に関する Gr\"obner 基底になることと, 任意の $9\in G$ に対して,$\sigma_{\delta}(g)arrow^{*}\sigma_{l}(G_{d})0$となることは必要十分である.
したがって, 重要なことは $K(A)[$ 」$\overline{X}]$

上での Gr\"obner 基底が得られることであって.

問わない. ということである. この定理から,算することを考えると, 次の補題が成立する.

$K(\overline{A})$

その計算方法は上の Gr\"obner 基底を block 順序を使って $K$ 上で計

133
補題 4
有限集合
任意の

$\overline{a}\in V(G\cap K[\overline{A}])$

Gr\"obner 基底である.
の$<_{\overline{A},\overline{X}}$の項順序$F\subset K[\overline{A},\overline{X}]$$T(\overline{X})$

ここで,

への制限は

したがって,$F\subset K[\overline{A},\overline{X}]$$\bigcup_{g\in G\backslash K[\overline{A}J^{V(HC}<x}(g))$$\sigma_{\overline{a}}(HC<x(g))\neq 0$

項順序$<\overline{x}$に関する Gr\"obner 基底を $G$ とする.

$<_{\overline{A},\overline{X}}$に対して,$<\overline{A},\overline{X}$

は

ならば,

$T(\overline{A},\overline{X})$$\sigma_{\overline{a}}(G)$上の順序で,はもし, 任意の$\langle\sigma_{\delta}(F)\rangle\subset L[\overline{X}]$$\overline{X}$$\overline{A}$$g\in G\backslash K[\overline{A}]$の$<\overline{x}$

と

に関する

を満たす blo 櫨順序であり,に等しいとする.

の項順序

に対して,

$<_{\overline{A},\overline{X}}$$\sigma_{\overline{a}}(G)$はに関する Gr\"obner 基底を $G$ とし, 任意の$\langle\sigma_{\overline{a}}(F)\rangle\subset L[\overline{X}]$の$<\overline{x}$$\overline{a}\in V(G\cap K[\overline{A}])\backslash$に関する Gr\"obner 基底となる.

SS-CGS アルゴリズムではこのアイデアを再帰的に適用して完全な CGS, あるいは CGB を得る. 詳細は鈴木佐藤 [17] を参照されたい. 鈴木・佐藤アルゴリズムにはいくらかのバリエーションが考えられるが, 基本形は以下に示す再帰的アルゴリズム CGS である.

Algorithm CGS

A finite subset ofand a tem order $<A,x$ .
OUTPUT: A finite setof triples $(S, T, G)$ of a set of polynomials
a Gr\"obner basis in.
INPUT:$F$$K[\overline{A},\overline{X}]$$\mathcal{H}$

$G$

$S$

and

$T$

in

$K[\overline{A}]$, and$K[\overline{A},\overline{X}]$BEGIN$Garrow ReducedGrobnerBasis(F, <_{A,X})$ ;;$\mathcal{H}arrow\{(F\cap K[\overline{A}], G\cap K[\overline{A}], \{1\})\}$

IF $1\in G$ THEN
return ;END$\mathcal{H}$$h arrow SquareFree(\prod HC(g))$ ;$\{h_{1}, \ldots , h_{l}\}arrow Factors(h)$;;$\mathcal{H}arrow \mathcal{H}\cup\{(G\cap K[\overline{A}], \{h\}, G\backslash K[\overline{A}])\}$

F0R $i=1,$

, DO
$l$

$\ldots$$\mathcal{H}arrow \mathcal{H}UCGS(GU\{h_{i}\}, <\lambda,\overline{x})$END
return$\mathcal{H}$

;

;

END

3

開発動機
すでに,

SS-CGS 計算法は従来からある方法に比べていくらかの例で高速に結果を出力することが分かっているが, 実際のところ計算が速い理由が何かはっきりとは分かっていない. 具体的には以下の疑問点がある.
$\bullet$.

ベースシステム (REDUCE, Maple, $Risa/Asir$ ) の多項式演算速度の性能差の影響はどうか ? 特に整数演算部の性能差は確実に存在する.
$K(\overline{A})[\overline{X}]$

順序
さらに,

上の Gr\"obner 基底は$\overline{A}\ll\overline{X}$$K(\overline{A})$上の多項式環で直接計算するより,で計算する方が良いとされているが,このアルゴリズムの登場で,$K$上の多項式環でブロック

どの程度それがいえるのか ?

CGS 計算がずいぶん効率的になったと言われているが,少しでも複雑な問題を入力するとすぐに計算不能に陥るのも事実である.
めると以下のようになる.

そこで,

それでも

改めて研究動機をまと

134

.

1. 実際に利用できる $CGS$ CGB 計算プログラムの提供.
特にプログラムは多くの人に利用されることによって開発が進むので.

2. 研究成果の統合.
鈴木, 鍋島, 倉田とそれぞれで SS-CGS アルゴリズムに関連した研究をしており, その研究成果を統合する.

3. CGS 計算過穆・結果の解析用関数群の開発.
計算効率を上げる工夫, 計算時間等の解析に必要.

4. Selection strategy の研究.
今後の研究課題の 1 つ. Selection stratey とは何か ?

は第 6 節にて触れる.

5. 先ほどの疑問点の検証用.

4

開発プロジェクトと現在までの成果物$Riga/Asir$ PGB プロジェクトとして, 以下の URL にて研究開発成果の提供を行う.

http: $//www$ . math. kobe-u. ac. $jp/Asir/PGB/$
現在までの成果物としては,.

1. SS-CGS アルゴリズムによる $CGS$ CGB 計算プログラム. ss-cgs. rr

2. 倉田・野呂 [6] アルゴリズムによる Discrete Comprehensive Gr\"obner Basae 計算プログラム.
yk-dcgr. rr. このプログラムの詳細は [6] を参照してもらいたい.

CGS CGB 計算プログラム “ss-cgs. rr”

5.
.

$\bullet$

5.1$ss_{-}cgs$.rr は $SS_{-}CGS$ アルゴリズムを実装している.

このプログラムで, パラメータ付き多項式集合$F\subset \mathbb{Q}[\overline{A},\overline{X}]$の reduoed CGS,

rduced CGB が計算できる.
計算過程や計算時間, パラメータ空間の解析用関数が付属している.

パッケージの読み込みの通常のパッケージの読み込み方法と同じである.
locaJ ディスクに $ss$ -cgs.rr をダウンロードした後に.
$Ri_{8}a/Asir$load($\prime\prime\{ss_{-}cgs$.rr のあるディレクトリの full $path\}/ss$ -cgs. rr“);をタイプして読み込む.
なお,

自動的に gr, primdec パッケージも読み込まれる.

reduced faithful CGS,

135

. CGB 計算関数

5.2

$CGS$

5.2.1

ss-cgs.cgs-main, ss-cgs.fcgs-main

ss-cgs. cgsmain($plist$ , vlist, hom , mod ular, order)$0$$::Comprehensive$ Gr\"obner System の計算.

ss-cgs. fcgsmain($plist$ , vlist, homo, modular, order)$::Faithful$ Comprehensive Gr\"obner System の計算.
ret urnvlist
homo

内部表現 ss-branch のリスト.

多項式のリスト.

plist
order
modular

不定元のリストフラグ

数,

リストまたは行列.

フラグまたは素数.

・パラメータ付き多項式リスト plist の変数順序 vlist, 項順序型 order に関する reduced CGS, およびreduced faithful CGS を求める.

.

vlist に含まれない不定元はパラメータと見なされる.

$\bullet$

パラメータの変数順序, 項順序型 (通常は$\bullet$

内部の$\bullet$

フラグ homo の値は内部で呼び出される $nd_{-}gr_{-}trace$ の引数 homo に渡され, 斉次化経由の Gr\"obner.

$\mathbb{Q}$$0’$) および, ブロック順序は自動的に生成される.

上多項式環の Gr\"obner 基底計算では組み込み関数 $nd_{-}gr_{-}trace$ を用いている.

基底計算をするかしないかの制御をする.

modulax の値も内部で呼び出される $nd_{-}gr_{-}trace$ の引数 modular $(p)$ に渡され, Gr\"obner trace アル
ゴリズムの制御をする.
内部表現 $ss_{-}bran\epsilon h$ を読みやすい文字列に変換するには,$\bullet$$ss$-cgs. cgsprint を利用する.

計算例 1:$\mathbb{Q}[z, r, l, s_{1}, c_{1}, s_{2}, c_{2}]$のイデアル,$I=\langle r-c_{1}+l(s_{1}s_{2}-c_{1}c_{2}), z-s_{1}-l(s_{1}c_{2}+s_{2}c_{1}), s_{1}^{2}+c_{1}^{2}-1, s_{2}^{2}+c_{2}^{2}-1\rangle$

に対して, 変数 $z,$ $r,$
これは,

る

[301]

$F$

鴎

[302] $G-$$l$をパラメータとする辞書式順序 $s_{1}>c_{1}>82>c_{2}$ に関する reduced CGS を計算す

The inverse kinematics problem for asimple robot で, [8] の Application 113 からである.
$[r-cl+1*(sl*s2-cl*c2), z-sl-1*(sl*c2+s2*cl). s1^{rightarrow}2+c1^{\wedge}2-1, s2^{\wedge}2+c2^{\wedge}2-1]$

ss-cgs. $cgs_{-}main$ (F. [sl, $cl,$ $s2,c2].0,1.2$ );The CGS computation done.
UP [ 0.03125 0.015625],$\cdot$$ZC\cdot 2$. $ZCT-[00]$ .

$ALC-16,$$MaxDepth\cdot 4,$$AEC\cdot 4$.

...
0.015625 $0]$ ,AET$=[0. 0156250]$$RA\Leftrightarrow$$[$.

, NZCT [ 0.0625 0.03125],$BEC-14$BET
0.015625 $0]$

$NZC\Leftrightarrow 10$.

$=$$-$ $[$.

$MaxWidth\cdot 6$[{ $[s1$ , cl, $s2,c2],2,$ $[z,r,1],0,0$ }, $\{[0]$.

$[ 00 ]$ , $1,\{[],$ $[(1^{\wedge}3-1)*r*z^{-}3+(1^{\wedge}3-1)*r^{\wedge}3*z]$ ,$[-z^{\wedge}2-r^{rightarrow}2+1^{\wedge}2+2*c2*1+1,z^{-}4+(2*r^{rightarrow}2-2*1^{rightarrow}2-2)*z^{\wedge}2+r^{-}4+(-2*1^{\wedge}2-2)*r^{arrow}2+1^{\wedge}4+(4*s2^{\wedge}2-2)*1^{\wedge}2+1$

136
計算結果は reduced CGS を返すが, 見ての通り内部表現の構造体を返す. 計算の最後に, 各部の計算に要した時間, 不要なために除去された segment の数などの情報がレポートされる. 内部表現で出力された

ss-cgs.cgsprint で文宇列に変換できる.

ものは,

[303]
$[]$

ss-cgs. cgsprint (G);, $[(1)*(1-1)*(1+1)*(r)*(z)*(z^{rightarrow}2+r^{\wedge}2)]$$\Leftrightarrow=0$$[-z^{\wedge}2-r^{\wedge}2+1^{-}2+2*c2*1+1$$\downarrow=0$,,$z^{\wedge}4+(2*r^{\wedge}2-2*1^{\wedge}2-2)*z^{\wedge}2+r^{s}4+(-2*1^{\wedge}2-2)*r^{\wedge}2+1^{*}4+(4*s2^{\wedge}2-2)*1^{\wedge}2+1$$(-r+2*c1)*z^{\wedge}2-2*s2*1*z-r^{rightarrow}3+2*c1*r^{-}2+(1^{\wedge}2-1)*r$,,$-r*z^{\wedge}3+2*s1*r*z^{\wedge}2+(-r^{\wedge}3+(1^{\wedge}2-1)*r)*z+2*s1*r^{-}3+2*s2*1*r^{\wedge}2]$[1]$=\cdot 0$,$[(z^{-}2+r^{rightarrow}2-1)]$$!\approx 0$.

[1][1-1] $==0$ ,$[(r)*(z)*(z^{\wedge}2+r^{\wedge}2)]!=0$.

,$[-z^{-}2-r^{\wedge}2+2*c2+2,z^{\wedge}4+(2*r^{\wedge}2-4)*z^{\wedge}2+r^{arrow}4-4*r^{arrow}2+4*s2^{-}2$$(r-2*c1)*z^{\wedge}2+2*s2*z+r^{-}3-2*c1*r^{\alpha}2,r*z^{\wedge}3-2*s1*r*z^{-}2+r^{rightarrow}3*z-2*s1*r^{\wedge}3-2*s2*r^{-}2]$$[1-1_{*}r]=\cdot 0$.

$[(z)]$$!\cdot 0$,$[-z^{\wedge}2+2*c2+2,z^{rightarrow}4-4*z^{\wedge}2+4*s2^{\wedge}2.-c1*z+s2,z^{-}2-2*s1*z]$$[1-1, r,z]–0$ ,$[]$$!\approx 0$,$[c2+1, s2, c1^{\wedge}2+s1^{\wedge}2-1]$$[$

1-1. $z]<0$.

$[(r)]!\cdot 0$.

$[-r^{\wedge}2+2*c2+2,r^{\wedge}4-4*r^{\wedge}2+4*s2^{\wedge}2,r^{\wedge}2-2*c1*r, sl*r+s2]$$[z^{\wedge}2+r^{\wedge}2,1-1]--0$,$[(z), (r)*(z), (r)]!=0$

.

[1]

:
となる. 1 つの segment はパラメータ空間の零点条件と非零点条件, そして, 対応する reduced Gr\"obner
基底の組である. 例えば,
[1-1]$\Leftrightarrow 0$,$[(r)*(z)*(z^{-}2+r^{-}2)]$$!\Leftrightarrow 0$,$[-z^{\wedge}2-r^{\wedge}2+2*c2+2,z^{-}4+(2*r^{\wedge}2-4)*z^{-}2+r^{\wedge}4-4*r^{\wedge}2+4*s2^{\wedge}2$,$(r-2*c1)*z^{-}2+2*s2*z+r^{\wedge}3-2*c1*r^{rightarrow}2,r*z^{-}3-2*s1*r*z^{\wedge}2+r^{arrow}3*z-2*s1*r^{rightarrow}3-2*s2*r^{-}2]$の意味する segme 批は,$(V(l-1)\backslash V(rz(z^{2}+r^{2})),$ $\{-z^{2}-r^{2}+2c_{2}+2,$ $z^{4}+(2r^{2}-4)z^{2}+r^{4}-4r^{2}+4s_{2}^{2}$,$(r-2c_{1})z^{2}+2s_{2}z+r^{3}-2c_{1}r^{2},$ $rz^{3}-2s_{1}rz^{2}+r^{3}z-2s_{1}r^{3}-2s_{2}r^{2}$

}

$)$

137
であり,

$V(l-1)\backslash V(rz(z^{2}+r^{2}))$の任意の点に対して,$\{-z^{2}-r^{2}+2c_{2}+2,$ $z^{4}+(2r^{2}-4)z^{2}+r^{4}-4r^{2}+$$(r-2c_{1})z^{2}+2s_{2}z+r^{3}-2c_{1}r^{2},$ $rz^{3}-2s_{1}rz^{2}+r^{3}z-2s_{1}r^{3}-2s_{2}r^{2}$$4s_{2}^{2},$}$\subset L[s_{1}, c_{1}, s_{2}, c_{2}]$が辞書式順序$s_{1}>c_{1}>s_{2}>c_{2}$ に関する reduced Gr\"obner 基底であることを示している.

5.2.2$ss_{-}cgs.cgsmain,$ $ss_{-}cgs.fcgs$ -main のオプション

ss-cgs. cgs main, ss-cgs.fcgs.nain はオプション指定により色々と動作を変更することができる.
$pv$, po: パラメータに関する明示的な指定を行う. $pv=list$ でパラメータ変数順序を, $po–$: number, lis$t$or matrix で項順序型をそれぞれ指定できる.
phom :phom $=Bag$ で, パラメータ部分のみの Gr\"obner 基底計算に斉次化を用いるかどうかを指定する.
デフォルトでは $phom=0$ である.

pmod :pmod $=Bag$ or prime number でパラメータ部分のみの Gr\"obner 基底計算でのムの制御を行う. デフォルトでは $pmod=1$ である.

$tra\infty$

アルゴリズ

ra

:ra $=flag$ で結果を reduced CGS にするかどうかの制御を行う. デフォルトでは ra $=1$ である.

elim

:elim $=number$ で, パラメータ空間がすでに計算されている別の segment のパラメータ空間に含まれた場合の事前除去のレベルを設定する. $elim=0$ の時は除去は行わず, $elim=- 1$ で根基所属判定を用いて完全な除去を行う. デフォルトでは $elim=2$ である.

prim :prim $=Bag$ で, 素分解を使った計算を行うかどうかの制御を行う. デフォルトでは $prim=0$ で
ある.

zrad

次元根基イデアルを使った計算を行うか:s8-cg8.cgs.nain のみのオプション. $zrad=flag$ で,どうかの制御を行う. デフォルトでは $zrad=0$ である.
$0$

print :print $=Rag$ で, 計算途中の中間情報を表示する. デフォルトは $pdnt=0$ である.

ss-cgs.cgs, ss-cgs.hcgs, ss-cgs.fcgs, ss-cgs.hfcgs

5.2.3

ss-cgs. cgs(plist, vlist, order)
ss-cgs. hcgs ($p1ist$ , vlist, order)$::Comprehensive$ Grobner System の計算.

ss-cgs. cgs (Plist, vlist, order)s-cgs. hf cgs (Plist, vlist, order)$::Faithful$ Comprehensive Grobner System の計算.
$f$

$s$

retun
vlist
$\bullet$.
$\bullet$

内部表現 $ss$ -bran $ch$ のリスト.

plist

不定元のリスト

order

多項式のリスト.
数, リストまたは行列.

パラメータ付き多項式リスト plist の変数順序 vlist, 項順序型 order に関する reduced CGS および,
reduced faithful CGS を求める.

ss-cgs. $cgs$ (Plist, vlist, order) は, ss-cgs.

$cgs\ovalbox{\tt\small REJECT} ain$($plist$ , vlist, $0,1$ , order) の省略形である.

ss-cgs. hcgs(Plist, vlis , order) は, ss-cgs.cgs-main(plist, vlist, 1, 1, order) の省略形である.
$t$

138

.
.

ss-cgs. cgs (plist, vlist, order) は, ss-cgs. fcgs main(plis , vlis
$f$

$t$

$t,$

$0,1$ ,

order) の省略形である.

ss-cgs. hf cgs (plist, vlist, order) は, ss-cgs. fcgsmain( $plist$ , vlist, 1, 1, order) の省略形である.

5.2.4$ss_{-}cgs.cgb$

ss-cgs. $cgb$ ( $plist$ , vlist, order)
ss-cgs. hcgb ($plist$ , vlist, order): : Comprehensive Gr\"obner Basis の計算.

turn
vlist

$t$

不定元のリスト多項式のリスト.
数,

リストまたは行列.

パラメータ付き多項式リスト plist の変数順序 vlist, 項順序型 order に関する reduced CGB を求める.

$\bullet$$\bullet$

plis
order

内部表現 ss-branch のリスト.

$re$ss-cgs. cgb(plist, vlist, order) は, 8ss $-cgs.fcgs_{-}main$ ($plist$ , vlist, $0,1$ , order) で faithful reduced
CGS を計算し, 結果の和集合を返す.

$\bullet$ss-cgs. hcgb(plist, vlist, order) は, ss-cgs. fcgs-main(plist, vlist, 1, 1, order) で f 菰 thful reduced
CGS を計算し, 結果の和集合を返す.

計算例 2:

先ほどの計算例でのイデアル $\langle r-c_{1}+l(s_{1}s_{2}-c_{1}c_{2}), z-s_{1}-l(s_{1}c_{2}+s_{2}c_{1}), s_{1}^{2}+c_{1}^{2}-1, s_{2}^{2}+d-1\rangle\subset$
に対して, 辞書式順序 $s_{1}>c_{1}>s_{2}>c_{2}$ に関する reduced CGB を計算する.

$\mathbb{Q}[z, r, l, s_{1}, c_{1}, s_{2}, c_{2}]$

[301]

$F$

$[r-c1+1*(s1*s2-c1*c2), z-s1-1*(s1*c2+s2*c1). s1^{-}2+c1^{-}2-1_{*}s2^{r}2+c2^{-}2-1]$

富gs. $cgb$ ( , [sl, cl, 82. $c2].2$ );$[302]G\Leftrightarrow ss_{-}c$$F$

The faithful CGS computation done.

UP$\cdot$$ZCT$. $[ 00]$ .
[$AEC\Leftrightarrow 0$

$RA=$

$AET$

...

$[ 00],$. . $[ 00]$ .

0.015625 0.046875],

NZCT [ 0.234375 0.09375],$NZC\approx 15,$

$BEC\cdot 20,$

BET$\cdot$$ZC\cdot 2$$\cdot$$[ 00],$$ALC\cdot 17,$

$MaxDepth\cdot 4$,.

$MaxWidth-6$$[s2^{-}2+c2^{\wedge}2-1,c1^{\wedge}2+s1^{\wedge}2-1,-cl*z+sl*r+s2*1,$$cl*z-sl*r-s2*1,$ $-z^{\wedge}2-r^{\wedge}2+1^{\wedge}2+2*c2*1+1$ ,.

$-z^{-}2+2*s1*z-r^{-}2+2*c1*r+1^{\wedge}2-1.z^{arrow}2+r^{arrow}2-1^{\wedge}2-2*c2*1-1,z^{\wedge}2-2*s1*z+r^{-}2-2*c1*r-1^{\wedge}2+1$$(-r+2*c1)*z^{rightarrow}2-2*s2*1*z-r^{\wedge}3+2*c1*r^{\wedge}2+(1^{\wedge}2-1)*r$$(r-2*c1)*z^{\wedge}2+2*s2*1*z+r^{\wedge}3-2*c1*r^{\wedge}2+(-1^{-}2+1)*r$ ,:ss-cgs.cgsprint

5.2.5
$s$

s-cgs. cgsprint (brlist)$::CGS$ の内部表現を読みやすい文字列に変換する.

return文字列.

brlistCGS の内部表現 $ss$ -bran $ch$ のリスト.

.

139
出力は文字列で,を表す.
$\bullet$$[slist]==0$ , [tlist] $!=0,$ $[gbl_{l}’st]$“[slist] $==0$ ’ は slist に含まれるすべての多項式がまれる多項式のうち, 少なくとも 1 つが

5.3

$0$

で 1 つの segment ( $V(slist)\backslash V(tlist)$ , {gblist})$0$になることを意味し,[tlist] $!=0$ ’ は tlist に含でないことを意味する.

CGS 解析用関数あまり詳しくは述べないが, 以下のような解析用関数を用意している.

ss-cgs.segprint :ss-cgs.8egprint(扮揄 , number) で CGS (内部表現) に含まれる詳しい情報を文字列
$t$

で返す.

ss-cgs.segno: $ss$ -cgs. segno(nolist, brlist) で CGS (内部表現) のうち番号 nolist を持っ segment を抽出する.

ss-cgs.trmlseg :ss-cgs. trmlseg(brlist) で, CGS 計算の各分岐の最終 segment を抽出する.
$ss_{-}cgs.upperseg:ss_{-}cgs.$ uPperseg(nolist, brlist) で CGS (内部表現)のうち番号 nolist を持つ segmentの上位 segment をすべて抽出する.

ss-cgs.seghdim :ss-cgs. seghdim(brlist) で, CGS (内部表現) の各 segment のパラメータ空間 (零条件多様体) の次元を計算する.
これらの関数はどちらかと言えば, アルゴリズムのメンテナンス用関数で開発者向けのものであるが, い
まだに多くの問題が CGS 計算で時間を大量に使うため, 利用者が状況を解析するのにも役に立っと思われる.

6

CGS 計算における選択戦略
SS-CGS の中心である,を項順序$<_{\overline{A}},\overline{x}$に関する$G\backslash K[\overline{A}]\}\subset K[\overline{A}]$アルゴリズム CGS は再帰的なアルゴリズムである.
$\langle F\rangle\subset K[\overline{A},\overline{X}]$とする. このとき,の reduced Gr\"obner 基底とし,$\{h_{1}, \ldots, h_{t}\}=$$(V(G\backslash K[\overline{A}])\backslash (V(h_{1})\cup\cdots\cup V(h_{l})), G)$

CGS の 1 つの segment であるが, その他の segment を得るために,$l$$F\subset K[\overline{A},\overline{X}]$

に対して.

$G$

{HC $<x(g)|g\in$

は $F$ の項順序個の多項式集合 $F\cup\{h_{1}\},$$<\overline{x}$$\ldots,$

に関する$F\cup\{h_{t}\}$に対して, 再帰的にアルゴリズム CGS を適用していく.

このとき, アルゴリズムの動作として,$F\cup\{h_{1}\},$$\ldots,$$F\cup\{h_{t}\}$の内のどれから segment 計算をしていく

これまで論じられてこなかった. しかし, 計算中に不要な segment を適宜除去していく過程 (すでに計算が完了した別の segment のパラメータ空間に新しい segment のパラメータ空間が含まれるかについては,場合に不要と判断して除去をする) を考えれば,どの多項式集合から計算していくか (選択戦略) は重要な問題といえる. 例えば,$\langle F\rangle=\langle aX^{3}Y+cXY^{2}, X^{4}Y+3dY, cX^{2}+bXY, X^{2}Y^{2}+aX^{2}, X^{5}+Y^{5}\rangle\subset \mathbb{Q}[a,b, c,d,X,Y]$を変数とするイデアルの $X>Y$ を満たす辞書式順序 $<\{X,Y\}$$F\cup\{h_{t}\}$ に対して,に関する CGS を今回の実装で計算することを考える. 先ほどの $F\cup\{h_{1}\},$
パラメー
タのみの項集合 $T(a, b, c, d)$ 上の全次数逆辞書式順序 $<\{a,b,c,d\}$ で,の小さい順に $F\cup\{h_{t}\}$
}

に対して,

$a,$ $b,$ $c,$$d$をパラメータとし,$X,$ $Y$$\ldots,$$HT<ta,b,e,\text{\’{e}}$$(h_{i})$を選んできて, 計算をした場合は, 全計算時間は 0688 秒, 全 segment 数は 31 で, 計算中に除去された

segment 数は 100 であり, 不要な segment の検出には 0563 秒かかるが, 大きい順に選んだ場合は, 全計140
算時間は 2594 秒, 全 segment 数は 89 で, 計算中に除去された segment 数は 234 であり, 不要な segmentの検出には 2234 秒かかる. ちなみに, 不要な segment の除去を行わなかった場合は, 全計算時間は 2543
秒, 全 segment 数は 7930 にもなる.

7

最後に
今回は, $Risa/Asir$ PGB プロジエクトの発足と, 鈴木・佐藤の SS-CGS アルゴリズムの実装を中心に紹介をした.

SS-CGS アルゴリズムの最適化に関する新しい結果である, 鍋島 [10] の実装はまだ行っておらず,
実装評価の実施を予定している. $Risa/Asir$ PGB プロジェクトでは, $CGS$ CGB 計算利用者の方々からまた,.

のご要望, そして問題提供をお待ちしております.

参考文献[1] Becker, T. and Weispfenning, V. Grobner Bases. GTM 141, Springer, 1993.
[2] Cox, D., Little, J. and O’Shea, D. Ideals, Varteties, and Algorithms, Third Edition. UTM, Springer,

2007.
[3] Cox, D., Little, J. and O’Shea, D. Using Algebrai Geometry, Second Edition GTM 185, Springer,
$c$

2005.
[4] Dolzmann, A., Sturm, T. and Neun, W. CGB: Comprehensive Gr\"obner as es.
http: $//students.fim$ . un -passau. $de/\sim reduce/cgb/$ . 2007.
$B$

$i$

[5] Kalkbrener, M. On the Stability of Grobner Bases Under Specializations. J. Symbolic Computation.
Vol. 24/1, pp. 51-58. 1997.
[6] Kurata, Y. and Noro, M. Computation of Discrete Comprehensive Gr\"obner Bases Using Modular Dynamic Evaluation. Proc. Intemational Symposium on Symbolic and Algebraic Computation(ISSAC 07). ACM Press, New York, pp. 243-250. 2007.
[7] Manubens, M. and Montes, A. Improving the DISPGB algorithm using the discriminant ideal.
Symbolic Computation. Vol. 41/11, pp. 1245-1263. 2006.

.

$J$[8] Montes, A. A new algorithm for discussing Gr\"obner bases with parameters. J. Symbolic Computation.
Vol. 33/2, pp. 183-208. 2002.
[9] Montes, A. DPGB: Discussing Parametric Gr\"obner Bases.
http: $//ww-ma2$ . upc. $es/\sim montes/$ . 2007.
[10] Nabeshima, K. A Sp\’e-Up of the Algorithm for Computing Comprehensive Gr\"obner Systems. Prvc.
Intemational Symposium on Symbolic and Algebraic Computation (ISSAC ’07). ACM Press, New
York, pp. 299-306. 2007.
[11] Noro, M. and Yokoyama, K. Computational Fundamentals of Grobner Bases (in Japanese). University of Tokyo Press, 203.

[12] Noro, M. et al. A Computer Algebra System $Rsa/Asir$ .
http: $//www$ . math. $kobe-u.ac.jp/Asir/asir$ . html. 2007.

141[13] Sato, Y. and Suzuki, A. Discrete Comprehensive Grobner Bases. Proc. Intemational Symposium on
Symbolic and Algebmic Computation (ISSAC 01), ACM Press, New York, pp. 292-296. 2001.
[14] Sato, Y., Suzuki, A and Nabeshima, K. Discrete Comprehensive Grobner Bases II. Computer Mathematics, Proc. 6th Asian Symposium (ASCM 2003), Lecture Notes Series on Computing Vol. 10,

World Scientific, pp. 240-247, 2003.
[15] Sato, Y., Suzuki, A and Nabeshima, K. ACGB on Varieties. Proc. 6th Intemational Workshop on
Computer Algebra in Scientific Computing (CASC 2008), pp. 313-318. 2003.
[16] Suzuki, A. and Sato, Y. An alternative approach to Comprehensive Gr\"obner Bases. J. Symbolic
Computation. Vol. 36/3-4, pp.
. 2003.
$649\triangleleft 67$[17] Suzuki, A. and Sato, Y. A Simple Algorithm to Compute Comprehensive Gr\"obner Bases Using
Grobner Bases. Proc. Intemational Symposium on Symbolic and Algebraic Computation (ISSAC06), ACM Press, New York, pp. 326-331. 2006.
[18] Weispfenning, V. Gr\"obner bases for polynomial ideals over commutative regular rings. Proc. EUROCAL 87, LNCS Vol. 378, Springer, pp. 336-347. 1989.

[19] Weispfeuning, V. Comprehensive Grobner bases. J. Symbolic Computation. Vol. 14/1, pp. 1-29. 1992.
[20] Weispfenning, V. Canonical Comprehen8ive Grobner bases. J. Symbolic Computation. Vol. $36/3A$ ,pp. 669-683. 2003.