Annotation of OpenXM/doc/Papers/dag-noro.tex, Revision 1.4
1.4 ! noro 1: % $OpenXM: OpenXM/doc/Papers/dag-noro.tex,v 1.3 2001/10/12 02:22:17 noro Exp $
1.3 noro 2: \documentclass{slides}
3: \usepackage{color}
4: \usepackage{rgb}
5: \usepackage{graphicx}
6: \usepackage{epsfig}
1.1 noro 7: \newcommand{\qed}{$\Box$}
8: \newcommand{\mred}[1]{\smash{\mathop{\hbox{\rightarrowfill}}\limits_{\scriptstyle #1}}}
9: \newcommand{\tmred}[1]{\smash{\mathop{\hbox{\rightarrowfill}}\limits_{\scriptstyle #1}\limits^{\scriptstyle *}}}
10: \def\gr{Gr\"obner basis }
11: \def\st{\, s.t. \,}
12: \def\ni{\noindent}
13: \def\ve{\vfill\eject}
14: \textwidth 9.2in
15: \textheight 7.2in
16: \columnsep 0.33in
17: \topmargin -1in
1.4 ! noro 18: \def\tc{\color{red}}
! 19: \def\fbc{\bf\color{MediumBlue}}
! 20: \def\itc{\color{brown}}
! 21: \def\urlc{\bf\color{DarkGreen}}
! 22: \def\bc{\color{LightGoldenrod1}}
1.1 noro 23:
1.4 ! noro 24: \title{\tc A computer algebra system Risa/Asir and OpenXM}
1.1 noro 25:
1.3 noro 26: \author{Masayuki Noro\\ Kobe University, Japan}
1.1 noro 27: \begin{document}
28: \setlength{\parskip}{10pt}
29: \maketitle
1.3 noro 30:
31: %\begin{slide}{}
32: %\begin{center}
1.4 ! noro 33: %\fbox{\fbc \large Part I : OpenXM and Risa/Asir --- overview and history}
1.3 noro 34: %\end{center}
35: %\end{slide}
36:
37: %\begin{slide}{}
1.4 ! noro 38: %\fbox{\fbc Integration of mathematical software systems}
1.3 noro 39: %
40: %\begin{itemize}
41: %\item Data integration
42: %
43: %\begin{itemize}
1.4 ! noro 44: %\item OpenMath ({\urlc \tt http://www.openmath.org}) , MP [GRAY98]
1.3 noro 45: %\end{itemize}
46: %
47: %Standards for representing mathematical objects
48: %
49: %\item Control integration
50: %
51: %\begin{itemize}
52: %\item MCP [WANG99], OMEI [LIAO01]
53: %\end{itemize}
54: %
55: %Protocols for remote subroutine calls or session management
56: %
57: %\item Combination of two integrations
58: %
59: %\begin{itemize}
60: %\item MathLink, OpenMath+MCP, MP+MCP
61: %
1.4 ! noro 62: %and OpenXM ({\urlc \tt http://www.openxm.org})
1.3 noro 63: %\end{itemize}
64: %
65: %Both are necessary for practical implementation
66: %
67: %\end{itemize}
68: %\end{slide}
69: \begin{slide}{}
1.4 ! noro 70: \fbox{\fbc A computer algebra system Risa/Asir}
1.3 noro 71:
1.4 ! noro 72: ({\urlc \tt http://www.math.kobe-u.ac.jp/Asir/asir.html})
1.3 noro 73:
74: \begin{itemize}
1.4 ! noro 75: \item {\itc Software mainly for polynomial computation}
1.3 noro 76:
1.4 ! noro 77: \item {\itc User language with C-like syntax}
1.3 noro 78:
79: C language without type declaration, with list processing
80:
1.4 ! noro 81: \item {\itc Builtin {\tt gdb}-like debugger for user programs}
1.3 noro 82:
1.4 ! noro 83: \item {\itc Open source}
1.3 noro 84:
85: Whole source tree is available via CVS
86:
1.4 ! noro 87: The latest version : see {\urlc \tt http://www.openxm.org}
1.3 noro 88:
1.4 ! noro 89: \item {\itc OpenXM interface}
1.3 noro 90:
91: \begin{itemize}
92: \item OpenXM
93:
94: An infrastructure for exchanging mathematical data
95: \item Risa/Asir is a main client in OpenXM package.
96: \item An OpenXM server {\tt ox\_asir}
97: \item A library with OpenXM library interface {\tt libasir.a}
98: \end{itemize}
99: \end{itemize}
100: \end{slide}
101:
102: \begin{slide}{}
1.4 ! noro 103: \fbox{\fbc Goal of developing Risa/Asir}
1.3 noro 104:
105: \begin{itemize}
1.4 ! noro 106: \item {\itc Testing new algorithms}
1.3 noro 107:
108: \begin{itemize}
109: \item Development started in Fujitsu labs
110:
111: Polynomial factorization, Groebner basis related computation,
112: cryptosystems , quantifier elimination , $\ldots$
113: \end{itemize}
114:
1.4 ! noro 115: \item {\itc To be a general purpose, open system}
1.3 noro 116:
117: Since 1997, we have been developing OpenXM package
118: containing various servers and clients
119:
120: Risa/Asir is a component of OpenXM
121:
1.4 ! noro 122: \item {\itc Environment for parallel and distributed computation}
1.3 noro 123:
124: \end{itemize}
125: \end{slide}
126:
127: %\begin{slide}{}
1.4 ! noro 128: %\fbox{\fbc Capability for polynomial computation}
1.3 noro 129: %
130: %\begin{itemize}
131: %\item Fundamental polynomial arithmetics
132: %
133: %recursive representation and distributed representation
134: %
135: %\item Polynomial factorization
136: %
137: %\begin{itemize}
138: %\item Univariate : over {\bf Q}, algebraic number fields and finite fields
139: %
140: %\item Multivariate : over {\bf Q}
141: %\end{itemize}
142: %
143: %\item Groebner basis computation
144: %
145: %\begin{itemize}
146: %\item Buchberger and $F_4$ [FAUG99] algorithm
147: %
148: %\item Change of ordering/RUR [ROUI96] of 0-dimensional ideals
149: %
150: %\item Primary ideal decomposition
151: %
152: %\item Computation of $b$-function (in Weyl Algebra)
153: %\end{itemize}
154: %\end{itemize}
155: %\end{slide}
156:
157: \begin{slide}{}
1.4 ! noro 158: \fbox{\fbc History of development : Polynomial factorization}
1.3 noro 159:
160: \begin{itemize}
1.4 ! noro 161: \item {\itc 1989}
1.3 noro 162:
163: Start of Risa/Asir with Boehm's conservative GC
164:
1.4 ! noro 165: ({\urlc \tt http://www.hpl.hp.com/personal/Hans\_Boehm/gc})
1.3 noro 166:
1.4 ! noro 167: \item {\itc 1989-1992}
1.3 noro 168:
169: Univariate and multivariate factorizers over {\bf Q}
170:
1.4 ! noro 171: \item {\itc 1992-1994}
1.3 noro 172:
173: Univariate factorization over algebraic number fields
174:
175: Intensive use of successive extension, non-squarefree norms
176:
1.4 ! noro 177: \item {\itc 1996-1998}
1.3 noro 178:
179: Univariate factorization over large finite fields
180:
181: Motivated by a reseach project in Fujitsu on cryptography
182:
1.4 ! noro 183: \item {\itc 2000-current}
1.3 noro 184:
185: Multivariate factorization over small finite fields (in progress)
186: \end{itemize}
187: \end{slide}
188:
189: \begin{slide}{}
1.4 ! noro 190: \fbox{\fbc History of development : Groebner basis}
1.3 noro 191:
192: \begin{itemize}
1.4 ! noro 193: \item {\itc 1992-1994}
1.3 noro 194:
195: User language $\Rightarrow$ C version; trace lifting [TRAV88]
196:
1.4 ! noro 197: \item {\itc 1994-1996}
1.3 noro 198:
199: Trace lifting with homogenization
200:
201: Omitting GB check by compatible prime [NOYO99]
202:
203: Modular change of ordering/RUR[ROUI96] [NOYO99]
204:
205: Primary ideal decomposition [SHYO96]
206:
1.4 ! noro 207: \item {\itc 1996-1998}
1.3 noro 208:
209: Efficient content reduction during NF computation [NORO97]
210: Solved {\it McKay} system for the first time
211:
1.4 ! noro 212: \item {\itc 1998-2000}
1.3 noro 213:
214: Test implementation of $F_4$ [FAUG99]
215:
1.4 ! noro 216: \item {\itc 2000-current}
1.3 noro 217:
218: Buchberger algorithm in Weyl algebra
219:
220: Efficient $b$-function computation[OAKU97] by a modular method
221: \end{itemize}
222: \end{slide}
223:
224: \begin{slide}{}
1.4 ! noro 225: \fbox{\fbc Timing data --- Factorization}
1.3 noro 226:
1.4 ! noro 227: \underline{\itc Univariate; over {\bf Q}}
1.3 noro 228:
229: $N_i$ : a norm of a polynomial, $\deg(N_i) = i$
230: \begin{center}
231: \begin{tabular}{|c||c|c|c|c|} \hline
232: & $N_{105}$ & $N_{120}$ & $N_{168}$ & $N_{210}$ \\ \hline
233: Asir & 0.86 & 59 & 840 & hard \\ \hline
234: Asir NormFactor & 1.6 & 2.2& 6.1& hard \\ \hline
235: %Singular& hard? & hard?& hard? & hard? \\ \hline
236: CoCoA 4 & 0.2 & 7.1 & 16 & 0.5 \\ \hline\hline
237: NTL-5.2 & 0.16 & 0.9 & 1.4 & 0.4 \\ \hline
238: \end{tabular}
239: \end{center}
240:
1.4 ! noro 241: \underline{\itc Multivariate; over {\bf Q}}
1.3 noro 242:
243: $W_{i,j,k} = Wang[i]\cdot Wang[j]\cdot Wang[k]$ in {\tt asir2000/lib/fctrdata}
244: \begin{center}
245: \begin{tabular}{|c||c|c|c|c|c|} \hline
246: & $W_{1,2,3}$ & $W_{4,5,6}$ & $W_{7,8,9}$ & $W_{10,11,12}$ & $W_{13,14,15}$ \\ \hline
247: Asir & 0.2 & 4.7 & 14 & 17 & 0.4 \\ \hline
248: %Singular& $>$15min & --- & ---& ---& ---\\ \hline
249: CoCoA 4 & 5.2 & $>$15min & $>$15min & $>$15min & 117 \\ \hline\hline
250: Mathematica 4& 0.2 & 16 & 23 & 36 & 1.1 \\ \hline
251: Maple 7& 0.5 & 18 & 967 & 48 & 1.3 \\ \hline
252: \end{tabular}
253: \end{center}
254:
255: %--- : not tested
256: \end{slide}
257:
258: \begin{slide}{}
1.4 ! noro 259: \fbox{\fbc Timing data --- DRL Groebner basis computation}
1.3 noro 260:
1.4 ! noro 261: \underline{\itc Over $GF(32003)$}
1.3 noro 262: \begin{center}
263: \begin{tabular}{|c||c|c|c|c|c|c|c|} \hline
264: & $C_7$ & $C_8$ & $K_7$ & $K_8$ & $K_9$ & $K_{10}$ & $K_{11}$ \\ \hline
265: Asir $Buchberger$ & 31 & 1687 & 2.6 & 27 & 294 & 4309 & --- \\ \hline
266: Singular & 8.7 & 278 & 0.6 & 5.6 & 54 & 508 & 5510 \\ \hline
267: CoCoA 4 & 241 & $>$ 5h & 3.8 & 35 & 402 &7021 & --- \\ \hline\hline
268: Asir $F_4$ & 5.3 & 129 & 0.5 & 4.5 & 31 & 273 & 2641 \\ \hline
269: FGb(estimated) & 0.9 & 23 & 0.1 & 0.8 & 6 & 51 & 366 \\ \hline
270: \end{tabular}
271: \end{center}
272:
1.4 ! noro 273: \underline{\itc Over {\bf Q}}
1.3 noro 274:
275: \begin{center}
276: \begin{tabular}{|c||c|c|c|c|c|} \hline
277: & $C_7$ & $Homog. C_7$ & $K_7$ & $K_8$ & $McKay$ \\ \hline
278: Asir $Buchberger$ & 389 & 594 & 29 & 299 & 34950 \\ \hline
279: Singular & --- & 15247 & 7.6 & 79 & $>$ 20h \\ \hline
280: CoCoA 4 & --- & 13227 & 57 & 709 & --- \\ \hline\hline
281: Asir $F_4$ & 989 & 456 & 90 & 991 & 4939 \\ \hline
282: FGb(estimated) & 8 &11 & 0.6 & 5 & 10 \\ \hline
283: \end{tabular}
284: \end{center}
285: --- : not tested
286: \end{slide}
287:
288: \begin{slide}{}
1.4 ! noro 289: \fbox{\fbc Summary of performance}
1.3 noro 290:
291: \begin{itemize}
1.4 ! noro 292: \item {\itc Factorizer}
1.3 noro 293:
294: \begin{itemize}
295: \item Multivariate : reasonable performance
296:
297: \item Univariate : obsoleted by M. van Hoeij's new algorithm [HOEI00]
298: \end{itemize}
299:
1.4 ! noro 300: \item {\itc Groebner basis computation}
1.3 noro 301:
302: \begin{itemize}
303: \item Buchberger
304:
305: Singular shows nice perfomance
306:
307: Trace lifting is efficient in some cases over {\bf Q}
308:
309: \item $F_4$
310:
311: FGb is much faster than Risa/Asir
312:
313: But we observe that {\it McKay} is computed efficiently by $F_4$
314: \end{itemize}
315: \end{itemize}
316:
317: \end{slide}
318:
319: \begin{slide}{}
1.4 ! noro 320: \fbox{\fbc What is the merit to use Risa/Asir?}
1.3 noro 321:
322: \begin{itemize}
1.4 ! noro 323: \item {\itc Total performance is not excellent, but not bad}
1.3 noro 324:
1.4 ! noro 325: \item {\itc A completely open system}
1.3 noro 326:
327: The whole source is available
328:
1.4 ! noro 329: \item {\itc It serves as a test bench to try new ideas}
! 330:
! 331: Interactive debugger is very useful
! 332:
! 333: \item {\itc Interface compliant to OpenXM RFC-100}
1.3 noro 334:
335: The interface is fully documented
336:
337: \end{itemize}
338:
339: \end{slide}
340:
341:
342: %\begin{slide}{}
1.4 ! noro 343: %\fbox{\fbc CMO = Serialized representation of mathematical object}
1.3 noro 344: %
345: %\begin{itemize}
346: %\item primitive data
347: %\begin{eqnarray*}
348: %\mbox{Integer32} &:& ({\tt CMO\_INT32}, {\sl int32}\ \mbox{n}) \\
349: %\mbox{Cstring}&:& ({\tt CMO\_STRING},{\sl int32}\, \mbox{ n}, {\sl string}\, \mbox{s}) \\
350: %\mbox{List} &:& ({\tt CMO\_LIST}, {\sl int32}\, len, ob[0], \ldots,ob[m-1])
351: %\end{eqnarray*}
352: %
353: %\item numbers and polynomials
354: %\begin{eqnarray*}
355: %\mbox{ZZ} &:& ({\tt CMO\_ZZ},{\sl int32}\, {\rm f}, {\sl byte}\, \mbox{a[1]}, \ldots
356: %{\sl byte}\, \mbox{a[$|$f$|$]} ) \\
357: %\mbox{Monomial32}&:& ({\tt CMO\_MONOMIAL32}, n, \mbox{e[1]}, \ldots, \mbox{e[n]}, \mbox{Coef}) \\
358: %\mbox{Coef}&:& \mbox{ZZ} | \mbox{Integer32} \\
359: %\mbox{Dpolynomial}&:& ({\tt CMO\_DISTRIBUTED\_POLYNOMIAL},\\
360: % & & m, \mbox{DringDefinition}, \mbox{Monomial32}, \ldots)\\
361: %\mbox{DringDefinition}
362: % &:& \mbox{DMS of N variables} \\
363: % & & ({\tt CMO\_RING\_BY\_NAME}, name) \\
364: % & & ({\tt CMO\_DMS\_GENERIC}) \\
365: %\end{eqnarray*}
366: %\end{itemize}
367: %\end{slide}
368: %
369: %\begin{slide}{}
1.4 ! noro 370: %\fbox{\fbc Stack based communication}
1.3 noro 371: %
372: %\begin{itemize}
373: %\item Data arrived a client
374: %
375: %Pushed to the stack
376: %
377: %\item Result
378: %
379: %Pushd to the stack
380: %
381: %Written to the stream when requested by a command
382: %
383: %\item The reason why we use the stack
384: %
385: %\begin{itemize}
386: %\item Stack = I/O buffer for (possibly large) objects
387: %
388: %Multiple requests can be sent before their execution
389: %
390: %A server does not get stuck in sending results
391: %\end{itemize}
392: %\end{itemize}
393: %\end{slide}
394:
395: \begin{slide}{}
1.4 ! noro 396: \fbox{\fbc OpenXM (Open message eXchange protocol for Mathematics) }
1.3 noro 397:
398: \begin{itemize}
1.4 ! noro 399: \item {\itc An environment for parallel distributed computation}
1.3 noro 400:
401: Both for interactive, non-interactive environment
402:
1.4 ! noro 403: \item {\itc OpenXM RFC-100 = Client-server architecture}
1.3 noro 404:
405: Client $\Leftarrow$ OX (OpenXM) message $\Rightarrow$ Server
406:
407: OX (OpenXM) message : command and data
408:
1.4 ! noro 409: \item {\itc Data}
1.3 noro 410:
411: Encoding : CMO (Common Mathematical Object format)
412:
413: Serialized representation of mathematical object
414:
415: --- Main idea was borrowed from OpenMath
416:
1.4 ! noro 417: ({\urlc \tt http://www.openmath.org})
1.3 noro 418:
1.4 ! noro 419: \item {\itc Command}
1.3 noro 420:
421: stack machine command --- server is a stackmachine
422:
423: + server's own command sequences --- hybrid server
424: \end{itemize}
425: \end{slide}
426:
427: \begin{slide}{}
1.4 ! noro 428: \fbox{\fbc Example of distributed computation --- $F_4$ vs. $Buchberger$ }
1.3 noro 429:
430: \begin{verbatim}
431: /* competitive Gbase computation over GF(M) */
432: /* Cf. A.28 in SINGULAR Manual */
1.4 ! noro 433: /* Process list is specified as buch_vs_f4_mod(...|proc=P) */
! 434: def buch_vs_f4_mod(G,V,M,O)
1.3 noro 435: {
436: P = getopt(proc);
437: if ( type(P) == -1 ) return dp_f4_mod_main(G,V,M,O);
438: P0 = P[0]; P1 = P[1]; P = [P0,P1];
1.4 ! noro 439: map(ox_reset,P); /* resets the both servers */
! 440: ox_cmo_rpc(P0,"dp_f4_mod_main",G,V,M,O); /* for F4 */
! 441: ox_cmo_rpc(P1,"dp_gr_mod_main",G,V,0,M,O); /* for Buchberger */
1.3 noro 442: map(ox_push_cmd,P,262); /* 262 = OX_popCMO */
1.4 ! noro 443: F = ox_select(P); /* waits a server to return the result */
! 444: R = ox_get(F[0]); /* gets the result from the winner */
1.3 noro 445: if ( F[0] == P0 ) { Win = "F4"; Lose = P1;}
446: else { Win = "Buchberger"; Lose = P0; }
447: ox_reset(Lose); /* simply resets the loser */
448: return [Win,R];
449: }
450: \end{verbatim}
451: \end{slide}
452:
453: \begin{slide}{}
1.4 ! noro 454: \fbox{\fbc Real speedup by parallelism --- polynomial multiplication}
! 455:
! 456: {\itc Product of dense univariate polynomials with 3000bit coefficients}
! 457:
! 458: {\itc Algorithm : FFT+Chinese remainder (by Shoup)}
! 459:
! 460: \epsfxsize=20cm
! 461: \epsffile{3k.ps}
! 462:
! 463: {\itc Communication cost}
! 464:
! 465: \begin{itemize}
! 466: \item $O(n{\color{red}\log L})$ with server-server communication (OX-RFC102)
! 467: \item $O(n{\color{red}L})$ without server-server communication (OX-RFC100)
! 468: \end{itemize}
! 469: ($L$: number of processes, $n$: degree)
! 470:
! 471: \end{slide}
! 472:
! 473: \begin{slide}{}
! 474: \fbox{\fbc References}
1.3 noro 475:
476: [BERN97] L. Bernardin, On square-free factorization of
477: multivariate polynomials over a finite field, Theoretical
478: Computer Science 187 (1997), 105-116.
479:
480: [FAUG99] J.C. Faug\`ere,
481: A new efficient algorithm for computing Groebner bases ($F_4$),
482: Journal of Pure and Applied Algebra (139) 1-3 (1999), 61-88.
483:
484: [GRAY98] S. Gray et al,
485: Design and Implementation of MP, A Protocol for Efficient Exchange of
486: Mathematical Expression,
487: J. Symb. Comp. {\bf 25} (1998), 213-238.
488:
489: [HOEI00] M. van Hoeij, Factoring polynomials and the knapsack problem,
490: to appear in Journal of Number Theory (2000).
491:
492: [LIAO01] W. Liao et al,
493: OMEI: An Open Mathematical Engine Interface,
494: Proc. ASCM2001 (2001), 82-91.
495: [NORO97] M. Noro, J. McKay,
496: Computation of replicable functions on Risa/Asir.
497: Proc. PASCO'97, ACM Press (1997), 130-138.
498: \end{slide}
499:
500: \begin{slide}{}
501:
502: [NOYO99] M. Noro, K. Yokoyama,
503: A Modular Method to Compute the Rational Univariate
504: Representation of Zero-Dimensional Ideals.
505: J. Symb. Comp. {\bf 28}/1 (1999), 243-263.
506:
507: [OAKU97] T. Oaku, Algorithms for $b$-functions, restrictions and algebraic
508: local cohomology groups of $D$-modules.
509: Advances in Applied Mathematics, 19 (1997), 61-105.
510:
511: [ROUI96] F. Rouillier,
512: R\'esolution des syst\`emes z\'ero-dimensionnels.
513: Doctoral Thesis(1996), University of Rennes I, France.
514:
515: [SHYO96] T. Shimoyama, K. Yokoyama, Localization and Primary Decomposition of Polynomial Ideals. J. Symb. Comp. {\bf 22} (1996), 247-277.
516:
517: [TRAV88] C. Traverso, \gr trace algorithms. Proc. ISSAC '88 (LNCS 358), 125-138.
518:
519: [WANG99] P. S. Wang,
520: Design and Protocol for Internet Accessible Mathematical Computation,
521: Proc. ISSAC '99 (1999), 291-298.
522: \end{slide}
1.1 noro 523: \end{document}
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to dag-noro.tex CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM / doc / Papers