Return to rims2003-noro-ohp.tex CVS log

Up to [local] / OpenXM / doc / Papers

Update for CA-ALIAS03.

\documentclass{slides}
%\documentclass[pdf,distiller,slideColor,colorBG,azure]{prosper}
\usepackage{color}
\usepackage{rgb}
\usepackage{graphicx}
\usepackage{epsfig}
\newcommand{\qed}{$\Box$}
\newcommand{\mred}[1]{\smash{\mathop{\hbox{\rightarrowfill}}\limits_{\scriptstyle #1}}}
\newcommand{\tmred}[1]{\smash{\mathop{\hbox{\rightarrowfill}}\limits_{\scriptstyle #1}\limits^{\scriptstyle *}}}
\newtheorem{prop}{\redc $BL?Bj(B}
\def\gr{Gr\"obner basis }
\def\st{\, s.t. \,}
\def\ni{\noindent} 
\def\init{{\rm in}} 
\def\Q{{\bf Q}} 
\def\Spoly{{\rm Spoly}}
\def\Span{{\rm Span}}
\def\Supp{{\rm Supp}}
\def\StdMono{{\rm StdMono}}
\def\Im{{\rm Im}}
\def\Ker{{\rm Ker}}
\def\NF{{\rm NF}}
\def\HT{{\rm HT}}
\def\LT{{\rm LT}}
\def\ini{{\rm in}}
\def\Id#1{\langle #1 \rangle}
\def\ve{\vfill\eject} 
\textwidth 9.2in
\textheight 7.2in
\columnsep 0.33in
\topmargin -1in
\def\tc{\color{orange}}
\def\fbc{\bf\color{orange}}
%\def\itc{\color{LimeGreen}}
\def\itc{\color{DarkGreen}}
%\def\urlc{\bf\color{DarkGreen}}
\def\urlc{\bf\color{LimeGreen}}
\def\goldc{\color{goldenrod3}}
\def\redc{\color{orange}}
\def\vs{\vskip 1cm}
\def\vsh{\vskip 0.5cm}
\def\ns{\itc\LARGE}
\title{\tc\bf\ns Risa/Asir $B>e$N?7%0%l%V%J!<4pDl7W;;%Q%C%1!<%8$K$D$$$F(B}

%\slideCaption{Risa/Asir $B>e$N?7%0%l%V%J!<4pDl7W;;%Q%C%1!<%8$K$D$$$F(B}
\author{{\bf\Large $BLnO$(B $B@59T(B\\ $B?@8MBg3XM}3XIt?t3X2J(B}}
%\date{\bf\Large June 21, 2002}
%\date{\bf\Large Nov. 26, 2003}
\date{\bf\Large Dec. 18, 2003}
\begin{document}
\setlength{\parskip}{20pt}
\maketitle

%\itc: item color
%\fbc: fbox color
%\urlc: URL color
%\goldc: bold color a
%\redc: bold color b

\Large
\bf
\setlength{\parskip}{0pt}

\begin{slide}{\ns $B?7%Q%C%1!<%83+H/$N7P0^(B}

$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
$B0MB8(B

$BJ,;6I=8=B?9`<0(B {\tt DP} : $BC19`<0(B {\tt MP} $B$N(B linked list

{\tt MP} : $B;X?t%Y%/%H%k(B {\tt DL} $B$r%]%$%s%?$G$b$D(B

{\tt DL} : $BA4<!?t$*$h$S(B 32bit $B@0?tG[Ns(B (1 $BMWAG(B 32bit $B$G8GDj(B)

%\vskip 1cm
%\begin{tabular}{cc}
%\begin{minipage}{.5\hsize}
%\baselineskip 0.5in
%\begin{verbatim}
%typedef struct oMP {
%    struct oDL *dl;
%    P c;
%    struct oMP *next;
%} *MP;
%\end{verbatim}
%\end{minipage}
%&
%\begin{minipage}{.5\hsize}
%\baselineskip 0.5in
%\begin{verbatim}
%typedef struct oDL {
%    int td;
%    int d[1];
%} *DL;
%\end{verbatim}
%\end{minipage}
%\end{tabular}

\end{slide}

\begin{slide}{\ns Singular $B$H$NHf3S(B}

Singular 2-0-4

\begin{itemize}
\item $BM-8BBN>e$G9bB.(B

$B4pK\E*%"%k%4%j%:%`$O(B Asir $B$HF1$8(B.

$BO@J8$K$h$k$H(B, geobucket, $B2DJQD9;X?t%Y%/%H%k(B, $B8zN($h$$(B
$B%a%b%j4IM}(B etc. $B$r<BAu(B

\item $BM-M}?tBN>e$G$b9bB.(B

gmp $B$r@0?t1i;;$K;HMQ(B $\Rightarrow$ Asir $B$N(B bignum $B$h$j(B,
$BBg$-$$?t$G$OB.$$(B
\end{itemize}
\end{slide}

\begin{slide}{\ns $BIi$1$C$Q$J$7$O$/$d$7$$(B$\ldots$}

($B$"$k$$$O(B, $B!VIwI>!W$K<BBV$r9g$o$;$k(B)

$B$[$\40A4$K(B 0 $B$+$i=q$/(B

($B$G$-$l$P(B) $B%*%j%8%J%k$J9)IW$rF~$l$?$$(B

$\Rightarrow$ ($B;n9T:x8m$r$5$s$6$s$d$C$?(B)$B7k2L$H$7$F(B, 
geobucket, $B2DJQD9;X?t%Y%/%H%k$O<BAu(B

$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

$B@55,2=7W;;$K$*$1$k(B reducer $BC5$7$K%O%C%7%e$rMxMQ(B

$B4X?t$N%$%s%i%$%s(B, unrolling $B$NB?MQ(B
\end{slide}

\begin{slide}{\ns $B8zN(2=$N9)IW(B --- geobucket}

$BB?9`<0$r(B, $BG[Ns(B $g$$B$G;}$D(B

$g[i]$ $B$K$O(B, $B9`?t$,(B, $B9b!9(B $b^i$ $B$NB?9`<0$,F~$k(B

$BB?9`<0$O(B, $g[i]$ $BA4It$NOB(B

$B9`?t$,(B $l$ ($b^{(i-1)} < l \le b^i$) $B$NB?9`<0(B $p$ $B$r(B $g$ $B$K(B
$BB-$9>l9g(B

\begin{enumerate}
\item $p \leftarrow g[i]+p$
\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.
$B$5$b$J$/$P(B, $g[i] \leftarrow p$ $B$H$7$F=*N;(B
\end{enumerate}

$B8z2L(B : $BB??t$NOB$N7W;;$K$*$$$F(B, $BHf3S1i;;$r8:$i$9(B 

\end{slide}

\begin{slide}{\ns $B8zN(2=$N9)IW(B --- $B2DJQD9;X?t%Y%/%H%k(B}

$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
32 bit $B$K(B 4 $B$DF~$k(B.

\begin{tabular}{|c|c|c|c|} \hline
$e_1$ & $e_2$ & $e_3$ & $e_4$ \\ \hline
\end{tabular}

$B;X?t$NOB(B : 32bit $B@0?t$NOB(B

$B;X?t$NHf3S(B : $B<-=q<0$J$i(B, 32bit $B@0?t$NBg$-$5$NHf3S(B

$B5U<-=q<0$J$i(B, $B$"$i$+$8$a5U=g$K5M$a$k(B.

\end{slide}

\begin{slide}{\ns $B8zN(2=$N9)IW(B --- $BG[Ns$K$h$kB?9`<0$NJ];}(B}

$B4pK\A`:n(B : $f-mg$ ($m$ $B$OC19`<0(B)

$f-(mg)$ : geobucket

$mg$ : $g$ $B$NI=8=$K$h$j(B, $B8zN($,0[$J$k(B

$B;n9T:x8m$N7k2L(B : $g$ $B$,(B, $B%a%b%j>e$K0l<!85E*$KI=8=$5$l$F$$$k$H9bB.(B

$g$ $B$OCf4V4pDl(B $\Rightarrow$ $BCf4V4pDl$N$_(B, $BG[NsI=8=(B

$mg$ $B<+?H$O(B, $B2C;;$K$^$o$k$N$G(B, linked list $B$,$h$$(B

\end{slide}

\begin{slide}{\ns $B8zN(2=$N9)IW(B --- $B4X?t$N%$%s%i%$%s2=(B, unrolling}

$BBgJ*$rJRIU$1$k$H(B, $B>.J*$,L\$K$D$/(B

$B>.J*(B : $B;X?t%Y%/%H%k$NA`:n(B ($BOB(B, $B:9(B, $BHf3S(B, divisibility)

$B<B83$GHf3S$7$J$,$i(B, $B$7$?$[$&$,$h$$$b$N$r%$%s%i%$%s(B, unrolling
\end{slide}

\begin{slide}{\ns $B8zN(2=$N9)IW(B --- reducer $B%5!<%A$N%O%C%7%e2=(B}

$B9`(B t $B$r3d$j@Z$kCf4V4pDl(B $g_t$ $B$N%5!<%A$bLdBj$H$J$C$?(B

$g_t$ $B$O(B, $B8E$$4pDl$+$i=g$KC5$9(B $\Rightarrow$ $B$"$l$P0l0UE*(B

$\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,
$H[h(t)]$ $B$K(B $(t,g_t)$ $B$rEPO?$9$k(B.

$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.

$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
$BEPO?(B
\end{slide}

\begin{slide}{\ns $B8zN(2=$N9)IW(B --- $B@F<!$N>l9g$N8zN(2=(B}

\begin{itemize}
\item $B0lHL$N>l9g(B : $BESCf$G(B interreduction $B$7$J$$(B

\item $B@F<!$N>l9g(B : $B$7$F$h$$(B

$BF,9`$OJQ2=$7$J$$(B

$BF@$i$l$?Cf4V4pDl$O<B$O4JLs%0%l%V%J!<4pDl$N$&$A(B, $B8=<!?t$^$G$N$9$Y$F(B

$\Rightarrow$ 0 $B$K@55,2=$5$l$?(B S-poly $B$O(B, interreduction $B8e$b(B 0 $B$K9T$/(B
\end{itemize}
\end{slide}

\begin{slide}{\ns $B8zN(2=$N9)IW(B --- $B%a%b%j4IM}(B}

$BHf3SE*>.$5$$%a%b%jNN0h$,7+$jJV$7I,MW$H$J$k(B

$\Rightarrow$ $BKh2s(B {\tt GC\_malloc()} $B$O=E$9$.(B

$\Rightarrow$ GC $B$+$i$b$i$C$?%a%b%j$r(B, $B<+A0$G(B
$B%U%j!<%j%9%H4IM}(B
\end{slide}

\begin{slide}{\ns $B3FIt$N>\:Y(B --- $B%I%i%$%P(B}

\begin{itemize}
\item {\tt nd\_gr}

$BM-8BBN(B, $BM-M}?tBN78?t$J$I(B, $B$9$Y$F$KBP1~$9$k(B.

\item {\tt nd\_gr\_trace}

$BM-M}?tBN@lMQ(B. trace $B%"%k%4%j%:%`$r<B9T$9$k(B.

$B@F<!2=$rMxMQ$9$k$h$&;XDj$,2DG=(B

\item {\tt nd\_f4}

$BM-8BBN@lMQ(B $F_4$ $B<BAu(B. $B;~4V(B, $B6u4VAPJ}$K4X$9$k8zN(2=(B
$B$rL\;X$7$?<BAu(B

\end{itemize}
\end{slide}

\begin{slide}{\ns $B3FIt$N>\:Y(B --- $B;X?t%Y%/%H%k$ND9$5JQ99(B}

\begin{itemize}
\item $B$"$U$l(B 

$BB?9`<0(B $f$  $\Rightarrow$ $B:GBg;X?t%Y%/%H%k(B $M_f$ $B$rBP1~(B

\item $x^E f$ 

$E+M_f$ $B$,$"$U$l$r$*$3$9$+$I$&$+D4$Y$k(B

\item $B%A%'%C%/$,I,MW$J>l=j(B

S-poly $B7W;;(B, $B@55,2=$K$*$1$k(B, $BC19`<0(B $\times$ reducer $B$N7W;;(B
\end{itemize}

\end{slide}

\begin{slide}{\ns $B3FIt$N>\:Y(B --- $B$=$NB>(B}

\begin{itemize}
\item $BCf4V4pDl$r%G%#%9%/>e$KCV$-(B, demand loading

$B4{B85!G=$HF1$8%9%$%C%A$r;H$&(B. ({\tt dp\_gr\_flags()}).

\item content $B=|5n(B

default $B$G9T$&(B. $BF,78?t$,(B 2 $BG\$N(B bit $BD9$K$J$C$?$i(B
content $B=|5n(B
\end{itemize}

\end{slide}

\begin{slide}{\ns $B@-G=(B --- $BM-8BBN>e$G$N(B cyclic-$n$ }

\vskip 1cm

\begin{tabular}{c||c|c|c|c}
 $n$        & {\tt nd\_gr} & Singular & {\tt nd\_f4} & {\tt dp\_gr\_mod\_main} \\ \hline
  7         &   5.1        &  5.0         & 1.8      & 17                      \\
  8         &   124        &  135         & 34       & 564                     \\
  9         &   27810      &  29725       & 3951     &    ---                  \\
\end{tabular}
\vskip 1cm

{\tt nd\_gr} cyclic-$8$

geobucket $B$J$7(B : 155sec

+reducer hash $B$J$7(B : 187sec

+inline $B$J$7(B : 240sec

+$B;X?t(B 32bit $B8GDj(B : 390sec

\end{slide}

\begin{slide}{\ns $B@-G=(B --- $BM-8BBN>e$G$N%Y%s%A%^!<%/(B }

\begin{tabular}{c||c|c|c}
       & {\tt nd\_gr} & Singular & {\tt nd\_f4} \\ \hline
dl & 5.9 & 4.9 &4.0 \\
eco10 & 7.1 & 10 &3.1 \\
eco11 & 63 & 106 &23 \\
eco12 & 507 & 1012 &198 \\
extcyc6 & 11 & 9.4 &4.1 \\
extcyc7 & 1813 & 1283 &447 \\
f855 & 3.6 & 3.4 &2.5 \\
filter9 & 0.28 & 0.80 &3.2 \\
hairer2 & 5.9 & 3.8 &4.5 \\
hairer3 & 11 & 35 &* 
\end{tabular}
\end{slide}

\begin{slide}{\ns $B@-G=(B --- $BM-8BBN>e$G$N%Y%s%A%^!<%/(B }

\begin{tabular}{c||c|c|c}
       & {\tt nd\_gr} & Singular & {\tt nd\_f4} \\ \hline
hcyclic7 & 6.5 & 4.8 &3.1 \\
hcyclic8 & 213 & 163 &82 \\
hf744 & 1.1 & 1.1 &1.6 \\
hf855 & 25 & 25 &17 \\
ilias13 & 11 & 8.4 &6.0\\
ilias\_k\_2 & 3.1 & 2.7 &1.1\\
ilias\_k\_3 & 4.4 & 2.9 &1.2 \\
katsura10 & 285 & 218 &80 \\
katsura8 & 4.1 & 3.3 &1.3 \\
katsura9 & 35 & 29 &11 \\
\end{tabular}
\end{slide}

\begin{slide}{\ns $B@-G=(B --- $BM-8BBN>e$G$N%Y%s%A%^!<%/(B }

\begin{tabular}{c||c|c|c}
       & {\tt nd\_gr} & Singular & {\tt nd\_f4} \\ \hline
noon7 & 4.4 & 1.8 &13 \\
noon8 & 35 & 18 &220 \\
pinchon1 & 3.6 & 1.0 &7.6 \\
rbpl & 1.0 & 0.89 &1.2 \\
redcyc7 & 3.5 & 3.3 &1.2 \\
redeco10 & 2.8 & 2.3 &1.3 \\
redeco11 & 24 & 18 &12 \\
redeco12 & 177 & 134 &74 \\
reimer6 & 11 & 32 &10 \\
reimer7 & 4000 & 4108 & 956 \\
virasoro & 1.8 & 1.4 & 0.65 
\end{tabular}
\end{slide}

\begin{slide}{\ns $B:#8e$NM=Dj(B}

\begin{itemize}
\item $BM-M}4X?tBN>e$N%0%l%V%J!<4pDl7W;;(B

\item $BM-M}?tBN>e$N(B $F_4$ $B7W;;(B

\item tangent cone $B%"%k%4%j%:%`(B, $BI8=`4pDl(B

\item incremental $B$JF~NO$NDI2C(B

(Singular $B$N40A4$J$^$M$J$N$G(B, $B$d$kM=Dj$J$7(B)

$BF~NOB?9`<0$O(B S-poly $B%j%9%H$K2C$($k(B

$B%Z%"(B $\Rightarrow$ S-poly $B$r@55,2=(B

$BB?9`<0(B $\Rightarrow$ $B$=$N$^$^@55,2=(B

$BF@$9$k>l9g$,$"$k(B
\end{itemize}
\end{slide}

\begin{slide}{\ns $B$*CN$i$;(B}

Risa/Asir Conference 2004

3/22--3/24

$B?@8MBg3X(B

$B!:@Z(B : 2/28

$B?=9~@h(B : takayama@math.kobe-u.ac.jp

{\tt http://www.math.kobe-u.ac.jp/RisaCon/}

$B!V?t<0=hM}!W$GFC=89f$r=P$9M=Dj(B
\end{slide}
\begin{slide}{\ns $B9V5fO?869F(B}

$B!:@Z(B : 3/19

$BAw$j@h(B : {\tt noro@math.kobe-u.ac.jp}

$B>\:Y$O(B : {\tt http://www.jssac.org} $B$K7G:\M=Dj(B
\end{slide}
%\begin{slide}{}
%\end{slide}
\end{document}