Return to rims2003-noro-ohp.tex CVS log

Up to [local] / OpenXM / doc / Papers

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}