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