Return to ohp.tex CVS log

Up to [local] / OpenXM / doc / ascm2001p

Final version of ascm2001 lecture.
I explained on the OHP.  Noro show demonstrations of Cantor-Zassenhaus and
competitive GB computation.

%% $OpenXM: OpenXM/doc/ascm2001p/ohp.tex,v 1.5 2001/09/29 08:33:41 takayama Exp $
\documentclass{slides}
%%\documentclass[12pt]{article}
\usepackage{color}
\usepackage{epsfig}
\newcommand{\htmladdnormallink}[2]{#1}
\begin{document}
\noindent
{\color{green} Design and Implementation of OpenXM-RFC 100 and 101}

\noindent
M.Maekawa ($BA0(B $B@n(B $B!!(B $B>-(B $B=((B), \\ M.Noro ($BLn(B $BO$(B $B!!(B $B@5(B $B9T(B), \\
K.Ohara ($B>.(B $B86(B $B!!(B $B8y(B $BG$(B), \\ N.Takayama ($B9b(B $B;3(B $B!!(B $B?.(B $B5#(B), \\
Y.Tamura ($BED(B $BB<(B $B!!(B $B63(B $B;N(B)\\
\htmladdnormallink{{\color{red}http://www.openxm.org}}{{\color{red}http://www.openxm.org}}


\newpage
\noindent
{\color{red} 1. Architecture} \\
Integrating (existing) mathematical software systems.

Two main applications of the project \\
\begin{enumerate}
\item Providing an environment for interactive distributed computation.
{\color{blue} Risa/Asir}
(computer algebra system for general purpose, 
 open source (c) Fujitsu, \\
 http://www.openxm.org, \\
 http://risa.cs.ehime-u.ac.jp, \\
 http://www.math.kobe-u.ac.jp/Asir/asir.html)
\item e-Bateman project 
(Electronic version of higher transcendental functions of the 21st century)\\
1st step: Generate and verify hypergeometric function identities.
\end{enumerate}
\newpage

\noindent
OpenXM-RFC 100 \\
{\color{green} Control}: \\
\begin{enumerate}
\item Client-server model. Tree structure of processes.
\item Wrap (existing) mathematical software systems by the
OpenXM {\color{red} stackmachine}.
\item execute\_string
\begin{verbatim}
  Pid = ox_launch(0,"ox_asir");
  ox_execute_string(Pid," poly_factor(x^10-1);");
\end{verbatim}
\end{enumerate}
\newpage

\noindent
{\color{green} Data}: \\
\begin{tabular}{|c|c|}
\hline
{\color{red} TAG}& {\color{blue} BODY} \\ 
\hline
\end{tabular} \\
Two layers: {\color{green} OX message} layer. 
Layer of Command, CMO, and other data encodings.

\noindent
{\color{blue} Example 1}: \\
\begin{verbatim}
P = ox_launch(0,"ox_sm1");
ox_push_cmo(P,1);
ox_push_cmo(P,1);
ox_execute_string(P,"add");
ox_pop_cmo(P);
\end{verbatim}

{\color{green} CMO} is an encoding method based on XML like OpenMath.

\begin{tabular}{|c|c|c|}
\hline
{\tt OX\_DATA} & {\it CMO\_ZZ} & 1 \\ 
\hline
\end{tabular} \\
\begin{tabular}{|c|c|c|}
\hline
{\tt OX\_DATA} & {\it CMO\_ZZ} & 1 \\ 
\hline
\end{tabular} \\
\begin{tabular}{|c|c|c|}
\hline
{\tt OX\_DATA} & {\it CMO\_STRING} & add \\ 
\hline
\end{tabular} \\
\begin{tabular}{|c|c|}
\hline
{\tt OX\_COMMAND} & {\it SM\_executeString} \\ 
\hline
\end{tabular} \\
\begin{tabular}{|c|c|}
\hline
{\tt OX\_COMMAND} & {\it SM\_popCMO} \\ 
\hline
\end{tabular} \\
\htmladdnormallink{http://www.openxm.org}{http://www.openxm.org}
\newpage

\noindent
{\color{red} 2. Error Handling and Resetting} \\
\begin{verbatim}
P = ox_launch(0,"ox_asir");
ox_rpc(P,"fctr",1.2*x^2-1.21);
ox_dup_errors(P);
ox_pop_cmo(P);
\end{verbatim}
{\color{green}
\verb# [error([8,fctr: invalid argument])] #
}\\
{\color{blue}
Servers say nothing unless is is asked.
}
\newpage

\begin{verbatim}
P=ox_launch(0,"ox_asir");
ox_rpc(P,"fctr",x^1000-y^1000);
ox_reset(P);
\end{verbatim}

\setlength{\unitlength}{1cm}
\begin{picture}(20,7)(0,0)
\thicklines
\put(5,1.7){\line(1,0){7}}
\put(5,4.7){\line(3,-1){7}}
\put(12,1){\framebox(5,2.5){client}}
\put(1,4){\framebox(4,1.5){\color{blue} controller}}
\put(1,1){\framebox(4,1.5){\color{red} engine}}
\thinlines
\put(0,0.3){\framebox(6,6){}}
\put(1.5,-0.7){server}
\end{picture}
\newpage

\noindent
{\color{red} 4. e-Bateman project} (Electronic mathematical formula book)\\
First Step: \\
Gauss Hypergeometric function:
$$ {\color{blue} F(a,b,c;x)} = \sum_{n=1}^\infty
  \frac{(a)_n (b)_n}{(1)_n (c)_n} x^n
$$
where
$$ (a)_n = a(a+1) \cdots (a+n-1). $$
{\color{green}
$$ \log (1+x) = x F(1,1,2;-x) $$
$$ \arcsin x = x F(1/2,1/2,3/2;x^2) $$
}

\noindent
Appell's $F_1$:
$$ {\color{blue} F_1(a,b,b',c;x,y)} = \sum_{m,n=1}^\infty
  \frac{(a)_{m+n} (b)_m (b')_n}{(c)_{m+n}(1)_m (1)_n} x^m y^n.
$$
\newpage
Mathematical formula book, e.g.,
Erdelyi: {\color{green} Higher Transcendental Functions} \\
{\color{blue} Formula (type A)}\\
The solution space of the ordinary differential equation
$$ x(1-x) \frac{d^2f}{dx^2} -\left( c-(a+b+1)x \right) \frac{df}{dx} - a b f = 0$$
is spanned by
$$ F(a,b,c;x) = {\color{red}1} + O(x), \  
   x^{1-c} F(a,b,c;x) = {\color{red}x^{1-c}}+O(x^{2-c}))$$

when $c \not\in {\bf Z}$. \\
{\color{blue} Formula (type B)}\\
\begin{eqnarray*}
&\ & F(a_1, a_2, b_2;z) \, F(-a_1,-a_2,2-b_2;z)  \\
&+& \frac{z}{e_2}\, F'(a_1, a_2, b_2;z) \, F(-a_1,-a_2,2-b_2;z)  \\
&-& \frac{z}{e_2}\, F(a_1, a_2, b_2;z) \, F'(-a_1,-a_2,2-b_2;z)  \\
&-& \frac{a_1+a_2-e_2}{a_1 a_2 e_2}z^2\,
  F'(a_1, a_2, b_2;z)\,F'(-a_1,-a_2,2-b_2;z) \\
&=& 1
\end{eqnarray*}
where $e_2 = b_2-1$ and $a_1, a_2, e_2, e_2-a_2 \not\in {\bf Z}$.  \\
(generalization of $\sin^2 x + \cos^2 x =1$.)

\noindent
Project in progress: \\
We are trying to generate or verify type A formulas and type B formulas
for {\color{blue} GKZ hypergeometric systems}.

\begin{tabular}{|c|c|c|}
\hline
  & type A & type B \\ \hline
Algorithm &  {\color{red} OK} (SST book) &  in progress \\ \hline
Implementation & partially done & NO \\ \hline
\end{tabular}

\noindent
Our ox servers
{\tt ox\_asir}, {\tt ox\_sm1}, {\tt ox\_tigers}, {\tt ox\_gnuplot},
{\tt ox\_mathematica}, {\tt OpenMathproxy} (JavaClasses), {\tt ox\_m2}
are used to generate, verify and present formulas of type A
for GKZ hypergeometric systems.

\newpage

\noindent{\color{red} 5. Easy to try and evaluate distributed algorithms} \\

\noindent
{\color{green} Example 1} \\
Theorem (Cantor-Zassenhaus) \\
Let $f_1$ and $f_2$ be degree $d$ irreducible polynomials in $F_q[x]$.
For a random degree $2d-1$ polynomial $g \in F_q[x]$,
the chance of
$$ GCD(g^{(q^d-1)/2}-1,f_1 f_2) = f_1 \,\mbox{or}\, f_2 $$
is 
$$ \frac{1}{2}-\frac{1}{(2q)^d}. $$

\begin{picture}(20,14)(0,0)
\put(7,12){\framebox(4,1.5){client}}
\put(2,6){\framebox(4,1.5){server}}
%%\put(7,6){\framebox(4,1.5){server}}
\put(12,6){\framebox(4,1.5){server}}
\put(0,0){\framebox(4,1.5){server}}
\put(5,0){\framebox(4,1.5){server}}
\put(13.5,0){\framebox(4,1.5){server}}

\put(9,12){\vector(-1,-1){4.3}}
%%\put(9,12){\vector(0,-1){4.3}}
\put(9,12){\vector(1,-1){4.3}}
\put(4,6){\vector(-1,-2){2.2}}
\put(4,6){\vector(1,-2){2.2}}
\put(14,6){\vector(1,-3){1.4}}
\end{picture}

\begin{verbatim}
/* factorization of F */
/* E = degree of irreducible factors in F */
def c_z(F,E,Level)
{
  V = var(F); N = deg(F,V);
  if ( N == E ) return [F];
  M = field_order_ff(); K = idiv(N,E); L = [F];
  while ( 1 ) {
    /* gererate a random polynomial */
    W = monic_randpoly_ff(2*E,V);
    /* compute a power of the random polynomial */
    T = generic_pwrmod_ff(W,F,idiv(M^E-1,2));
    if ( !(W = T-1) ) continue;
    /* G = GCD(F,W^((M^E-1)/2)) mod F) */
    G = ugcd(F,W);
    if ( deg(G,V) && deg(G,V) < N ) {
      /* G is a non-trivial factor of F */
      if ( Level >= LevelMax ) {
        /* everything is done on this server */
        L1 = c_z(G,E,Level+1);
        L2 = c_z(sdiv(F,G),E,Level+1);
      } else {
        /* launch a server if necessary */
        if ( Proc1 < 0 ) Proc1 = ox_launch();
        /* send a request with Level = Level+1 */
        /* ox_c_z is a wrapper of c_z on the server */
        ox_cmo_rpc(Proc1,"ox_c_z",lmptop(G),E,
            setmod_ff(),Level+1);
        /* the rest is done on this server */
        L2 = c_z(sdiv(F,G),E,Level+1);
        L1 = map(simp_ff,ox_pop_cmo(Proc1));
      }
      return append(L1,L2);
    }
  }
}
\end{verbatim}
\newpage

\epsfxsize=17cm
\epsffile{cz.ps}

\noindent
{\color{blue} Performance of parallel CZ algorithm} \\
$d=1$, $k=200$ : product of $200$ linear forms. \\
$d=2$, $k=50$ : product of $50$ irreducible degree $2$ polynomials. \\

\newpage
{\color{green} Example 2} \\
Shoup's algorithm to multiply polynomials.  \\
{\color{green} Example 3} \\
Competitive Gr\"obner basis computation. \\
\newpage

\noindent
{\color{green} Example 3. Competitive Gr\"obner Basis Computation}
\begin{verbatim}
extern Proc1,Proc2$
Proc1 = -1$ Proc2 = -1$
/* G:set of polys; V:list of variables */
/* Mod: the Ground field GF(Mod); O:type of order */
def dgr(G,V,Mod,O)
{
  /* invoke servers if necessary */
  if ( Proc1 == -1 ) Proc1 = ox_launch();
  if ( Proc2 == -1 ) Proc2 = ox_launch();
  P = [Proc1,Proc2];
  map(ox_reset,P); /* reset servers */
  /* P0 executes Buchberger algorithm over GF(Mod) */
  ox_cmo_rpc(P[0],"dp_gr_mod_main",G,V,0,Mod,O);
  /* P1 executes F4 algorithm over GF(Mod) */
  ox_cmo_rpc(P[1],"dp_f4_mod_main",G,V,Mod,O);
  map(ox_push_cmd,P,262); /* 262 = OX_popCMO */
  F = ox_select(P); /* wait for data */
  /* F[0] is a server's id which is ready */
  R = ox_get(F[0]);
  if ( F[0] == P[0] ) { Win = "Buchberger"; Lose = P[1]; }
  else { Win = "F4"; Lose = P[0]; }
  ox_reset(Lose); /* reset the loser */
  return [Win,R];
}
\end{verbatim}
\newpage

\end{document}