Annotation of OpenXM/doc/Papers/rims2003-noro-ohp.tex, Revision 1.2
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}}
1.2 ! noro 34: %\def\itc{\color{LimeGreen}}
! 35: \def\itc{\color{DarkGreen}}
1.1 noro 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}
1.2 ! noro 42: \def\ns{\itc\LARGE}
! 43: \title{\tc\bf\ns Risa/Asir $B>e$N?7%0%l%V%J!<4pDl7W;;%Q%C%1!<%8$K$D$$$F(B}
1.1 noro 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}
1.2 ! noro 51: \setlength{\parskip}{20pt}
1.1 noro 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:
1.2 ! noro 64: \begin{slide}{\ns $B?7%Q%C%1!<%83+H/$N7P0^(B}
1.1 noro 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:
1.2 ! noro 73: {\tt DL} : $BA4<!?t$*$h$S(B 32bit $B@0?tG[Ns(B (1 $BMWAG(B 32bit $B$G8GDj(B)
1.1 noro 74:
1.2 ! noro 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}
1.1 noro 98:
99: \end{slide}
100:
1.2 ! noro 101: \begin{slide}{\ns Singular $B$H$NHf3S(B}
1.1 noro 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:
1.2 ! noro 120: \begin{slide}{\ns $BIi$1$C$Q$J$7$O$/$d$7$$(B$\ldots$}
! 121:
! 122: ($B$"$k$$$O(B, $B!VIwI>!W$K<BBV$r9g$o$;$k(B)
1.1 noro 123:
124: $B$[$\40A4$K(B 0 $B$+$i=q$/(B
125:
126: ($B$G$-$l$P(B) $B%*%j%8%J%k$J9)IW$rF~$l$?$$(B
127:
128: $\Rightarrow$ ($B;n9T:x8m$r$5$s$6$s$d$C$?(B)$B7k2L$H$7$F(B,
129: geobucket, $B2DJQD9;X?t%Y%/%H%k$O<BAu(B
130:
131: $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
132:
133: $B@55,2=7W;;$K$*$1$k(B reducer $BC5$7$K%O%C%7%e$rMxMQ(B
134:
135: $B4X?t$N%$%s%i%$%s(B, unrolling $B$NB?MQ(B
136: \end{slide}
137:
1.2 ! noro 138: \begin{slide}{\ns $B8zN(2=$N9)IW(B --- geobucket}
1.1 noro 139:
140: $BB?9`<0$r(B, $BG[Ns(B $g$$B$G;}$D(B
141:
142: $g[i]$ $B$K$O(B, $B9`?t$,(B, $B9b!9(B $b^i$ $B$NB?9`<0$,F~$k(B
143:
144: $BB?9`<0$O(B, $g[i]$ $BA4It$NOB(B
145:
1.2 ! noro 146: $B9`?t$,(B $l$ ($b^{(i-1)} < l \le b^i$) $B$NB?9`<0(B $p$ $B$r(B $g$ $B$K(B
1.1 noro 147: $BB-$9>l9g(B
148:
149: \begin{enumerate}
150: \item $p \leftarrow g[i]+p$
151: \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.
152: $B$5$b$J$/$P(B, $g[i] \leftarrow p$ $B$H$7$F=*N;(B
153: \end{enumerate}
154:
155: $B8z2L(B : $BB??t$NOB$N7W;;$K$*$$$F(B, $BHf3S1i;;$r8:$i$9(B
156:
157: \end{slide}
158:
1.2 ! noro 159: \begin{slide}{\ns $B8zN(2=$N9)IW(B --- $B2DJQD9;X?t%Y%/%H%k(B}
1.1 noro 160:
161: $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
162: 32 bit $B$K(B 4 $B$DF~$k(B.
163:
164: \begin{tabular}{|c|c|c|c|} \hline
165: $e_1$ & $e_2$ & $e_3$ & $e_4$ \\ \hline
166: \end{tabular}
167:
168: $B;X?t$NOB(B : 32bit $B@0?t$NOB(B
169:
170: $B;X?t$NHf3S(B : $B<-=q<0$J$i(B, 32bit $B@0?t$NBg$-$5$NHf3S(B
1.2 ! noro 171:
1.1 noro 172: $B5U<-=q<0$J$i(B, $B$"$i$+$8$a5U=g$K5M$a$k(B.
173:
174: \end{slide}
175:
1.2 ! noro 176: \begin{slide}{\ns $B8zN(2=$N9)IW(B --- $BG[Ns$K$h$kB?9`<0$NJ];}(B}
1.1 noro 177:
178: $B4pK\A`:n(B : $f-mg$ ($m$ $B$OC19`<0(B)
179:
180: $f-(mg)$ : geobucket
181:
182: $mg$ : $g$ $B$NI=8=$K$h$j(B, $B8zN($,0[$J$k(B
183:
184: $B;n9T:x8m$N7k2L(B : $g$ $B$,(B, $B%a%b%j>e$K0l<!85E*$KI=8=$5$l$F$$$k$H9bB.(B
185:
186: $g$ $B$OCf4V4pDl(B $\Rightarrow$ $BCf4V4pDl$N$_(B, $BG[NsI=8=(B
187:
188: $mg$ $B<+?H$O(B, $B2C;;$K$^$o$k$N$G(B, linked list $B$,$h$$(B
189:
190: \end{slide}
191:
1.2 ! noro 192: \begin{slide}{\ns $B8zN(2=$N9)IW(B --- $B4X?t$N%$%s%i%$%s2=(B, unrolling}
1.1 noro 193:
194: $BBgJ*$rJRIU$1$k$H(B, $B>.J*$,L\$K$D$/(B
195:
196: $B>.J*(B : $B;X?t%Y%/%H%k$NA`:n(B ($BOB(B, $B:9(B, $BHf3S(B, divisibility)
197:
198: $B<B83$GHf3S$7$J$,$i(B, $B$7$?$[$&$,$h$$$b$N$r%$%s%i%$%s(B, unrolling
199: \end{slide}
200:
1.2 ! noro 201: \begin{slide}{\ns $B8zN(2=$N9)IW(B --- reducer $B%5!<%A$N%O%C%7%e2=(B}
1.1 noro 202:
203: $B9`(B t $B$r3d$j@Z$kCf4V4pDl(B $g_t$ $B$N%5!<%A$bLdBj$H$J$C$?(B
204:
205: $g_t$ $B$O(B, $B8E$$4pDl$+$i=g$KC5$9(B $\Rightarrow$ $B$"$l$P0l0UE*(B
206:
207: $\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,
208: $H[h(t)]$ $B$K(B $(t,g_t)$ $B$rEPO?$9$k(B.
209:
210: $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.
211:
212: $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
213: $BEPO?(B
214: \end{slide}
215:
1.2 ! noro 216: \begin{slide}{\ns $B8zN(2=$N9)IW(B --- $B@F<!$N>l9g$N8zN(2=(B}
1.1 noro 217:
218: \begin{itemize}
219: \item $B0lHL$N>l9g(B : $BESCf$G(B interreduction $B$7$J$$(B
220:
221: \item $B@F<!$N>l9g(B : $B$7$F$h$$(B
222:
223: $BF,9`$OJQ2=$7$J$$(B
224:
225: $BF@$i$l$?Cf4V4pDl$O<B$O4JLs%0%l%V%J!<4pDl$N$&$A(B, $B8=<!?t$^$G$N$9$Y$F(B
226:
227: $\Rightarrow$ 0 $B$K@55,2=$5$l$?(B S-poly $B$O(B, interreduction $B8e$b(B 0 $B$K9T$/(B
228: \end{itemize}
229: \end{slide}
230:
1.2 ! noro 231: \begin{slide}{\ns $B8zN(2=$N9)IW(B --- $B%a%b%j4IM}(B}
1.1 noro 232:
233: $BHf3SE*>.$5$$%a%b%jNN0h$,7+$jJV$7I,MW$H$J$k(B
234:
235: $\Rightarrow$ $BKh2s(B {\tt GC\_malloc()} $B$O=E$9$.(B
236:
237: $\Rightarrow$ GC $B$+$i$b$i$C$?%a%b%j$r(B, $B<+A0$G(B
238: $B%U%j!<%j%9%H4IM}(B
239: \end{slide}
240:
1.2 ! noro 241: \begin{slide}{\ns $B3FIt$N>\:Y(B --- $B%I%i%$%P(B}
1.1 noro 242:
243: \begin{itemize}
244: \item {\tt nd\_gr}
245:
246: $BM-8BBN(B, $BM-M}?tBN78?t$J$I(B, $B$9$Y$F$KBP1~$9$k(B.
247:
248: \item {\tt nd\_gr\_trace}
249:
250: $BM-M}?tBN@lMQ(B. trace $B%"%k%4%j%:%`$r<B9T$9$k(B.
251:
252: $B@F<!2=$rMxMQ$9$k$h$&;XDj$,2DG=(B
253:
254: \item {\tt nd\_f4}
255:
256: $BM-8BBN@lMQ(B $F_4$ $B<BAu(B. $B;~4V(B, $B6u4VAPJ}$K4X$9$k8zN(2=(B
257: $B$rL\;X$7$?<BAu(B
258:
259: \end{itemize}
260: \end{slide}
261:
1.2 ! noro 262: \begin{slide}{\ns $B3FIt$N>\:Y(B --- $B;X?t%Y%/%H%k$ND9$5JQ99(B}
1.1 noro 263:
264: \begin{itemize}
265: \item $B$"$U$l(B
266:
267: $BB?9`<0(B $f$ $\Rightarrow$ $B:GBg;X?t%Y%/%H%k(B $M_f$ $B$rBP1~(B
268:
269: \item $x^E f$
270:
271: $E+M_f$ $B$,$"$U$l$r$*$3$9$+$I$&$+D4$Y$k(B
272:
273: \item $B%A%'%C%/$,I,MW$J>l=j(B
274:
275: S-poly $B7W;;(B, $B@55,2=$K$*$1$k(B, $BC19`<0(B $\times$ reducer $B$N7W;;(B
276: \end{itemize}
277:
278: \end{slide}
279:
1.2 ! noro 280: \begin{slide}{\ns $B3FIt$N>\:Y(B --- $B$=$NB>(B}
1.1 noro 281:
282: \begin{itemize}
283: \item $BCf4V4pDl$r%G%#%9%/>e$KCV$-(B, demand loading
284:
285: $B4{B85!G=$HF1$8%9%$%C%A$r;H$&(B. ({\tt dp\_gr\_flags()}).
286:
287: \item content $B=|5n(B
288:
289: default $B$G9T$&(B. $BF,78?t$,(B 2 $BG\$N(B bit $BD9$K$J$C$?$i(B
290: content $B=|5n(B
291: \end{itemize}
292:
293: \end{slide}
294:
1.2 ! noro 295: \begin{slide}{\ns $B@-G=(B --- $BM-8BBN>e$G$N(B cyclic-$n$ }
1.1 noro 296:
297: \vskip 1cm
298:
299: \begin{tabular}{c||c|c|c|c}
300: $n$ & {\tt nd\_gr} & Singular & {\tt nd\_f4} & {\tt dp\_gr\_mod\_main} \\ \hline
301: 7 & 5.1 & 5.0 & 1.8 & 17 \\
302: 8 & 124 & 135 & 34 & 564 \\
303: 9 & 27810 & 29725 & 3951 & --- \\
304: \end{tabular}
1.2 ! noro 305: \vskip 1cm
! 306:
! 307: {\tt nd\_gr} cyclic-$8$
! 308:
! 309: geobucket $B$J$7(B : 155sec
! 310:
! 311: +reducer hash $B$J$7(B : 187sec
! 312:
! 313: +inline $B$J$7(B : 240sec
! 314:
! 315: +$B;X?t(B 32bit $B8GDj(B : 390sec
! 316:
1.1 noro 317: \end{slide}
318:
1.2 ! noro 319: \begin{slide}{\ns $B@-G=(B --- $BM-8BBN>e$G$N%Y%s%A%^!<%/(B }
1.1 noro 320:
321: \begin{tabular}{c||c|c|c}
322: & {\tt nd\_gr} & Singular & {\tt nd\_f4} \\ \hline
323: dl & 5.9 & 4.9 &4.0 \\
324: eco10 & 7.1 & 10 &3.1 \\
325: eco11 & 63 & 106 &23 \\
326: eco12 & 507 & 1012 &198 \\
327: extcyc6 & 11 & 9.4 &4.1 \\
328: extcyc7 & 1813 & 1283 &447 \\
329: f855 & 3.6 & 3.4 &2.5 \\
330: filter9 & 0.28 & 0.80 &3.2 \\
331: hairer2 & 5.9 & 3.8 &4.5 \\
332: hairer3 & 11 & 35 &*
333: \end{tabular}
334: \end{slide}
335:
1.2 ! noro 336: \begin{slide}{\ns $B@-G=(B --- $BM-8BBN>e$G$N%Y%s%A%^!<%/(B }
1.1 noro 337:
338: \begin{tabular}{c||c|c|c}
339: & {\tt nd\_gr} & Singular & {\tt nd\_f4} \\ \hline
340: hcyclic7 & 6.5 & 4.8 &3.1 \\
341: hcyclic8 & 213 & 163 &82 \\
342: hf744 & 1.1 & 1.1 &1.6 \\
343: hf855 & 25 & 25 &17 \\
344: ilias13 & 11 & 8.4 &6.0\\
345: ilias\_k\_2 & 3.1 & 2.7 &1.1\\
346: ilias\_k\_3 & 4.4 & 2.9 &1.2 \\
347: katsura10 & 285 & 218 &80 \\
348: katsura8 & 4.1 & 3.3 &1.3 \\
349: katsura9 & 35 & 29 &11 \\
350: \end{tabular}
351: \end{slide}
352:
1.2 ! noro 353: \begin{slide}{\ns $B@-G=(B --- $BM-8BBN>e$G$N%Y%s%A%^!<%/(B }
1.1 noro 354:
355: \begin{tabular}{c||c|c|c}
356: & {\tt nd\_gr} & Singular & {\tt nd\_f4} \\ \hline
357: noon7 & 4.4 & 1.8 &13 \\
358: noon8 & 35 & 18 &220 \\
359: pinchon1 & 3.6 & 1.0 &7.6 \\
360: rbpl & 1.0 & 0.89 &1.2 \\
361: redcyc7 & 3.5 & 3.3 &1.2 \\
362: redeco10 & 2.8 & 2.3 &1.3 \\
363: redeco11 & 24 & 18 &12 \\
364: redeco12 & 177 & 134 &74 \\
365: reimer6 & 11 & 32 &10 \\
366: reimer7 & 4000 & 4108 & 956 \\
367: virasoro & 1.8 & 1.4 & 0.65
368: \end{tabular}
369: \end{slide}
370:
1.2 ! noro 371: \begin{slide}{\ns $B:#8e$NM=Dj(B}
1.1 noro 372:
373: \begin{itemize}
374: \item $BM-M}4X?tBN>e$N%0%l%V%J!<4pDl7W;;(B
375:
376: \item $BM-M}?tBN>e$N(B $F_4$ $B7W;;(B
377:
378: \item tangent cone $B%"%k%4%j%:%`(B, $BI8=`4pDl(B
379:
1.2 ! noro 380: \item incremental $B$JF~NO$NDI2C(B
! 381:
! 382: (Singular $B$N40A4$J$^$M$J$N$G(B, $B$d$kM=Dj$J$7(B)
! 383:
! 384: $BF~NOB?9`<0$O(B S-poly $B%j%9%H$K2C$($k(B
! 385:
! 386: $B%Z%"(B $\Rightarrow$ S-poly $B$r@55,2=(B
! 387:
! 388: $BB?9`<0(B $\Rightarrow$ $B$=$N$^$^@55,2=(B
! 389:
! 390: $BF@$9$k>l9g$,$"$k(B
1.1 noro 391: \end{itemize}
392: \end{slide}
393:
1.2 ! noro 394: \begin{slide}{\ns $B$*CN$i$;(B}
! 395:
! 396: Risa/Asir Conference 2004
! 397:
! 398: 3/22--3/24
! 399:
! 400: $B?@8MBg3X(B
! 401:
! 402: $B!:@Z(B : 2/28
! 403:
! 404: $B?=9~@h(B : takayama@math.kobe-u.ac.jp
! 405:
! 406: {\tt http://www.math.kobe-u.ac.jp/RisaCon/}
! 407:
! 408: $B!V?t<0=hM}!W$GFC=89f$r=P$9M=Dj(B
! 409: \end{slide}
! 410: \begin{slide}{\ns $B9V5fO?869F(B}
! 411:
! 412: $B!:@Z(B : 3/19
! 413:
! 414: $BAw$j@h(B : {\tt noro@math.kobe-u.ac.jp}
! 415:
! 416: $B>\:Y$O(B : {\tt http://www.jssac.org} $B$K7G:\M=Dj(B
! 417: \end{slide}
1.1 noro 418: %\begin{slide}{}
419: %\end{slide}
420: \end{document}
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>