File: [local] / OpenXM / doc / Papers / rims2003-noro-ohp.tex (download)
Revision 1.2, Mon Mar 22 02:48:47 2004 UTC (20 years, 6 months ago) by noro
Branch: MAIN
CVS Tags: R_1_3_1-2, RELEASE_1_3_1_13b, RELEASE_1_2_3_12, RELEASE_1_2_3, KNOPPIX_2006, HEAD, DEB_REL_1_2_3-9 Changes since 1.1: +98 -51
lines
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}