数理解析研究所講究録
第 1652 巻 2009 年 19-25

19

グレブナー walk アルゴリズムの実装と効率化について
野呂正行

崎山裕尊

MASAYUKI NOROHIROTAKA SAKIYAMA神戸大学大学院理学研究科*

神戸大学大学院自然科学研究科\daggerAbstract
グレブナー walk アルゴリズムは, ある項順序でのグレブナー基底から他のグレブナー項順序のグレブナー基底を計算する change of orderging アルゴリズムの一っである. 1997 年に Collart ら [2] が提案して以来, さまざまな改良が行われてきた ([3][4][5]). ここでは, グレブナー wal-k について簡単に紹介し,Risa$/Asir$ での実装, 効率化のための改良およびその効果について述べる.

1

Change of ordering アルゴリズム
多項式イデアル

$I$の有限部分集合 $G$ が, ある項順序 $<1$ に関するグレブナー基底であることがあらかじ

め分かっている場合に, 別の項順序 $<2$ に関するグレブヂー基底を計算することを一般に change of orderingと呼ぶ. この方法としては以下のような方法が知られている.

.
.
.

Buchberger アルゴリズム$G$がグレブナー基底であることを忘れて単に Buchberger アルゴリズムを実行するだけのことだが,既に $G$ が「良い」性質を持っている場合には計算が効率よくできる場合がある.

FGLM アルゴリズム$I$が$0$次元の場合には, 線形代数を用いて $<2$ のグレブナー基底を計算することができる.

modular change of ordering
係数体が $Q$ の場合, in $<1(G)$ を割らない素数$p$をとり, Fp 上で$(G\rangle$の$<2$に関するグレブナー基底を計算して, その要素と同じサポートを持つ の元を求めることで, $<2$ に関するグレブナー基底を求めることができる. 求め方としては, Buchberger trace アルゴリズムで候補生成のみを行う, あるいは未定係数法により線形代数に持ち込む方法などがある.
$I$.

Hilbert driven アルゴリズム$I$が斉次の場合, $K[x]/I$ が次数環になり, その各斉次成分の次元が Hilbert 関数により分かることを用いて, Buchberger アルゴリズム実行における userless $pa$廿の計算を省く方法である.
$\bullet$

グレブナー walk アルゴリズム$<1,$ $<2$と compatible な weight vector (後述) を選び, それらを結ぶ線分と交わるグレブナー cone(後述) に対応するグレブナー基底を次々と計算していく方法である. weight wctor がうまくとってあれば, 手間の少ない Buchberger アルゴリズム実行と, inter-reduction が主たる計算となる.
’noro@math. kobe-u. ac.jp$\uparrow\epsilon akiyamaOmath.kobe\cdot u$. ac.jp20
それぞれに特色があり, 入力に応じて使い分けられる.

これまで Risa $/Asir$ では, modular change ofordering の実装, 改良を行ってきたが, 特に次元でないイデアルの場合に効率に不満があった. 最近,
Fukuda らにより新しいグレブナー walk アルゴリズム (generic walk [5]) が考案された. これは, これまで提案された weight の摂動方法の曖昧さを除く方法を提案しており理論的に興味深く, また, 実用性も感じられたため, Risa $/Asir$ に実装して実験を行った. その過程で, 効率上の問題が発生したが, それに対する一っの改良を提案する. また, 常に問題となる, $<2$ と compatible な weight をどうとるか, について, 安直ではあるが有効な方法を提案する. 最後に, これらの改良を採り入れた generic waJk, walk アルゴリズムを実装した場合の実験結果を示す.
$0$2

グレブナー walk アルゴリズム
以下では, 多項式 $f$ に対し, 項順序 $<$ に関する先頭項を in $<(f)$ , weightに関する最高次部分を 4 $(f)$ で表す. また,K を体, $R=K[x_{1}, \ldots,x_{n}]$ とし, イデアル $I\subset R$ を固定する. 項順序 $<$ に関するの簡約グレブナー基底を GB $<(I)$ と書く. $\langle in_{w}(f)|f\in I\rangle$ を $in_{w}(I)$ と書く. 一般に, 多項式集合 $F$ ,$w\in R_{\geq 0}^{n}$$I$$w\in R_{\geq 0}^{n}$に対し, in $<(f)=$ in $<(in_{w}(f))$ が全ての $f\in F$ について成り立っとき, $w$ は $<$ について $F$ とcompatible であるという. $C<(I)=$ { $w\in R_{\geq 0}^{n}|w$ は $<$ について GB $<(I)$ と compatible} と定義し, $<$ 上のグレブナー cone と呼ぶ.
$C<(I)=$ { $w \in R_{\geq 0}^{n}|f=cx^{a}+\sum_{\beta<\alpha}c_{\beta^{X^{\beta}\in}}$ GB $<(I)$ に現れる全ての に対し$\beta$$\langle w,\alpha\rangle\geq\langle w,\beta\rangle$}(1)だから, $C_{<}(I)$ は凸多角錐である. あらゆる項順序に関するグレブナー cone およびその face を全部集めた集合を $GF(I)$ と書く.
定理 1 (Mora-Robbiano [1])
$GF(I)$ はた D である.

特に, $GF(I)$ は有限集合であり, グレブナー cone の集合と, {in $<(I)|<$ は項順序} の集合は 1 対 1 に対応する. 後者は, 相異なる GB $<(I)$ の集合と考えてもよい. 以下で, weightw で比較し, 項順序 $<$ を tie
breaker とする項順序を $w+<$ と書く.
グレブナー walk アルゴリズムは, 項順序 $<1,$ $<2$ に対し GB $<1(I)$ から GB $<a(I)$ を計算する change ofordering アルゴリズムである. $w_{1}\in C_{<1},$ $w_{2}\in C<a$ を選び,$(1\leq t\leq 1)$と$w_{2}$を結ぶ線分 $L:w(t)=(1-t)w_{1}+tw_{2}$を考える. この線分は, 有限個のグレブナー cone と交わる. すなわち, $0=t_{0}<t_{1}<\cdots<t_{m}=1$および相異なるグレブナー cone$t_{i}\}\subset C_{1}$$w_{1}$. ここで,$L_{:}$$C_{1},$ $\ldots C_{m}$が存在して, $L=L_{1}\cup L_{2}\cup\cdots\cup L_{m},$ $L:=\{w(t)$$ti- i\leq t\leq$

が 2 つ以上の cone に属する場合には, $w(t_{i})+<2$ に対応する cone を選ぷものとす

る. 次の定理がグレブナー walk の基本である.

定理 2 (cf. Fukuda et al.[5] Propositlon 5)$<,$ $<$’ を項順序とし, weightw が $w\in C\cap C$ , を満たすとし, $G$ をイデアル$I$の $<$に関するグレブナー基底とする. このとき次が成り立つ.

1. GB $<(in_{w}(I))=\{in_{w}(g)|g\in G\}$

2 $H=$ GB

3. GB$<^{\prime(in_{w}(I))}$$<^{\prime(I)}=$

ならば, $\{f- NFG(f)|f\in H\}$ は

GB $w+<’(I)$ .

$I$の $w+<’$に関する極小グレブナー基底.

21
この定理により, 隣り合う cone に対応するグレブナー基底を, GB $<(in_{w}(I))$ を仲立ちとして変換することができる. $<’$ に関する極小グレブナー基底を interreduce(相互簡約) して簡約グレブナー基底を得る操作
を convert $(G, w, <, </)$ と書く.

アルゴ

in $<1(G_{0})\neq$ in $<z(in_{w_{1}}(G_{0}))$ thenifGe灼

ズム 1 (グレブナー walk7) レゴリズム)$l)$$arrow$

convert $(G_{0}, w_{1}, <w+<2)$$e$$Garrow G_{0}$endif$t_{0}arrow 0$do$t_{1} arrow\max\{s>t_{0}|w(s)\in C_{w(t_{0})+<2}\}$$Garrow c\sigma nvert(G,w(t_{1}),w(t_{0})+<2,w(t_{1})+<2)$if$t_{1}\geq 1$

ret urn$G$$t_{0}arrow ti$

end $do$3

generic グレブナー walk

前節のアルゴリズムにおいては, cmvert の効率が全体の効率を左右する. convert においては, $in_{w}(I)$のグレブナー基底計算の入力となる $\{in_{w}(g)|g\in G\}$ に現れる多項式の複雑さが問題となる. 考えるべき$w$ はグレブナー cone の bound4 上にある.
この場合, $w$ を含む face の数が多い程, $in1_{w}(g)$ の項数が増え$()$$()$る可能性がある.
例1$G=\{x+y_{1}+\cdots+y\iota, f_{2}(y), \ldots , f_{k}(y)\},$ $y=(y_{1}, \ldots,y\iota)$

式順序 $<1$ での簡約グレブナー基奥とする.
$w_{1}=(1,1, \ldots, 1),$ $w_{2}=(1,0, \ldots,0)$$\langle G)$

で, $G$ が $x>y_{1}>\cdots>y\iota$ なる全次数辞書の辞書式順序 $<2$ でのグレブナー基底を計算する場合,を選ぶことができる. このとき, 線分 $L$ は $C_{<}1(I)$ に含まれる. よって, ループ内の最初のステップで $t_{1}=1$ となる. すると, $G$ のが, この場合, $f_{2}(y),$$\ldots,$$f_{k}(y)$$w_{2}$-斉次な最高次部分を抜き出すことになるがそのまま出て来ることになり, 単なる $<2$ に関するグレブナー基底計算と変わらないことになる.
がグレブナー cone と少ない個数の face
この欠点を回避するため, 各ステップで $w(t_{1})$ を摂動させ, 線分と交わるようにする方法が提案された (fractal walk [3]). 原理は次の命題である.
$L_{i}$

命題 3

項順序 $<$ が weigbt の列$(\omega_{1}, \ldots,\omega_{n})$による辞書式順序として与えれているとする. このとき$\omega_{\epsilon}=\omega_{1}+\epsilon\omega_{2}+\ldots+\epsilon^{n-1}\omega_{n}$とおくと,$\epsilon>0$を十分小さくとれば,$\omega_{e}$は $<$ と(2)compatible で $C_{<}(I)$ の内部にある.の始点あるいは終点 (あるいは双方) を十分小さい によりこの形に摂動させればそうすれば, 直
よって,が cone を出るとき, 1 つの facet のみ通過することが期待できる. ここで, 始点の摂動は, 既線 (折れ線)$L_{i}$$\epsilon$$L$22に始点が現在のグレブナー基底と compatible なので計算で可能となるが, 終点の摂動は, 新しいグレブナーがいくつ基底がないと計算できないので, fractal walk では heuristic な試行錯誤で行われている. 特にかの face の交わり上にある場合, 最終ステップを効率よく計算するにはの摂動が必須である. Than Q.
$w_{2}$$w_{2}$Nam [4] は, グレブナー基底の元の degree bound を元に, 摂動を deterministic に与えているが, weight のの成分が非現実的な大きさになるため, 実用的には問題がある. generic walk [5] では, この問題を,から (2)「無限小」摂動を導入することで解決した. $<1,$ $<2$ を表す weight の列がそれぞれ $CC1’ 2$ の内部にあり, これによりを作る. このとき,を十分小さくとれば,がグレブナー cone の内部を通過しながら, cone を出るときには常にただ一つの facet とらを結ぶ線分$w_{1},$$(\omega_{1}, \ldots,\omega_{n}),$$\omega_{\delta},$$\delta,$$\tau_{\epsilon}$$\epsilon$$\omega_{\delta},$$w_{2}$$(\tau_{1}, \ldots, \tau_{n})$$\tau_{\epsilon}$$L_{\delta.\epsilon}$

交わることが証明できる.
が cone を出るときにどの facetを十分小さくとることにより, walk の各ステップにおいて,更に,を表すを用いた計算のみで求めることができる. 各 facet はある vectorと交差するかを$<2$
weight$v=\alpha-\beta\in Z^{n}$ (は (1) に現れる vector) により $F_{v}=\{w\in R_{\geq 0}|\langle w,v\rangle=0\}$ と表される. $u,v\in Z^{n}$$\delta,$$L_{\delta,e}$$\epsilon$$\rangle<1,$$\alpha,$$\beta$$F$に対し, facet preorder$\prec$を$u\prec v\Leftrightarrow(\langle\tau_{1},u\rangle v, \ldots, \langle\tau_{n}, u\rangle v)<1,l\epsilon ae(\langle\tau_{1},v\rangle u, \ldots, \langle\tau_{n}, v\rangle u)$(3)で定義する. ここで, $<1,lex$ は $<1$ を左の成分から辞書式に適用することを意味する. すると, walk の各が交差する facet は, faoet preorder
ステップにおける cone の facet のうち, 進行方向にあって最初に$L_{\delta,\epsilon}$で最小のものであることが証明できる. 注目すべきことは, 実際に交点での weight $w$ を求めることなしに, 交差する$\sum_{\beta}c_{\beta}x^{\beta}|x^{\alpha}$facet
は $g$を求めることができることである.

さらに,に対し, $in_{w}(g)=\{c_{\alpha}x^{\alpha}+$の先頭項, $\alpha-\beta\prec v$ かつ $v\prec\alpha-\beta$ } となり $in_{w}(g)$ の計算にも $w$ は不要である. convert$F_{v}$

この$w$においては, 現在のグレブナー基底 $G$ に関する剰余計算が必要である. 途中の weight がないと項順序が定められないが, $G$ の先頭項は常に知られていることに注意する.

定轄 4$G$をある項順序 $<$ に関する$I$のグレブナー基底とするとき $\{(g, in<(g))|g\in G\}$ を marked グレブナー基底と呼ぶ.

marked グレブナー基底が与えられればそれによる剰余計算は, 項順序なしで可能である. このようにして,形式的にを考え, それらが交差する cone をたどりながら walk を実行するのが generic walk アルゴリ
はズムである. この場合, $in_{w}(g)$ に現れる項が平行であるものに限られる. これはどのようなweight を用いても同時に含まれるので, $in_{w}(g)$ の項数は最小に押えられている.
$L_{\delta,e}$$x^{\beta}$$\alpha-\beta$

generic グレブナー walk の実装と問題点

4

Fukuda et al. [5] では, ある種の toric イデアル (lattice イデアル) に対する実装とその効果が述べられている. Risa/Asir 上への実装においては, まず Asir 言語でプロトタイプを書き, weight の計算, marked
グレブナー基底による剰余計算など, 効率に影響を与える関数を組み込みとした.
$\bullet$.

dp-compute last-w $(G.H,W,M1,M2)$
現在の cone に対応する marked グレブナー基底 $(G,H)$ を与え,facet を表す vector を求める. $M1,$ $M2$ は $<1,$$<_{2}$$L_{\delta,\epsilon}$が facet $F_{W}$ の次に交差するを表す行列である.

dp-true $\ovalbox{\tt\small REJECT} fnared(Ind.F,G,H)$
グレブナー基底による剰余を求める dp-true-nf の marked グレブナー基底版である.

23
しかし, 我々の最初の実装で, より一般的なイデアルに対して辞書式 頃序への変換を試したところ, GB $<_{2}(in_{w}(I))$$|$の計算は常に高速であるが, marked グレブナー基底による剰余計算が大変時間がかかる場合がしばしばあることが分かった. これは, dividend に現れる項が正しい項順序で整列されていないため, 低い順序の項を無駄に書き換えてしまうことが起こっているためである. これを解決する方法として, やや本末転倒かっ安直ではあるが, marked グレブナー基底 $G$ から, それを与えるような weight を計算し, その weight により剰余計算を行うことにした. これは, 連立不等式系(4)$\{\langle w,\alpha-\beta\rangle>0|(g,x^{\alpha})\in G,x^{\beta}\in Supp(g)\backslash \{x^{\alpha}\}\}$の解を求めることを意味する. 経験上, 不等式の数は数千に達する場合も多いため, 定評ある cddlib (Fukuda,2006) に実装されている, 線形不等式系の内点解を求める関数 ddJindRelativelnterior を, OpenXM サーバ ox-cdd, ox-cddgp (藤原 [6]) に追加し使用することにした.に前者は浮動小数による計算, 後者はよる厳密計算を行う. ここで必要な weight はあくまで剰余計算のヒントであるため, 完全に先頭項を与える必要はないと考えたため, 浮動小数版も用いることにした. この計算は, 各ステップでの interreduce の前に行われる. ここで得た新しいグレブナー基底は, 次のステップでの GB $<2(in_{w}(I))$ に続く剰余計算でも使われるが, この weight はそこでも用いられる.
$\Psi P$

5

通常の walk における modular 計算の応用

前節では, generic walk をより効率化するために, 敢えて途中で weight を逆算する方法を提案した. ここでは, 元の walk に戻り, スタート, ターゲットの weight wl,を摂動する方法を考える.
については,既にグレブナー基底を知っているため, 前節の線形不等式系 (4) を解くことで cone 内部の vector を得る.
である. 有理数体上での $<2$ に関するグレブナー基底を $G$ とするとき, 有限体問題は上での計算により, $<2$ に関するグレブナー基底はなんらかの方法で効率よく計算できる場合がしばしばある. このとき, 有限個の素数 を除いて,の各元のサポートは, $G$ のそれと一致している. よって,を使った計算で, の内部の vector を推測し, そこをターゲットとして通常の walk を行うという方法が考えられる.
$w_{2}$$w_{1}$$u;_{2}$$F_{p}$$G_{p}$$G_{p}$$P$$G_{p}$$C_{<}$

6

実験

これまでに述べた方法を実装し, いくつかの例について計算を行った結果を示す. 全て, 全次数逆辞書式順序から辞書式順序への change of ordering を行う.

6.1

種々の change of ordering アルゴリズムの比較$\bullet t$

屋 lex

まず有限体上で, 次元イデアルに対しては, FGLM により, 次元でない場合には, Buchberger アルゴリズムにより辞書式順序グレブナー基底を計算する. そのサポートをもとに未定係数法と Hensel
lif も ing で有理数体上の基底を計算する.
$0$.

$0$gwalkmarked グレブナー基底と compatible な weight を ox.cdd により計算し,逆辞書式順序を用いて interreduce を行う generic グレブナー wal-k を実行する.

$ti\triangleright breaker$として全次数24.

mwalk

入力のグレブナー基底, および有限体上での辞書式順序グレブナー基底それぞれについて, compatibleな weight を ox-cdd により計算する. それらに対し, tie-breaker として全次数逆辞書式順序を用いる項順序をそれぞれ設定し, 通常のグレブナー walk を実行する.
計算環境は, Intel Xeon X5365 $3GHz,$ $16GB$ memory である. 計算時間は実経過時間を秒で表示した. 入力多項式イデアルは [9],[10] から取った. かっこ内の数字は walk のステップ数を表す. ldim は, 次元イデアルの場合, 剰余環の線形次元を表す.
は, イデアルが 次元でないことを表す. これらの例にっいてい$0$–$0$

表 1: 種々の change of ordering アルゴリズムの比較

次元イデアルに対しては, 概ね modular FGLM である tolex がまだ高速な場合が多いが, いくつ次元でない場合の例は少ないが, やはり walk が tolex に勝る例がある
かの例では walk が勝っている.
(cohn3). walk の間の比較も, これらの例については劇 alk がやや有利に見えるが, はっきりした優劣は見えば,$0$$0$られない. 興味深い点は, step 数が必ずしも計算時間と相関しない点である. これは, gwalk においてはもともとの weight の近くの facet を通過していくのに比べ, mwalk では modular 計算でターゲットの weightとは相当かけ離れた vector が選ばれている可能性がある. 結果として通過する coneを選ぶ場合, このは全く異なっていることもあり得る. よって計算経過は異なり, step 数も異なるのであろう. いずれにせよ,計算時間の比較をみれば, どのアルゴリズムも捨て難い. CPU 数に余裕があれば, 同時に実行するのが現実$w_{2}$的かもしれない. なお, [7] においては, 中間的な項順序への walk(寄り道) を行うことの効果についての実25験も行った. これは, 例えばターゲットが辞書式順序の場合, いくつかの変数を消去する項順序 (ブロック順序 への walk を行 , そこからターゲットヘ walk するという方法である. この場合, 中間項順序で消去す$A$$)$$a$る変数の個数を heuristic に決める必要があるものの, 直接 walk するより高速になる場合があることが示されている.

参考文献[1] Mora, T., Robbiano, L., The Groebner fan of an ideal. J. Symb. Comp., 6, 183-208 (1988).

[2] Collart, S., Kalkbrener, M., Mall, D., Coverting bases with the Groebner walk. J. Symb. Comp., 24,443.464 (1997).
[3] Amrhein, B., Gloor, O., The Fractal Walk. Buchberger, B. Winkler, F. (eds), Groebner Bases andApplications, 305-322 (1998).

[4] Tran, Q., A fast alorithm for Groebner basis conversion and its applications. J. Symb. Comp., 30,451-467 (2000).
[5] Fukuda, K., Jensen, A.N., Lauritzen, N., Thomas, R., The generic Groebner walk. J. Symb. Comp.,
42, 298-312 (2007).

[6] 藤原健志, multiva iate resultants の実装と比較. 神戸大学修士論文 (2005).
[7] 崎山裕尊, 種々の Groebner walk algorithm の実装および改良について. 神戸大学修士論文 (2008).
[8] Fukuda, K., cddl ib. http $://\iota ww$ . if or. math. ethz. $ch/-fukuda/$ cdd-home/cdd. html (2007).

[9] http: //invo.

$j$inr. $ru/$.

[10] http $://ww$ symbol cdat
$i$

$a$

. org