Return to ohp.tex CVS log

Up to [local] / OpenXM / doc / ascm2001p

Annotation of OpenXM/doc/ascm2001p/ohp.tex, Revision 1.4

1.4     ! takayama    1: %% $OpenXM: OpenXM/doc/ascm2001p/ohp.tex,v 1.3 2001/09/25 01:17:08 takayama Exp $
1.1       takayama    2: \documentclass{slides}
                      3: %%\documentclass[12pt]{article}
                      4: \usepackage{color}
                      5: \usepackage{epsfig}
                      6: \newcommand{\htmladdnormallink}[2]{#1}
                      7: \begin{document}
                      8: \noindent
                      9: {\color{green} Design and Implementation of OpenXM-RFC 100 and 101}
                     10:
                     11: \noindent
1.3       takayama   12: 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), \\
                     13: 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), \\
                     14: Y.Tamura ($BED(B $BB<(B $B!!(B $B63(B $B;N(B)\\
                     15: \htmladdnormallink{{\color{red}http://www.openxm.org}}{{\color{red}http://www.openxm.org}}
                     16:
1.1       takayama   17:
                     18: \newpage
                     19: \noindent
                     20: {\color{red} 1. Architecture} \\
                     21: Integrating (existing) mathematical software systems.
                     22:
                     23: Two main applications of the project \\
                     24: \begin{enumerate}
                     25: \item Providing an environment for interactive distributed computation.
                     26: {\color{blue} Risa/Asir}
1.3       takayama   27: (computer algebra system for general purpose,
                     28:  open source (c) Fujitsu, \\
                     29:  http://www.openxm.org, \\
                     30:  http://risa.cs.ehime-u.ac.jp, \\
                     31:  http://www.math.kobe-u.ac.jp/Asir/asir.html)
1.1       takayama   32: \item e-Bateman project
                     33: (Electronic version of higher transcendental functions of the 21st century)\\
                     34: 1st step: Generate and verify hypergeometric function identities.
                     35: \end{enumerate}
                     36: \newpage
                     37:
                     38: \noindent
                     39: OpenXM-RFC 100 \\
                     40: {\color{green} Control}: \\
                     41: \begin{enumerate}
                     42: \item Client-server model. Tree structure of processes.
                     43: \item Wrap (existing) mathematical software systems by the
                     44: OpenXM {\color{red} stackmachine}.
                     45: \item execute\_string
                     46: \begin{verbatim}
                     47:   P = ox_launch(0,"ox_asir");
                     48:   ox_execute_string(Pid," poly_factor(x^10-1);");
                     49: \end{verbatim}
                     50: \end{enumerate}
                     51: \newpage
                     52:
                     53: \noindent
                     54: {\color{green} Data}: \\
                     55: \begin{tabular}{|c|c|}
                     56: \hline
                     57: {\color{red} TAG}& {\color{blue} BODY} \\
                     58: \hline
                     59: \end{tabular} \\
                     60: Two layers: {\color{green} OX message} layer.
                     61: Layer of Command, CMO, and other data encodings.
                     62:
                     63: \noindent
                     64: {\color{blue} Example 1}: \\
                     65: \begin{verbatim}
                     66: P = ox_launch(0,"ox_sm1");
                     67: ox_push_cmo(P,1);
                     68: ox_push_cmo(P,1);
                     69: ox_execute_string(P,"add");
                     70: ox_pop_cmo(P);
                     71: \end{verbatim}
                     72:
                     73: {\color{green} CMO} is an encoding method based on XML like OpenMath.
                     74:
                     75: \begin{tabular}{|c|c|c|}
                     76: \hline
                     77: {\tt OX\_DATA} & {\it CMO\_ZZ} & 1 \\
                     78: \hline
                     79: \end{tabular} \\
                     80: \begin{tabular}{|c|c|c|}
                     81: \hline
                     82: {\tt OX\_DATA} & {\it CMO\_ZZ} & 1 \\
                     83: \hline
                     84: \end{tabular} \\
                     85: \begin{tabular}{|c|c|c|}
                     86: \hline
                     87: {\tt OX\_DATA} & {\it CMO\_STRING} & add \\
                     88: \hline
                     89: \end{tabular} \\
                     90: \begin{tabular}{|c|c|}
                     91: \hline
                     92: {\tt OX\_COMMAND} & {\it SM\_executeString} \\
                     93: \hline
                     94: \end{tabular} \\
                     95: \begin{tabular}{|c|c|}
                     96: \hline
                     97: {\tt OX\_COMMAND} & {\it SM\_popCMO} \\
                     98: \hline
                     99: \end{tabular} \\
                    100: \htmladdnormallink{http://www.openxm.org}{http://www.openxm.org}
                    101: \newpage
                    102:
                    103: \noindent
                    104: {\color{red} 2. Error Handling and Resetting} \\
                    105: \begin{verbatim}
                    106: P = ox_launch(0,"ox_asir");
                    107: ox_rpc(P,"fctr",1.2*x^2-1.21);
                    108: ox_dup_errors(P);
                    109: ox_pop_cmo(P);
                    110: \end{verbatim}
                    111: {\color{green}
                    112: \verb# [error([8,fctr: invalid argument])] #
                    113: }\\
                    114: {\color{blue}
                    115: Servers say nothing unless is is asked.
                    116: }
                    117: \newpage
                    118:
                    119: \begin{verbatim}
                    120: P=ox_launch(0,"ox_asir");
                    121: ox_rpc(P,"fctr",x^1000-y^1000);
                    122: ox_reset(P);
                    123: \end{verbatim}
                    124:
                    125: \setlength{\unitlength}{1cm}
                    126: \begin{picture}(20,7)(0,0)
                    127: \thicklines
                    128: \put(5,1.7){\line(1,0){7}}
                    129: \put(5,4.7){\line(3,-1){7}}
                    130: \put(12,1){\framebox(5,2.5){client}}
                    131: \put(1,4){\framebox(4,1.5){\color{blue} controller}}
                    132: \put(1,1){\framebox(4,1.5){\color{red} engine}}
                    133: \thinlines
                    134: \put(0,0.3){\framebox(6,6){}}
                    135: \put(1.5,-0.7){server}
                    136: \end{picture}
                    137: \newpage
                    138:
                    139: \noindent{\color{red} 4. Easy to try and evaluate distributed algorithms} \\
                    140:
                    141: \noindent
1.3       takayama  142: {\color{green} Example 1} \\
1.1       takayama  143: Theorem (Cantor-Zassenhaus) \\
1.4     ! takayama  144: Let $f_1$ and $f_2$ be degree $d$ irreducible polynomials in $F_q[x]$.
1.1       takayama  145: For a random degree $2d-1$ polynomial $g \in F_q[x]$,
                    146: the chance of
                    147: $$ GCD(g^{(q^d-1)/2}-1,f_1 f_2) = f_1 \,\mbox{or}\, f_2 $$
                    148: is
                    149: $$ \frac{1}{2}-\frac{1}{(2q)^d}. $$
                    150:
                    151: \begin{picture}(20,14)(0,0)
                    152: \put(7,12){\framebox(4,1.5){client}}
                    153: \put(2,6){\framebox(4,1.5){server}}
                    154: \put(7,6){\framebox(4,1.5){server}}
                    155: \put(12,6){\framebox(4,1.5){server}}
                    156: \put(0,0){\framebox(4,1.5){server}}
                    157: \put(5,0){\framebox(4,1.5){server}}
                    158: \put(13.5,0){\framebox(4,1.5){server}}
                    159:
                    160: \put(9,12){\vector(-1,-1){4.3}}
                    161: \put(9,12){\vector(0,-1){4.3}}
                    162: \put(9,12){\vector(1,-1){4.3}}
                    163: \put(4,6){\vector(-1,-2){2.2}}
                    164: \put(4,6){\vector(1,-2){2.2}}
                    165: \put(14,6){\vector(1,-3){1.4}}
                    166: \end{picture}
                    167:
                    168: \begin{verbatim}
                    169: /* factorization of F */
                    170: /* E = degree of irreducible factors in F */
                    171: def c_z(F,E,Level)
                    172: {
                    173:   V = var(F); N = deg(F,V);
                    174:   if ( N == E ) return [F];
                    175:   M = field_order_ff(); K = idiv(N,E); L = [F];
                    176:   while ( 1 ) {
                    177:     /* gererate a random polynomial */
                    178:     W = monic_randpoly_ff(2*E,V);
                    179:     /* compute a power of the random polynomial */
                    180:     T = generic_pwrmod_ff(W,F,idiv(M^E-1,2));
                    181:     if ( !(W = T-1) ) continue;
                    182:     /* G = GCD(F,W^((M^E-1)/2)) mod F) */
                    183:     G = ugcd(F,W);
                    184:     if ( deg(G,V) && deg(G,V) < N ) {
                    185:       /* G is a non-trivial factor of F */
                    186:       if ( Level >= LevelMax ) {
                    187:         /* everything is done on this server */
                    188:         L1 = c_z(G,E,Level+1);
                    189:         L2 = c_z(sdiv(F,G),E,Level+1);
                    190:       } else {
                    191:         /* launch a server if necessary */
                    192:         if ( Proc1 < 0 ) Proc1 = ox_launch();
                    193:         /* send a request with Level = Level+1 */
                    194:         /* ox_c_z is a wrapper of c_z on the server */
                    195:         ox_cmo_rpc(Proc1,"ox_c_z",lmptop(G),E,
                    196:             setmod_ff(),Level+1);
                    197:         /* the rest is done on this server */
                    198:         L2 = c_z(sdiv(F,G),E,Level+1);
                    199:         L1 = map(simp_ff,ox_pop_cmo(Proc1));
                    200:       }
                    201:       return append(L1,L2);
                    202:     }
                    203:   }
                    204: }
                    205: \end{verbatim}
                    206: \newpage
1.3       takayama  207:
1.4     ! takayama  208: \epsfxsize=17cm
        !           209: \epsffile{cz.ps}
        !           210:
        !           211: \noindent
        !           212: {\color{blue} Performance of parallel CZ algorithm} \\
        !           213: $d=1$, $k=200$ : product of $200$ linear forms. \\
        !           214: $d=2$, $k=50$ : product of $50$ irreducible degree $2$ polynomials. \\
        !           215:
        !           216: \newpage
1.3       takayama  217: {\color{green} Example 2} \\
1.4     ! takayama  218: Shoup's algorithm to multiply polynomials.  \\
        !           219: {\color{green} Example 3} \\
        !           220: Competitive Gr\"obner basis computation. \\
1.3       takayama  221: \newpage
                    222:
1.1       takayama  223: \noindent
1.4     ! takayama  224: {\color{red} 5. e-Bateman project} (Electronic mathematical formula book)\\
1.1       takayama  225: First Step: \\
                    226: Gauss Hypergeometric function:
                    227: $$ {\color{blue} F(a,b,c;x)} = \sum_{n=1}^\infty
1.4     ! takayama  228:   \frac{(a)_n (b)_n}{(1)_n (c)_n} x^n
1.1       takayama  229: $$
                    230: where
                    231: $$ (a)_n = a(a+1) \cdots (a+n-1). $$
1.4     ! takayama  232: {\color{green}
1.2       takayama  233: $$ \log (1+x) = x F(1,1,2;-x) $$
                    234: $$ \arcsin x = x F(1/2,1/2,3/2;x^2) $$
1.4     ! takayama  235: }
1.1       takayama  236:
                    237: \noindent
                    238: Appell's $F_1$:
                    239: $$ {\color{blue} F_1(a,b,b',c;x,y)} = \sum_{m,n=1}^\infty
                    240:   \frac{(a)_{m+n} (b)_m (b')_n}{(c)_{m+n}(1)_m (1)_n} x^m y^n.
                    241: $$
                    242: \newpage
                    243: Mathematical formula book, e.g.,
                    244: Erdelyi: {\color{green} Higher Transcendental Functions} \\
                    245: {\color{blue} Formula (type A)}\\
                    246: The solution space of the ordinary differential equation
                    247: $$ x(1-x) \frac{d^2f}{dx^2} -\left( c-(a+b+1)x \right) \frac{df}{dx} - a b f = 0$$
                    248: is spanned by
1.3       takayama  249: $$ F(a,b,c;x) = {\color{red}1} + O(x), \
                    250:    x^{1-c} F(a,b,c;x) = {\color{red}x^{1-c}}+O(x^{2-c}))$$
                    251:
1.1       takayama  252: when $c \not\in {\bf Z}$. \\
                    253: {\color{blue} Formula (type B)}\\
                    254: \begin{eqnarray*}
                    255: &\ & F(a_1, a_2, b_2;z) \, F(-a_1,-a_2,2-b_2;z)  \\
                    256: &+& \frac{z}{e_2}\, F'(a_1, a_2, b_2;z) \, F(-a_1,-a_2,2-b_2;z)  \\
                    257: &-& \frac{z}{e_2}\, F(a_1, a_2, b_2;z) \, F'(-a_1,-a_2,2-b_2;z)  \\
                    258: &-& \frac{a_1+a_2-e_2}{a_1 a_2 e_2}z^2\,
                    259:   F'(a_1, a_2, b_2;z)\,F'(-a_1,-a_2,2-b_2;z) \\
                    260: &=& 1
                    261: \end{eqnarray*}
                    262: where $e_2 = b_2-1$ and $a_1, a_2, e_2, e_2-a_2 \not\in {\bf Z}$.  \\
                    263: (generalization of $\sin^2 x + \cos^2 x =1$.)
                    264:
                    265: \noindent
                    266: Project in progress: \\
                    267: We are trying to generate or verify type A formulas and type B formulas
                    268: for {\color{blue} GKZ hypergeometric systems}.
                    269:
                    270: \begin{tabular}{|c|c|c|}
                    271: \hline
                    272:   & type A & type B \\ \hline
                    273: Algorithm &  {\color{red} OK} (SST book) &  in progress \\ \hline
                    274: Implementation & partially done & NO \\ \hline
                    275: \end{tabular}
                    276:
                    277: \noindent
                    278: Our ox servers
                    279: {\tt ox\_asir}, {\tt ox\_sm1}, {\tt ox\_tigers}, {\tt ox\_gnuplot},
1.2       takayama  280: {\tt ox\_mathematica}, {\tt OMproxy} (JavaClasses), {\tt ox\_m2}
1.1       takayama  281: are used to generate, verify and present formulas of type A
                    282: for GKZ hypergeometric systems.
1.2       takayama  283:
                    284: \newpage
                    285: \noindent
1.4     ! takayama  286: {\color{green} Example 3. Competitive Gr\"obner Basis Computation}
1.2       takayama  287: \begin{verbatim}
                    288: extern Proc1,Proc2$
                    289: Proc1 = -1$ Proc2 = -1$
                    290: /* G:set of polys; V:list of variables */
                    291: /* Mod: the Ground field GF(Mod); O:type of order */
                    292: def dgr(G,V,Mod,O)
                    293: {
                    294:   /* invoke servers if necessary */
                    295:   if ( Proc1 == -1 ) Proc1 = ox_launch();
                    296:   if ( Proc2 == -1 ) Proc2 = ox_launch();
                    297:   P = [Proc1,Proc2];
                    298:   map(ox_reset,P); /* reset servers */
                    299:   /* P0 executes Buchberger algorithm over GF(Mod) */
                    300:   ox_cmo_rpc(P[0],"dp_gr_mod_main",G,V,0,Mod,O);
                    301:   /* P1 executes F4 algorithm over GF(Mod) */
                    302:   ox_cmo_rpc(P[1],"dp_f4_mod_main",G,V,Mod,O);
                    303:   map(ox_push_cmd,P,262); /* 262 = OX_popCMO */
                    304:   F = ox_select(P); /* wait for data */
                    305:   /* F[0] is a server's id which is ready */
                    306:   R = ox_get(F[0]);
                    307:   if ( F[0] == P[0] ) { Win = "Buchberger"; Lose = P[1]; }
                    308:   else { Win = "F4"; Lose = P[0]; }
                    309:   ox_reset(Lose); /* reset the loser */
                    310:   return [Win,R];
                    311: }
                    312: \end{verbatim}
                    313: \newpage
1.1       takayama  314:
                    315: \end{document}