%$OpenXM: OpenXM/doc/compalg/effgr.tex,v 1.4 2001/02/27 08:07:24 noro Exp $ \chapter{グレブナ基底計算の効率化} 第 \ref{chapgr} 章でグレブナ基底を計算するアルゴリズムである Buchberger アルゴリズムの最も原始的な形を示した. しかし, そこで述べた ように, アルゴリズム \ref{buch}をそのまま実行することは, 効率の点から みて問題がある. これは, アルゴリズムの進行につれて, 正規化して 0 にな る対が増加していくためである. また, 対の選び方にも任意性がある. どのよ うな選び方を用いても, 最終結果であるグレブナ基底の一意性は保証されてい るが, 選び方により効率に大きな差がでることが多くの実験により確かめられ ている. 本章では, グレブナ基底の計算を効率化するさまざまな方法を紹介 する. \begin{nt} 以下で, 次のような記法を用いる. \noi $p$ : 素数.\\ $GF(p)$ : $p$ 元体.\\ $\Z_{(p)}$ = $\{a/b \mid a \in \Z; b \in \Z \setminus p\Z\} \subset \Q$ : $\Z$\, の $p\Z$ における局所化.\\ $X = \{x_1,\cdots,x_n\}$ : 不定元.\\ $\phi_p$ : $\Z_{(p)}[X]$ から $GF(p)[X]$ への標準的射影. $\phi_p(a/b) = \phi_p(a)/\phi_p(b)$. ($a \in \Z$, $b\in \Z\setminus p\Z$.)\\ $<$, $<_0$, $<_1$, $<_i$ : term order.\\ $HT_<(f)$ : $f$ の $<$ に関する頭項.\\ $HC_<(f)$ : $f$ の $<$ に関する頭係数.\\ $T(f)$ : $f$ に現れる項全体の集合.\\ $GB_<(S)$ : $S$ の $<$ に関する被約グレブナ基底.\\ $f_1,\cdots,f_m$ : $\Z[X]$ の元.\\ $NF_<(f,G)$ : $f$ の $G$ に関する正規形の一つ.\\ $Init_<(I)$ : \{$HT_<(f)\mid f\in I$\} で生成されるイデアル.\\ $Useless\_Pairs(D)$ : 不必要対の検出.\\ $Select\_Pair(D)$ : 対の選択\\ $Sp(C)$ : 多項式対の S-多項式の計算 \end{nt} \section{不必要対の検出} Buchberger アルゴリズムにおいて, 正規化により 0 になる対を不必要対と呼 ぶ. これらは, ある多項式集合が グレブナ基底であることの確認のためにのみ意味が あり, もし計算せずに 0 に正規化されることがわかれば計算効率の点からみ て極めて好都合である. さらに, この 「0 への正規化」は, アルゴリズムの ある時点においてではなく, グレブナ基底のすべての元が生成されたのち, 0 に正規化 されるのであってもよい. 実際, そのような状況は, 命題 \ref{'thomo'} に おいて現れている. この命題を, Taylor 基底に適用すれば, Taylor 基底のう ち, 冗長な (すなわち他の基底により生成される) 基底をとり除いた残りにつ いて 0 に正規化されればよいことになる. ここで取り除かれる基底に対応す る多項式対のほか, 他の方法により 0 に正規化されることがわかり, とり除 かれる対もあり得る. これらについて述べる. \subsection{冗長な基底の除去} Taylor 基底から冗長な基底を取り除くための基本的な道具は, 基底間の次の 自明な恒等式である. $$ {T_{ijk}\over T_{ij}} S_{ij} + {T_{ijk}\over T_{jk}} S_{jk} + {T_{ijk}\over T_{ki}} S_{ki} = 0 $$ この恒等式において, いずれかの係数が 1 であれば, その項に対応する基底 は, 他の基底により生成される. これを繰り返して冗長な基底を取り除いて 行くが, この際, 相互に依存し合う基底を誤って取り除くことを避けるため, 基底間に全順序を入れ, ある基底がそれより順序の低い基底により生成されて いる場合にのみ, その基底を取り除くこととする. \begin{df} $\{S_{ij}\mid i < j\}$ における全順序を次のように定義する. \noi $S_{ij} < S_{kl} \Leftrightarrow$\\ $T_{ij} < T_{kl}$ または\\ ($T_{ij} = T_{kl}$ かつ ($j < l$ または ($j = l$ かつ $i < k$))) \end{df} \begin{df} 対 $(i,j)$ に関する三つの性質を次のように定義する. \noi $M(i,j) \Leftrightarrow$ ある $k < j$ が存在して $T_{kj} \mid T_{ij}$ かつ $T_{kj} \neq T_{ij}$ \noi $F(i,j) \Leftrightarrow$ ある $k < i$ が存在して $T_{kj} = T_{ij}$ \noi $B(i,j) \Leftrightarrow$ ある $k > j$ が存在して $T_{k} \mid T_{ij}$ かつ $T_{jk} \neq T_{ij}$ かつ $T_{ik} \neq T_{ij}$ \end{df} \noi これらは, 前記恒等式において, $S_{ij}$ の係数が 1 かつ $S_{ij}$ の順序 が最大になる条件を場合分けにより表したものである. いずれの性質においても $T_{k} | T_{ij}$ より $S_{ij}$ の係数は 1. それぞれについて確かめれば, 実際に $S_{ij}$ が最大順序となっていることがわかる. よって, 次の命題が なり立つ. \begin{pr}(Gebauer and M\"oller{\rm\cite{GEB}}) Taylor 基底は, $\{S_{ij} \mid \neg M(i,j), \neg F(i,j), \neg B(i,j)\}$ で生成される. \end{pr} \begin{re} 実際のアルゴリズムにおいては, 0 でない正規形が生成されて, $D$ に対を 追加する際に, 上記の性質を満たす対を削除していくが, 性質 $M, F, B$ のうち, $M, F$ は, 多項式集合 $G$ に追加する元を含む対が対象となるのに対し, $B$ は既に存在している対が対象となる. この事実は, 正規化対の選択戦略との 関連で, アルゴリズムの進行に重大な影響を及ぼす場合がある. \end{re} \subsection{0 に正規化される対の除去} 前節で述べたもの以外に, 頭項のみにより, 0 に正規化できると判断できる対 があり得る. \begin{pr}(Buchberger)\\ $\GCD(HT(f),HT(g))=1$ ならば $Sp(f,g) \tmred{\{f,g\}} 0$ \end{pr} \proof $f = \sum_i f_i$, $g = \sum_i g_i$ ($f_i, g_i \in M; f_1 > f_2 > \cdots, g_1 > g_2 > \cdots$; ある添字以降は 0 としておく) とする. 仮定により $\GCD(f_1,g_1) = 1$. このとき, $Sp(f,g) = g_1\sum_{i\ge 2}f_i - f_1\sum_{j\ge 2}g_j$これから, 任意の $m \ge 2$ に対してある $k$ が存在して \\ $Sp(f,g) \tmred{\{f,g\}} R_m = (g_1+\cdots+g_k)(f_{m-k+1}+\cdots)-(f_1+\cdots+f_{m-k})(g_{k+1}+\cdots)$\\ となる. 実際, $m = 2$ については正しい. $m$ まで正しいとする. $\GCD(f_1,g_1) = 1$ より, $g_1f_{m-k+1} \neq f_1g_{k+1}$ が言える. よっ て, もし $g_1f_{m-k+1} > f_1g_{k+1}$ ならば, $HM(R_m) = g_1f_{m-k+1}$. すると, \\ $R_m \mred{f} R_m - gf_{m-k+1} = (g_1+\cdots+g_k)(f_{m-k+2}+\cdots)-(f_1+\cdots+f_{m-k+1})(g_{k+1}+\cdots)$\\ となり, $m+1$ の時も正しい. $g_1f_{m-k+1} < f_1g_{k+1}$ でも同様である. よって, この操作を繰り返して, 結局 $Sp(f,g) \tmred{\{f,g\}} 0$ を得る. \qed \noi この命題により, 前節の操作で残った基底の中からさらに 0 に正規化される 対を除去することができる. \section{正規化対の選択戦略} アルゴリズム \ref{buch} のループにおける, 正規化の対象となる対の選択は, アルゴリズムの正当性にはなんら影響しないが, 実際の計算効率に大きく影響 を与える. Buchberger により提案された戦略は次のものである. \begin{df} {\bf normal strategy}\\ $T_{ij}$ が最小な対から選択する戦略をいう. \end{df} \noi この戦略は, 順序の低い頭項をもつ基底を早めに生成するという実用的な意味 をもつ他に, この戦略によれば S 多項式は, 簡約の仕方によらず一意的な正 規形となることが示されている. この戦略は, term order によっては極めて 悪い結果をもたらす場合が多く, 特に, 辞書式順序のように, 全次数による 比較を行わない順序で甚だしい. \begin{df} {\bf 斉次化}\\ $t$ を斉次化変数とし, $R = k[x_1,\cdots,x_n]$ and $R_h = k[x_1,\cdots,x_n,t]$ とする. $f \in R$ の斉次化を $f^*$, $g\in R_h$ の非斉次化を $g_*$ と書く. 以下, $f$ の全次数を $\tdeg(f)$ と書く. $$f^* = t^{\tdeg(f)}f(x_1/t,\cdots,x_n/t)$$ $$g_* = g|_{t=1}$$である. 多項式集合 $F \subset R$, $G \subset R_h$ に 対しても, 各元を斉次化, 非斉次化したものをそれぞれ $F^*$, $F_*$ と書く. このとき, $R$ の order $<$ に対して, $R_h$ の order $<_h$ が \begin{center} (H) 任意の斉次多項式 $g \in R_h$ に対し, $HT(g)_* = HT(g_*)$ \end{center} を満たすとき, $<_h$ を $<$ の斉次化と呼ぶことにする. \end{df} \begin{ex} \label{horder} $X \cup \{t\}$ ($X$ に関して $<$) による block order は $<$ の斉次化の一つ であるが, 定義により, \begin{center} $ut^m <_h vt^n \Leftrightarrow \tdeg(ut^m) < \tdeg(vt^n)$ または $\tdeg(ut^m) = \tdeg(vt^n)$ かつ $u < v$ \end{center} なる $<_h$ も $<$ の斉次化である. \end{ex} \begin{pr} \label{hcomp} $F \subset R$ とし, $<_h$ を $<$ の斉次化 order とする. このとき, もし $G$ が $Id(F^*)$ の斉次多項式からなるグレブナ基底なら, $G_*$ は $Id(F)$ のグレブナ基底となる. \end{pr} 斉次化は選択戦略そのものではないが, 入力を斉次化した後, 上の例で述べた 全次数比較入りの $<_h$ のもとで normal strategy で計算した後非斉次化す るという手順でグレブナ基底を求めると, 不必要対は増加するものの, 計算が スムーズに進行することが経験的に知られていた. 係数体が有限体の場合には, 後で述べる, 不必要対に対する正規形計算で生じる係数膨張の問題が生じない ため, 有限体上でのグレブナ基底計算には斉次化は有用である. \begin{df} {\bf sugar strategy}\\ グレブナ基底計算の途中に現れる多項式 $f$ に, 次の規則によりある自然数 $s_f$ (sugar) を対応させる. \begin{enumerate} \item 入力多項式 $f$ に対しては, $s_f = \tdeg(f)$ \item $m$ が monomial の時 $s_{mf} = \tdeg(m)+s_f$ \item $s_{f+g} = \max(s_f,s_g)$ \end{enumerate} sugar strategy とは, S 多項式の sugar の最も小さいものの集合から normal strategy で対を選択する戦略をいう. \end{df} Giovini ら{\rm\cite{SUGAR}}により提案されたこの戦略は, 入力多項式集合 を斉次化してのグレブナ基底計算を{\bf 仮想的}に行なうもので, sugar は 斉次化後の次数に対応している. \section{Trace lifting} sugar strategy により, 少なくとも係数体が有限体の場合には, 十分な効率 が達成できるようになった. しかし, 係数体が有理数の場合, 前に述べた検 出基準にかからない不必要対の S 多項式の正規化計算にかかるコストが大き い場合がしばしばある. そのため, 次のようなアルゴリズム ({\bf trace lifting}) が提案された \cite{TRAV}. \begin{al} \label{tl} \begin{tabbing} \\ trace\_lifting$(F,<)$\\ Input : $F \subset \Z[X]$; term order $<$\\ Output : $F$ の $<$ に関するグレブナ基底\\ do \= \{\\ \> $p \leftarrow$ 未使用の素数\\ \> $G \leftarrow tl\_guess(F,<,p)$\\ \> if \= $G \neq$ {\bf nil} かつ tl\_check$(F,G,<) =1$ \\ \> then return $G$\\ \} \end{tabbing} \end{al} \begin{al} \label{tlguess} \begin{tabbing} \\ tl\_guess$(F,<,p)$\\ Input : $F \subset \Z[X]$; term order $<$; 素数 $p$\\ Output : $F$ のグレブナ基底候補または {\bf nil}\\ if \= ある $f \in F$ が存在して $\phi_p(HC(f))=0$ then return {\bf nil}\\ $G \leftarrow F$\\ $G_p \leftarrow \{\phi_p(f) \mid f \in G\}$\\ $D \leftarrow \{\{f,g\} \mid f,g \in G; f \neq g\}$\\ do \= \{\\ \> $D \leftarrow D \setminus Useless\_Pairs(D)$\\ \> if \= $D = \emptyset$ then return $G$\\ \> else \{ \= $C \leftarrow Select\_Pair(D)$\\ \> \> $D \leftarrow D \setminus \{C\}$\\ \> \}\\ \> $s \leftarrow Sp(C)$\\ \> $t_p = NF(\phi_p(s),G_p)$\\ \> if \= $t_p \neq 0$ then \{\\ \> \> $t \leftarrow NF(s,G)$\\ \> \> if $\phi_p(HC(f)) = 0$ then return {\bf nil}\\ \> \> $D \leftarrow D \cup \{\{f,t\} \mid f \in G\}$\\ \> \> $G \leftarrow G \cup \{t\}$\\ \> \> $G_p \leftarrow G_p \cup \{t_p\}$\\ \> \}\\ \} \end{tabbing} \end{al} \noi アルゴリズム \ref{tlguess} は, 有理数体上での正規形計算を行なう前に有限体上 で正規形を計算し, それが 0 となる場合には, 有理数体上の正規形も 0 であ ると仮定してその計算を省略する. このような操作を行なっても, 生成される 0でない多項式について, その頭項は, 通常の Buchberger アルゴリズムと同 様の性質を持つためアルゴリズムは停止する. しかし, $p$ の選び方によって はグレブナ基底を出力しない場合があるため, 次のようなテストが必要となる. \begin{al} \label{tlcheck} \begin{tabbing} \\ tl\_check$(F,G,<)$\\ Input : 多項式集合 $F, G \subset \Z[X] \st G \subset Id(F)$; order $<$\\ Output :\= もし $G$ が $<$ に関する $F$ のグレブナ基底なら 1\\ \> そうでなければ 0\\ if \= $G$ が $<$ に関してグレブナ基底でない then return 0\\ if すべての $f \in F$ に対し $NF_<(f,G) = 0$ then return 1 else return 0 \end{tabbing} \end{al} 実際, アルゴリズム \ref{tlguess} の出力 $G$ に対し, $G \subset Id(F)$ は構成法より常に成り立つから, \ref{tlcheck} が 1 を返せば $Id(G) = Id(F)$ で, $G$ は $Id(F)$ のグレブナ基底となる. このテストを組み合わせ たものが, アルゴリズム \ref{tl} である. このテストを通過できるような $p$ としては, 通常の Buchberger アルゴリズムを実行した場合に現れるすべ ての多項式の頭係数を割らないような素数をとればよい. もちろんこのような 素数はあらかじめ決定することはできないが, 不都合な素数は有限個であり, アルゴリズム全体としての停止性も保証される. このアルゴリズムにおいては, \begin{center} 不必要対に対する S 多項式の計算コスト\\ $\Downarrow$\\ 有限体上でのグレブナ基底計算 + グレブナ基底テスト + 入力多項式に対する メンバシップテスト \end{center} という置き換えが行なわれている. よって, この置き換えが効率を向上させる ためには, 後者が前者より高速に実行できなければならない. この比較は入力 多項式集合 $F$ の性質, あるいは用いる order の性質によって異なるが, 一 般的には次のようなことが言える. \begin{itemize} \item $V(Id(F))$ の余次元が大きい場合 グレブナ基底計算に現れる係数が 長大になる傾向が大きく, 特に, $V(Id(F))$ が有限集合になる場合に, $F$ の グレブナ基底を辞書式順序で計算する場合に甚だしい. そのような場合でも, 最終的なグレブナ基底の係数, 元の個数は小さい場合が多く, 2 つのテスト も比較的容易である. \item $V(Id(F))$ の余次元が小さい場合 多項式の項数が増大する場合が多く, そのような場合には, 後者がそのまま余 分なコストにつながる. \end{itemize} このように, 効果が期待できない場合もあり得るが, そのような場合でも 高々 2 倍程度の時間で計算は終了するため, 常に trace lifting を用いる のが安全であろう. 以上の議論においては, $p$ としては計算機が提供する 1 ワード以内の整数 を用いることを仮定している. これは, 1 ワード以内の整数に対する加減乗除 が通常は機械命令として提供されていて, 高速に実行されるからである. また, 係数が法 $p$ で一様に分布していると仮定すれば, $p$ が大きい程, $p$ が 頭係数のどれかを割り切る確率は小さくなると期待できる. よって, 実際の計 算では $p$ として 1 ワードの範囲内でなるべく大きい整数を選ぶのがよい. \section{斉次化 と trace lifting の組合せ} trace lifting により, 不必要対に対する S 多項式の計算コストを, 有限体 上のグレブナ基底計算および, グレブナ基底候補生成後のグレブナ基底テスト と入力多項式のメンバシップテストに置き換えることができた. しかし, 実際 に斉次化した場合には生じないような中間係数膨張が, sugar strategy の適 用により生じる場合がしばしば見られる. 本節では, この困難を克服するため の方法について述べる.\\ このような係数膨張を簡単な例で示す. \begin{ex} $I = Id(-3x_1-3x_2-5,-3x_1x_0^2-8x_0-6,4x_0^2+(-2x_1^3-7)x_0-3x_3x_1^2-2,-x_0^4-x_0^2+3x_1x_0-4x_1)$ \end{ex} $I$ の $x_0>x_1>x_2>x_3$ なる辞書式順序のもとでのグレブナ基底 $GB(I)$ は, \\ $GB(I) = \{f_3(x_3), f_2(x_2,x_3), f_1(x_1,x_3), f_0(x_0,x_3) \}$\\ $f_3=286978140000x_3^6-30735638450064x_3^5+139368108773718x_3^4-401122901874078x_3^3\\ +3813285736741284x_3^2-17712668879937657x_3+25309718023001309$\\ $f_2=-24359129516408255978429894458178435051554483918248x_2\\ -9117338725200447183121773483618146011417380000x_3^5\\ +945437242481668390348909147393962329546603617488x_3^4\\ -1215199713704678902273407299537086048391876350746x_3^3\\ +9203891427703221172499174842307408763060278519544x_3^2\\ -87128026603776953223695902278763008965980027109460x_3\\ +198072128718550346069760390022952204794356946307195$\\ $f_1=24359129516408255978429894458178435051554483918248x_1\\ -9117338725200447183121773483618146011417380000x_3^5\\ +945437242481668390348909147393962329546603617488x_3^4\\ -1215199713704678902273407299537086048391876350746x_3^3\\ +9203891427703221172499174842307408763060278519544x_3^2\\ -87128026603776953223695902278763008965980027109460x_3\\ +238670677912564106033810214119916263213614419504275$\\ $f_0=-9134673568653095991911210421816913144332931469343x_0\\ -334442494143970788481038492015748108482000000x_3^5\\ +37671432710327352302696037580172208903376423200x_3^4\\ -352356049164307536666247874973386638400872538040x_3^3\\ +499969270855985351160909518989653220917608771262x_3^2\\ -6841618915067057146509523126510725094238856771432x_3\\ +31588951614319486540726259755101613855437086625238$\\ この計算を, 斉次化を経由して行った場合, 現れる中間基底の係数のビット長の和 の最大値は 1489 ビットだが, sugar strategy のみを用いて行った場合その 最大値は 10258121 ビットであった. このような小さい問題に対しても, sugar strategy がうまく働かない場合には不必要な係数膨張が生じてしまう. 斉次化は生成される基底の係数膨張が起こらないような strategy を与える場 合が多いが, 非斉次の場合に比べて前に述べた不必要対の検出にかからない不 必要対を多く生成し, 問題が大きくなると, それらの 0 への正規化のコスト が非常に大きくなる. これらを克服する有力な方法が, 次のアルゴリズムであ る. \begin{al} \label{htl} \begin{tabbing} \\ homogenized\_trace\_lifting$(F,<)$\\ Input : $F \subset \Z[X]$; term order $<$\\ Output : $F$ の $<$ に関するグレブナ基底\\ do \= \{\\ \> $p \leftarrow$ 未使用の素数\\ \> $G \leftarrow tl\_guess(F^*,<_h,p)$\\ \> if \= $G \neq$ nil\\ \> \>かつ $G_*$ が $<$ に関するグレブナ基底\\ \> \>かつすべての $f \in F$ に対し $NF(f,G_*) = 0$\\ \> then return $G_*$\\ \} \end{tabbing} \end{al} $<_h$ は 例 \ref{horder} で述べた order の全次数付斉次化を用いてい る. この方法と, 単に入力を斉次化したものに対してtrace lifting によりグ レブナ基底を求めてから非斉次化する方法を比較すると次のようになる. いず れも, 斉次化により選択戦略を安定にし, かつ斉次化により増加した不必要対 に関するコストは trace lifting により緩和される. \begin{itemize} \item 斉次化 $\Rightarrow$ 候補生成 $\Rightarrow$ 非斉次化 $\Rightarrow$ テスト 非斉次化を行なった時点で冗長な基底を取り除くため, テストにかかるコ ストは斉次化を行なわない場合と変わらない. \item 斉次化 $\Rightarrow$ 候補生成 $\Rightarrow$ テスト $\Rightarrow$ 非斉次化 斉次なグレブナ基底候補の場合, 冗長な基底がほとんどなく, trace lifting に よりカットされた大部分の不必要対を有理数体上で改めて正規化する必要がある. \end{itemize} すなわち, 入力が既に斉次の場合を除いて, 非斉次化後にテストを行なう方が効率 がよい. この方法により, trace lifting のみでは計算不可能だった多くの問題 が計算可能になった. \section{$F_4$ アルゴリズム} 代数方程式求解に限らず, 代数幾何における不変量の計算などにおいても 任意入力多項式集合からのグレブナ基底の計算は, 計算量的にみて dominant step となることが多い. このような場合の計算法としては Buchberger アルゴリズムがほぼ唯一の方法であったが, 最近 Faug\`ere により $F_4$ (あるいは $F_5$) アルゴリズムが提案され, その高速性が 注目されている. 本節では, このアルゴリズムについて概説する. \subsection{Symbolic preprocessing} アルゴリズム \ref{buch} を実行する場合, $D$ からどの元を選んで来るか で, その後の計算の進行の様子が全くことなる, ということが 起こる. また, 最善の元を選んだつもりでも, 特に有理数体上 などにおいて, $NF(Sp(f,g),G)$ の係数が極端に大きくなり, 計算不能になることも起こる. そのため, trace lifting, homogenization などの種々のテクニックのもとで計算が試みられて 来た. ここで, Buchberger アルゴリズムの核心である $NF(Sp(f,g),G)$ について考察する. $NF(Sp(f,g),G)$ は次のような手順で計算される. \begin{tabbing} $r \leftarrow af - bg$ ($a, b$ は単項式) \\ while \= ( $r$ の項 $t$ を割り切る $h \in G$ がある )\\ \> $ r \leftarrow r - ch $\\ \> ($r$ に $t$ の項はない) \end{tabbing} ここで, $r$ を簡約するのに必要な $h \in G$ は一見実際に簡約 操作を実行しなければ分からないように見えるが, 冗長な元 (すなわち, 実際には簡約に用いられない元) も許せば, 次のような 方法で事前に得られる. \begin{al} (Symbolic preprocessing) \label{symred} \begin{tabbing} Input : 多項式 $f$, 多項式集合 $G$\\ Output : $Red=\{ah \mid a :$ 単項式, $h \in G \}$ \\ $T \leftarrow T(f)$ \\ $Red \leftarrow \emptyset$\\ while \= $HT(g)|t$ なる $t\in T$, $g \in G$ が存在する do \{\\ \>$Red \leftarrow Red \cup \{t/HT(g)\cdot g\}$\\ \>$T \leftarrow (T \setminus \{t\}) \cup T(reductum(t/HT(g)\cdot g)$\\ \}\\ return $Red$ \end{tabbing} \end{al} このアルゴリズムで得られた $Red$ (Reducer) は次の性質をもつ: \begin{itemize} \item $\{f\} \cup Red$ の元のある項 $t$ がある $g\in G$ に対し $HT(g)$ で割り切れるならば, $HT(x)=t$ なる $x \in Red$ がある. \end{itemize} これより, 次が言える. \begin{itemize} \item $\{f\}$ の, $Red$ の元による $K$ 係数の簡約操作での正規形は, $G$ に 関する正規形となる. \end{itemize} これを, 行列の言葉で言い換えるために次の準備をする. まず, $\{f\} \cup Red$ に現れる全ての項を $T$ とし, $T$ の元を順序の高い 順に並べたものを $t_1 > t_2 > \cdots $ とする. $T$ で $K$ 上張られる線形空間の元 $h$ の, $(t_1,t_2,\cdots)$ を基底とする行ベクトル表現を $[h]$, 行ベクトル $v$ に対する多項式を $poly(v)$ と書くことにする. $$[f] = [f_1 f_2 \cdots]$$ $$r_i = [r_{i1} r_{i2} \cdots] \quad (r_i \in Red)$$ とするとき, $$A=\left( \begin{tabular}{ccc} $f_1$ & $f_2$ & $\cdots$ \\ $r_{11}$ & $r_{12}$ & $\cdots$ \\ $r_{21}$ & $r_{22}$ & $\cdots$ \\ & $\cdots$ & \\ \end{tabular} \right)$$ とならべ, これを, 行に関する基本変形により次の条件を満たす行列 $B$ に変形する. \begin{itemize} \item $poly(B_i)$ が 0 でないとき, $poly(B_k) (k\neq i)$ は $HT(poly(B_i))$ を含まない. \end{itemize} $$B=\left( \begin{tabular}{ccccccc} 1 & 0 & ? & ? & ? & 0 & $\cdots$ \\ 0 & 1 & ? & ? & ? & 0 & $\cdots$ \\ 0 & 0 & 0 & $\cdots$ & 0 & 1 & $\cdots$ \\ & & & $\cdots$ & & & \\ 0 & 0 & 0 & $\cdots$ & 0 & 0 & $\cdots$ \end{tabular} \right)$$ このとき, $poly(B_i)$ のうち, $HT(poly(B_i))$ が $\{HT(r)\mid r\in Red\}$ に 含まれないものが, $NF(f,G)$ となる. \subsection{$F_4$ アルゴリズム} 前節での 正規形計算の言い替えは, 多項式剰余演算計算においてもしばしば 用いられ, 特に目新しいものでもない. $F_4$ アルゴリズムは, 複数の S-多項式をまとめて行列形式で簡約する. そのための symbolic preprocessing も, 出発点が, S-多項式に現れる項の和集合となるだけで, 既に 述べたアルゴリズムがそのまま適用される. \begin{al} (Symbolic preprocessing) \label{multisymred} \begin{tabbing} Input : 多項式集合 $F$, 多項式集合 $G$\\ Output : $Red=\{ah \mid a :$ 単項式, $h \in G \}$ \\ $T \leftarrow \cup_{f\in F}T(f)$ \\ $Red \leftarrow \emptyset$\\ while \= $HT(g)|t$ なる $t \in T$, $g \in G$ が存在する do \{\\ \>$Red \leftarrow Red \cup \{t/HT(g)\cdot g\}$\\ \>$T \leftarrow (T \setminus \{t\}) \cup T(reductum(t/HT(g)\cdot g)$\\ \}\\ return $Red$ \end{tabbing} \end{al} 行列 $A$ も, 全ての S-多項式に対応するベクトルおよび symbolic preprocessing で 得られた $Red$ に属する多項式に対応するベクトルを行とする行列として 構成される. この行列を, 行基本変形により, 次の条件を満たす行列 $B$ に 変形する. \begin{itemize} \item $poly(B_i)$ が 0 でないとき, $poly(B_k) (k\neq i)$ は $HT(poly(B_i))$ を含まない. \end{itemize} これは, $t_1 > t_2 > \cdots$ を新たな変数とみて, この順序で reduced な グレブナ基底を計算した結果に対応する. $$F' = \{h=poly(B_i) \mid h\neq 0, HT(h)\notin \{HT(r)\mid r\in Red\}\}$$ $$Red' = \{h=poly(B_i) \mid h\neq 0, HT(h)\in \{HT(r)\mid r\in Red\}\}$$ とおく. \begin{pr} \begin{enumerate} \item $h\in F'$ は $G \cup (F'\setminus \{h\})$ に関して正規形 \item $f\in F$ ならば $f \tmred{G\cup F'} 0$ \end{enumerate} \end{pr} {\bf Proof}\\ 1: $h\in F'$ ならば $T(h) \cap \{HT(r)\mid r\in Red\} = \emptyset$. これは, $Red$ の作り方より $h$ が $G$ に関して正規形であることを意味する. もちろん $h$ は $F'\setminus \{h\}$ に関しても正規形である. \\ 2: $f\in F$ とする. $$NF(f,G) = f-\sum_{r_i\in Red} c_i r_i\quad (c_i\in K)$$ と書ける. よって, $NF(f,G)$ は $F \cup Red$ で $K$ 上生成される 線形空間に属する. ここで, $F\cup Red$ と $F' \cup Red'$ が $K$ 上同一の線形空間を生成し, かつ $NF(f,G)$ には $Red'$ の元の頭項は現れないから, $$NF(f,G)=\sum_{f_i\in F'} d_i f_i\quad (d_i \in K)$$ と書ける. この線形和は直ちに $F'$ に関する正規形計算となる. \qed\\ 2. により $F$ として, いくつかの S-多項式の集合をとり, $F'$ をまとめて $G$ に付け加えることにより, $F$ に属する S-多項式 が 0 に簡約されることが分かる. また, 1. により, アルゴリズムの停止性も言える. $F$ として一つの S-多項式をとった場合が通常の Buchberger アルゴリズム であり, その場合には, 選び方 (selection strategy) によって効率に 大きく差がでることは既に述べた. $F_4$ においても $F$ の選び方が 問題となるが, 複数元を選択できることで, selection strategy の効率に 対する影響が少なくなることが実験により知られている. 例えば, 次のような strategy により, 多くの例が効率よく計算できる. \begin{df} S-多項式の sugar の最小のものを全て選ぶ. \end{df} ここで, $F_4$ の場合, 正規形計算において通常の sugar は意味を持たないので, ある sugar の S-多項式を集めて計算した場合, 生成された基底の sugar も その値であるとして, 再帰的に sugar の値を定めることとする. 特に, 入力多項式集合が homogeneous の場合, この strategy により, 各ステップで計算される基底は, 次数が $d$ の場合, {\bf reduced} なグレブナ 基底のうちの, $d$ 次の元全てとなる. これは, homogeneous ideal の 場合次が成り立つことから分かる. \begin{enumerate} \item $d$ 次の基底を生成するための S-多項式は全て $d-1$ 次以下の 基底から作られる. \item $d$ 次の斉次多項式は, $d+1$ 次以上の基底では簡約されない. \end{enumerate} \subsection{Modular 計算による線形方程式の求解} $F_4$ においては, selection strategy に従って構成された行列を, 左基本変形するという操作の繰り返しで基底を生成していく. ここで, 左基本変形は, 線形方程式求解とみなすことができる. すなわち, \begin{enumerate} \item 行列 $A$ から線形独立な行を全て抜きだして $A'$ を作る. \item $A'$ の列を左から順に見て, それまで取り出した列と線形独立な 列を抜き出す, という操作を繰り返して正方行列 $A''$ を作る. \item $A'$ で残った列を集めて $B''$ とする. \item $A''X=B''$ なる線形方程式を解く. \item $X$ から, $A'$ の行基本変形の結果を構成する. \end{enumerate} 元の体上で考える限り, これは単なる言い替えに過ぎないが, 例えば有理数体 上の場合, $\det(A'')\neq 0$ なる $A''$ を modular 計算により推測して抜 きだし, $A''X=B''$ の解候補を modular 計算などにより構成し, \begin{itemize} \item $A$ の各行に, 第 5 項の結果を代入して 0 になることを 確かめる. \end{itemize} というチェックにより modular 計算の結果が, 有理数体上での行基本 変形の結果と等しいこと, 特に $A$ を構成する多項式 で張られていること, 線形方程式の解の一意性により言える. このような解候補を与えるものとして, 中国剰余定理および Hensel 構成 がある. 中国剰余定理を用いる方法は, 法 $p$ が有理数上の掃き出しと 異なるものを与えない限り, 自明な方法で精度をあげていき, 整数-有理数 変換の結果が stable になったら $A$ に代入してチェックという方法である. また, Hensel 構成は アルゴリズム \ref{lineq} そのものである. Faug\`ere によれば, $F_4$ においては $B$ が大きくなるため, $B$ の列数 が $A$ のサイズを越える場合には中国剰余定理を用いたほうがよいとのことである. いずれにせよ, modular 計算による方法が効率を上げる場合というのは, $det(A'')$ に比べて解の係数が小さい場合である. これは一般に期待 できることではないが, 前節で述べたように, homogeneous の場合に $F_4$ が reduced なグレブナ基底の一部を生成する, ということから, reduced に した場合に係数が小さくなるような問題では modular 計算が効率を向上 させることが期待できる. \subsection{例} \cite{REP} では, 4 変数の代数方程式系 (odd order 方程式) のグレブナ基底計算 を Buchberger アルゴリズムにより行った. この計算に現れる中間基底におい て, 16 次の基底を線形形式とみて, inter reduction してみた結果, 係数が 極端に小さくなることがわかる. もともと, Buchberger アルゴリズムで odd order 方程式を計算する場合, 最後に係数が大変小さい基底が何本か出て終了 する. 特に, 最初に現れる, 係数の小さい基底が, 16 次の基底のうち最後の ものであったため, その基底を用いて一つ前の基底を簡約したところ, 係数が 小さくなった. その操作を基底全てに適用したところ, 16 次の基底全ての係 数が, inter reduction により小さくできることが分かったのである. 既に 述べたように, このような場合には, modular 計算による解候補の計算が有効 となる. しかし, 15 次の基底を inter reduction したところ, 係数の大きさ はほとんど変わらず, 大きいままであった. 以上のような背景のもとに, 現在 の実装での odd order 方程式に対する Buchbergerアルゴリズム計算 (homogenization+trace lifting) および $F_4$ の比較を示す. 表で, GaussElim, ChRem, IntRat, Check はそれぞれ Gauss 消去, 中国剰余定理, 整数-有理数変換, 結果のチェックにかかった時間を示す. \begin{table}[hbtp] \caption{計算時間の比較} \begin{center} \begin{tabular}{|c||c|c|c|c|c|} \hline & total & GaussElim & ChRem & IntRat& Check \\ \hline Buchberger & 264710 & --- & --- & --- & --- \\ \hline $F_4$ homo & 32880 & 6437 & 6300 & 5763 & 13340 \\ \hline $F_4$ non homo & 39970 & 4832 & 6143 & 18240 & 9950 \\ \hline \end{tabular} \end{center} \end{table} \begin{table}[hbtp] \caption{各次数の行列のサイズ} \begin{center} \begin{tabular}{|c||c|c|c|c|c|c|} \hline & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline $F_4$ homo &(56,334) & (119,441) & (182,545) & (362,774) & (671,1009) & (1195,1359) \\ \hline $F_4$ non homo &(62,339) & (128,448) & (137,461) & (227,571) & (307,621) & (955,1149) \\ \hline \end{tabular} \begin{tabular}{|c||c|c|c|c|c|c|} \hline & 16 & 17 & 18 & 19 & 20 & 21 \\ \hline $F_4$ homo &(836,688) &(2323,1761) &(895,964) &(204,271) &(446,515) &(308,374) \\ \hline $F_4$ non homo & (555,508) & (2022,1763) & --- & --- & --- & --- \\ \hline \end{tabular} \begin{tabular}{|c||c|c|c|c|} \hline & 22 & 23 & 24 & 25 \\ \hline $F_4$ homo & --- & --- & --- & --- \\ \hline $F_4$ non homo & (799,868)& (300,367) & (398,467) & (361,427) \\ \hline \end{tabular} \end{center} \end{table} \begin{table}[hbtp] \caption{各次数の基底の計算時間} \begin{center} \begin{tabular}{|c||c|c|c|c|c|c|} \hline & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline Buchberger & 2.3 & 11 & 43 & 164 & 1214 & 32512 \\ \hline $F_4$ homo & 1.8 & 10 & 45 & 357 & 2574 & 26519\\ \hline $F_4$ non homo & 2.2 & 12& 28 & 166& 1064 & 35906\\ \hline \end{tabular} \begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|} \hline & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 \\ \hline Buchberger & 205234 & 10300 & 4530 & --- & 10700 & --- & --- & --- & --- & --- \\ \hline $F_4$ homo & 1340 & 1097 & 359 & 45 & 208 & 150 & --- & --- & --- & --- \\ \hline $F_4$ non homo & 937 & 902 & --- & --- & --- & --- & 341& 132 & 186 & 164 \\ \hline \end{tabular} \end{center} \end{table} \begin{figure}[htbp] \epsfxsize=15cm \epsffile{ps/blenall.ps} \caption{中間基底の最大係数のビット長} \label{nftime} \end{figure} まず, total 時間が 1/8 程度に減っていることに注目したい. これは, 基底の 計算時間の内訳をみればわかるように, Buchberger アルゴリズムによる計算で 全体の計算時間の大部分を占めていた 16 次の計算が 1/100 程度の時間で終って いるためである. これは, 最大係数のビット長が reduced な基底で非常に小さく なることに対応している. それ以上の次数については, 小さい係数を持つ 多項式による簡約化で済むことが高速化の理由である. \subsection{まとめ} $F_4$ は本質的には Buchberger アルゴリズムの改良と考えられるが, 次のような 長所を持つ. \begin{itemize} \item 行列の掃き出し中は, 項の順序比較が単なる index の比較になる. \item 中間基底を reduced あるいはそれに近い形に保つため, その後の 掃き出し計算が効率化する. (「対角化」された行列による簡約化 vs. 「三角化」 された行列による簡約化) \item reduced な基底の係数が小さくなる場合には, modular 計算による 効率化が期待できる. \end{itemize} 一方で, \begin{itemize} \item 多数の S-多項式および reducer を一度に行列として扱うために, 巨大なメモリを必要とする場合がしばしば生ずる. \item 一般に行列は疎となるため, 大規模疎行列を効率よく保持し, 掃き出す必要 がある. \item modular 計算を行う場合, 行列の各行の 0 簡約チェック によるオーバーヘッドが問題となる. \end{itemize} などの困難により, 実用的な実装を行うには Buchberger アルゴリズムと同様 さまざまな工夫が必要となる. とはいえ, 前節の例で見たように, 実験的な実 装でも従来の Buchberger アルゴリズムより効率よく計算できる場合があるこ とは確かで, Faug\`ere によるもの以外にもさまざまな実装実験が行われることが 期待される.