%$OpenXM: OpenXM/doc/compalg/fglm.tex,v 1.3 2000/03/28 02:02:30 noro Exp $ \chapter{Change of ordering} 前節では, 主として Buchberger アルゴリズムの効率化について述べた. しかし, グレブナ基底の計算法は Buchberger アルゴリズムだけとは限らない. 本節では, 既に何らかの order に関してグレブナ基底になっている多項式 集合を入力として, 他の order のグレブナ基底を求める方法について述べる. \section{FGLM アルゴリズム} $I \subset K[X]$ を 0 次元イデアルとし, $I$ のある order $<_1$ に関する 被約グレブナ基底 $G_1$ が既に得られているとする. このとき, 他の order $<$ に関する $I$ のグレブナ基底 $G$ を, 主として線形代数により求めるのが FGLM アルゴリズムである. \begin{lm} $<$ を admissible order, $F = GB_<(I)$ とする. $T = \{t_1,\cdots,t_l\} \subset T(X)$ を項の集合とする. $a_i$ を未定係数とし, $$E = \displaystyle{\sum_{i=1}^l a_i NF_<(t_i,F)}$$ とおく. $E$ の $X$ に関する係数の集合を $C$ とすれば, $Eq = \{ f = 0 \mid f \in C\}$ は $a_i$ に関する線形方程式となる. この時 \begin{center} $Eq$ が自明でない解を持つ $\Leftrightarrow$ $T$ が $K[X]/I$ において $K$-線形従属 \end{center} \end{lm} \begin{al} (FGLM アルゴリズム\cite{FGLM}) \label{fglm} \begin{tabbing} FGLM$(F,<_1,<)$\\ Input : \= order $<_1$, $<$; $F \subset K[X]$ \st $F = GB_{<_1}(I)$ かつ $\dim(I)=0$\\ Output : $F$ の $<$ に関するグレブナ基底\\ ($C_2$)\= \kill $G \leftarrow \emptyset$\\ $h \leftarrow 1$\\ $B \leftarrow \{h\}$\\ $H \leftarrow \emptyset$\\ do \{\\ \> $N \leftarrow \{u \mid u > h$ かつすべての $m \in H$ に対し $m {\not|} u\}$\\ (0)\> if $N = \emptyset$ then return $G$\\ (1)\> $h_1 \leftarrow \min(N)$\\ \> $a_t$ : $t \in B$ に対応する未定係数\\ \> $a_{h_1} \leftarrow 1$\\ (2)\> $E \leftarrow \displaystyle{NF_{<_1}(h_1,F)+\sum_{t \in B} a_t NF_{<_1}(t,F)}$\\ \> $C \leftarrow$ $E$ の $X$ に関する係数の集合\\ \> if \= 線形方程式 $\{ f = 0 \mid f \in C\}$ が解 $\{a_t = c_t \mid c_t \in K\}$ を持つ\\ \> then \\ \> \>$G \leftarrow G \cup \{\displaystyle{h_1+\sum_{t \in B} c_t t}\}$\\ \> \>$H \leftarrow H \cup \{h_1\}$\\ \> else $B \leftarrow \{h_1\} \cup B$\\ \> $h \leftarrow h_1$\\ \}\\ \end{tabbing} \end{al} \begin{lm} \label{fglml1} (0) において, $B= \{u \mid u \le h$ かつすべての $m \in H$ に対し $m {\not|} u\}$. \end{lm} \proof ループに関する帰納法で示す. 最初にループに入った時点では 成立している. ある時点で成立しているとする. その時点からループが一回 回った時点の (0) において成立することを示す. 示そうとする時点の一つ前の時点での $N$, $B$, $h$ を $N_0$, $B_0$, $h_0$ と書く. $h = \min(N_0)$ で, $B = B_0 \cup \{h\}$ または $H = H_0 \cup \{h\}$ である. \\ \underline{$B = B_0 \cup \{h\}$ の時}\, $H = H_0$ より, 右辺 $= B_0 \cup \{u \mid$ $h_0 < u \le h$ かつすべての $m \in H_0$ に 対し $m{\not|} u\}= B_0 \cup \{h\}$.\\ \underline{$H = H_0 \cup \{h\}$ の時}\, 右辺 $= B_0 \cup (\{u \mid h_0 < u \le h$ かつすべての $m \in H_0$ に対し $m {\not|} u\} \cap \{u \mid h {\not|} u \}) = B_0 \cup (\{h\} \cap \{u \mid h {\not|} u \}) = B_0$.\\ よって, いずれの場合にも右辺 = $B$ となる. \qed \begin{lm} \label{fglml2} (1) において, $h_1 \in x_1B \cup \cdots \cup x_nB$. \end{lm} \proof $h_1>1$ よりある $k$ が存在して $h_1=x_kh'$ と書ける. もし $h' \in N$ ならば $h_1 = \min(N)$ に反するから $h' \in B$. \qed \begin{pr} アルゴリズム \ref{fglm} は $GB_<(F)$ を出力する. \end{pr} \proof 補題 \ref{fglml2}より, (1) における $h$ の候補は 有限集合 $x_1B \cup \cdots \cup x_nB$ の元だから $\min(N)$ を与える選択アルゴリ ズムが存在する. \\ \underline{停止性} まず, (2) が解を持たないことと, $\{h_1\} \cup B$ が $K[X]/I$ で $K$ 上一次独立であることが同値であることに注意する. よって, $|B|$ は$\dim_K K[X]/I$ を越えられない. また, $H$ の元は, どの元も他の 元を割らないから, 系 \ref{noether} よりやはり有限集合. よってアルゴリ ズムは停止する.\\ \underline{$G = GB_<(F)$} $f \in I$ とし, $t=HT_<(F)$ とする. $f$ は $G$ に関して被約としてよい. $H = \{h_1,\cdots,h_m\}$ \quad ($h_1<\cdots $F \subset \Z[X]$ \st $F = GB_{<_1}(Id(F))$\\ \> $F$ の各元の $<_1$ に関する主係数を割らない $p$ \\ Output : $F$ の $<$ に関するグレブナ基底候補または {\bf nil}\\ ($C_2$)\= \kill $\overline{G} \leftarrow$ $GB_<(Id(\phi_p(F)))$ (被約グレブナ基底) \\ $G \leftarrow \emptyset$\\ for \= each $h \in \overline{G}$ do \{\\ \> $a_t$ : $t \in T(h)$ に対応する未定係数\\ \> $a_t \leftarrow 1$ ($t = ht_{<}(h)$ に対して)\\ \> $H \leftarrow \displaystyle{\sum_{t \in T(h)} a_t NF_{<_1}(t,F)}$\\ \> $C \leftarrow$ $H$ の $X$ に関する係数の集合\\ \> if \= 線形方程式 $E_h = \{ f = 0 \mid f \in C\}$ が解 $S_h = \{a_t = c_t \mid c_t \in \Q\}$ を持つ\\ \> then $G \leftarrow G \cup \{\displaystyle{d\sum_{t \in T(h)} c_t t}\}$\\ \> {\rm ($d$ : $c_t$ の分母の LCM)}\\ \> else return {\bf nil}\\ \}\\ return $G$ \end{tabbing} \end{al} \begin{pr} アルゴリズム \ref{mfglm} は, 有限個の $p$ を除いて $GB_<(F)$ を 与える. \end{pr} \proof trace lifting の場合と同様に, 有限体上でのグレブナ基底の各 元に現れる項が, 有理数体上でのそれと一致していれば, 全ての線形方程式は 解を持ち, $G = GB_<(F)$ となる. そうでない $p$ は有限個しかないため, それらを除いては, このアルゴリズムは $GB_<(F)$ を与える. \qed \begin{re} 線形方程式が全部解けたとしても, 結果が $Id(F)$ のグレブナ基底になって いる保証は現時点ではないので, この命題は不十分である. 実は, 次で述べる 結果により, アルゴリズム \ref{mfglm} が {\bf nil} でない多項式集合を 返せば, それはただちに $Id(F)$ のグレブナ基底となっていることが分かる. これについては, 線形方程式の, 結果の大きさに応じた計算量を必要とする 求解法とともに, 後で述べる. \end{re} \subsection{グレブナ基底候補がグレブナ基底となる条件} ここでは, change of ordering の場合には, trace lifting の場合に必要だったグレブナ基底テストとメンバシップテスト が不必要になることを示す. $F \subset \Z[X]$ とする. \begin{as} \label{nf} 有理数体上と有限体上の計算が異らないよう次の仮定をおく. \begin{enumerate} \item 不必要対の検出基準は頭項のみで行う. \item 正規形計算において, 正規化に用いる元 (reducer) の選択は, 正規化される 多項式の項および reducer の頭項の集合にのみ依存する. \end{enumerate} \end{as} \begin{df} {\rm (compatibile な素数)} 素数 $p$ が $F$ に関し compatible とは, $$\phi_p(Id(F)\cap\Z[X]) (=\phi_p(Id(F)\cap\Z_{(p)}[X])) = Id(\phi_p(F))$$ なること. \end{df} \begin{df} 素数 $p$ が $(F,<)$ に関して strongly compatible とは $p$ が $F$ に関して compatible で $$E_<(Id(F)) = E_<(Id(\phi_p(F))$$ なること. \end{df} \begin{df}(permissible な素数) 素数 $p$ が $(F,<)$ について permissible とは 各 $f \in F$ に対し \valid{p}{f}{<} なること. \end{df} \begin{df} $f \in \Q[X]$ が $p$ に関し stable とは $f \in \Z_{(p)}[X]$ なること. \end{df} \begin{df} {\rm (modular グレブナ基底の逆像)} $G \subset Id(F)\cap \Z[X]$ が $F$ の $<$ に関する $p$-compatible なグレブナ基底候補とは $p$ が $(G,<)$ について permissible で $\phi_p(G)$ が$Id(\phi_p(F))$ の $<$ に関するグレブナ基底なるときをいう. \end{df} \begin{re} compatibility は order に独立な概念である. \end{re} \begin{lm} \label{valid} $G \subset \Z[X]$, $p$ を $(G,<)$ について permissible な素数, $f \in \Z[X]$ とする. このとき 仮定 \ref{nf} のもとで $$NF(\phi_p(f),\phi_p(G)) = \phi_p(NF(f,G)).$$ \end{lm} \proof $NF(f,G)$ は次の recurrence で計算される. $$f_0 \leftarrow f, f_i \leftarrow f_{i-1} - \alpha_i t_i g_{k_i}$$ ここで, $\alpha_i\in {\bf \Q}$, $t_i$ : a term, $g_{k_i}\in G$. すると, $p$ が $(G,<)$ に対して permissible より $\alpha_i \in \Z_{(p)}$. よって 全ての $i$ に対し $f_i \in \Z_{(p)}[X]$ で, この recurrence に $\phi_p$ を適用して次を得る. $$\phi_p(f_i) = \phi_p(f_{i-1}) - \phi_p(\alpha_i) t_i \phi_p(g_{k_i}).$$ もし $\phi_p(\alpha_i) \neq 0$ ならば $\phi_p(f_{i-1}) \neq 0$ で, $$\phi_p(f_i) \leftarrow \phi_p(f_{i-1}) - \phi_p(\alpha_i) t_i \phi_p(g_{k_i})$$ は $\phi_p(G)$ による頭項消去である. もし $\phi_p(\alpha_i) = 0$ ならば $\phi_p(f_i) = \phi_p(f_{i-1})$ で $$\{\phi_p(f_i)\mid i=0\, {\rm or}\, \phi_p(\alpha_i)\neq 0\}$$ なる列は $NF(\phi_p(f),\phi_p(G))$ の計算に対応する. もし$\phi_p(f_i) = 0$ なる $i$ が存在すれば像は途中で切れるが $$NF(\phi_p(f),\phi_p(G)) = \phi_p(NF(f,G)) = 0$$ だから主張が成立する. \qed \medskip \begin{th} \label{comp} $G \subset Id(F)\cap\Z[X]$ を $Id(F)$ の $<$ に関するグレブナ基底とする. もし $p$ が $(G,<)$ に関して permissible かつ $\phi_p(G) \subset Id(\phi_p(F))$ ならば $p$ は $F$ に関して compatible である. 更に, $\phi_p(G)$ は $Id(\phi_p(F))$ のグレブナ基底で $p$ は $(F,<)$ について strongly compatible である. \end{th} \proof $h \in Id(F) \cap \Z[X]$ とする. $G$ が $Id(F)$ のグレブナ基底だから, $NF(h,G)=0$ より $h = \sum_{g\in G} a_g g$ と書ける. ここで $a_g \in \Q[X]$. 更に $p$ が $(G,<)$ について permissible より, $a_g$ は $p$ について stable で, 仮定 $\phi_p(g)\in Id(\phi_d(F))$ より $$\phi_p(h)=\sum_{g\in G} \phi_p(a_g) \phi_p(g).$$ よって $\phi_p(h)\in Id(\phi_p(F))$. 故に $\phi_p(Id(F)\cap \Z[X])\subset Id(\phi_p(F))$. \\ 逆に $\overline{h} \in Id(\phi_p(F))$ は $$\overline{h} = \sum_{f\in F} \overline{a}_f \phi_p(f)$$ と書ける. ここで $\overline{a}_f \in GF(p)[X]$. すると, $\phi_p(a_f)=\overline{a}_f$ なる $a_f$ を選んで $h=\sum_{f\in F} a_f f$ とおけば $\phi_p(h)=\overline{h}$. これから $\phi_p(Id(F)\cap \Z[X])=Id(\phi_p(F))$. \\ 最後に $\phi(G)$ が $Id(\phi_p(F))$ のグレブナ基底となることを示す. 上で述べたことから, $\overline{h} \in Id(\phi_p(F))$ に対し, $h \in Id(F)\cap \Z[X]$ が存在して $\overline{h}=\phi_p(h)$. すると, 補題 \ref{valid} より $$NF(\overline{h},\phi_p(G))=\phi_p(NF(h,G))=0.$$ 従って, $\phi_p(G)$ は $Id(\phi_p(F))$ のグレブナ基底. strong compatibility は $E_<(Id(F))$ が $E_<(G)$ で生成されることから分かる. \qed \\ この定理で, $\phi_p(G) \subset Id(\phi_p(F))$ は $Id(\phi_p(F))$ のグレブナ基底によりチェックできる. よって, $p$ の compatibility のチェックは有理数体上, 有限体上の 任意の order でのグレブナ基底を計算することで行うことができる. もし, 入力が既にある order でのグレブナ基底なら compatibility のチェック は極めて簡単である. \begin{co} \label{compco} $G \subset \Z[X]$ が $<$ に関する $Id(G)$ のグレブナ基底とする. もし $p$ が $(G,<)$ に対し permissible ならば $\phi_p(G)$ は $Id(\phi_p(G))$ のグレブナ基底で $p$ は $(G,<)$ に対し strongly compatible. \end{co} 次の定理は, グレブナ基底候補が実際にグレブナ基底になるための十分条件を与える. すなわち, 我々が求めるものである. \begin{th} \label{candi} $p$ が $F$ について compatible で $G$ が $<$ に関して $p$-compatible なグレブナ 基底候補ならば, $G$ は $<$ に関する $Id(F)$ のグレブナ基底である. \end{th} \proof 全ての $f \in Id(F)$ が $<$ に関して $G$ により 0 に正規化 されることを示せばよい. $f$ は $G$ について被約としてよい. もし $f \neq 0$ ならば, 適当な有理数をかけて, $f \in Id(F)\backslash \{0\}$ が $G$ について被約で $f$ の係数の整数 GCD ($cont(f)$ と書く) が 1 に等し い, としてよい. すると $\phi_p(f) \neq 0$. さもなくば $cont(f)$ は因子 $p$ を持つことになる. $p$ は $F$ につき compatible だから $\phi_p(f) \in Id(\phi_p(F))$. すると $\phi_p(f)$ は $<$ に関し, $\phi_p(G)$ により 0 に正規化されなければ ならない. しかし $f$ は $G$ について被約だから $\phi_p(G)$ の頭項の集合は $G$ のそれと等しい. よって $\phi_p(f)$ は $\phi_p(G)$ について被約となり, $\phi_p(f) = 0$. これは 矛盾. \qed \medskip 次の定理は前定理の精密化である. すなわち, 昇順に計算された部分的な $p$-compatible なグレブナ基底候補が実際にグレブナ基底の一部となって いることを保証する. これは, 途中までの結果を再利用できるという点で 有用である. また, 後で述べるように, グレブナ基底のある特定の元, 例えば, 順序最小の元のみを求めたい, あるいは elimination 後の結果のみ を求めたい場合にも有用である. \begin{th} $p$ が $F$ について compatible とする. $\overline{G}\subset GF(p)[X], \overline{G} = GB_<(Id(\phi_p(F))$ とし $\overline{g}_1<\cdots<\overline{g}_s$ なる $\overline{g}_i$ により $\overline{G}=\{\overline{g}_1,\cdots,\overline{g}_s\}$ と書く. 更に, ある正数 $t\leq s$ に対し, $g_i \in Id(F) \cap \Z_{(p)}[X]$ ($1 \le i \le t$) が存在して $\phi_p(g_i) = \overline{g}_i$ かつ $g_i$ は $\{g_1,\cdots,g_{i-1}\}$ について 被約とする. このとき, $g_1,\cdots,g_t$ は $GB_<(Id(F))$ の最初の $t$ 個の元に一致する. \end{th} 証明略 (帰納法による.)\\ 以上述べたことにより, 次のような一般的な change of ordering アルゴリズム が得られる. \begin{pro} \begin{tabbing} \\ candidate$(F,p,<)$\\ Input : \= $F \subset Z[X]$\\ \> 素数 p\\ \> order $<$\\ Output : $F$ の $p$-compatible なグレブナ基底候補またば {\bf nil}\\ {\rm (各 $F$ に対し, {\bf nil} を返す $p$ の個数は有限個でなければならない.)}\\ \end{tabbing} \end{pro} \begin{al}(compatibility check によるテストの省略) \label{bconv} \begin{tabbing} gr\"obner\_by\_change-of-ordering$(F,<)$\\ Input : \= $F \subset \Z[X]$, order $<$\\ Output : $Id(F)$ の $<$ に関するグレブナ基底 $G$\\ $G_0 \leftarrow$ $F$ の, ある order $<_0$ に関するグレブナ基底; $G_0 \subset \Z[X]$\\ {\bf again:}\\ for\= \kill \> $p \leftarrow (G_0,<_0)$ に関して permissible な未使用の素数 \\ \> $G \leftarrow$ candidate($G_0$,$p$,$<$)\\ \> If $G$ = {\bf nil} goto {\bf again:}\\ \> else return $G$ \end{tabbing} \end{al} candidate() においては, $p$-compatible なグレブナ基底候補を返す 任意のアルゴリズムが使用可能である. これまで述べたものでは, \begin{itemize} \item tl\_guess() \item 斉次化 + tl\_guess() + 非斉次化 \item candidate\_by\_linear\_algebra() \end{itemize} が適合する. これらのうち, 前者 2 つについては明らかだが, 最後のものに ついては検証を要する. これについて次節で述べる. \subsection{candidate\_by\_linear\_algebra()} \begin{lm} \label{munique} アルゴリズム \ref{mfglm} において $C$ に属する多項式は $p$ について stable で, $E_{h,p}=\{\phi_p(c)=0 \mid c \in C\}$ は一意解を持つ. \end{lm} \proof $p$ が $(F,<_1)$ に関し permissible より $NF_{<_1}(t,F)$ は $p$ について stable. よって $c \in C$ も $p$ について stable. $$S_{h,p}=\{a_t=\overline{c}_t \mid \overline{c}_t \in GF(p)\}$$ が $E_{h,p}$ の解とする. $$\overline{h}=\displaystyle{\sum_{t \in T(h)} \overline{c}_t t}$$ とおく. すると, $$0=\displaystyle{\sum_{t \in T(h)} \overline{c}_t \phi_p(NF_{<_1}(t,F)})= NF_{<_1}(\overline{h},\phi_p(F)).$$ よって $\overline{h} \in Id(\phi_p(F))$ より $NF_<(\overline{h},\overline{G})=0$. すると $\overline{G}$ が被約グレブナ基底で $T(\overline{h})\subset T(h)$ より $\overline{h}=h$ が成り立つ. これは, 解が一意的で $h$ に一致することを意味する. \qed \medskip \begin{co} \label{sqmat} $n$ を不定元 $a_t$ の個数とすると, $E_h$ から次の性質をもつ subsystem $E'_h$ を選ぶことができる. \begin{itemize} \item $E'_h$ は $n$ 個の方程式からなる. \item $\phi_p(E'_h)$ は $GF(p)$ 上で一意解をもつ. \end{itemize} これから次のことが分かる. \begin{itemize} \item $E'_h$ は $\Q$\, 上一意解を持ち, 解は $p$ について stable. \item $E_h$ が解をもてば, それは $E'_h$ の一意解に一致する. \end{itemize} \end{co} \begin{th} アルゴリズム \ref{mfglm} が多項式集合 $G$ を返せば, $G$ は $F$ の $<$ に関して $p$-compatible なグレブナ基底候補である. \end{th} \proof 各 $g \in G$ に対し $$g = \displaystyle{\sum_{t \in T(h)} c_t t}$$ と書け, $\{c_t/c\}$\, ($c = c_{hc_<(g)}$) が $E_h$ の解となるような $h \in \overline{G}$ が存在する. すると, $$0 = c\displaystyle{\sum_{t \in T(h)} c_t/c NF_{<_1}(t,F)} = NF_{<_1}(g,F).$$ 故に $g \in Id(F)$. 系 \ref{sqmat} により $p$ は $(G,<)$ について permissible で $\phi_p(g)$ = $\phi_p(c) h$ より $\phi_p(G)$ は $\overline{G}$ のグレブナ基底である. \qed\\ \medskip 上の補題を用いて $E_h$ を次の手順で解く. \begin{enumerate} \item $E'_h$ を選ぶ. \item $S \leftarrow$ $E'_h$ の一意解. \item もし $S$ が $E_h$ を満たせば $S$ は $E_h$ の一意解, さもなくば $E_h$ は解を持たない. \end{enumerate} $E_h$ は $E'_h$ を $GF(p)$ 上で解く仮定で得られる. 以下では, $E'_h$ を解く方法について述べる. これは次のように 定式化できる. \begin{prob} $M$, $B$ をそれぞれ $n\times n$, $n\times 1$ 整数行列とし, $X$ を, 未定係数を成分とする $n\times 1$ 行列とする. $\det(\phi_p(M))\neq 0$ のもとで, $MX=B$ を解け. \end{prob} $M$, $B$ は, 一般に, 長大な整数を成分に持つ密行列となる. しかし, もともとの入力多項式の係数が小さい場合, グレブナ基底の元の係数 すなわち $MX=B$ の解 $X$ は比較的小さい場合が多い. このような場合に この問題を Gauss 消去で解くことはこの節の最初の例で述べたように 非効率的である. このような場合に有効なのが, Hensel 構成, 中国剰余定理 などによる modular 計算である. ここでは Hensel 構成による方法を 紹介する. \begin{al} \label{lineq} \begin{tabbing} \\ solve\_linear\_equation\_by\_hensel$(M,B,p)$\\ ($C_2$)\= \kill Input : \= $n\times n$ 行列 $M$, $n\times 1$ 行列 $B$\\ \> $\phi_p(\det(M))\neq 0$ なる素数\\ Output : $MX=B$ なる $n\times 1$ matrix $X$\\ $R \leftarrow \phi_p(M)^{-1}$\\ $c \leftarrow B$\\ $x \leftarrow 0$\\ $q \leftarrow 1$\\ $count \leftarrow 0$\\ do \{\\ (1)\> $t \leftarrow \phi_p^{-1}(R \phi_p(c))$\\ (2)\> $x \leftarrow x + qt$\\ \> $c \leftarrow (c-Mt)/p$\\ \> $q \leftarrow qp$\\ \> $count \leftarrow count+1$\\ \> {\rm ($\phi_p^{-1}$ は $[-p/2,p/2]$ に正規化された逆像, $(c-Mt)/p$ は整除.)}\\ \> if \= $count = {\bf Predetermined\_Constant}$ then \{\\ \> \> $count \leftarrow 0$\\ \> \> $X \leftarrow$ inttorat$(x,q)$\\ \> \> if \= $X \neq$ {\bf nil} かつ $MX=B$ then return $X$\\ \> \}\\ \} \end{tabbing} \end{al} \begin{al} \label{intrat} \begin{tabbing} \\ inttoat$(x,q)$\\ ($C_2$)\= \kill Input : $q>x$, $\GCD(x,q)=1$ なる正整数 $x$, $q$ \\ Output : $bx \equiv a \bmod q$ かつ $|a|,|b| \le \sqrt{q\over 2}$ なる有理数 $a/b$ または {\bf nil}\\ if $x \le \sqrt{q\over 2}$ then return $x$\\ $f_1 \leftarrow q$, $f_2 = x$, $a_1 \leftarrow 0$, $a_2 \leftarrow 1$\\ $i \leftarrow 1$\\ do \= \{\\ \> if \= $|f_i| \le \sqrt{q\over 2}$ then \\ \>\> if $|a_i| \le \sqrt{q\over 2}$ then return $f_i/a_i$\\ \>\> else return {\bf nil}\\ \> $f_i - q_i f_{i+1} < f_{i+1}$ なる $q_i$ を求める\\ \> $f_{i+2} \leftarrow f_i - q_i f_{i+1}$\\ \> $a_{i+2} \leftarrow a_i - q_i a_{i+1}$\\ \> $i \leftarrow i+1$\\ \} \end{tabbing} \end{al} \begin{lm}(\cite{WANG2}\cite{DIXON}) \label{intratlm} $x$, $q$ を $q>x>1$, $\GCD(x,q)=1$ なる正整数とする. このとき, $|a|,|b|\le\sqrt{q/2}$, $\GCD(a,b)=1$ なる整数 $a,b$ $(b>0)$ および整数 $c$ があって $ax+cq=b$ となるならば, $(a,b,c)$ は $(q,x)$ に対する拡張 Euclid 互除法により得られる. \end{lm} [略証] $x>1$ より $a \neq b$ としてよい. $ax+cq=b$ より ${x \over q}+{c \over a} = {b \over aq}.$ ここで $$|{b \over {aq}}| = |{{ab} \over {a^2q}}| < {1 \over {2a^2}}$$ より $$|{x \over q}+{c \over a}| < {1 \over {2a^2}}.$$よって, $-c/a$ は $x/q$ の主近似分数の一つ. (連分数の性質による. \cite[Section 24]{TAKAGI} 参照.) $\GCD(a,b)=1$ より $\GCD(a,c)=1$ であり, $b>0$ に対して $(a,c)$ は一意 的に決まる. よって, $(a,b,c)$ は $(q,x)$ に対する拡張 Euclid 互除法の 係数として得られる. \qed \begin{lm} \label{lineqlm} (1) において $Mx \equiv B \bmod q$ かつ $c = (B-Mx)/q$. \end{lm} \proof 帰納法により示す. $count = 0$ のとき明らか. $count = m$ まで言えたとする. このとき, (2) で $Mt \equiv c \bmod p$ より $M(x+qt) \equiv Mx+q(B-Mx)/q \bmod qp$. すなわち $M(x+qt) \equiv B \bmod qp$. また, $(c-Mt)/p = ((B-Mx)-qMt)/qp = (B-M(x+qt))/qp$ より $count = m+1$ でも言える. \qed \begin{pr} アルゴリズム \ref{lineq} は $MX=B$ の解 $X$ を出力する. \end{pr} \proof 補題 \ref{lineqlm} より, $count=m$ のとき (1) において $Mx \equiv B \bmod p^m$. $\det(M) \neq 0$ より $x$ は法 $p^m$ で一意的である. 一方 $MX=B$ は有理数体上一意的に解を持つ. この解を$X=N/D$ ($D$ は整数, $N$ は整数ベクトル) と書くとき, $Dr \equiv 1 \bmod p^m$なる整数 $r$ をとれ ば $M(rN) \equiv B \bmod p^n$. よって $rN \equiv x \bmod p^m$. $D$, $N$ の各成分が $A$ を越えないとき, $p^m > 2A^2$ なる $m$ をとれば, 補題 \ref{intratlm} より $rN$ すなわち $x$ からアルゴリズム \ref{intrat} により $N/D$ が復元される. \qed\\ {\bf Predetermined\_Constant} はある正整数で, 有理数に引き戻してチェッ クを行う頻度を制御する. アルゴリズム \ref{lineq} において $c$ は $nMAX(\|M\|_\infty,\|B\|_\infty)$で押えられることがわかる. これは, 各 ステップがある constant 時間内で計算できることを示す. また, 解の分母分 子が $A$ で押えられていれば, $q > 2A^2$ になった段階で解を復元でき る. これは, 解の大きさに応じた手間で計算できることを意味する. これに対 して, 係数膨張を押えた Gauss 消去法である fraction-free 法によっても, 解の大きさにかかわらず, 係数行列の行列式を計算してしまうという点で, Gauss 消去法は, この問題を解くためには不適切である. \section{タイミングデータ} 本節では, 以下のようなベンチマーク問題に関し, 本章で述べた様々な change of ordering アルゴリズムの効率の比較を示す. また, 命題 \ref{RUR} で触れた RUR のモジュラ計算を同じ問題に適用し, その優位性を実験結果により示す. 計測は, PC (FreeBSD, 300MHz Pentium II, 512MB of memory) で行った. 単位は秒. garbage collection 時間は除い てある. \begin{tabbing} $MMM\;\;$ \= \kill $C(n)$ \> The cyclic n-roots system of n variables. (Faugere {\it et al.},1993).\\ \> $\{f_1,\cdots,f_n\}$ where $f_k= \displaystyle{\sum_{i=1}^n\prod_{j=i}^{k+j-1}c_{j \bmod n}-\delta_{k,n}}$. ($\delta$ is the Kronecker symbol.) \\ \> The variables and ordering : $c_n \succ c_{n-1} \succ \cdots \succ c_1$\\ $K(n)$ \> The Katsura system of n+1 variables. \\ \> $\{u_l - \sum_{i=-n}^n u_i u_{l-i} (l = 0,\cdots, n-1), \sum_{l=-n}^n u_l - 1\}$\\ \> The variables and ordering : $u_0 \succ u_1 \succ \cdots \succ u_n$.\\ \> Conditions : $u_{-l} = u_l$ and $u_l = 0 (|l| > n)$. \\ $R(n)$ \> {\tt e7} in Rouillier (1996). \\ \> $\{-1/2+\sum_{i=1}^n(-1)^{i+1}x_i^k (k=2, \cdots, n+1) \}$\\ \> The variables and ordering : $x_n \succ x_{n-1} \succ \cdots \succ x_1$.\\ $D(3)$ \> {\tt e8} in Rouillier (1996). \\ \> $\{f_0,f_1,f_2,\cdots,f_7\}$\\ \> {\scriptsize $f_0=-420y^2-280zy-168uy-140vy-120sy-210ty-105ay+12600y-13440$}\\ \> {\scriptsize $f_1=-840zy-630z^2-420uz-360vz-315sz-504tz-280az+18900z-20160$}\\ \> {\scriptsize $f_2=-630ty-504tz-360tu-315tv-280ts-420t^2-252at+12600t-13440$}\\ \> {\scriptsize $f_3=-5544uy-4620uz-3465u^2-3080vu-2772su-3960tu-2520au+103950u-110880$}\\ \> {\scriptsize $f_4=-4620vy-3960vz-3080vu-2772v^2-2520sv-3465tv-2310av+83160v-88704$}\\ \> {\scriptsize $f_5=-51480sy-45045sz-36036su-32760sv-30030s^2-40040ts-27720as+900900s-960960$}\\ \> {\scriptsize $f_6=-45045ay-40040az-32760au-30030av-27720as-36036at-25740a^2+772200a-823680$}\\ \> {\scriptsize $f_7=-40040by-36036bz-30030bu-27720bv-25740bs-32760bt-24024ba+675675b-720720$}\\ \normalsize \> The variables and ordering : $b \succ a \succ s \succ v \succ u \succ t \succ z \succ y$.\\ $Rose$ \> The Rose system.\\ % \> $\{u_4^4-20/7a_{46}^2, a_{46}^2u_3^4+7/10a_{46}u_3^4+7/48u_3^4-50/27a_{46}^2-35/27a_{46}-49/216,$\\ % \> $a_{46}^5u_4^3+7/5a_{46}^4u_4^3+609/1000a_{46}^3u_4^3+49/1250a_{46}^2u_4^3$\\ % \> $-27391/800000a_{46}u_4^3-1029/160000u_4^3+3/7a_{46}^5u_3u_4^2+3/5a_{46}^6u_3u_4^2$\\ % \> $+63/200a_{46}^3u_3u_4^2+147/2000a_{46}^2u_3u_4^2+4137/800000a_{46}u_3u_4^2$\\ % \> $-7/20a_{46}^4u_3^2u_4-77/125a_{46}^3u_3^2u_4-23863/60000a_{46}^2u_3^2u_4$\\ % \> $-1078/9375a_{46}u_3^2u_4-24353/1920000u_3^2u_4-3/20a_{46}^4u_3^3-21/100a_{46}^3u_3^3$\\ % \> $-91/800a_{46}^2u_3^3-5887/200000a_{46}u_3^3-343/128000u_3^3 \}$\\ \> $O_1$ : $u_3 \succ u_4 \succ a_{46}$, $O_2$ : $u_3 \succ a_{46} \succ u_4$.\\ $Liu$ \> The Liu system.\\ \> $\{y(z-t)-x+a, z(t-x)-y+a, t(x-y)-z+a, x(y-z)-t+a\}$\\ \> The variables and ordering : $x \succ y \succ z \succ t \succ a$.\\ $Fate$ \> The Fateman system, appeared on NetNews. \\ \> $\{s^3+2r^3+2q^3+2p^3$, $s^5+2r^5+2q^5+2p^5$,\\ \> $-s^5+(r+q+p)s^4+(r^2+(2q+2p)r+q^2+2pq+p^2)s^3+(r^3+q^3+p^3)s^2$\\ \> $+(3r^4+(2q+2p)r^3+(4q^3+4p^3)r+3q^4+2pq^3+4p^3q+3p^4)s+(4q+4p)r^4$\\ \> $+(2q^2+4pq+2p^2)r^3+(4q^3+4p^3)r^2+(6q^4+4pq^3+8p^3q+6p^4)r$\\ \> $+4pq^4+2p^2q^3+4p^3q^2+6p^4q\}$\\ \> The variables and ordering : $p \succ q \succ r \succ s$.\\ $hC(6)$ \> A homogenization of C(6). \\ \> $(C_6\backslash \{c_1c_2c_3c_4c_5c_6-1\})\cup \{c_1c_2c_3c_4c_5c_6-t^6\}$\\ \> The variables and ordering : $c_1 \succ c_2 \succ c_3 \succ c_4 \succ c_5 \succ c_6 \succ t$.\\ \end{tabbing} \subsection{Change of ordering} 予め計算してある DRL (全次数逆辞書式順序)グレブナ基底から出発して, LEX (辞書式順序)グレブナ基底を計算する. 用いるアルゴリズムは, TL (tl\_guess$()$; アルゴリズム \ref{tlguess}), HTL (斉次化 +tl\_guess$()$+非斉化), LA (candidate\_by\_linear\_algebra$()$;アルゴ リズム \ref{mfglm} (0 次元システムのみ))である. 表 \ref{mcotab} は DRL から LEX への変換にかかる時間をしめす. {\it DRL} は, DRL の計算時間を示す. グレブナ基底チェックを省く効果を示すために, tl\_ckeck$()$ (アルゴリズム \ref{tlcheck}) の時間も示す. \begin{table}[hbtp] \caption{Modular change of ordering} \label{mcotab} \begin{center} \begin{tabular}{|c||c|c|c|c|c|c|c|} \hline & $K(5)$ & $K(6)$ & $K(7)$ & $C(6)$ & $C(7)$ & $R(5)$ & $R(6)$ \\ \hline {\it DRL}&0.84 &8.4 &74 &3.1 &1616 &11 &1775 \\ \hline {\it TL}&$\infty$ &$\infty$ &$\infty$ &$\infty$ &$\infty$ &$\infty$ &$\infty$ \\ \hline {\it HTL} &16 &1402 &$1.6\times 10^5$ &5.6 &$2\times 10^4$ &383 &$2.1\times 10^5$ \\ \hline {\it LA} &4.7 &158 &6813 &4 &435 &9.5 &258 \\ \hline tl\_check &2.3 &177 &$1.3\times 10^4$ &1.1 &2172 &3 &40 \\ \hline \end{tabular} \begin{tabular}{|c||c|c|c||c|c|c|} \hline & $D(3)$ & $RoseO_1$ & $RoseO_2$ & $Liu$ & $Fate$ & $hC(6)$ \\ \hline {\it DRL} &30 &0.19 &0.15 &0.06 &0.5 &7.2 \\ \hline {\it TL} & $\infty$ &1.7 &354 &$\infty$ &4 &25 \\ \hline {\it HTL} &$4.1\times 10^4$ &1.7 &36 &18 &4 &25 \\ \hline {\it LA} &585 &3.3 &12 & --- & --- & --- \\ \hline tl\_check &575 &0.6 &13 &17 &26 &24 \\ \hline \end{tabular} \end{center} \end{table} 整数係数多項式に対し, その {\bf maginitude} を, 係数のビット長の和で定義する. {\it TL} と {\it HTL} の差を見るために, 表 \ref{magnitude} で, 計算途中における最大 magnitude を示す. \begin{table}[hbtp] \caption{Maximal magnitude} \label{magnitude} \begin{center} \begin{tabular}{|c||c|c|c|c|c|c|} \hline & $C(6)$ & $K(5)$ & $K(6)$ & $RoseO_1$ & $RoseO_2$ & Liu \\ \hline {\it TL}& $>$ 735380 & $> 2407737 $ & $>$ 57368231 & 69764 & 947321 & $>$ 327330 \\ \hline {\it HTL}& 1992 & 44187 & 422732 & 37220 & 70018 & 21095 \\ \hline \end{tabular} \end{center} \end{table} 表より明らかに, {\it TL} は非斉次多項式に対するグレブナ基底計算に不向き であることがわかる. さらに, 表 \ref{mcotab} は {\it HTL} に対する {\it LA} の優位性を示している. これは, Buchberger アルゴリズムが Euclid の互除法に対応していて, 中間係数膨張で効率が左右されるの に対し, modular アルゴリズムの効率は結果の大きさのみに依存する ことによる. \subsection{RUR} RUR の modular 計算のタイミングデータを示す. 計算環境は前節と同様であ る. ここでは, 予め modular 計算により separating elementを求めてあ る. これらを用いて, それぞれ次のような多項式を添加したイデアルに対し, $w$ に関する RUR 計算を行う. \begin{tabbing} $MMM\;\;$ \= \kill $C(6)$ \> $w-(c_1+3c_2+9c_3+27c_4+81c_5+243c_6)$\\ $C(7)$ \> $w-(c_1+3c_2+9c_3+27c_4+81c_5+243c_6+729c_7)$\\ $K(n)$ \> $w-u_n$\\ $R(5)$ \> $w-(x_1-3x_2-2x_3+3x_4+2x_5)$\\ $R(6)$ \> $w-(x_1-3x_2-2x_3+3x_4+2x_5-4x_6)$\\ $D(3)$ \> $w-y$ \end{tabbing} %\begin{table}[hbtp] %\label{mrurdata} %\caption{入力イデアルに関するデータ} %\begin{center} %\begin{tabular}{|c||c|c|c|c||c|c|c|c|c|} \hline % & $K(5)$ & $K(6)$ & $K(7)$ & $K(8)$ & $C(6)$& $C(7)$ & $R(5)$ & $R(6)$ & $D(3)$ \\ \hline %$\dim_{\Q} R/I$ & 32 & 64 & 128 & 256 & 156 & 924 &144 &576 & 128 \\ \hline %DRL GB& 0.8 & 7.2 & 68 & 798 & 3.1 & 1616 & 11 & 1775 & 30 \\ \hline %\end{tabular} %\end{center} %\end{table} \begin{table}[hbtp] \label{mrurtab} \caption{計算時間 (秒)} \begin{center} \begin{tabular}{|c|c|c|c||c|c|c|c|c|} \hline & $K(6)$& $K(7)$& $K(8)$& $C(6)$& $C(7)$& $R(5)$ & $R(6)$ & $D(3)$ \\ \hline Total & 7.4 & 69 & 1209 & 4.6 & 1643 & 52 & 8768 & 67 \\ \hline Quick test& 0.4 & 3.2 & 26 & 0.5 & 57 & 6.5 & 384 & 3.1 \\ \hline Normal form& 1.1 & 12 & 308 & 1.4 & 762 & 15 & 2861 & 7.3 \\ \hline Linear equation& 4.1 & 43 & 775 & 1.4 & 641 & 22 & 3841 & 45 \\ \hline Garbage collection& 1.7 & 10 & 100 & 1.2 & 181 & 7.8 & 1681 & 11 \\ \hline \end{tabular} \end{center} \end{table} %\begin{table}[hbtp] %\label{maxblen} %\caption{Maximal bit length of coefficients in LEX basis and the RUR} %\begin{center} %\begin{tabular}{|c||c|c|c|c|c|} \hline %& $K(5)$ & $K(6)$ & $K(7)$ & $K(8)$ & $D(3)$ \\ \hline %LEX & 1421 & 6704 & 36181 & --- & 6589 \\ \hline %RUR & 120 & 249 & 592 & 1258 & 821 \\ \hline %\end{tabular} %\end{center} %\end{table} 表で, Quick Test は modular 計算で $w$が separating element となること をチェックする時間, Normal Form は, 線形方程式を生成するための, monomial の正規形の計算, Linear Equation は, 線形方程式求解の時間であ る. 表 \ref{mcotab} と比較すれば, ある変数が separating element となっ ているような問題では, RUR 計算の効率が非常によいことが分かる. この理由 は, RUR に現れる係数の bit 長が, LEX 基底のそれに比べて非常に小さい(例 えば $K(7)$ では 60 分の 1 程度) ことと, 線形方程式の求解が, 結果の大 きさに応じた手間でできることから分かる.