Annotation of OpenXM/doc/ascm2001p/ohp.tex, Revision 1.5
1.5 ! takayama 1: %% $OpenXM: OpenXM/doc/ascm2001p/ohp.tex,v 1.4 2001/09/25 02:28:27 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}
1.5 ! takayama 47: Pid = ox_launch(0,"ox_asir");
1.1 takayama 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:
1.5 ! takayama 139: \noindent
! 140: {\color{red} 4. e-Bateman project} (Electronic mathematical formula book)\\
! 141: First Step: \\
! 142: Gauss Hypergeometric function:
! 143: $$ {\color{blue} F(a,b,c;x)} = \sum_{n=1}^\infty
! 144: \frac{(a)_n (b)_n}{(1)_n (c)_n} x^n
! 145: $$
! 146: where
! 147: $$ (a)_n = a(a+1) \cdots (a+n-1). $$
! 148: {\color{green}
! 149: $$ \log (1+x) = x F(1,1,2;-x) $$
! 150: $$ \arcsin x = x F(1/2,1/2,3/2;x^2) $$
! 151: }
! 152:
! 153: \noindent
! 154: Appell's $F_1$:
! 155: $$ {\color{blue} F_1(a,b,b',c;x,y)} = \sum_{m,n=1}^\infty
! 156: \frac{(a)_{m+n} (b)_m (b')_n}{(c)_{m+n}(1)_m (1)_n} x^m y^n.
! 157: $$
! 158: \newpage
! 159: Mathematical formula book, e.g.,
! 160: Erdelyi: {\color{green} Higher Transcendental Functions} \\
! 161: {\color{blue} Formula (type A)}\\
! 162: The solution space of the ordinary differential equation
! 163: $$ x(1-x) \frac{d^2f}{dx^2} -\left( c-(a+b+1)x \right) \frac{df}{dx} - a b f = 0$$
! 164: is spanned by
! 165: $$ F(a,b,c;x) = {\color{red}1} + O(x), \
! 166: x^{1-c} F(a,b,c;x) = {\color{red}x^{1-c}}+O(x^{2-c}))$$
! 167:
! 168: when $c \not\in {\bf Z}$. \\
! 169: {\color{blue} Formula (type B)}\\
! 170: \begin{eqnarray*}
! 171: &\ & F(a_1, a_2, b_2;z) \, F(-a_1,-a_2,2-b_2;z) \\
! 172: &+& \frac{z}{e_2}\, F'(a_1, a_2, b_2;z) \, F(-a_1,-a_2,2-b_2;z) \\
! 173: &-& \frac{z}{e_2}\, F(a_1, a_2, b_2;z) \, F'(-a_1,-a_2,2-b_2;z) \\
! 174: &-& \frac{a_1+a_2-e_2}{a_1 a_2 e_2}z^2\,
! 175: F'(a_1, a_2, b_2;z)\,F'(-a_1,-a_2,2-b_2;z) \\
! 176: &=& 1
! 177: \end{eqnarray*}
! 178: where $e_2 = b_2-1$ and $a_1, a_2, e_2, e_2-a_2 \not\in {\bf Z}$. \\
! 179: (generalization of $\sin^2 x + \cos^2 x =1$.)
! 180:
! 181: \noindent
! 182: Project in progress: \\
! 183: We are trying to generate or verify type A formulas and type B formulas
! 184: for {\color{blue} GKZ hypergeometric systems}.
! 185:
! 186: \begin{tabular}{|c|c|c|}
! 187: \hline
! 188: & type A & type B \\ \hline
! 189: Algorithm & {\color{red} OK} (SST book) & in progress \\ \hline
! 190: Implementation & partially done & NO \\ \hline
! 191: \end{tabular}
! 192:
! 193: \noindent
! 194: Our ox servers
! 195: {\tt ox\_asir}, {\tt ox\_sm1}, {\tt ox\_tigers}, {\tt ox\_gnuplot},
! 196: {\tt ox\_mathematica}, {\tt OpenMathproxy} (JavaClasses), {\tt ox\_m2}
! 197: are used to generate, verify and present formulas of type A
! 198: for GKZ hypergeometric systems.
! 199:
! 200: \newpage
! 201:
! 202: \noindent{\color{red} 5. Easy to try and evaluate distributed algorithms} \\
1.1 takayama 203:
204: \noindent
1.3 takayama 205: {\color{green} Example 1} \\
1.1 takayama 206: Theorem (Cantor-Zassenhaus) \\
1.4 takayama 207: Let $f_1$ and $f_2$ be degree $d$ irreducible polynomials in $F_q[x]$.
1.1 takayama 208: For a random degree $2d-1$ polynomial $g \in F_q[x]$,
209: the chance of
210: $$ GCD(g^{(q^d-1)/2}-1,f_1 f_2) = f_1 \,\mbox{or}\, f_2 $$
211: is
212: $$ \frac{1}{2}-\frac{1}{(2q)^d}. $$
213:
214: \begin{picture}(20,14)(0,0)
215: \put(7,12){\framebox(4,1.5){client}}
216: \put(2,6){\framebox(4,1.5){server}}
1.5 ! takayama 217: %%\put(7,6){\framebox(4,1.5){server}}
1.1 takayama 218: \put(12,6){\framebox(4,1.5){server}}
219: \put(0,0){\framebox(4,1.5){server}}
220: \put(5,0){\framebox(4,1.5){server}}
221: \put(13.5,0){\framebox(4,1.5){server}}
222:
223: \put(9,12){\vector(-1,-1){4.3}}
1.5 ! takayama 224: %%\put(9,12){\vector(0,-1){4.3}}
1.1 takayama 225: \put(9,12){\vector(1,-1){4.3}}
226: \put(4,6){\vector(-1,-2){2.2}}
227: \put(4,6){\vector(1,-2){2.2}}
228: \put(14,6){\vector(1,-3){1.4}}
229: \end{picture}
230:
231: \begin{verbatim}
232: /* factorization of F */
233: /* E = degree of irreducible factors in F */
234: def c_z(F,E,Level)
235: {
236: V = var(F); N = deg(F,V);
237: if ( N == E ) return [F];
238: M = field_order_ff(); K = idiv(N,E); L = [F];
239: while ( 1 ) {
240: /* gererate a random polynomial */
241: W = monic_randpoly_ff(2*E,V);
242: /* compute a power of the random polynomial */
243: T = generic_pwrmod_ff(W,F,idiv(M^E-1,2));
244: if ( !(W = T-1) ) continue;
245: /* G = GCD(F,W^((M^E-1)/2)) mod F) */
246: G = ugcd(F,W);
247: if ( deg(G,V) && deg(G,V) < N ) {
248: /* G is a non-trivial factor of F */
249: if ( Level >= LevelMax ) {
250: /* everything is done on this server */
251: L1 = c_z(G,E,Level+1);
252: L2 = c_z(sdiv(F,G),E,Level+1);
253: } else {
254: /* launch a server if necessary */
255: if ( Proc1 < 0 ) Proc1 = ox_launch();
256: /* send a request with Level = Level+1 */
257: /* ox_c_z is a wrapper of c_z on the server */
258: ox_cmo_rpc(Proc1,"ox_c_z",lmptop(G),E,
259: setmod_ff(),Level+1);
260: /* the rest is done on this server */
261: L2 = c_z(sdiv(F,G),E,Level+1);
262: L1 = map(simp_ff,ox_pop_cmo(Proc1));
263: }
264: return append(L1,L2);
265: }
266: }
267: }
268: \end{verbatim}
269: \newpage
1.3 takayama 270:
1.4 takayama 271: \epsfxsize=17cm
272: \epsffile{cz.ps}
273:
274: \noindent
275: {\color{blue} Performance of parallel CZ algorithm} \\
276: $d=1$, $k=200$ : product of $200$ linear forms. \\
277: $d=2$, $k=50$ : product of $50$ irreducible degree $2$ polynomials. \\
278:
279: \newpage
1.3 takayama 280: {\color{green} Example 2} \\
1.4 takayama 281: Shoup's algorithm to multiply polynomials. \\
282: {\color{green} Example 3} \\
283: Competitive Gr\"obner basis computation. \\
1.3 takayama 284: \newpage
285:
1.2 takayama 286: \noindent
1.4 takayama 287: {\color{green} Example 3. Competitive Gr\"obner Basis Computation}
1.2 takayama 288: \begin{verbatim}
289: extern Proc1,Proc2$
290: Proc1 = -1$ Proc2 = -1$
291: /* G:set of polys; V:list of variables */
292: /* Mod: the Ground field GF(Mod); O:type of order */
293: def dgr(G,V,Mod,O)
294: {
295: /* invoke servers if necessary */
296: if ( Proc1 == -1 ) Proc1 = ox_launch();
297: if ( Proc2 == -1 ) Proc2 = ox_launch();
298: P = [Proc1,Proc2];
299: map(ox_reset,P); /* reset servers */
300: /* P0 executes Buchberger algorithm over GF(Mod) */
301: ox_cmo_rpc(P[0],"dp_gr_mod_main",G,V,0,Mod,O);
302: /* P1 executes F4 algorithm over GF(Mod) */
303: ox_cmo_rpc(P[1],"dp_f4_mod_main",G,V,Mod,O);
304: map(ox_push_cmd,P,262); /* 262 = OX_popCMO */
305: F = ox_select(P); /* wait for data */
306: /* F[0] is a server's id which is ready */
307: R = ox_get(F[0]);
308: if ( F[0] == P[0] ) { Win = "Buchberger"; Lose = P[1]; }
309: else { Win = "F4"; Lose = P[0]; }
310: ox_reset(Lose); /* reset the loser */
311: return [Win,R];
312: }
313: \end{verbatim}
314: \newpage
1.1 takayama 315:
316: \end{document}
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to ohp.tex CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM / doc / ascm2001p