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}
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>