\chapter{$B%?%$%_%s%0%G!<%?$*$h$SNc(B}
\section{$B%?%$%_%s%0%G!<%?(B : $BJ}Dx<0(B}
\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{$B%?%$%_%s%0%G!<%?(B : change of ordering}
$B$3$3$G$O(B, $B$5$^$6$^$J(B change of ordering $B%"%k%4%j%:%`$N%?%$%_%s%0%G!<%?(B
$B$r<($9(B. $B7WB,$O(B, PC (FreeBSD, 300MHz Pentium II, 512MB of memory) $B$G9T$C$?(B.
$BC10L$OIC(B. garbage collection $B;~4V$O=|$$$F$"$k(B.
$BM=$a7W;;$7$F$"$k(B DRL \gr $B4pDl$+$i=PH/$7$F(B, LEX \gr $B4pDl7W;;$9$k(B.
$BMQ$$$k%"%k%4%j%:%`$O(B,
TL ({\it tl\_guess$()$}),
HTL ($B@F<!2=(B+{\it tl\_guess$()$}+$BHs@F2=(B),
LA ({\it candidate\_by\_linear\_algebra$()$}; 0 $B<!85%7%9%F%`$N$_(B)
$B$G$"$k(B.
$BI=(B \ref{mcotype} $B$O(B DRL $B$+$i(B LEX $B$X$NJQ49$K$+$+$k;~4V$r$7$a$9(B.
{\it DRL} $B$O(B, DRL $B$N7W;;;~4V$r<($9(B. $B%0%l%V%J4pDl%A%'%C%/$N8z2L$r(B
$B<($9$?$a$K(B, {\it tl\_check$()$} $B$N;~4V$b<($9(B.
\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}
$B@0?t78?tB?9`<0$KBP$7(B, $B$=$N(B {\bf maginitude} $B$r(B, $B78?t$N%S%C%HD9$NOB$GDj5A$9$k(B.
{\it TL} $B$H(B {\it HTL} $B$N:9$r8+$k$?$a$K(B,
$BI=(B \ref{magnitude} $B$G(B, $B7W;;ESCf$K$*$1$k:GBg(B magnitude $B$r<($9(B.
\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}
$BI=$h$jL@$i$+$K(B, {\it TL} $B$OHs@F<!B?9`<0$KBP$9$k%0%l%V%J4pDl7W;;$KIT8~$-(B
$B$G$"$k$3$H$,$o$+$k(B. $B$5$i$K(B, $BI=(B \ref{mcotype} $B$O(B {\it HTL} $B$KBP$9$k(B
{\it LA} $B$NM%0L@-$r<($7$F$$$k(B. $B$3$l$O(B, Buchberger $B%"%k%4%j%:%`$,(B
Euclid $B$N8_=|K!$KBP1~$7$F$$$F(B, $BCf4V78?tKDD%$G8zN($,:81&$5$l$k$N(B
$B$KBP$7(B, modular $B%"%k%4%j%:%`$N8zN($O7k2L$NBg$-$5$N$_$K0MB8$9$k(B
$B$3$H$K$h$k(B.
\section{$B%?%$%_%s%0%G!<%?(B : RUR}
RUR $B$N(B modular $B7W;;$N%?%$%_%s%0%G!<%?$r<($9(B. $B7W;;4D6-$OA0@a$HF1MM$G$"(B
$B$k(B. $B$3$3$G$O(B, $BM=$a(B modular $B7W;;$K$h$j(B separating element$B$r5a$a$F$"(B
$B$k(B. $B$3$l$i$rMQ$$$F(B, $B$=$l$>$l<!$N$h$&$JB?9`<0$rE:2C$7$?%$%G%"%k$KBP$7(B,
$w$ $B$K4X$9$k(B RUR $B7W;;$r9T$&(B. $BI=$G(B, Quick Test $B$O(B modular $B7W;;$G(B $w$
$B$,(B separating element $B$H$J$k$3$H$r%A%'%C%/$9$k;~4V(B, Normal Form $B$O(B,
$B@~7AJ}Dx<0$r@8@.$9$k$?$a$N(B, monomial $B$N@55,7A$N7W;;(B, Linear Equation $B$O(B,
$B@~7AJ}Dx<05a2r$N;~4V$G$"$k(B. $BI=(B \ref{maxblen} $B$G$O(B, LEX $B4pDl$H(B RUR $B$G(B
$B78?t$NBg$-$5$,$I$N$/$i$$0c$&$+$r<($7$F$$$k(B.
\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{$BF~NO%$%G%"%k$K4X$9$k%G!<%?(B}
\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{$B7W;;;~4V(B ($BIC(B)}
\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{$BNc(B : $B=`AGJ,2r(B}
$B<!$NNc$O(B, symplectic integrator $B$H8F$P$l$k0BDj$J@QJ,%9%-!<%`$N(B
$B?tCM7W;;K!$K4X$7$F8=$l$?J}Dx<07O$G$"$k(B \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
$B$3$l$r=`AGJ,2r$K$+$1$k$H(B, $B<!$NJ,2r$,F@$i$l$k(B.
\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{$BNc(B : $BAPBP6J@~$N7W;;(B}
$f(x_1,x_2) \in \Q[x_1,x_2]$ $B$H$7(B, $F$ $B$N(B total degree $B$r(B $d$ $B$H$9$l$P(B,
$F(x_0,x_1,x_2)=x_0^df(x_1/x_0,x_2/x_0)$
$B$O(B $d$ $B<!F1<!B?9`<0$G(B, $F$ $B$NDj5A$9$kBe?t6J@~$NAPBP6J@~$O(B,
$$\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.$$
$B$+$i(B $x_0, x_1, x_2$ $B$r>C5n$7$FF@$i$l$k(B. $B>C5nK!$N0l$D$H$7$F%0%l%V%J4pDl(B
$B$K$h$k>C5n$,2DG=$G$"$k(B.
$$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)$$
$B$H$9$k;~(B, $\{x_0, x_1, x_2\}$ $\succ$ $\{u_0, u_1, u_2\}$ $B$J$kG$0U$N>C(B
$B5n=g=x$K$h$j(B $I$ $B$N%0%l%V%J4pDl(B $GB(I)$ $B$r7W;;$9$l$P(B,
$$I \cap \Q[u_0,u_1,u_2] = Id(GB(I) \cap Q[u_0,u_1,u_2]).$$
$B0J2<$NNc$G(B, $V(g_i)$ $B$O(B $V(f_i)$ $B$NAPBP6J@~$G$"$k(B.
\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}
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to ex.tex CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM / doc / compalg