\chapter{タイミングデータおよび例} \section{タイミングデータ : 方程式} \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} \section{タイミングデータ : change of ordering} ここでは, さまざまな change of ordering アルゴリズムのタイミングデータ を示す. 計測は, PC (FreeBSD, 300MHz Pentium II, 512MB of memory) で行った. 単位は秒. garbage collection 時間は除いてある. 予め計算してある DRL \gr 基底から出発して, LEX \gr 基底計算する. 用いるアルゴリズムは, TL ({\it tl\_guess$()$}), HTL (斉次化+{\it tl\_guess$()$}+非斉化), LA ({\it candidate\_by\_linear\_algebra$()$}; 0 次元システムのみ) である. 表 \ref{mcotype} は DRL から LEX への変換にかかる時間をしめす. {\it DRL} は, DRL の計算時間を示す. グレブナ基底チェックの効果を 示すために, {\it tl\_check$()$} の時間も示す. \begin{table}[hbtp] \caption{Modular change of ordering} \label{mcotype} \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 {\it 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 {\it 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{mcotype} は {\it HTL} に対する {\it LA} の優位性を示している. これは, Buchberger アルゴリズムが Euclid の互除法に対応していて, 中間係数膨張で効率が左右されるの に対し, modular アルゴリズムの効率は結果の大きさのみに依存する ことによる. \section{タイミングデータ : RUR} RUR の modular 計算のタイミングデータを示す. 計算環境は前節と同様であ る. ここでは, 予め modular 計算により separating elementを求めてあ る. これらを用いて, それぞれ次のような多項式を添加したイデアルに対し, $w$ に関する RUR 計算を行う. 表で, Quick Test は modular 計算で $w$ が separating element となることをチェックする時間, Normal Form は, 線形方程式を生成するための, monomial の正規形の計算, Linear Equation は, 線形方程式求解の時間である. 表 \ref{maxblen} では, LEX 基底と 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}[h] \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}[h] \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}[h] \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} \section{例 : 準素分解} 次の例は, symplectic integrator と呼ばれる安定な積分スキームの 数値計算法に関して現れた方程式系である \cite{SYMP}. \vskip\baselineskip {\small $\left\{ \parbox[c]{6in}{ $d_1+d_2+d_3+d_4=1, c_1+c_2+c_3+c_4=1,$\\ $(6d_1c_2+(6d_1+6d_2)c_3+(6d_1+6d_2+6d_3)c_4)c_1 +(6d_2c_3+(6d_2+6d_3)c_4)c_2+6d_3c_4c_3=1,$\\ $(3d_1^2+(6d_2+6d_3+6d_4)d_1+3d_2^2+(6d_3+6d_4)d_2+3d_3^2+6d_4d_3+3d_4^2)c_1$\\ $+(3d_2^2+(6d_3+6d_4)d_2+3d_3^2+6d_4d_3+3d_4^2)c_2+(3d_3^2+6d_4d_3+3d_4^2)c_3+3d_4^2c_4=1,$\\ $(3d_1+3d_2+3d_3+3d_4)c_1^2+((6d_2+6d_3+6d_4)c_2+(6d_3+6d_4)c_3+6d_4c_4)c_1$\\ $+(3d_2+3d_3+3d_4)c_2^2+((6d_3+6d_4)c_3+6d_4c_4)c_2+(3d_3+3d_4)c_3^2+6d_4c_4c_3+3d_4c_4^2=1,$\\ $(24d_2d_1c_3+(24d_2+24d_3)d_1c_4)c_2+(24d_3d_1+24d_3d_2)c_4c_3=1,$\\ $(12d_2^2+(24d_3+24d_4)d_2+12d_3^2+24d_4d_3+12d_4^2)d_1c_2 +((12d_3^2+24d_4d_3+12d_4^2)d_1$\\ $+(12d_3^2+24d_4d_3+12d_4^2)d_2)c_3 +(12d_4^2d_1+12d_4^2d_2+12d_4^2d_3)c_4=1,$\\ $4d_1c_2^3+(12d_1c_3+12d_1c_4)c_2^2+(12d_1c_3^2+24d_1c_4c_3 +12d_1c_4^2)c_2+(4d_1+4d_2)c_3^3$\\ $+(12d_1+12d_2)c_4c_3^2+(12d_1+12d_2)c_4^2c_3+(4d_1+4d_2+4d_3)c_4^3=1$ } \right.$} \vskip\baselineskip \noindent これを準素分解にかけると, 次の分解が得られる. \vskip\baselineskip $\left\{ \parbox[c]{8in}{ $24c_4^2-6c_4+1=0$\\ $c_1=-c_4+{1\over 4}$, $c_2=-c_4+{1\over 2}$, $c_3=c_4+{1\over 4}$ $d_1=-2c_4+{1\over 2}$, $d_2={1\over 2}$, $d_3=2c_4$, $d_4=0$} \right.$ $\left\{ \parbox[c]{8in}{ $6c_4^3-12c_4^2+6c_4-1=0$\\ $c_1=0$, $c_2=c_4$, $c_3=-2c_4+1$ $d_1={1\over 2}c_4$, $d_2=-{1\over 2}c_4+{1\over 2}$, $d_3=-{1\over 2}c_4+{1\over 2}$, $d_4={1\over 2}c_4$} \right.$ $\left\{ \parbox[c]{8in}{ $48c_4^3-48c_4^2+12c_4-1=0$\\ $c_1=c_4$, $c_2=-c_4+{1\over 2}$, $c_3=-c_4+{1\over 2}$ $d_1=2c_4$, $d_2=-4c_4+1$, $d_3=2c_4$, $d_4=0$} \right.$ $\left\{ \parbox[c]{8in}{ $6c_4^2-3c_4+1=0$\\ $c_1=0$, $c_2=-c_4+{1\over 2}$, $c_3={1\over 2}$ $d_1=-{1\over 2}c_4+{1\over 4}$, $d_2=-{1\over 2}c_4+{1\over 2}$, $d_3={1\over 2}c_4+{1\over 4}$, $d_4={1\over 2}c_4$} \right.$ \section{例 : 双対曲線の計算} $f(x_1,x_2) \in \Q[x_1,x_2]$ とし, $F$ の total degree を $d$ とすれば, $F(x_0,x_1,x_2)=x_0^df(x_1/x_0,x_2/x_0)$ は $d$ 次同次多項式で, $F$ の定義する代数曲線の双対曲線は, $$\left\{ \parbox[c]{8in}{ $u_i={{\partial F}\over {\partial x_i}} (x_0,x_1,x_2)$ $(i=0,1,2)$\\ $F(x_0,x_1,x_2)=0$ } \right.$$ から $x_0, x_1, x_2$ を消去して得られる. 消去法の一つとしてグレブナ基底 による消去が可能である. $$I = Id( u_0-{{\partial F}\over {\partial x_0}}, u_1-{{\partial F}\over {\partial x_1}}, u_2-{{\partial F}\over {\partial x_2}}, F)$$ とする時, $\{x_0, x_1, x_2\}$ $\succ$ $\{u_0, u_1, u_2\}$ なる任意の消 去順序により $I$ のグレブナ基底 $GB(I)$ を計算すれば, $$I \cap \Q[u_0,u_1,u_2] = Id(GB(I) \cap Q[u_0,u_1,u_2]).$$ 以下の例で, $V(g_i)$ は $V(f_i)$ の双対曲線である. \vskip\baselineskip $\left\{ \parbox[c]{6in}{ $f_1=x^5-x^3+y^2$\\ $g_1=108x^7-108x^5+1017y^2x^4-16y^4x^3-4250y^2x^2+1800y^4x-108y^6+3125y^2$ } \right.$ \vskip\baselineskip $\left\{ \parbox[c]{6in}{ $f_2=x^6+3y^2x^4+(3y^4-4y^2)x^2+y^6$\\ $g_2=-256x^6+(64y^4-192y^2+864)x^4+(-192y^4+1620y^2-729)x^2-256y^6+864y^4-729y^2$ } \right.$ \vskip\baselineskip $\left\{ \parbox[c]{6in}{ $f_3=2x^4-3yx^2+y^4-2y^3+y^2$\\ $g_3=-12x^6+(-y^2+178y-37)x^4+(12y^3-768y^2+2208y+4608)x^2-32y^4+1024y^3-7680y^2-8192y-2048$ } \right.$ \vskip\baselineskip \begin{figure}[hbtp] \begin{tabular}{cc} \begin{minipage}{.5\hsize} \begin{center} \epsfxsize=7cm \epsffile{ps/1.ps} \end{center} \caption{$f_1=0$} \label{f2} \end{minipage} & \begin{minipage}{.5\hsize} \begin{center} \epsfxsize=7cm \epsffile{ps/1d.ps} \end{center} \caption{$g_1=0$} \label{g2} \end{minipage} \end{tabular} \end{figure} \begin{figure}[hbtp] \begin{tabular}{cc} \begin{minipage}{.5\hsize} \begin{center} \epsfxsize=7cm \epsffile{ps/2.ps} \end{center} \caption{$f_2=0$} \label{f3} \end{minipage} & \begin{minipage}{.5\hsize} \begin{center} \epsfxsize=7cm \epsffile{ps/2d.ps} \end{center} \caption{$g_2=0$} \label{g3} \end{minipage} \end{tabular} \end{figure} \begin{figure}[hbtp] \begin{tabular}{cc} \begin{minipage}{.5\hsize} \begin{center} \epsfxsize=7cm \epsffile{ps/4.ps} \end{center} \caption{$f_3=0$} \label{f5} \end{minipage} & \begin{minipage}{.5\hsize} \begin{center} \epsfxsize=7cm \epsffile{ps/4d.ps} \end{center} \caption{$g_3=0$} \label{g5} \end{minipage} \end{tabular} \end{figure}