% $OpenXM: OpenXM/doc/Papers/jsiamb-noro.tex,v 1.1 2001/10/04 08:16:27 noro Exp $
\setlength{\parskip}{10pt}

\begin{slide}{}
\fbox{$B7W;;5!Be?t%7%9%F%`(B Risa/Asir}

\begin{itemize}
\item $BB?9`<04D$K$*$1$kBg5,LO9bB.7W;;$rL\;X$7$F3+H/(B

\begin{itemize}
\item C $B$G5-=R(B
\item $B%a%b%j4IM}$O(B Boehm's conservative GC $B$K$h$k(B
\end{itemize}

\item C $B8@8l$K;w$?%f!<%68@8l%$%s%?%U%'!<%9$r$b$D(B.

\begin{itemize}
\item $B7?@k8@$J$7(B
\item $B%f!<%68@8l%G%P%C%,$,AH$_9~$_(B
\end{itemize}

\item $B%*!<%W%s%=!<%9(B

\begin{itemize}
\item 2000 $BG/$^$GIY;NDL8&$G3+H/(B $\Rightarrow$ $B?@8M(B branch [Risa/Asir]
$B$,%9%?!<%H(B

CVS $B$G:G?7HG$,F~<j2DG=(B ($BF~<jJ}K!$O8e=R(B)
\end{itemize}

\item OpenXM ((Open message eXchange protocol for Mathematics) $B%$%s%?%U%'!<%9(B
\end{itemize}
\end{slide}

\begin{slide}{}
\fbox{$B<g$J5!G=(B}

\begin{itemize}
\item $BB?9`<0$N4pK\1i;;(B

\begin{itemize}
\item $B2C8:>h=|(B, GCD, $B=*7k<0(B etc.
representation
\end{itemize}

\item $BB?9`<00x?tJ,2r(B

\begin{itemize}
\item $B0lJQ?tB?9`<0(B : $B78?tBN$OM-M}?tBN(B, $BBe?tBN(B, $B<o!9$NM-8BBN(B

\item $BB?JQ?tB?9`<0(B : $B78?tBN$OM-M}?tBN(B
\end{itemize}

\item $B%0%l%V%J4pDl7W;;(B

\begin{itemize}
\item Buchberger $B%"%k%4%j%:%`(B, Fag\`ere $F_4$ [Faug\`ere] $B%"%k%4%j%:%`(B

$BB?9`<04D$*$h$S(B Weyl $BBe?t(B

\item 0 $B<!85%$%G%"%k$N(B change of ordering/RUR [Rouillier]

\item $B=`AG%$%G%"%kJ,2r(B

$BB?JQ?tBe?tJ}Dx<07O$N2r$NJ,2r$rM?$($k(B

\item $BB?9`<0$N(B $b$-$B4X?t$N7W;;(B [Oaku]

$b$-$B4X?t(B : $BB?9`<0$NNmE@$G$"$kD66JLL$NITJQNL(B

$D$-$B2C72$K$*$1$k7W;;$N(B, $BM-8B<!85$N@~7ABe?t$X$N5"Ce$KI,MW(B
\end{itemize}
\end{itemize}
\end{slide}

\begin{slide}{}
\fbox{$B<g$J5!G=(B ($B$D$E$-(B)}

\begin{itemize}

\item PARI [PARI] $B%i%$%V%i%j%$%s%?%U%'!<%9(B

$B?tO@%i%$%V%i%j(B PARI $B$r%j%s%/$7$F$$$F<g$J4X?t$,8F$Y$k(B

bigfloat $B7W;;(B, $BD61[4X?t$NI>2A$K$bMQ$$$i$l$k(B

\item OpenXM $B$N85$G$NJ,;6JBNs7W;;(B

OpenXM $B$K$h$kF1<o$^$?$O0[<o$N?t3X%=%U%H%&%'%"$N7k9g(B

client-server $B7?J,;6JBNs7W;;$,MF0W$K<B83$G$-$k(B

\item 2 $BJQ?t4X?t$NNmE@$N@:L)IA2h(B

$BCf4VCM$NDjM}(B, Sturm $BNs$NMxMQ$K$h$k(B, 2 $BJQ?t4X?t$NNmE@$N@:L)IA2h(B

OpenXM server $B$H$7$F<B8=(B
\end{itemize}
\end{slide}

\begin{slide}{}
\fbox{$B3+H/$NNr;K(B : ---1994}

\begin{itemize}
\item --1989

Prolog $B$N%5%V%k!<%A%s$H$7$F(B, $B$$$/$D$+$N5!G=$r3+H/(B

\item 1989--1992

\begin{itemize}
\item parser $B$*$h$S(B Boehm $B$N(B GC [Boehm] $B$H$H$b$K(B Risa/Asir $B$,%9%?!<%H(B

\item $BM-M}?tBN>e0lJQ?t(B, $BB?JQ?tB?9`<0$N0x?tJ,2r$r3+H/(B
\end{itemize}

\item 1992--1994

\begin{itemize}
\item Buchberger $B%"%k%4%j%:%`$N<BAu3+;O(B

$B%f!<%68@8l$G5-=R(B $\Rightarrow$ C $B$G=q$-D>$7(B (by $BB<Hx(B@$B8=:_EEDLBg(B)

$\Rightarrow$ trace lifting [Traverso] $B$N<BAu(B

\item $BBe?tBN>e$N0lJQ?tB?9`<0$N0x?tJ,2r(B

$BC`<!3HBg$*$h$S(B, $B=EJ#0x;R$r$b$D%N%k%`$NAH?%E*MxMQ(B
\end{itemize}
\end{itemize}

\end{slide}

\begin{slide}{}
\fbox{$B3+H/$NNr;K(B : 1994-1996}

\begin{itemize}
\item $B%P%$%J%jHG$rIY;NDL$h$j8x3+(B

\item $B=`AG%$%G%"%kJ,2r$N<BAu(B

\begin{itemize}
\item $B2<;3(B-$B2#;3%"%k%4%j%:%`(B [SY]
\end{itemize}

\item Buchberger $B%"%k%4%j%:%`$N2~NI(B

\begin{itemize}
\item Trace lifting+$B@F<!2=(B

\item compatible prime $B$K$h$k%0%l%V%J4pDl%A%'%C%/$N>JN,(B

\item Modular change of ordering, Modular RUR

$B2#;3$H$N6&F18&5f(B [NY]
\end{itemize}
\end{itemize}

\end{slide}

\begin{slide}{}
\fbox{$B3+H/$NNr;K(B : 1996-1998}

\begin{itemize}
\item $BJ,;67W;;5!G=$N<BAu(B

\begin{itemize}
\item OpenXM $B$N%W%m%H%?%$%W(B
\end{itemize}

\item Buchberger $B%"%k%4%j%:%`$N2~NI(B

\begin{itemize}
\item $B@55,7A7W;;Cf$K$*$1$k78?t$N6&DL0x;R$N8zN(E*=|5n(B

\item $B$=$NJBNs2=(B

\item odd order replicable functions $B$N7W;;(B [Noro]

Risa/Asir : DRL basis $B7W;;(B({\it McKay}) $B$K(B 5 $BF|$+$+$C$?(B

Faug\`ere $B$N(B FGb : $B$3$N7W;;$r(B 53 $BIC$G<B9T(B
\end{itemize}


\item $BBg$-$JM-8BBN>e$N0lJQ?tB?9`<0$N0x?tJ,2r(B

\begin{itemize}
\item Schoof-Elkies-Atkin $B%"%k%4%j%:%`$N<BAu$N$?$a(B

$BM-8BBN>e$NBJ1_6J@~$NM-M}E@8D?t7W;;MQ(B

--- $B$3$N%W%m%0%i%`$O%U%j!<$G$O$J$$$,(B, $B4X78$9$k4X?t(B
$B$O%U%j!<(B
\end{itemize}
\end{itemize}

\end{slide}

\begin{slide}{}
\fbox{$B3+H/$NNr;K(B : 1998-2000}
\begin{itemize}
\item OpenXM

\begin{itemize}
\item OpenXM $B;EMM=q(B : $BLnO$(B, $B9b;3(B [OpenXM]

enconding, phrasebook $B$K4X$9$k%"%$%G%#%"$O(B OpenMath [OpenMath] $B$+$i<ZMQ(B

\item $BJ,;67W;;4X?t$O(B, OpenXM $B;EMM$K=q$-D>$7(B
\end{itemize}

\item Risa/Asir on Windows

\begin{itemize}
\item $B;E;v>eI,MW$K$J$C$?(B

Visual C++ $B$G5-=R(B
\end{itemize}

\item $F_4$ $B$N;n83<BAu(B

\begin{itemize}
\item [Faug\`ere]$B$K=`5r$7$F5-=R(B

\item $GF(p)$ $B>e(B : $B$J$+$J$+$h$$(B

\item $BM-M}?tBN>e(B :{\it McKay} $B$r=|$$$F$@$a(B
\end{itemize}
\end{itemize}
\end{slide}

\begin{slide}{}
\fbox{$B3+H/$NNr;K(B : 2000-current}
\begin{itemize}
\item $B%*!<%W%s%=!<%92=(B

\begin{itemize}
\item $BLnO$$,IY;NDL8&$h$j?@8MBg$K0\@R(B

Started Kobe branch $B$N%9%?!<%H(B
\end{itemize}

\item OpenXM

\begin{itemize}
\item $B;EMM=q(B : OX-RFC100, 101, (102)

\item OX-RFC102 ($BL$40@.(B) : MPI $B$rMQ$$$?%5!<%P4VDL?.(B
\end{itemize}

\item Weyl $BBe?t(B

\begin{itemize}
\item Buchberger $B%"%k%4%j%:%`(B [Takayama]

\item $b$-$B4X?t(B

$b$-$B4X?t$r:G>.B?9`<0$H$7$F%b%8%e%i7W;;(B
\end{itemize}
\end{itemize}

\end{slide}

\begin{slide}{}
\fbox{$B@-G=(B --- $B0x?tJ,2r(B}

\begin{itemize}
\item 10 $BG/A0(B

REDUCE, Mathematica $B$KHf$Y$F9b@-G=$@$C$?(B

\item 4 $BG/A0(B

$B%N%k%`$+$i@8$8$kB?9`<0$N0x?tJ,2r$KBP$9$k%H%j%C%/$K(B
$B$h$j(B, $BBe?tBN>e$NJ,2r$O0MA3$H$7$FM%0L$@$C$?(B

\item $B8=:_(B

$BB?JQ?t(B : $B$^$:$^$:(B

$BM-M}?tBN>e0lJQ?t(B : M. van Hoeij $B$N?7%"%k%4%j%:%`$K$h$j40A4$KIi$1(B
\end{itemize}

\end{slide}

\begin{slide}{}
\fbox{$B@-G=(B --- $B%0%l%V%J4pDl4XO"5!G=(B}

\begin{itemize}
\item 8 $BG/A0(B

$B$H$j$"$($:F0$/DxEY$N@-G=(B

\item 7 $BG/A0(B

Rather trace lifting $B$K$h$j9b@-G=$@$C$?$,(B, Faug\`ere' $B$N(B Gb $B$K$O(B
$BIi$1$F$$$?(B

$B$7$+$7(B, $B@F<!2=$H$NAH9g$;$K$h$j(B, $B$h$j9-$$HO0O$NF~NO$KBP$7$F%0%l%V%J(B
$B4pDl$,7W;;$G$-$k$h$&$K$J$C$?(B

\item 4 $BG/A0(B

Modular RUR $B7W;;$O(B Rouillier $B$N<BAu$HHf3S$7$FF1Ey$"$k$$$OM%0L$@$C$?(B

\item $B8=:_(B

FGb $B$O(B Risa/Asir $B$N(B $F_4$ $B<BAu$h$j$:$$$V$s9bB.$N$h$&(B

Singular [Singular] $B$OB?9`<0$N8zN($h$$I=8=$K$h$j(B, Risa/Asir $B$N?tG\9bB.(B
$B$N>l9g$b$"$k(B. ($B78?t$,Bg$-$/$J$k>l9g$O$^$@(B Risa/Asir $B$,M%0L(B)

\end{itemize}
\end{slide}

\begin{slide}{}
\fbox{$BBg5,LO7W;;$X$NBP1~(B}

\begin{itemize}
\item $B%0%l%V%J4pDl7W;;Cf$K@8@.$5$l$?4pDl$r%G%#%9%/$KJ]B8(B

\begin{itemize}
\item $B<g5-21$NM-8zMxMQ(B

\item $BESCf$+$i7W;;$r:F3+$G$-$k(B
\end{itemize}

\item OpenXM $B$K$h$kJ,;67W;;(B

\begin{itemize}
\item $BJBNs2=$K$h$kBf?t8z2L(B

\item $BJ#?t$N%"%k%4%j%:%`$N6%AhE*<B9T$,MF0W(B
\end{itemize}

\end{itemize}
\end{slide}

\begin{slide}{}
\fbox{$B1~MQ;vNc(B}

\begin{itemize}
\item $BBJ1_6J@~0E9f%Q%i%a%?@8@.(B

$BM-8BBN>e$NB?9`<00x?tJ,2r$N1~MQ(B

\item $D$-$B2C72$K$*$1$k<o!9$N7W;;(B

de Rham $B%3%[%b%m%8(B, $BBe?tE*6I=j%3%[%b%m%8(B, $D$-$B2C72$N@)8B(B, $B%F%s%=%k@Q(B
$B7W;;$K$*$$$F(B, $BB?9`<00x?tJ,2r(B, $B=`AGJ,2r(B, $b$-$B4X?t7W;;$rC4Ev(B (OpenXM $B7PM3(B)

\item $BBe?tJ}Dx<07O$N5a2r(B

$B;;K!(B, $B<BAuN>LL$+$iBg5,LO7W;;$KBP1~(B

$BL$Dj78?tK!$K$h$k2D@QJ,7O$N7hDj(B

$BBPOCE*%7%9%F%`$N%P%C%/%(%s%I$GBe?tJ}Dx<05a2r(B

\item $B%"%k%4%j%:%`<BAu<B83%D!<%k(B

$BIbF0>.?t78?t%0%l%V%J4pDl7W;;(B, Wu $B$NJ}K!(B, $B6h4V1i;;(B
$B$J$I$N%"%k%4%j%:%`$N<BAu<B83(B. $B%=!<%9%l%Y%k$G$N(B
$B2~JQ$b2DG=(B

\end{itemize}

\begin{slide}{}
\fbox{$B8=:_3+H/Cf$N5!G=(B}

\begin{itemize}
\item $BM-8BBN>e$NB?JQ?tB?9`<0$N0x?tJ,2r(B, $BM-8BBN>e$N=`AGJ,2r(B

\begin{itemize}
\item $BBe?t4v2?Id9f$X$N1~MQ$r8+9~$s$@M-8BBN>e$N=`AGJ,2r<BAu(B

\item $BI8?t$,>.$5$$>l9gFCM-$N:$Fq$,$"$k(B

\item $B4pAC$H$J$kM-8BBN>e$NB?JQ?tB?9`<0$N0x?tJ,2r$r<BAuCf(B
\end{itemize}

\item $B$h$j9-HO$J%G!<%?$NJ];}J}K!(B, $B5-=RG=NO$N8~>e(B

\begin{itemize}
\item $B8=>u$G$O(B, $B2D49B?9`<04D0J30$N%G!<%?$N<+A3$J<h$j07$$$,:$Fq(B

\item $B0[<o%7%9%F%`$H$N%G!<%?8r49(B, $B%f!<%6$K$h$k%G!<%?=hM}$,2DG=$J$h$&$K(B
$BFbItI=8=$r3HD%Cf(B
\end{itemize}

\end{itemize}
\end{slide}

\end{slide}

\begin{slide}{}
\fbox{$BJ,;67W;;$NNc(B --- $F_4$ vs. $Buchberger$ }

\begin{verbatim}
/* competitive Gbase computation over GF(M) */
/* Cf. A.28 in SINGULAR Manual */
/* Process list is specified as an option : grvsf4(...|proc=P) */
def grvsf4(G,V,M,O)
{
  P = getopt(proc);
  if ( type(P) == -1 ) return dp_f4_mod_main(G,V,M,O);
  P0 = P[0]; P1 = P[1]; P = [P0,P1];
  map(ox_reset,P);
  ox_cmo_rpc(P0,"dp_f4_mod_main",G,V,M,O);
  ox_cmo_rpc(P1,"dp_gr_mod_main",G,V,0,M,O);
  map(ox_push_cmd,P,262); /* 262 = OX_popCMO */
  F = ox_select(P); R = ox_get(F[0]);
  if ( F[0] == P0 ) { Win = "F4"; Lose = P1;}
  else { Win = "Buchberger"; Lose = P0; }
  ox_reset(Lose); /* simply resets the loser */
  return [Win,R];
}
\end{verbatim}
\end{slide}

\begin{slide}{}
\fbox{$B;29MJ88%(B}

[Bernardin] L. Bernardin, On square-free factorization of 
multivariate polynomials over a finite field, Theoretical
Computer Science 187 (1997), 105-116.

[Boehm] {\tt http://www.hpl.hp.com/personal/Hans\_Boehm/gc}

[Faug\`ere] J.C. Faug\`ere,
A new efficient algorithm for computing Groebner bases  ($F_4$),
Journal of Pure and Applied Algebra (139) 1-3 (1999), 61-88.

[Hoeij] M. van Heoij, Factoring polynomials and the knapsack problem,
to appear in Journal of Number Theory (2000).

[NY] M. Noro, K. Yokoyama, 
A Modular Method to Compute the Rational Univariate
Representation of Zero-Dimensional Ideals.
J. Symb. Comp. {\bf 28}/1 (1999), 243-263.

[Oaku] T. Oaku, Algorithms for $b$-functions, restrictions and algebraic
local cohomology groups of $D$-modules.
Advancees in Applied Mathematics, 19 (1997), 61-105.

\end{slide}

\begin{slide}{}
[OpenMath] {\tt http://www.openmath.org}

[OpenXM] {\tt http://www.openxm.org}

[PARI] {\tt http://www.parigp-home.de}

[Risa/Asir] {\tt http://www.math.kobe-u.ac.jp/Asir/asir.html}

[Rouillier] F. Rouillier,
R\'esolution des syst\`emes z\'ero-dimensionnels. 
Doctoral Thesis(1996), University of Rennes I, France.

[SY] T. Shimoyama, K. Yokoyama, Localization and Primary Decomposition of Polynomial Ideals.  J. Symb. Comp. {\bf 22} (1996), 247-277.

[Singular] {\tt http://www.singular.uni-kl.de}

[Traverso] C. Traverso, \gr trace algorithms. Proc. ISSAC '88 (LNCS 358), 125-138.

\end{slide}
