Return to ohp.tex CVS log

Up to [local] / OpenXM / doc / ascm2001p

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

1.3     ! takayama    1: %% $OpenXM: OpenXM/doc/ascm2001p/ohp.tex,v 1.2 2001/09/23 08:31:18 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) \\
                    144: Let $f_1$ and $f_2$ be degree $d$ polynomials in $F_q[x]$.
                    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:
        !           208: {\color{green} Example 2} \\
        !           209: Shoup's algorithm to multyply polynomials.
        !           210: \newpage
        !           211:
1.1       takayama  212: \noindent
                    213: {\color{red} 5. e-Bateman project} \\
                    214: First Step: \\
                    215: Gauss Hypergeometric function:
                    216: $$ {\color{blue} F(a,b,c;x)} = \sum_{n=1}^\infty
                    217:   \frac{(a)_n (b)_n}{(1)_n}{(c)_n} x^n
                    218: $$
                    219: where
                    220: $$ (a)_n = a(a+1) \cdots (a+n-1). $$
1.2       takayama  221: $$ \log (1+x) = x F(1,1,2;-x) $$
                    222: $$ \arcsin x = x F(1/2,1/2,3/2;x^2) $$
1.1       takayama  223:
                    224: \noindent
                    225: Appell's $F_1$:
                    226: $$ {\color{blue} F_1(a,b,b',c;x,y)} = \sum_{m,n=1}^\infty
                    227:   \frac{(a)_{m+n} (b)_m (b')_n}{(c)_{m+n}(1)_m (1)_n} x^m y^n.
                    228: $$
                    229: \newpage
                    230: Mathematical formula book, e.g.,
                    231: Erdelyi: {\color{green} Higher Transcendental Functions} \\
                    232: {\color{blue} Formula (type A)}\\
                    233: The solution space of the ordinary differential equation
                    234: $$ x(1-x) \frac{d^2f}{dx^2} -\left( c-(a+b+1)x \right) \frac{df}{dx} - a b f = 0$$
                    235: is spanned by
1.3     ! takayama  236: $$ F(a,b,c;x) = {\color{red}1} + O(x), \
        !           237:    x^{1-c} F(a,b,c;x) = {\color{red}x^{1-c}}+O(x^{2-c}))$$
        !           238:
1.1       takayama  239: when $c \not\in {\bf Z}$. \\
                    240: {\color{blue} Formula (type B)}\\
                    241: \begin{eqnarray*}
                    242: &\ & F(a_1, a_2, b_2;z) \, F(-a_1,-a_2,2-b_2;z)  \\
                    243: &+& \frac{z}{e_2}\, F'(a_1, a_2, b_2;z) \, F(-a_1,-a_2,2-b_2;z)  \\
                    244: &-& \frac{z}{e_2}\, F(a_1, a_2, b_2;z) \, F'(-a_1,-a_2,2-b_2;z)  \\
                    245: &-& \frac{a_1+a_2-e_2}{a_1 a_2 e_2}z^2\,
                    246:   F'(a_1, a_2, b_2;z)\,F'(-a_1,-a_2,2-b_2;z) \\
                    247: &=& 1
                    248: \end{eqnarray*}
                    249: where $e_2 = b_2-1$ and $a_1, a_2, e_2, e_2-a_2 \not\in {\bf Z}$.  \\
                    250: (generalization of $\sin^2 x + \cos^2 x =1$.)
                    251:
                    252: \noindent
                    253: Project in progress: \\
                    254: We are trying to generate or verify type A formulas and type B formulas
                    255: for {\color{blue} GKZ hypergeometric systems}.
                    256:
                    257: \begin{tabular}{|c|c|c|}
                    258: \hline
                    259:   & type A & type B \\ \hline
                    260: Algorithm &  {\color{red} OK} (SST book) &  in progress \\ \hline
                    261: Implementation & partially done & NO \\ \hline
                    262: \end{tabular}
                    263:
                    264: \noindent
                    265: Our ox servers
                    266: {\tt ox\_asir}, {\tt ox\_sm1}, {\tt ox\_tigers}, {\tt ox\_gnuplot},
1.2       takayama  267: {\tt ox\_mathematica}, {\tt OMproxy} (JavaClasses), {\tt ox\_m2}
1.1       takayama  268: are used to generate, verify and present formulas of type A
                    269: for GKZ hypergeometric systems.
1.2       takayama  270:
                    271: \newpage
                    272: \noindent
                    273: {\color{green} Competitive Gr\"obner Basis Computation}
                    274: \begin{verbatim}
                    275: extern Proc1,Proc2$
                    276: Proc1 = -1$ Proc2 = -1$
                    277: /* G:set of polys; V:list of variables */
                    278: /* Mod: the Ground field GF(Mod); O:type of order */
                    279: def dgr(G,V,Mod,O)
                    280: {
                    281:   /* invoke servers if necessary */
                    282:   if ( Proc1 == -1 ) Proc1 = ox_launch();
                    283:   if ( Proc2 == -1 ) Proc2 = ox_launch();
                    284:   P = [Proc1,Proc2];
                    285:   map(ox_reset,P); /* reset servers */
                    286:   /* P0 executes Buchberger algorithm over GF(Mod) */
                    287:   ox_cmo_rpc(P[0],"dp_gr_mod_main",G,V,0,Mod,O);
                    288:   /* P1 executes F4 algorithm over GF(Mod) */
                    289:   ox_cmo_rpc(P[1],"dp_f4_mod_main",G,V,Mod,O);
                    290:   map(ox_push_cmd,P,262); /* 262 = OX_popCMO */
                    291:   F = ox_select(P); /* wait for data */
                    292:   /* F[0] is a server's id which is ready */
                    293:   R = ox_get(F[0]);
                    294:   if ( F[0] == P[0] ) { Win = "Buchberger"; Lose = P[1]; }
                    295:   else { Win = "F4"; Lose = P[0]; }
                    296:   ox_reset(Lose); /* reset the loser */
                    297:   return [Win,R];
                    298: }
                    299: \end{verbatim}
                    300: \newpage
1.1       takayama  301:
                    302: \end{document}