Return to rims2003-noro.tex CVS log

Up to [local] / OpenXM / doc / Papers

Annotation of OpenXM/doc/Papers/rims2003-noro.tex, Revision 1.4

1.1       noro        1: \documentclass[12pt]{jarticle}
1.2       noro        2: \topmargin -0.5in
                      3: \oddsidemargin -0in
                      4: \evensidemargin -0in
                      5: \textheight 9.5in
                      6: \textwidth 6in
1.1       noro        7: \IfFileExists{my.sty}{\usepackage{my}}{}
                      8: \IfFileExists{graphicx.sty}{\usepackage{graphicx}}{}
                      9: \IfFileExists{epsfig.sty}{\usepackage{epsfig}}{}
1.3       noro       10: \title{Risa/Asir $B$N?7%0%l%V%J!<4pDl7W;;%Q%C%1!<%8$K$D$$$F(B}
1.1       noro       11: \author{$BLnO$(B $B@59T(B \\ ($B?@8MBgM}(B)}
                     12: \date{}
                     13: \begin{document}
                     14: \maketitle
                     15: \def\gr{Gr\"obner $B4pDl(B}
                     16: \def\st{\, s.t. \,}
                     17: \def\noi{\noindent}
                     18: \def\ve{\vfill\eject}
                     19:
                     20: \section{$B3+H/$N7P0^(B}
                     21: Risa/Asir $B$K$*$$$F$O!"B?9`<0$O:F5"I=8=$^$?$OJ,;6I=8=$K$h$jJ];}$5$l$k!#(B
                     22: $B8e<T$O%0%l%V%J!<4pDl4XO"7W;;$K$*$1$k4pK\E*$J%G!<%?7A<0$G$"$j!"(B
                     23: $BC19`<0$rI=$99=B$BN(B {\tt oMP} $B$N(B linked list $B$G$"$k!#(B
                     24:
                     25: \vskip 5mm
                     26: \begin{tabular}{cc}
                     27: \begin{minipage}{.5\hsize}
                     28: \begin{verbatim}
                     29: typedef struct oMP {
                     30:     struct oDL *dl;
                     31:     P c;
                     32:     struct oMP *next;
                     33: } *MP;
                     34: \end{verbatim}
                     35: \end{minipage}
                     36: &
                     37: \begin{minipage}{.5\hsize}
                     38: \begin{verbatim}
                     39: typedef struct oDL {
                     40:     int td;
                     41:     int d[1];
                     42: } *DL;
                     43: \end{verbatim}
                     44: \end{minipage}
                     45: \end{tabular}
                     46: \vskip 5mm
                     47:
                     48: {\tt oMP} $B$N78?t$O(B {\tt c} $B$G$"$k!#(B
                     49: {\tt oDL} $B$N%a%s%P!<(B {\tt d}
                     50: $B$OC19`<0$N;X?t%Y%/%H%k$rI=$7$F$*$j!"<B:]$K$OJQ?t$N8D?tJ,$ND9$5$N(B
                     51: $BG[Ns$,%;%C%H$5$l$k!#:F5"I=8=$5$l$?B?9`<0$OJ,;6I=8=$KJQ49$5$l!"(B
                     52: Buchberger, $F_4$, $B$"$k$$$O(B change of ordering $B$J$I$N%"%k%4%j%:%`(B
                     53: $B%I%i%$%P$K$h$j=hM}$5$l$k!#(B
                     54:
                     55: Risa/Asir $B$N%0%l%V%J!<4pDl7W;;$K$*$$$F$O!"%Z%"$NA*Br@oN,!"@F<!2=!"%b%8%e(B
                     56: $B%i7W;;!"8zN(E*MFNL=|5n$J$I$5$^$6$^$J8zN(2=$N9)IW$r:N$jF~$l$k$3$H$K$h$j!"(B
                     57: $BM-M}?tBN>e$G$N7W;;8zN($K4X$7$F$O0lDj$NI>2A$rF@$F$-$?$,!"M-8BBN>e(B
                     58: $B$G$N7W;;$K$*$$$F$O!"(BSingular $B$N:G6a$NHG$HHf3S$9$k$HBg$-$/@-G=$,Nt$C$F$$$?!#(B
                     59: $B$^$?!"M-M}?tBN>e$K$*$$$F$b!"B?G\D91i;;$K(B {\tt gmp} $B$r;HMQ$7$F$$$k(B
                     60: Singular $B$J$I$N%7%9%F%`$G$O!"6aG/$H$_$K9bB.2=$7$?(B
                     61: {\tt gmp} $B$N@-G=$H!"(BRisa/Asir $B$G(B
1.2       noro       62: $B;HMQ$7$F$$$k<+<g3+H/$NB?G\D91i;;5!G=$H$N@-G=:9$K$h$j!"I,$:$7$b(B Risa/Asir $B$N(B
1.1       noro       63: $BM%0L@-$,<gD%$G$-$J$/$J$C$F$-$?!#(B
                     64: $B0lJ}$G!"(BPC $B$KEk:\$G$-$k%a%b%jNL$b?t(B GB $B$KC#$7!"(BCPU $B$b$I$s$I$s9bB.2=$7!"(B
                     65: $B%0%l%V%J!<4pDl7W;;$N1~MQHO0O$O$I$s$I$sBg$-$/$J$C$F$$$k!#$=$3$G!"(B
                     66: $B$3$l$^$G$N$5$^$6$^$J7P83$*$h$S!"<BAu$K4X$9$k:G6a$NCN8+$r$b$H$K!"(B
                     67: $B$G$-$k8B$j9bB.$JJ,;6I=8=B?9`<07W;;$*$h$S%0%l%V%J!<4pDl7W;;$r<B8=$9$k(B
1.2       noro       68: $B%Q%C%1!<%8(B {\bf nd} (New Distributed polynomial package) $B$r?75,$K=q$/$3$H$K$7$?!#(B
1.1       noro       69:
1.2       noro       70: \section{$B8zN(2=$N9)IW(B}
1.1       noro       71:
                     72: Buchberger $B%"%k%4%j%:%`$K4X$7$F$O!"(B
                     73: Gebauer-Moeller $B$N(B useless pair detection$B!"(Bsugar strategy $B$J$I$K(B
                     74: $B$h$j!"%"%k%4%j%:%`E*$K$O$"$kDxEY8G$^$C$?$,!":G6a$K$J$C$F$$$/$D$+(B
                     75: $B<BAu$K4X$9$kDs0F$,$J$5$l$?!#:#2s$N<BAu$K:N$jF~$l$?$b$N$K$D$$$F(B
1.2       noro       76: $B@bL@$9$k(B.
1.1       noro       77:
1.2       noro       78: \begin{enumerate}
1.1       noro       79: \item geobucket
                     80:
1.2       noro       81: $B$3$l$O!"B?9`<0$N2C;;$r8zN(2=$9$k$?$a$NJ}K!$G$"$j(B,
                     82: \cite{Geo} $B$GDs0F$5$l(B, Macaulay2, Singular $B$J$IB?$/$N%7%9%F%`$G(B
                     83: $B:NMQ$5$l(B, $B<B:]$K8z2L$,$"$k$3$H$,<B>Z$5$l$F$$$k(B.
1.1       noro       84: $B@55,2=7W;;$G$O(B, $B?tB?$/$NB?9`<0$N2C;;$,9T$o$l$k$,(B, $BHs>o$K(B
                     85: $B9`?t$NB?$$B?9`<0$K(B, $B9`?t$NHf3SE*>/$J$$B?9`<0$r7+$jJV$7B-$9$h$&$J>l9g(B,
                     86: $B9`$I$&$7$NHf3S1i;;$N%3%9%H$,BgJQBg$-$/$J$k(B. geobucket $B$H$O(B, $BB?9`<0$r(B
                     87: $BMWAG$H$9$kG[Ns(B $g$ $B$G$"$C$F(B, $BE,Ev$J@0?t(B $b$ ($BNc$($P(B 2) $B$KBP$7(B, $g[i]$
                     88: $B$NB?9`<0$,9b!9(B $b^i$ $B$N9`?t$r;}$D$h$&$J$b$N$G$"$k(B. $g$ $B$K(B, $B9`?t(B $l$
                     89: ($b^{i-1} < l \le b^i$) $B$NB?9`<0(B $p$ $B$rB-$9>l9g(B, $B$^$:(B $g[i]+p$ $B$r(B
                     90: $B7W;;$9$k(B. $B$3$l$N9`?t$,(B $b^i$ $B0J2<$J$i$=$N$^$^(B $g[i]$ $B$rCV$-49$((B,
                     91: $b^i$ $B$h$jBg$-$1$l$P(B $g[i+1]$ $B$K2C$($k(B, $B$H$$$&A`:n$r(B geobucket $B$N(B
                     92: $B>r7o$,K~$?$5$l$k$^$GB3$1$k(B. $B$3$l$K$h$j(B, $BOB$K8=$o$l$kB?9`<0$N9`$NAm?t$r(B
                     93: $N$ $B$H$9$k$H$-(B, $O(N\log N)$ $B$N%3%9%H$GB?9`<0$NOB$,7W;;$G$-$k(B.
                     94:
1.2       noro       95:
1.1       noro       96: \item $B2DJQD9;X?t%Y%/%H%k(B
                     97:
                     98: {\tt oDL} $B$N%a%s%P!<$G$O(B, $BC19`<0$NJQ?t$N3F;X?t$r(B 32 bit $B8GDj$GI=8=$7$F(B
1.4     ! noro       99: $B$$$?$,(B, $BB?$/$N>l9g$3$l$O2aJ,$G$"$k(B.
        !           100: $BI,MW:G>.8B$N(B bit $BD9$r;X?t$K3d$jEv$F$k$3$H$K$9$l$P(B, 32 bit $BCf$KJ#?t$N(B
        !           101: $B;X?t$rJ];}$G$-(B, $BHf3S(B, $BOB$J$I$r0lEY$KJ#?t8D<B9T$G$-$k(B. $B$^$?(B, $B;X?t$N(B
        !           102: $BJ];}$KI,MW$J%a%b%jNL$b8:$k(B. $B$3$&$9$k$H(B, $BOB$G$"$U$l$,@8$8$k>l9g$,$"$k$,(B,
        !           103: $B$3$N>l9g$K$O%5%$%:$rJQ99$7$F(B
        !           104: $BB?9`<0$r:n$j$J$*$9(B. $B$3$l$O(B \cite{Singular}
1.2       noro      105: $B$GDs0F$5$l$F$$$kJ}K!$G$"$k(B.
1.1       noro      106:
                    107: \item $BG[Ns$K$h$kB?9`<0$NJ];}(B
                    108:
                    109: Buchberger $B%"%k%4%j%:%`$K$*$1$k4pK\A`:n$O(B, $f-mg$ ($f$, $g$ $B$OB?9`<0(B,
                    110: $m$ $B$OC19`<0(B) $B$G$"$k(B. $B$3$l$r$5$i$K(B $mg$ $B$r:n$kA`:n$H(B, $BB?9`<0$NOB$r(B
                    111: $B:n$kA`:n$KJ,2r$7$F9M$($k(B. $B8e<T$O(B geobucket $B$K$h$j9bB.2=$,2DG=$G$"$k(B.
                    112: $BA0<T$K4X$7$F$O(B, $B$I$&$7$h$&$b$J$5$=$&$K$b;W$($k$,(B, $B$3$N1i;;$O(B, $g$ $B$N(B
                    113: $BI=8=J}K!$K$h$j7W;;8zN($,Bg$-$/0[$J$k(B. $B7kO@$r8@$($P(B,
                    114: $g$ $B$,(B $BC19`<0$N(B linked list $B$GI=8=$5$l$F$$$k$h$j(B, $BC19`<0(B ($B$3$l<+?H(B
                    115: $BG[Ns$G$"$k(B) $B$NG[Ns$H$7$FI=8=$5$l$F$$$k$[$&$,(B, $mg$ $B$N7W;;$,9bB.(B
                    116: $B$G$"$k(B. $g$ $B$O(B, $B$9$G$K7W;;$5$l$?Cf4V4pDl$J$N$G(B, $BG[Ns$H$7$FJ];}$9$k$3$H(B
                    117: $B$KLdBj$O$J$$(B. $B$?$@$7(B, $mg$ $B$O(B, $BB?9`<02C;;$K$^$o$k$N$G(B, linked list
                    118: $B$H$7$FI=<($5$l$F$$$J$$$HET9g$,0-$$(B. $B0J>e$K$h$j(B, $BB?9`<0$O>u67$K1~$8$F(B
                    119: linked list $B$HG[Ns$N(B 2 $B$D$NI=8=$r$H$k$3$H$K$J$C$?(B.
                    120:
                    121: \item $B4X?t$N%$%s%i%$%s2=(B, unrolling
                    122:
                    123: $B3+H/$,?J$`$K$D$$$F(B, $B%\%H%k%M%C%/$H$J$kItJ,$,<!Bh$KDc%l%Y%k$JItJ,$K(B
                    124: $B$J$C$F$$$C$?(B. $BFC$KLdBj$H$J$k$N$,(B, $BC19`<0$N;X?t%Y%/%H%k$KBP$9$kA`:n(B
                    125: $B$G$"$k(B. $B$9$J$o$A(B, $B;X?t%Y%/%H%k$NOB(B, $B:9(B, $BHf3S(B, divisibility $B$J$I$G$"$k(B.
                    126: $B$3$l$i$NItJ,$K4X$7$F$O(B, $B%$%s%i%$%s2=(B, $B$*$h$S(B unrolling $B$N@'Hs$r(B
                    127: $B8DJL$K<B83$K$h$jH=CG$7$?(B.
                    128:
                    129: \item reducer $B$N%5!<%A$N%O%C%7%e2=(B
                    130:
                    131: $B9`(B $t$ $B$r3d$j@Z$kF,9`$r$b$DCf4V4pDl(B (reducer) $g_i$ $B$N%5!<%A$b(B,
                    132: $BB>ItJ,$N8zN(2=$,?J$`$K$D$l(B, $B$=$N%3%9%H$,LdBj$K$J$C$F$-$?(B.
                    133: reducer $B$H$7$F$O(B, $B7P83>e(B,
                    134: $i$ $B$N>.$5$$=g$+$iC5$7$F(B, $t$ $B$r3d$j@Z$k:G=i$N$b$N$rMQ$$$k$N$,(B
                    135: $B$h$$$H$5$l$k(B ($BNc30$b$"$k$,(B). $B$3$N$?$a(B, $t$ $B$N(B reducer $B$O$"$l$P0l0U(B
                    136: $B$K$-$^$k(B.
                    137: $t$ $B$N(B reducer $g_t$ $B$,8+$D$+$C$?$i(B,
1.2       noro      138: $t$ $B$N%O%C%7%eCM(B $h_t$ $B$r7W;;$7$F(B, $B%O%C%7%e%F!<%V%k$N(B $h_t$ $B$N0LCV$K(B,
1.1       noro      139: $(t,g_t)$ $B$rEPO?$9$k(B. $t$ $B$N(B reducer $B$rC5$9:]$K$O(B, $h_t$ $B$N0LCV(B
                    140: $B$KEPO?$5$l$?%G!<%?$+$i(B, $t$ $B$N(B reducer $B$rC5$7$F(B, $B$b$7$"$l$P$=$l$r(B
                    141: $BMQ$$$l$P$h$$(B.
                    142:
1.2       noro      143: \item $B@F<!$N>l9g$N8zN(2=(B
                    144:
                    145: $B0lHL$K$O(B, $B?7$?$K@8@.$5$l$?Cf4V4pDl$G(B, $B4{B8$NCf4V4pDl$N@55,2=$O9T$o$J$$$,(B,
                    146: $BF~NO$,@F<!$N>l9g$K$O(B, $B$"$k(B(weight $B$D$-(B)$BA4<!?t$N=hM}$,=*$C$?;~E@$G(B
                    147: $B$=$N<!?t$NCf4V4pDl$I$&$7$G(B inter reduction $B$r9T$&(B. $B$3$N>l9g(B, $BF,9`$O(B
                    148: $BJQ2=$7$J$$$N$G(B, criteria $B$X$N1F6A$O$J$/(B, $B$^$?(B, $BDc$$A4<!?t$+$i=g$K(B
                    149: $BCf4V4pDl$r@8@.$7$F$$$l$P(B, $B4{$K(B, $B8=<!?t$^$G$N4JLs%0%l%V%J!<4pDl$N(B
                    150: $B$9$Y$F$NMWAG$,F@$i$l$F$$$k$N$G(B, $B$3$l$^$G$K(B 0 $B$K4JLs$5$l$?(B S-poly $B$O(B
                    151: $B$d$O$j?7$7$$4pDl$G$b(B 0 $B$K4JLs$5$l$k(B. $B$3$N=hM}$r9T$&$3$H$K$h$j(B,
                    152: $B0J9_$N7W;;$,4JLs4pDl$K$h$j@55,2=$5$l$k$3$H$K$J$j(B, $B@55,2=$,8zN(2=(B
                    153: $B$5$l$k$3$H$,4|BT$G$-$k(B.
                    154:
1.1       noro      155: \item $B%a%b%j4IM}(B
                    156:
                    157: $B7W;;ESCf(B, $B$5$^$6$^$JBg$-$5$NNN0h$,7+$jJV$7I,MW$H$J$k(B. $BFC$KB?$/I,MW$H$5(B
                    158: $B$l$k$$$/$D$+$N9=B$BNMQNN0h$O(B, garbage collector (GC) $B$GF@$?$b$N$r<+A0(B
                    159: $B$G%U%j!<%j%9%H4IM}$7$F$$$k(B. $B$3$l$O(B, GC $B$K$h$k(B allocation, collection
                    160: $B$,0lDj$N%3%9%H$rH<$&$?$a$G$"$k(B.  $B$3$N4IM}$O(B nd $B%Q%C%1!<%8Fb$GJD$8$F$*(B
                    161: $B$j(B, $B$+$D%U%j!<%j%9%H$N(B root $B$r(B 0 $B$K$7$F$*$1$P(B, $B$$$:$l(B GC $B$K$h$j2s<}$5(B
                    162: $B$l$k(B.
1.2       noro      163: \end{enumerate}
1.1       noro      164:
                    165: \section{$B4pK\%G!<%?9=B$(B}
                    166:
1.4     ! noro      167: %\vskip 5mm
        !           168: %\begin{tabular}{cc}
        !           169: %\begin{minipage}{.5\hsize}
        !           170: %\begin{verbatim}
        !           171: %typedef struct oND {
        !           172: %    struct oNM *body;
        !           173: %    int nv,len,sugar;
        !           174: %} *ND;
        !           175: %\end{verbatim}
        !           176: %\end{minipage}
        !           177: %&
        !           178: %\begin{minipage}{.5\hsize}
        !           179: %\begin{verbatim}
        !           180: %typedef struct oNDV {
        !           181: %    struct oNMV *body;
        !           182: %    int nv,len,sugar;
        !           183: %} *NDV;
        !           184: %\end{verbatim}
        !           185: %\end{minipage}
        !           186: %\end{tabular}
        !           187: %\vskip 5mm
1.1       noro      188:
1.4     ! noro      189: $BJ,;6I=8=B?9`<0$rJ];}$9$k$?$a$N9=B$BN$,Fs$DDj5A$5$l$F$$$k(B.
1.1       noro      190: {\tt ND} $B$O(B linked list $B7A<0$N(B, {\tt NDV} $B$OG[Ns7A<0$NB?9`<0(B
1.4     ! noro      191: $B$rI=$9(B. $BA0<T$O<!$G=R$Y$k(B {\tt oNM} $B$X$N(B, $B8e<T$O(B {\tt oNMV} $B$X$N(B
        !           192: $B%]%$%s%?$r;}$C$F$$$k(B.
1.1       noro      193:
                    194: \vskip 5mm
                    195: \begin{tabular}{cc}
                    196: \begin{minipage}{.5\hsize}
                    197: \begin{verbatim}
                    198: typedef struct oNM {
                    199:     struct oNM *next;
                    200:     union oNDC c;
                    201:     UINT dl[1];
                    202: } *NM;
                    203: \end{verbatim}
                    204: \end{minipage}
                    205: &
                    206: \begin{minipage}{.5\hsize}
                    207: \begin{verbatim}
                    208: typedef struct oNMV {
                    209:     union oNDC c;
                    210:     UINT dl[1];
                    211: } *NMV;
                    212: \end{verbatim}
                    213: \end{minipage}
                    214: \end{tabular}
                    215: \vskip 5mm
                    216:
                    217: $B$3$l$i$O(B, $BC19`<0$rI=$9$?$a$N9=B$BN$G$"$k(B.  {\tt dl} $B$OC19`<0$N;X?t%Y%/(B
1.2       noro      218: $B%H%k$rI=$7$F$*$j!"<B:]$K$O(B, $B9=B$BN:n@.;~E@$G$N;X?t$N(Bbit $BD9$HJQ?t$N(B
                    219: $B8D?t$K1~$8$?D9$5$NG[Ns$NBg$-$5J,$NNN0h$,3NJ]$5$l$k(B.
1.1       noro      220: {\tt NM} $B$O(B linked list $B7A<0$N(B, {\tt NMV} $B$OG[Ns7A<0$NB?9`<0$K$*$1$k(B
1.2       noro      221: $BC19`<0$rI=$9(B. {\tt NDV} $B$O(B, {\tt oNMV} $B$9$J$o$A9=B$BN$=$N$b$N$N(B
                    222: $BG[Ns$X$N%]%$%s%?$r;}$D(B.
                    223:
                    224: \vskip 5mm
                    225: \begin{tabular}{cc}
                    226: \begin{minipage}{.5\hsize}
1.1       noro      227: \begin{verbatim}
                    228: typedef union oNDC {
                    229:     int m;
                    230:     Q z;
                    231:     P p;
                    232: } *NDC;
                    233: \end{verbatim}
1.2       noro      234: \end{minipage}
                    235: &
1.1       noro      236: \begin{minipage}{.5\hsize}
                    237: \begin{verbatim}
                    238: typedef struct oRHist {
                    239:     struct oRHist *next;
                    240:     int index;
                    241:     int sugar;
                    242:     UINT dl[1];
                    243: } *RHist;
                    244: \end{verbatim}
                    245: \end{minipage}
                    246: \end{tabular}
1.2       noro      247: \vskip 5mm
1.1       noro      248:
1.2       noro      249: {\tt NDC} $B$O78?t$rJ];}$9$k$?$a$NHFMQ$N6&MQBN$G$"$k(B.
                    250: {\tt m} $B$O(B, $B0L?t$,(B 1 $B%o!<%I$G<}$^$kM-8BBN$N85$rJ];}$9$k$?$a$N(B
                    251: $B%a%s%P!<$G$"$k(B.
1.1       noro      252: {\tt RHist} $B$O(B reducer $B$NMzNr$r%O%C%7%e%F!<%V%k$KEPO?$9$k$?$a$N9=B$BN$G$"$k(B.
1.2       noro      253: $B3F%(%s%H%j$O(B, {\tt RHist} $B$N%j%9%H$H$7$FEPO?$5$l$k(B.
1.1       noro      254: \section{$B3FIt$N>\:Y(B}
                    255:
                    256: \subsection{$B%I%i%$%P(B}
                    257:
                    258: Buchberger $B%"%k%4%j%:%`$N%I%i%$%P$O(B, {\tt nd\_gb} $B$H(B {\tt nd\_gb\_trace}
                    259: $B$NFs$D$,$"$k(B. {\tt nd\_gb} $B$O(B, $BG$0U$N78?tBN>e$G(B, sugar $B%9%H%i%F%8!<$D$-$N(B
                    260: Buchberger $B%"%k%4%j%:%`$r<B9T$9$k$?$a$N$b$N$G$"$k(B.
                    261: $B$3$3$G$O(B,
                    262:
                    263: \begin{enumerate}
                    264: \item S-pair $B%j%9%H$N%a%s%F%J%s%9(B
                    265: \item S-pair $B$N<h$j=P$7(B, $B@55,2=7W;;$N8F$S=P$7(B
                    266: \item $B@55,7A$N(B, content $B=|5n(B, {\tt NDV} $B$X$NJQ49(B
                    267: \item $B;X?t$K$"$U$l$,=P$?>l9g$N(B, $BCf4V4pDl$N:n$j$J$*$7(B
                    268: \end{enumerate}
                    269:
                    270: $B$J$I$,9T$o$l$k(B. {\tt nd\_gb\_trace} $B$O(B, $BM-M}?tBN(B, $BM-M}4X?tBN>e$N%0%l%V%J!<(B
                    271: $B4pDl7W;;$r(B trace $B%"%k%4%j%:%`$K$h$j9T$&$?$a$N$b$N$G$"$j(B, $B>e5-$N;E;v$K(B
                    272: $B2C$((B, $B7k2L$r%A%'%C%/$9$k4X?t$N8F$S=P$7(B, homogenization, dehomogenization
                    273: $B$b9T$o$l$k(B.
                    274:
                    275: $B$5$i$K(B, $B8=>u$G$OM-8BBN>e$N$_$G$"$k$,(B, $F_4$ $B%I%i%$%P(B {\tt nd\_f4} $B$b(B
                    276: $B<BAu$7$?(B. S-pair, $BCf4V4pDl$N07$$$K4X$7$F$O(B {\tt nd\_gb} $B$HF1MM$G$"$k(B.
                    277: symbolic preprocessing $B$O(B, $B@lMQ$N(B geobucket $B$,<BAu$5$l$F$$$k(B.
                    278: $F_4$ $B$N3K?4$G$"$k(B, $BJ#?t$N(B S-pair $B$+$i(B, reducer $B$r$^$H$a$F(B
                    279: $B9TNs$H$7$FA]$-=P$9:n6H$r9T$&$^$($K(B, $B3F(B reducer $B$K$h$j(B S-poly $B$r(B
                    280: $B@55,2=$7$F$$$k(B. $B$3$NA`:n$r9T$&$?$a$K(B, $B3F(B reducer $B$r(B, $B05=L%Y%/%H%k(B
                    281: $B7A<0$KJQ49$7$F$*$-(B, $B@55,2=$5$l$kB&$N(B S-poly $B$OHs05=L$N%Y%/%H%k(B
                    282: $B7A<0$H$7$F@55,2=$r9T$&(B. $B:G8e$K(B, $B;D$C$?ItJ,$r=8$a$F9TNs$H$7(B,
                    283: $BA]$-=P$7$r9T$C$F$$$k(B. $B$3$l$i$K$h$j(B, $B$G$-$k8B$j;HMQ%a%b%jNL$r2!$($F(B
                    284: $B$$$k(B.
                    285:
                    286: \subsection{$B;X?t%Y%/%H%k$NJQ99(B}
                    287:
                    288: $B;X?t%Y%/%H%k$NJQ99$O(B, $B;X?t$NOB$G$"$U$l$,@8$8$?$H$-$KI,MW$H$J$k(B.
                    289: $B$3$l$,5/$3$jF@$k$N$O(B, S-poly $B$N7W;;$H(B, $B@55,7A$N7W;;$K$*$1$k(B,
                    290: $BC19`<0$HB?9`<0$N@Q$N7W;;$K$*$$$F$G$"$k(B. $B$3$NCf$G$N(B, $BC19`<0(B
                    291: $B$I$&$7$N@Q$N7W;;$N$?$S$K%A%'%C%/$9$k$N$OHs8zN(E*$J$N$G(B,
                    292: $B3FCf4V4pDl$KBP$7(B, $B3FJQ?t$KBP$9$k;X?t$N:GBgCM$r5-O?$7$F$*$-(B,
                    293: $B$=$N%Y%/%H%k$H$NOB$,$"$U$l$r5/$3$9>l9g$K:n$j$J$*$7$r$7$F$$$k(B.
                    294:
1.4     ! noro      295: \subsection{$B$=$NB>(B}
1.1       noro      296:
                    297: {\tt dp} $B7O$GDs6!$5$l$F$$$k$N$HF1MM$K(B,
                    298: nd $B$K$*$$$F$b(B, $BCf4V4pDl$r%G%#%9%/>e$N;XDj$5$l$?%G%#%l%/%H%j$K(B
                    299: $BCV$/$3$H$,$G$-$k(B. $B;XDjJ}K!$O(B {\tt dp} $B7O$HF1MM(B {\tt dp\_gr\_flags()}
                    300: $B$G;XDj$9$k(B. $B%U%!%$%k$O(B {\tt dp} $B7O$HF1MM$N7A<0$J$N$G(B, {\tt bload()}
1.4     ! noro      301: $B$GFI$`$3$H$,$G$-$k(B. $B$^$?(B, $BM-M}?tBN>e$N>l9g(B,
1.1       noro      302: $B@55,2=7W;;ESCf$G$N(B content $B=|5n$O(B, $B>o$K9T$o$l$k(B. $B8=>u$G$O(B
                    303: $BF,78?t$,(B 2 $BG\(B ($B8GDj(B) $B$K$J$C$?$H$-$K=|5n$,9T$o$l$k!#(B
                    304:
                    305: \section{$B@-G=(B}
                    306:
                    307: $B0lHL$K(B, $BM-8BBN>e$N7W;;$N>l9g(B, {\tt nd\_gr} $B$O(B {\tt dp\_gr\_mod\_main}
1.2       noro      308: $B$h$j?tG\9bB.$G$"$k(B. $B$^$?(B, $BLdBj$K$b$h$k$,(B, {\tt nd\_f4} $B$O(B
1.1       noro      309: {\tt nd\_gr} $B$N?tG\DxEY9bB.$J>l9g$,$"$k(B. $B$*$J$8$_$N(B cyclic-$n$ $B$G(B
                    310: $BHf3S$9$k$HI=(B \ref{tab:cyclic}$B$N$h$&$J7k2L$rF@$k(B.
                    311:
                    312: \begin{table}[hbtp]
                    313: \begin{center}
1.2       noro      314: \begin{tabular}{c||c|c|c|c}
                    315:  $n$        & {\tt nd\_gr} & Singular & {\tt nd\_f4} & {\tt dp\_gr\_mod\_main} \\ \hline
                    316:   7         &   5.1        &  5.0         & 1.8      & 17                      \\
                    317:   8         &   124        &  135         & 34       & 564                     \\
                    318:   9         &   27810      &  29725       & 3951     &    ---                  \\
1.1       noro      319: \end{tabular}
                    320: \end{center}
1.2       noro      321: \caption{$GF(31991)$ $B>e$G$N(B DRL $B=g=x%0%l%V%J!<4pDl7W;;(B (cyclic-$n$)}
1.1       noro      322: \label{tab:cyclic}
                    323: \end{table}
                    324: $B$3$N$h$&$K(B, $B>/$J$/$H$b(B cyclic-$n$ $B$G$O(B, nd $B$N<BAu$N8z2L$,==J,$K8=$o$l$F$$$k(B.
1.2       noro      325: $BI=(B \ref{tab:janet} $B$O(B, $B<o!9$N%Y%s%A%^!<%/LdBj(B \cite{janet} $B$N7W;;;~4V$r<($9(B.
                    326: \begin{table}[hbtp]
                    327: \begin{center}
                    328: \begin{tabular}{cc}
                    329: \begin{minipage}{.5\hsize}
                    330: \begin{tabular}{c||c|c|c}
                    331:        & {\tt nd\_gr} & Singular & {\tt nd\_f4} \\ \hline
                    332: dl & 5.9 & 4.9 &4.0 \\
                    333: eco10 & 7.1 & 10 &3.1 \\
                    334: eco11 & 63 & 106 &23 \\
                    335: eco12 & 507 & 1012 &198 \\
                    336: extcyc6 & 11 & 9.4 &4.1 \\
                    337: extcyc7 & 1813 & 1283 &447 \\
                    338: f855 & 3.6 & 3.4 &2.5 \\
                    339: filter9 & 0.28 & 0.80 &3.2 \\
                    340: hairer2 & 5.9 & 3.8 &4.5 \\
                    341: hairer3 & 11 & 35 &* \\
                    342: hcyclic7 & 6.5 & 4.8 &3.1 \\
                    343: hcyclic8 & 213 & 163 &82 \\
                    344: hf744 & 1.1 & 1.1 &1.6 \\
                    345: hf855 & 25 & 25 &17 \\
                    346: ilias13 & 11 & 8.4 &6.0\\
                    347: ilias\_k\_2 & 3.1 & 2.7 &1.1
                    348: \end{tabular}
                    349: \end{minipage}
                    350: &
                    351: \begin{minipage}{.5\hsize}
                    352: \begin{tabular}{c||c|c|c}
                    353:        & {\tt nd\_gr} & Singular & {\tt nd\_f4} \\ \hline
                    354: ilias\_k\_3 & 4.4 & 2.9 &1.2 \\
                    355: katsura10 & 285 & 218 &80 \\
                    356: katsura8 & 4.1 & 3.3 &1.3 \\
                    357: katsura9 & 35 & 29 &11 \\
                    358: noon7 & 4.4 & 1.8 &13 \\
                    359: noon8 & 35 & 18 &220 \\
                    360: pinchon1 & 3.6 & 1.0 &7.6 \\
                    361: rbpl & 1.0 & 0.89 &1.2 \\
                    362: redcyc7 & 3.5 & 3.3 &1.2 \\
                    363: redeco10 & 2.8 & 2.3 &1.3 \\
                    364: redeco11 & 24 & 18 &12 \\
                    365: redeco12 & 177 & 134 &74 \\
                    366: reimer6 & 11 & 32 &10 \\
                    367: reimer7 & 4000 & 4108 & 956 \\
                    368: virasoro & 1.8 & 1.4 & 0.65
                    369: \end{tabular}
                    370: \end{minipage}
                    371: \end{tabular}
                    372:
                    373: \end{center}
                    374: \caption{$GF(31991)$ $B>e$G$N(B DRL $B=g=x%0%l%V%J!<4pDl7W;;(B}
                    375: \label{tab:janet}
                    376: \end{table}
1.1       noro      377:
                    378: $BM-M}?tBN>e$N7W;;$N>l9g(B, $BB?9`<0$d(B, $B;X?t%Y%/%H%k$NI=8=J}K!0J30$K(B, $BESCf$"$i$o$l$k(B
                    379: $B78?t$NKDD%$NJ}$,(B, $B7W;;;~4V$KBg$-$/1F6A$rM?$($k>l9g$,B?$$(B. $B$3$NE@$G$O(B
                    380: {\tt nd\_gr\_trace} $B$H(B {\tt dp\_gr\_main} $B$H$G$OBg:9$J$$$N$G3d0&$9$k$,(B,
1.2       noro      381: $B$h$j0-$/$J$k$3$H$O$J$$(B. $BFC$K(B, weight $B$rE,@Z$K@_Dj$9$k$3$H$K$h$j(B \cite{Kimura},
                    382: $B78?tKDD%$K4X$7$F$b$h$j5sF0$N$h$$7W;;$,2DG=$H$J$k$3$H$KCm0U$7$F$*$/(B.
1.1       noro      383:
                    384: \section{$B:#8e$NM=Dj(B}
                    385:
                    386: {\tt dp} $B7O$K$"$C$F(B nd $B$K$J$$5!G=$H$7$F(B, $BM-M}4X?tBN78?t$N%0%l%V%J!<4pDl(B
                    387: $B7W;;$H(B, $BM-M}?tBN>e$N(B $F_4$ $B7W;;$,$"$k(B. $B$J$k$Y$/Aa$$$&$A$K$3$l$i$r<BAu(B
1.2       noro      388: $B$7$?$$$H9M$($F$$$k(B. $B$^$?(B,
                    389: tangent cone $B%"%k%4%j%:%`$rMQ$$$?(B local ring $B$G$NI8=`4pDl(B
                    390: $B7W;;$b(B, reducer $B$rC5$94X?t$r?7$?$KMQ0U$9$k$3$H$GBP1~2DG=$H9M$($F$$$k(B.
                    391:
                    392: \begin{thebibliography}{99}
                    393: \bibitem{Geo}
                    394: Yan, T., The Geobucket Data Structure for Polynomials.
                    395: Journal of Symbolic Computation, {\bf 25}, 3 (1998), 285-293.
                    396: \bibitem{Singular}
                    397: Sch\"onemann, H., Singular in a Framework for Polynomial Computations.
                    398: Joswig, M. and Takayama, N. (eds.), Algebra, Geometry, and Software Systems,
                    399: Springer (2003), 163-176.
                    400: \bibitem{janet}
                    401: {\tt http://invo.jinr.ru/}. $B$^$?(B {\tt http://www.symbolicdata.org}
                    402: $B$K$O$5$i$KB?$/$N%Y%s%A%^!<%/LdBj$,$*$$$F$"$k(B.
                    403: \bibitem{Kimura}
                    404: $BLZB<(B, $BLnO$(B, $B%0%l%V%J!<4pDl7W;;$N$?$a$N(B weight $B@8@.%"%k%4%j%:%`(B.
                    405: $BK\8&5f=82q$K$*$1$kH/I=(B (2003).
                    406: \end{thebibliography}
1.1       noro      407: \end{document}