Annotation of OpenXM/doc/Papers/rims2003-noro-ohp.tex, Revision 1.1
1.1 ! noro 1: \documentclass{slides}
! 2: %\documentclass[pdf,distiller,slideColor,colorBG,azure]{prosper}
! 3: \usepackage{color}
! 4: \usepackage{rgb}
! 5: \usepackage{graphicx}
! 6: \usepackage{epsfig}
! 7: \newcommand{\qed}{$\Box$}
! 8: \newcommand{\mred}[1]{\smash{\mathop{\hbox{\rightarrowfill}}\limits_{\scriptstyle #1}}}
! 9: \newcommand{\tmred}[1]{\smash{\mathop{\hbox{\rightarrowfill}}\limits_{\scriptstyle #1}\limits^{\scriptstyle *}}}
! 10: \newtheorem{prop}{\redc $BL?Bj(B}
! 11: \def\gr{Gr\"obner basis }
! 12: \def\st{\, s.t. \,}
! 13: \def\ni{\noindent}
! 14: \def\init{{\rm in}}
! 15: \def\Q{{\bf Q}}
! 16: \def\Spoly{{\rm Spoly}}
! 17: \def\Span{{\rm Span}}
! 18: \def\Supp{{\rm Supp}}
! 19: \def\StdMono{{\rm StdMono}}
! 20: \def\Im{{\rm Im}}
! 21: \def\Ker{{\rm Ker}}
! 22: \def\NF{{\rm NF}}
! 23: \def\HT{{\rm HT}}
! 24: \def\LT{{\rm LT}}
! 25: \def\ini{{\rm in}}
! 26: \def\Id#1{\langle #1 \rangle}
! 27: \def\ve{\vfill\eject}
! 28: \textwidth 9.2in
! 29: \textheight 7.2in
! 30: \columnsep 0.33in
! 31: \topmargin -1in
! 32: \def\tc{\color{orange}}
! 33: \def\fbc{\bf\color{orange}}
! 34: \def\itc{\color{LimeGreen}}
! 35: %\def\itc{\color{DarkGreen}}
! 36: %\def\urlc{\bf\color{DarkGreen}}
! 37: \def\urlc{\bf\color{LimeGreen}}
! 38: \def\goldc{\color{goldenrod3}}
! 39: \def\redc{\color{orange}}
! 40: \def\vs{\vskip 1cm}
! 41: \def\vsh{\vskip 0.5cm}
! 42:
! 43: \title{\bf Risa/Asir $B>e$N?7%0%l%V%J!<4pDl7W;;%Q%C%1!<%8$K$D$$$F(B}
! 44:
! 45: %\slideCaption{Risa/Asir $B>e$N?7%0%l%V%J!<4pDl7W;;%Q%C%1!<%8$K$D$$$F(B}
! 46: \author{{\bf\Large $BLnO$(B $B@59T(B\\ $B?@8MBg3XM}3XIt?t3X2J(B}}
! 47: %\date{\bf\Large June 21, 2002}
! 48: %\date{\bf\Large Nov. 26, 2003}
! 49: \date{\bf\Large Dec. 18, 2003}
! 50: \begin{document}
! 51: \setlength{\parskip}{10pt}
! 52: \maketitle
! 53:
! 54: %\itc: item color
! 55: %\fbc: fbox color
! 56: %\urlc: URL color
! 57: %\goldc: bold color a
! 58: %\redc: bold color b
! 59:
! 60: \Large
! 61: \bf
! 62: \setlength{\parskip}{0pt}
! 63:
! 64: \begin{slide}{$B?7%Q%C%1!<%83+H/$N7P0^(B}
! 65:
! 66: $B%0%l%V%J!<4pDl7W;;$N8zN((B : $B%"%k%4%j%:%`$HF1;~$K(B, $B<BAu(B, $B%G!<%?9=B$$K$bBg$-$/(B
! 67: $B0MB8(B
! 68:
! 69: $BJ,;6I=8=B?9`<0(B {\tt DP} : $BC19`<0(B {\tt MP} $B$N(B linked list
! 70:
! 71: {\tt MP} : $B;X?t%Y%/%H%k(B {\tt DL} $B$r%]%$%s%?$G$b$D(B
! 72:
! 73: {\tt DL} : 32bit $B@0?tG[Ns(B (1 $BMWAG(B 32bit $B$G8GDj(B)
! 74:
! 75: \vskip 1cm
! 76: \begin{tabular}{cc}
! 77: \begin{minipage}{.5\hsize}
! 78: \baselineskip 0.5in
! 79: \begin{verbatim}
! 80: typedef struct oMP {
! 81: struct oDL *dl;
! 82: P c;
! 83: struct oMP *next;
! 84: } *MP;
! 85: \end{verbatim}
! 86: \end{minipage}
! 87: &
! 88: \begin{minipage}{.5\hsize}
! 89: \baselineskip 0.5in
! 90: \begin{verbatim}
! 91: typedef struct oDL {
! 92: int td;
! 93: int d[1];
! 94: } *DL;
! 95: \end{verbatim}
! 96: \end{minipage}
! 97: \end{tabular}
! 98:
! 99: \end{slide}
! 100:
! 101: \begin{slide}{Singular $B$H$NHf3S(B}
! 102:
! 103: Singular 2-0-4
! 104:
! 105: \begin{itemize}
! 106: \item $BM-8BBN>e$G9bB.(B
! 107:
! 108: $B4pK\E*%"%k%4%j%:%`$O(B Asir $B$HF1$8(B.
! 109:
! 110: $BO@J8$K$h$k$H(B, geobucket, $B2DJQD9;X?t%Y%/%H%k(B, $B8zN($h$$(B
! 111: $B%a%b%j4IM}(B etc. $B$r<BAu(B
! 112:
! 113: \item $BM-M}?tBN>e$G$b9bB.(B
! 114:
! 115: gmp $B$r@0?t1i;;$K;HMQ(B $\Rightarrow$ Asir $B$N(B bignum $B$h$j(B,
! 116: $BBg$-$$?t$G$OB.$$(B
! 117: \end{itemize}
! 118: \end{slide}
! 119:
! 120: \begin{slide}{$BIi$1$C$Q$J$7$O$/$d$7$$(B$\ldots$}
! 121:
! 122: $B$[$\40A4$K(B 0 $B$+$i=q$/(B
! 123:
! 124: ($B$G$-$l$P(B) $B%*%j%8%J%k$J9)IW$rF~$l$?$$(B
! 125:
! 126: $\Rightarrow$ ($B;n9T:x8m$r$5$s$6$s$d$C$?(B)$B7k2L$H$7$F(B,
! 127: geobucket, $B2DJQD9;X?t%Y%/%H%k$O<BAu(B
! 128:
! 129: $B>u67$K1~$8$?(B 2 $B<oN`$NB?9`<0I=8=(B ($B%j%9%H(B or $BG[Ns(B) $B$N@ZBX$((B
! 130:
! 131: $B@55,2=7W;;$K$*$1$k(B reducer $BC5$7$K%O%C%7%e$rMxMQ(B
! 132:
! 133: $B4X?t$N%$%s%i%$%s(B, unrolling $B$NB?MQ(B
! 134: \end{slide}
! 135:
! 136: \begin{slide}{$B8zN(2=$N9)IW(B --- geobucket}
! 137:
! 138: $BB?9`<0$r(B, $BG[Ns(B $g$$B$G;}$D(B
! 139:
! 140: $g[i]$ $B$K$O(B, $B9`?t$,(B, $B9b!9(B $b^i$ $B$NB?9`<0$,F~$k(B
! 141:
! 142: $BB?9`<0$O(B, $g[i]$ $BA4It$NOB(B
! 143:
! 144: $B9`?t$,(B $l$ ($b^(i-1) < l \le b^i$) $B$NB?9`<0(B $p$ $B$r(B $g$ $B$K(B
! 145: $BB-$9>l9g(B
! 146:
! 147: \begin{enumerate}
! 148: \item $p \leftarrow g[i]+p$
! 149: \item $B$b$7(B $p$ $B$ND9$5$,(B $b^i$ $B$h$jBg$J$i(B, $g[i]=0$, $i\leftarrow i+1$, 1. $B$X(B.
! 150: $B$5$b$J$/$P(B, $g[i] \leftarrow p$ $B$H$7$F=*N;(B
! 151: \end{enumerate}
! 152:
! 153: $B8z2L(B : $BB??t$NOB$N7W;;$K$*$$$F(B, $BHf3S1i;;$r8:$i$9(B
! 154:
! 155: \end{slide}
! 156:
! 157: \begin{slide}{$B8zN(2=$N9)IW(B --- $B2DJQD9;X?t%Y%/%H%k(B}
! 158:
! 159: $BNc$($P(B, $f(x_1,x_2,x_3,x_4)$ $B$N3FJQ?t$N;X?t$,(B 256 $B0J2<$J$i(B, $B;X?t%Y%/%H%k$O(B
! 160: 32 bit $B$K(B 4 $B$DF~$k(B.
! 161:
! 162: \begin{tabular}{|c|c|c|c|} \hline
! 163: $e_1$ & $e_2$ & $e_3$ & $e_4$ \\ \hline
! 164: \end{tabular}
! 165:
! 166: $B;X?t$NOB(B : 32bit $B@0?t$NOB(B
! 167:
! 168: $B;X?t$NHf3S(B : $B<-=q<0$J$i(B, 32bit $B@0?t$NBg$-$5$NHf3S(B
! 169: $B5U<-=q<0$J$i(B, $B$"$i$+$8$a5U=g$K5M$a$k(B.
! 170:
! 171: \end{slide}
! 172:
! 173: \begin{slide}{$B8zN(2=$N9)IW(B --- $BG[Ns$K$h$kB?9`<0$NJ];}(B}
! 174:
! 175: $B4pK\A`:n(B : $f-mg$ ($m$ $B$OC19`<0(B)
! 176:
! 177: $f-(mg)$ : geobucket
! 178:
! 179: $mg$ : $g$ $B$NI=8=$K$h$j(B, $B8zN($,0[$J$k(B
! 180:
! 181: $B;n9T:x8m$N7k2L(B : $g$ $B$,(B, $B%a%b%j>e$K0l<!85E*$KI=8=$5$l$F$$$k$H9bB.(B
! 182:
! 183: $g$ $B$OCf4V4pDl(B $\Rightarrow$ $BCf4V4pDl$N$_(B, $BG[NsI=8=(B
! 184:
! 185: $mg$ $B<+?H$O(B, $B2C;;$K$^$o$k$N$G(B, linked list $B$,$h$$(B
! 186:
! 187: \end{slide}
! 188:
! 189: \begin{slide}{$B8zN(2=$N9)IW(B --- $B4X?t$N%$%s%i%$%s2=(B, unrolling}
! 190:
! 191: $BBgJ*$rJRIU$1$k$H(B, $B>.J*$,L\$K$D$/(B
! 192:
! 193: $B>.J*(B : $B;X?t%Y%/%H%k$NA`:n(B ($BOB(B, $B:9(B, $BHf3S(B, divisibility)
! 194:
! 195: $B<B83$GHf3S$7$J$,$i(B, $B$7$?$[$&$,$h$$$b$N$r%$%s%i%$%s(B, unrolling
! 196: \end{slide}
! 197:
! 198: \begin{slide}{$B8zN(2=$N9)IW(B --- reducer $B%5!<%A$N%O%C%7%e2=(B}
! 199:
! 200: $B9`(B t $B$r3d$j@Z$kCf4V4pDl(B $g_t$ $B$N%5!<%A$bLdBj$H$J$C$?(B
! 201:
! 202: $g_t$ $B$O(B, $B8E$$4pDl$+$i=g$KC5$9(B $\Rightarrow$ $B$"$l$P0l0UE*(B
! 203:
! 204: $\Rightarrow$ $B%O%C%7%eI=(B $H$ $B$O(B, $t$ $B$N%O%C%7%eCM(B $h(t)$ $B$KBP$7(B,
! 205: $H[h(t)]$ $B$K(B $(t,g_t)$ $B$rEPO?$9$k(B.
! 206:
! 207: $t$ $B$,M?$($i$l$?$i(B, $H[h(t)]$ $B$rC5$7(B, $B$_$D$+$C$?$i(B $g_t$ $B$r;H$&(B.
! 208:
! 209: $B$J$1$l$P(B $g_t$ $B$rDL>o$NJ}K!$G$5$,$7(B, $B$"$l$P(B $H[h(t)]$ $B$K(B
! 210: $BEPO?(B
! 211: \end{slide}
! 212:
! 213: \begin{slide}{$B8zN(2=$N9)IW(B --- $B@F<!$N>l9g$N8zN(2=(B}
! 214:
! 215: \begin{itemize}
! 216: \item $B0lHL$N>l9g(B : $BESCf$G(B interreduction $B$7$J$$(B
! 217:
! 218: \item $B@F<!$N>l9g(B : $B$7$F$h$$(B
! 219:
! 220: $BF,9`$OJQ2=$7$J$$(B
! 221:
! 222: $BF@$i$l$?Cf4V4pDl$O<B$O4JLs%0%l%V%J!<4pDl$N$&$A(B, $B8=<!?t$^$G$N$9$Y$F(B
! 223:
! 224: $\Rightarrow$ 0 $B$K@55,2=$5$l$?(B S-poly $B$O(B, interreduction $B8e$b(B 0 $B$K9T$/(B
! 225: \end{itemize}
! 226: \end{slide}
! 227:
! 228: \begin{slide}{$B8zN(2=$N9)IW(B --- $B%a%b%j4IM}(B}
! 229:
! 230: $BHf3SE*>.$5$$%a%b%jNN0h$,7+$jJV$7I,MW$H$J$k(B
! 231:
! 232: $\Rightarrow$ $BKh2s(B {\tt GC\_malloc()} $B$O=E$9$.(B
! 233:
! 234: $\Rightarrow$ GC $B$+$i$b$i$C$?%a%b%j$r(B, $B<+A0$G(B
! 235: $B%U%j!<%j%9%H4IM}(B
! 236: \end{slide}
! 237:
! 238: \begin{slide}{$B3FIt$N>\:Y(B --- $B%I%i%$%P(B}
! 239:
! 240: \begin{itemize}
! 241: \item {\tt nd\_gr}
! 242:
! 243: $BM-8BBN(B, $BM-M}?tBN78?t$J$I(B, $B$9$Y$F$KBP1~$9$k(B.
! 244:
! 245: \item {\tt nd\_gr\_trace}
! 246:
! 247: $BM-M}?tBN@lMQ(B. trace $B%"%k%4%j%:%`$r<B9T$9$k(B.
! 248:
! 249: $B@F<!2=$rMxMQ$9$k$h$&;XDj$,2DG=(B
! 250:
! 251: \item {\tt nd\_f4}
! 252:
! 253: $BM-8BBN@lMQ(B $F_4$ $B<BAu(B. $B;~4V(B, $B6u4VAPJ}$K4X$9$k8zN(2=(B
! 254: $B$rL\;X$7$?<BAu(B
! 255:
! 256: \end{itemize}
! 257: \end{slide}
! 258:
! 259: \begin{slide}{$B3FIt$N>\:Y(B --- $B;X?t%Y%/%H%k$ND9$5JQ99(B}
! 260:
! 261: \begin{itemize}
! 262: \item $B$"$U$l(B
! 263:
! 264: $BB?9`<0(B $f$ $\Rightarrow$ $B:GBg;X?t%Y%/%H%k(B $M_f$ $B$rBP1~(B
! 265:
! 266: \item $x^E f$
! 267:
! 268: $E+M_f$ $B$,$"$U$l$r$*$3$9$+$I$&$+D4$Y$k(B
! 269:
! 270: \item $B%A%'%C%/$,I,MW$J>l=j(B
! 271:
! 272: S-poly $B7W;;(B, $B@55,2=$K$*$1$k(B, $BC19`<0(B $\times$ reducer $B$N7W;;(B
! 273: \end{itemize}
! 274:
! 275: \end{slide}
! 276:
! 277: \begin{slide}{$B3FIt$N>\:Y(B --- $B$=$NB>(B}
! 278:
! 279: \begin{itemize}
! 280: \item $BCf4V4pDl$r%G%#%9%/>e$KCV$-(B, demand loading
! 281:
! 282: $B4{B85!G=$HF1$8%9%$%C%A$r;H$&(B. ({\tt dp\_gr\_flags()}).
! 283:
! 284: \item content $B=|5n(B
! 285:
! 286: default $B$G9T$&(B. $BF,78?t$,(B 2 $BG\$N(B bit $BD9$K$J$C$?$i(B
! 287: content $B=|5n(B
! 288: \end{itemize}
! 289:
! 290: \end{slide}
! 291:
! 292: \begin{slide}{$B@-G=(B --- $BM-8BBN>e$G$N(B cyclic-$n$ }
! 293:
! 294: \vskip 1cm
! 295:
! 296: \begin{tabular}{c||c|c|c|c}
! 297: $n$ & {\tt nd\_gr} & Singular & {\tt nd\_f4} & {\tt dp\_gr\_mod\_main} \\ \hline
! 298: 7 & 5.1 & 5.0 & 1.8 & 17 \\
! 299: 8 & 124 & 135 & 34 & 564 \\
! 300: 9 & 27810 & 29725 & 3951 & --- \\
! 301: \end{tabular}
! 302: \end{slide}
! 303:
! 304: \begin{slide}{$B@-G=(B --- $BM-8BBN>e$G$N%Y%s%A%^!<%/(B }
! 305:
! 306: \vskip 1cm
! 307: \begin{tabular}{c||c|c|c}
! 308: & {\tt nd\_gr} & Singular & {\tt nd\_f4} \\ \hline
! 309: dl & 5.9 & 4.9 &4.0 \\
! 310: eco10 & 7.1 & 10 &3.1 \\
! 311: eco11 & 63 & 106 &23 \\
! 312: eco12 & 507 & 1012 &198 \\
! 313: extcyc6 & 11 & 9.4 &4.1 \\
! 314: extcyc7 & 1813 & 1283 &447 \\
! 315: f855 & 3.6 & 3.4 &2.5 \\
! 316: filter9 & 0.28 & 0.80 &3.2 \\
! 317: hairer2 & 5.9 & 3.8 &4.5 \\
! 318: hairer3 & 11 & 35 &*
! 319: \end{tabular}
! 320: \end{slide}
! 321:
! 322: \begin{slide}{$B@-G=(B --- $BM-8BBN>e$G$N%Y%s%A%^!<%/(B }
! 323:
! 324: \vskip 1cm
! 325: \begin{tabular}{c||c|c|c}
! 326: & {\tt nd\_gr} & Singular & {\tt nd\_f4} \\ \hline
! 327: hcyclic7 & 6.5 & 4.8 &3.1 \\
! 328: hcyclic8 & 213 & 163 &82 \\
! 329: hf744 & 1.1 & 1.1 &1.6 \\
! 330: hf855 & 25 & 25 &17 \\
! 331: ilias13 & 11 & 8.4 &6.0\\
! 332: ilias\_k\_2 & 3.1 & 2.7 &1.1\\
! 333: ilias\_k\_3 & 4.4 & 2.9 &1.2 \\
! 334: katsura10 & 285 & 218 &80 \\
! 335: katsura8 & 4.1 & 3.3 &1.3 \\
! 336: katsura9 & 35 & 29 &11 \\
! 337: \end{tabular}
! 338: \end{slide}
! 339:
! 340: \begin{slide}{$B@-G=(B --- $BM-8BBN>e$G$N%Y%s%A%^!<%/(B }
! 341:
! 342: \vskip 1cm
! 343: \begin{tabular}{c||c|c|c}
! 344: & {\tt nd\_gr} & Singular & {\tt nd\_f4} \\ \hline
! 345: noon7 & 4.4 & 1.8 &13 \\
! 346: noon8 & 35 & 18 &220 \\
! 347: pinchon1 & 3.6 & 1.0 &7.6 \\
! 348: rbpl & 1.0 & 0.89 &1.2 \\
! 349: redcyc7 & 3.5 & 3.3 &1.2 \\
! 350: redeco10 & 2.8 & 2.3 &1.3 \\
! 351: redeco11 & 24 & 18 &12 \\
! 352: redeco12 & 177 & 134 &74 \\
! 353: reimer6 & 11 & 32 &10 \\
! 354: reimer7 & 4000 & 4108 & 956 \\
! 355: virasoro & 1.8 & 1.4 & 0.65
! 356: \end{tabular}
! 357: \end{slide}
! 358:
! 359: \begin{slide}{$B:#8e$NM=Dj(B}
! 360:
! 361: \begin{itemize}
! 362: \item $BM-M}4X?tBN>e$N%0%l%V%J!<4pDl7W;;(B
! 363:
! 364: \item $BM-M}?tBN>e$N(B $F_4$ $B7W;;(B
! 365:
! 366: \item tangent cone $B%"%k%4%j%:%`(B, $BI8=`4pDl(B
! 367:
! 368: \end{itemize}
! 369: \end{slide}
! 370:
! 371: %\begin{slide}{}
! 372: %\end{slide}
! 373: \end{document}
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>