Annotation of OpenXM/doc/Papers/dagb-noro.tex, Revision 1.9
1.9 ! noro 1: % $OpenXM: OpenXM/doc/Papers/dagb-noro.tex,v 1.8 2001/10/11 01:34:42 noro Exp $
1.1 noro 2: \setlength{\parskip}{10pt}
3:
4: \begin{slide}{}
1.2 noro 5: \begin{center}
1.5 noro 6: \fbox{\large Part I : OpenXM and Risa/Asir --- overview and history}
1.2 noro 7: \end{center}
8: \end{slide}
9:
1.8 noro 10: %\begin{slide}{}
11: %\fbox{Integration of mathematical software systems}
12: %
13: %\begin{itemize}
14: %\item Data integration
15: %
16: %\begin{itemize}
17: %\item OpenMath ({\tt http://www.openmath.org}) , MP [GRAY98]
18: %\end{itemize}
19: %
20: %Standards for representing mathematical objects
21: %
22: %\item Control integration
23: %
24: %\begin{itemize}
25: %\item MCP [WANG99], OMEI [LIAO01]
26: %\end{itemize}
27: %
28: %Protocols for remote subroutine calls or session management
29: %
30: %\item Combination of two integrations
31: %
32: %\begin{itemize}
33: %\item MathLink, OpenMath+MCP, MP+MCP
34: %
35: %and OpenXM ({\tt http://www.openxm.org})
36: %\end{itemize}
37: %
38: %Both are necessary for practical implementation
39: %
40: %\end{itemize}
41: %\end{slide}
1.1 noro 42: \begin{slide}{}
1.7 noro 43: \fbox{A computer algebra system Risa/Asir}
1.1 noro 44:
1.7 noro 45: ({\tt http://www.math.kobe-u.ac.jp/Asir/asir.html})
1.1 noro 46:
47: \begin{itemize}
1.8 noro 48: \item Software mainly for polynomial computation
1.1 noro 49:
1.5 noro 50: \item User language with C-like syntax
1.1 noro 51:
1.5 noro 52: C language without type declaration, with list processing
1.1 noro 53:
1.5 noro 54: \item Builtin {\tt gdb}-like debugger for user programs
1.1 noro 55:
1.5 noro 56: \item Open source
1.1 noro 57:
1.5 noro 58: Whole source tree is available via CVS
1.2 noro 59:
1.8 noro 60: The latest version : see {\tt http://www.openxm.org}
61:
1.5 noro 62: \item OpenXM interface
1.1 noro 63:
1.5 noro 64: \begin{itemize}
1.8 noro 65: \item OpenXM
66:
67: An infrastructure for exchanging mathematical data
1.5 noro 68: \item Risa/Asir is a main client in OpenXM package.
69: \item An OpenXM server {\tt ox\_asir}
1.7 noro 70: \item A library with OpenXM library interface {\tt libasir.a}
1.1 noro 71: \end{itemize}
72: \end{itemize}
73: \end{slide}
74:
75: \begin{slide}{}
1.7 noro 76: \fbox{Goal of developing Risa/Asir}
1.1 noro 77:
78: \begin{itemize}
1.8 noro 79: \item Testing new algorithms
1.1 noro 80:
1.7 noro 81: \begin{itemize}
1.8 noro 82: \item Development started in Fujitsu labs
1.1 noro 83:
1.8 noro 84: Polynomial factorization, Groebner basis related computation,
85: cryptosystems , quantifier elimination , $\ldots$
1.7 noro 86: \end{itemize}
1.1 noro 87:
1.8 noro 88: \item To be a general purpose, open system
1.7 noro 89:
1.8 noro 90: Since 1997, we have been developing OpenXM package
91: containing various servers and clients
1.7 noro 92:
1.8 noro 93: Risa/Asir is a component of OpenXM
1.7 noro 94:
1.8 noro 95: \item Environment for parallel and distributed computation
1.1 noro 96:
97: \end{itemize}
98: \end{slide}
99:
1.8 noro 100: %\begin{slide}{}
101: %\fbox{Capability for polynomial computation}
102: %
103: %\begin{itemize}
104: %\item Fundamental polynomial arithmetics
105: %
106: %recursive representation and distributed representation
107: %
108: %\item Polynomial factorization
109: %
110: %\begin{itemize}
111: %\item Univariate : over {\bf Q}, algebraic number fields and finite fields
112: %
113: %\item Multivariate : over {\bf Q}
114: %\end{itemize}
115: %
116: %\item Groebner basis computation
117: %
118: %\begin{itemize}
119: %\item Buchberger and $F_4$ [FAUG99] algorithm
120: %
121: %\item Change of ordering/RUR [ROUI96] of 0-dimensional ideals
122: %
123: %\item Primary ideal decomposition
124: %
125: %\item Computation of $b$-function (in Weyl Algebra)
126: %\end{itemize}
127: %\end{itemize}
128: %\end{slide}
1.1 noro 129:
130: \begin{slide}{}
1.5 noro 131: \fbox{History of development : Polynomial factorization}
132:
1.1 noro 133: \begin{itemize}
1.5 noro 134: \item 1989
1.1 noro 135:
1.7 noro 136: Start of Risa/Asir with Boehm's conservative GC
137:
138: ({\tt http://www.hpl.hp.com/personal/Hans\_Boehm/gc})
1.1 noro 139:
1.5 noro 140: \item 1989-1992
1.2 noro 141:
1.5 noro 142: Univariate and multivariate factorizers over {\bf Q}
1.1 noro 143:
1.5 noro 144: \item 1992-1994
1.1 noro 145:
1.5 noro 146: Univariate factorization over algebraic number fields
1.1 noro 147:
1.5 noro 148: Intensive use of successive extension, non-squarefree norms
1.1 noro 149:
1.5 noro 150: \item 1996-1998
1.1 noro 151:
1.5 noro 152: Univariate factorization over large finite fields
1.2 noro 153:
1.8 noro 154: Motivated by a reseach project in Fujitsu on cryptography
155:
1.5 noro 156: \item 2000-current
1.1 noro 157:
1.5 noro 158: Multivariate factorization over small finite fields (in progress)
1.1 noro 159: \end{itemize}
160: \end{slide}
161:
162: \begin{slide}{}
1.5 noro 163: \fbox{History of development : Groebner basis}
164:
1.1 noro 165: \begin{itemize}
1.5 noro 166: \item 1992-1994
167:
1.7 noro 168: User language $\Rightarrow$ C version; trace lifting [TRAV88]
1.1 noro 169:
1.5 noro 170: \item 1994-1996
171:
172: Trace lifting with homogenization
173:
1.7 noro 174: Omitting GB check by compatible prime [NOYO99]
1.5 noro 175:
1.8 noro 176: Modular change of ordering/RUR[ROUI96] [NOYO99]
1.1 noro 177:
1.7 noro 178: Primary ideal decomposition [SHYO96]
1.1 noro 179:
1.5 noro 180: \item 1996-1998
1.1 noro 181:
1.7 noro 182: Efficient content reduction during NF computation [NORO97]
183: Solved {\it McKay} system for the first time
1.1 noro 184:
1.5 noro 185: \item 1998-2000
1.1 noro 186:
1.8 noro 187: Test implementation of $F_4$ [FAUG99]
1.1 noro 188:
1.5 noro 189: \item 2000-current
1.1 noro 190:
1.8 noro 191: Buchberger algorithm in Weyl algebra
1.1 noro 192:
1.8 noro 193: Efficient $b$-function computation[OAKU97] by a modular method
1.1 noro 194: \end{itemize}
195: \end{slide}
196:
197: \begin{slide}{}
1.7 noro 198: \fbox{Timing data --- Factorization}
199:
200: \underline{Univariate; over {\bf Q}}
201:
1.8 noro 202: $N_i$ : a norm of a polynomial, $\deg(N_i) = i$
1.7 noro 203: \begin{center}
204: \begin{tabular}{|c||c|c|c|c|} \hline
205: & $N_{105}$ & $N_{120}$ & $N_{168}$ & $N_{210}$ \\ \hline
206: Asir & 0.86 & 59 & 840 & hard \\ \hline
207: Asir NormFactor & 1.6 & 2.2& 6.1& hard \\ \hline
1.8 noro 208: %Singular& hard? & hard?& hard? & hard? \\ \hline
1.7 noro 209: CoCoA 4 & 0.2 & 7.1 & 16 & 0.5 \\ \hline\hline
210: NTL-5.2 & 0.16 & 0.9 & 1.4 & 0.4 \\ \hline
211: \end{tabular}
212: \end{center}
213:
214: \underline{Multivariate; over {\bf Q}}
215:
216: $W_{i,j,k} = Wang[i]\cdot Wang[j]\cdot Wang[k]$ in {\tt asir2000/lib/fctrdata}
217: \begin{center}
218: \begin{tabular}{|c||c|c|c|c|c|} \hline
219: & $W_{1,2,3}$ & $W_{4,5,6}$ & $W_{7,8,9}$ & $W_{10,11,12}$ & $W_{13,14,15}$ \\ \hline
220: Asir & 0.2 & 4.7 & 14 & 17 & 0.4 \\ \hline
1.8 noro 221: %Singular& $>$15min & --- & ---& ---& ---\\ \hline
1.7 noro 222: CoCoA 4 & 5.2 & $>$15min & $>$15min & $>$15min & 117 \\ \hline\hline
1.8 noro 223: Mathematica 4& 0.2 & 16 & 23 & 36 & 1.1 \\ \hline
1.9 ! noro 224: Maple 7& 0.5 & 18 & 967 & 48 & 1.3 \\ \hline
1.7 noro 225: \end{tabular}
226: \end{center}
227:
1.8 noro 228: %--- : not tested
1.2 noro 229: \end{slide}
230:
231: \begin{slide}{}
1.7 noro 232: \fbox{Timing data --- DRL Groebner basis computation}
1.6 noro 233:
234: \underline{Over $GF(32003)$}
235: \begin{center}
236: \begin{tabular}{|c||c|c|c|c|c|c|c|} \hline
237: & $C_7$ & $C_8$ & $K_7$ & $K_8$ & $K_9$ & $K_{10}$ & $K_{11}$ \\ \hline
238: Asir $Buchberger$ & 31 & 1687 & 2.6 & 27 & 294 & 4309 & --- \\ \hline
239: Singular & 8.7 & 278 & 0.6 & 5.6 & 54 & 508 & 5510 \\ \hline
1.8 noro 240: CoCoA 4 & 241 & $>$ 5h & 3.8 & 35 & 402 &7021 & --- \\ \hline\hline
1.6 noro 241: Asir $F_4$ & 5.3 & 129 & 0.5 & 4.5 & 31 & 273 & 2641 \\ \hline
242: FGb(estimated) & 0.9 & 23 & 0.1 & 0.8 & 6 & 51 & 366 \\ \hline
243: \end{tabular}
244: \end{center}
245:
246: \underline{Over {\bf Q}}
247:
248: \begin{center}
249: \begin{tabular}{|c||c|c|c|c|c|} \hline
250: & $C_7$ & $Homog. C_7$ & $K_7$ & $K_8$ & $McKay$ \\ \hline
251: Asir $Buchberger$ & 389 & 594 & 29 & 299 & 34950 \\ \hline
1.7 noro 252: Singular & --- & 15247 & 7.6 & 79 & $>$ 20h \\ \hline
253: CoCoA 4 & --- & 13227 & 57 & 709 & --- \\ \hline\hline
1.6 noro 254: Asir $F_4$ & 989 & 456 & 90 & 991 & 4939 \\ \hline
255: FGb(estimated) & 8 &11 & 0.6 & 5 & 10 \\ \hline
256: \end{tabular}
257: \end{center}
1.7 noro 258: --- : not tested
1.6 noro 259: \end{slide}
1.8 noro 260:
1.6 noro 261: \begin{slide}{}
1.8 noro 262: \fbox{Summary of performance}
1.2 noro 263:
1.8 noro 264: \begin{itemize}
265: \item Factorizer
1.7 noro 266:
1.2 noro 267: \begin{itemize}
1.8 noro 268: \item Multivariate : reasonable performance
269:
270: \item Univariate : obsoleted by M. van Hoeij's new algorithm [HOEI00]
271: \end{itemize}
1.7 noro 272:
1.8 noro 273: \item Groebner basis computation
1.7 noro 274:
275: \begin{itemize}
1.8 noro 276: \item Buchberger
277:
278: Singular shows nice perfomance
1.7 noro 279:
1.8 noro 280: Trace lifting is efficient in some cases over {\bf Q}
1.7 noro 281:
1.8 noro 282: \item $F_4$
1.7 noro 283:
1.8 noro 284: FGb is much faster than Risa/Asir
285:
286: But we observe that {\it McKay} is computed efficiently by $F_4$
287: \end{itemize}
1.7 noro 288: \end{itemize}
289:
1.8 noro 290: \end{slide}
291:
292: \begin{slide}{}
293: \fbox{Summary}
294:
295: \begin{itemize}
296: \item Total performance is not excellent, but not so bad
1.2 noro 297:
1.8 noro 298: \item A completely open system
1.2 noro 299:
1.8 noro 300: The whole source is available
1.2 noro 301:
1.8 noro 302: \item Interface compliant to OpenXM RFC-100
1.2 noro 303:
1.8 noro 304: The interface is fully documented
1.2 noro 305: \end{itemize}
306:
307: \end{slide}
308:
309:
310: %\begin{slide}{}
311: %\fbox{CMO = Serialized representation of mathematical object}
312: %
313: %\begin{itemize}
314: %\item primitive data
315: %\begin{eqnarray*}
316: %\mbox{Integer32} &:& ({\tt CMO\_INT32}, {\sl int32}\ \mbox{n}) \\
317: %\mbox{Cstring}&:& ({\tt CMO\_STRING},{\sl int32}\, \mbox{ n}, {\sl string}\, \mbox{s}) \\
318: %\mbox{List} &:& ({\tt CMO\_LIST}, {\sl int32}\, len, ob[0], \ldots,ob[m-1])
319: %\end{eqnarray*}
320: %
321: %\item numbers and polynomials
322: %\begin{eqnarray*}
323: %\mbox{ZZ} &:& ({\tt CMO\_ZZ},{\sl int32}\, {\rm f}, {\sl byte}\, \mbox{a[1]}, \ldots
324: %{\sl byte}\, \mbox{a[$|$f$|$]} ) \\
325: %\mbox{Monomial32}&:& ({\tt CMO\_MONOMIAL32}, n, \mbox{e[1]}, \ldots, \mbox{e[n]}, \mbox{Coef}) \\
326: %\mbox{Coef}&:& \mbox{ZZ} | \mbox{Integer32} \\
327: %\mbox{Dpolynomial}&:& ({\tt CMO\_DISTRIBUTED\_POLYNOMIAL},\\
328: % & & m, \mbox{DringDefinition}, \mbox{Monomial32}, \ldots)\\
329: %\mbox{DringDefinition}
330: % &:& \mbox{DMS of N variables} \\
331: % & & ({\tt CMO\_RING\_BY\_NAME}, name) \\
332: % & & ({\tt CMO\_DMS\_GENERIC}) \\
333: %\end{eqnarray*}
334: %\end{itemize}
335: %\end{slide}
336: %
337: %\begin{slide}{}
338: %\fbox{Stack based communication}
339: %
340: %\begin{itemize}
341: %\item Data arrived a client
342: %
343: %Pushed to the stack
344: %
345: %\item Result
346: %
347: %Pushd to the stack
348: %
349: %Written to the stream when requested by a command
350: %
351: %\item The reason why we use the stack
352: %
353: %\begin{itemize}
354: %\item Stack = I/O buffer for (possibly large) objects
355: %
1.7 noro 356: %Multiple requests can be sent before their execution
1.2 noro 357: %
358: %A server does not get stuck in sending results
359: %\end{itemize}
360: %\end{itemize}
361: %\end{slide}
362:
363: \begin{slide}{}
1.8 noro 364: \fbox{OpenXM (Open message eXchange protocol for Mathematics) }
365:
366: \begin{itemize}
367: \item An environment for parallel distributed computation
368:
369: Both for interactive, non-interactive environment
370:
371: \item OpenXM RFC-100 = Client-server architecture
372:
373: Client $\Leftarrow$ OX (OpenXM) message $\Rightarrow$ Server
374:
375: OX (OpenXM) message : command and data
376:
377: \item Data
378:
379: Encoding : CMO (Common Mathematical Object format)
380:
381: Serialized representation of mathematical object
382:
383: --- Main idea was borrowed from OpenMath
384:
385: ({\tt http://www.openmath.org})
386:
387: \item Command
388:
389: stack machine command --- server is a stackmachine
390:
391: + server's own command sequences --- hybrid server
392: \end{itemize}
393: \end{slide}
394:
395: \begin{slide}{}
1.2 noro 396: \fbox{Example of distributed computation --- $F_4$ vs. $Buchberger$ }
397:
398: \begin{verbatim}
399: /* competitive Gbase computation over GF(M) */
400: /* Cf. A.28 in SINGULAR Manual */
401: /* Process list is specified as an option : grvsf4(...|proc=P) */
402: def grvsf4(G,V,M,O)
403: {
404: P = getopt(proc);
405: if ( type(P) == -1 ) return dp_f4_mod_main(G,V,M,O);
406: P0 = P[0]; P1 = P[1]; P = [P0,P1];
407: map(ox_reset,P);
408: ox_cmo_rpc(P0,"dp_f4_mod_main",G,V,M,O);
409: ox_cmo_rpc(P1,"dp_gr_mod_main",G,V,0,M,O);
410: map(ox_push_cmd,P,262); /* 262 = OX_popCMO */
411: F = ox_select(P); R = ox_get(F[0]);
412: if ( F[0] == P0 ) { Win = "F4"; Lose = P1;}
413: else { Win = "Buchberger"; Lose = P0; }
414: ox_reset(Lose); /* simply resets the loser */
415: return [Win,R];
416: }
417: \end{verbatim}
418: \end{slide}
419:
420: \begin{slide}{}
421: \fbox{References}
422:
1.7 noro 423: [BERN97] L. Bernardin, On square-free factorization of
1.2 noro 424: multivariate polynomials over a finite field, Theoretical
425: Computer Science 187 (1997), 105-116.
426:
1.7 noro 427: [FAUG99] J.C. Faug\`ere,
1.2 noro 428: A new efficient algorithm for computing Groebner bases ($F_4$),
429: Journal of Pure and Applied Algebra (139) 1-3 (1999), 61-88.
430:
1.7 noro 431: [GRAY98] S. Gray et al,
432: Design and Implementation of MP, A Protocol for Efficient Exchange of
433: Mathematical Expression,
434: J. Symb. Comp. {\bf 25} (1998), 213-238.
435:
1.8 noro 436: [HOEI00] M. van Hoeij, Factoring polynomials and the knapsack problem,
1.2 noro 437: to appear in Journal of Number Theory (2000).
438:
1.7 noro 439: [LIAO01] W. Liao et al,
440: OMEI: An Open Mathematical Engine Interface,
441: Proc. ASCM2001 (2001), 82-91.
442: [NORO97] M. Noro, J. McKay,
1.4 noro 443: Computation of replicable functions on Risa/Asir.
1.7 noro 444: Proc. PASCO'97, ACM Press (1997), 130-138.
445: \end{slide}
1.4 noro 446:
1.7 noro 447: \begin{slide}{}
448:
449: [NOYO99] M. Noro, K. Yokoyama,
1.2 noro 450: A Modular Method to Compute the Rational Univariate
451: Representation of Zero-Dimensional Ideals.
452: J. Symb. Comp. {\bf 28}/1 (1999), 243-263.
1.4 noro 453:
1.7 noro 454: [OAKU97] T. Oaku, Algorithms for $b$-functions, restrictions and algebraic
1.3 noro 455: local cohomology groups of $D$-modules.
1.7 noro 456: Advances in Applied Mathematics, 19 (1997), 61-105.
1.2 noro 457:
1.7 noro 458: [ROUI96] F. Rouillier,
1.2 noro 459: R\'esolution des syst\`emes z\'ero-dimensionnels.
460: Doctoral Thesis(1996), University of Rennes I, France.
461:
1.7 noro 462: [SHYO96] T. Shimoyama, K. Yokoyama, Localization and Primary Decomposition of Polynomial Ideals. J. Symb. Comp. {\bf 22} (1996), 247-277.
1.3 noro 463:
1.7 noro 464: [TRAV88] C. Traverso, \gr trace algorithms. Proc. ISSAC '88 (LNCS 358), 125-138.
1.2 noro 465:
1.7 noro 466: [WANG99] P. S. Wang,
467: Design and Protocol for Internet Accessible Mathematical Computation,
468: Proc. ISSAC '99 (1999), 291-298.
1.2 noro 469: \end{slide}
470:
471: \begin{slide}{}
472: \begin{center}
473: \fbox{\large Part II : Algorithms and implementations in Risa/Asir}
474: \end{center}
475: \end{slide}
476:
477: \begin{slide}{}
1.1 noro 478: \fbox{Ground fields}
479:
480: \begin{itemize}
481: \item The rational number field
482: \item Algebraic number fields
483:
484: represented by successive extensions
485: \item Finite fields
486: \begin{itemize}
487: \item $GF(p)$ ($p<2^{30}$); represented by a single word
488: \item $GF(p^n)$ ($p^n < 2^{20}$); represented by a primitive root
489: \item $GF(2^n)$; represented by a bit string
490: \item $GF(p)$ ($p$ : arbitrary prime)
491: \item $GF(p^n)$ ($p$ : arbitrary odd prime)
492: \end{itemize}
493:
494: \item Real and complex number fields
495:
496: \begin{itemize}
497: \item Double float
498: \item PARI bigfloat
499: \end{itemize}
500:
501: \end{itemize}
502: \end{slide}
503:
504: \begin{slide}{}
505: \fbox{Polynomial factorization}
506: \begin{itemize}
507: \item Univariate factorization
508:
509: \begin{itemize}
510: \item Over the rationals
511:
512: Berlekamp-Zassenhaus
513:
514: (classical; knapsack has not yet implemented)
515:
516: \item Over algebraic number fields
517:
518: Trager's algorithm + some improvement
519:
1.7 noro 520: \item Over finite fields
1.1 noro 521:
522: DDF + Cantor-Zassenhaus; FFT for large finite fields
523: \end{itemize}
524:
525: \item Multivariate factorization
526:
527: \begin{itemize}
528: \item Over the rationals
529:
530: Classical EZ algorithm
531:
1.7 noro 532: \item Over small finite fields
1.2 noro 533:
1.7 noro 534: Modified Bernardin's square free algorithm [BERN97],
1.1 noro 535:
1.2 noro 536: possibly Hensel lifting over extension fields
1.1 noro 537: \end{itemize}
538:
539: \end{itemize}
540: \end{slide}
541:
542: \begin{slide}{}
543: \fbox{Groebner basis computation --- Buchberger algorithm}
544: \begin{itemize}
545: \item Polynomial rings
546: \begin{itemize}
547: \item Over finite fields
548:
549: Any finite field is available as a ground field
550:
551: \item Over the rationals
552:
553: Guess of a groebner basis by detecting zero reduction by modular computation
554: + check (trace lifting)
555:
556: Homogenization+guess+dehomogenization+check
557: \end{itemize}
558:
1.3 noro 559: \item Weyl Algebra
1.1 noro 560:
561: \begin{itemize}
562: \item Groebner basis of a left ideal
563:
1.2 noro 564: Key : an efficient implementation of Leibniz rule
1.1 noro 565: \end{itemize}
566:
567: \end{itemize}
568: \end{slide}
569:
570: \begin{slide}{}
571: \fbox{$F_4$ algorithm}
572: \begin{itemize}
573: \item Over small finite fields ($GF(p)$, $p < 2^{30}$)
574: \begin{itemize}
1.2 noro 575: \item More efficient than our Buchberger algorithm implementation
1.1 noro 576:
1.7 noro 577: but less efficient than FGb by Faug\`ere
1.1 noro 578: \end{itemize}
579:
580: \item Over the rationals
581:
582: \begin{itemize}
583: \item Very naive implementation
584:
1.2 noro 585: Modular computation + CRT + Checking the result at each degree
586:
1.1 noro 587: \item Less efficient than Buchberger algorithm
588:
1.2 noro 589: except for one example (={\it McKay})
1.1 noro 590: \end{itemize}
591:
592: \end{itemize}
593: \end{slide}
594:
595: \begin{slide}{}
1.2 noro 596: \fbox{Change of ordering for zero-dimensional ideals}
1.1 noro 597:
598: \begin{itemize}
599: \item Any ordering to lex ordering
600:
601: \begin{itemize}
602: \item Modular change of ordering
603:
604: Guess of the support by modular FGLM
605:
606: + solving linear systems by Hensel lifting
607:
608: \end{itemize}
609:
610: \item RUR (generalized shape lemma)
611:
612: \begin{itemize}
613: \item Modular RUR (only implemented on the shape base case)
614:
615: Almost the same as modular change of ordering
616: \end{itemize}
617:
618: \end{itemize}
619: \end{slide}
620:
621: \begin{slide}{}
622: \fbox{Primary decomposition --- Shimoyama-Yokoyama algorithm}
623:
624: \begin{itemize}
625: \item Only implemented over the rationals
626:
627: Finite field version will soon be available
628:
629: \item Pseudo primary ideal
630:
631: An ideal whose radical is prime
632:
633: \item Prime decomp. of the radical $\Rightarrow$ pseudo primary decomp.
634:
635: \item Extraction of embedded components
636:
637: \end{itemize}
638:
639: \end{slide}
640:
641: \begin{slide}{}
642: \fbox{Computation of $b$-function}
643:
1.3 noro 644: $D=K\langle x,\partial \rangle$ : Weyl algebra
1.1 noro 645:
646: $b(s)$ : a polynomial of the smallest degree s.t.
647: there exists $P(s) \in D[s]$, $P(s)f^{s+1}=b(s)f^s$
648:
649: $b(s)$ : $b$-function of a polynomial $f$
650:
651: $\Rightarrow$ $b(s)$ can be computed by Oaku's algorithm
652:
653: On Risa/Asir : $b(s)$ is computed by
654:
655: A groebner basis $\Rightarrow$ guess of $\deg(b(s))$ by modular
656: computation $\Rightarrow$ solving a linear system
657: \end{slide}
658:
659: \begin{slide}{}
660: \fbox{Interface to PARI library}
661:
662: \begin{itemize}
663: \item Data conversion
664:
665: \begin{itemize}
666:
667: \item Only primitive data can be passed to PARI
668:
669: Rational number, bignum, bigfloat, polynomial,
670: vector, matrix
671:
672: \item Results are converted to Risa objects
673:
674: \end{itemize}
675:
676: \item Evaluation of transcendental functions
677:
678: \begin{itemize}
679: \item Most of univariate functions in PARI can be
680: evaluated by {\tt eval()}
681: \end{itemize}
682:
683: \item Calling PARI functions
684:
685: \begin{itemize}
686: \item One can call PARI functions by {\tt pari({\it parifunction},{\it args})}
687:
688: The knapsack factorization is available via {\tt pari(factor,{\it poly})}
689: \end{itemize}
1.6 noro 690: \end{itemize}
691: \end{slide}
692:
693: \begin{slide}{}
694: \fbox{OpenXM server interface in Risa/Asir}
695:
696: \begin{itemize}
697: \item TCP/IP stream
698:
699: \begin{itemize}
700: \item Launcher
701:
702: A client executes a launcher on a host.
703:
704: The launcher launches a server on the same host.
705:
706: \item Server
707:
708: Reads from the descriptor 3
709:
710: Writes to the descriptor 4
711:
712: \end{itemize}
713:
714: \item Subroutine call
715:
716: In Risa/Asir subroutine library {\tt libasir.a}:
717:
1.7 noro 718: OpenXM functionalities are implemented as function calls
1.6 noro 719:
720: pushing and popping data, executing stack commands etc.
721: \end{itemize}
722: \end{slide}
723:
724: \begin{slide}{}
725: \fbox{OpenXM client interface in Risa/Asir}
726:
727: \begin{itemize}
728: \item Primitive interface functions
729:
730: Pushing and popping data, sending commands etc.
731:
732: \item Convenient functions
733:
734: Launching servers,
735:
736: Calling remote functions,
737:
738: Resetting remote executions etc.
739:
740: \item Parallel distributed computation
741:
742: Simple parallelization is practically important
743:
744: Competitive computation is easily realized ($\Rightarrow$ demo)
1.1 noro 745: \end{itemize}
746: \end{slide}
747:
1.5 noro 748: \begin{slide}{}
749: \fbox{Executing functions on a server (I) --- {\tt SM\_executeFunction}}
750:
751: \begin{enumerate}
752: \item (C $\rightarrow$ S) Arguments are sent in binary encoded form.
1.7 noro 753: \item (C $\rightarrow$ S) The number of arguments is sent as {\sl Integer32}.
1.5 noro 754: \item (C $\rightarrow$ S) A function name is sent as {\sl Cstring}.
755: \item (C $\rightarrow$ S) A command {\tt SM\_executeFunction} is sent.
756: \item The result is pushed to the stack.
757: \item (C $\rightarrow$ S) A command {\tt SM\_popCMO} is sent.
758: \item (S $\rightarrow$ C) The result is sent in binary encoded form.
759: \end{enumerate}
760:
761: $\Rightarrow$ Communication is fast, but functions for binary data
762: conversion are necessary.
763: \end{slide}
764:
765: \begin{slide}{}
766: \fbox{Executing functions on a server (II) --- {\tt SM\_executeString}}
767:
768: \begin{enumerate}
1.7 noro 769: \item (C $\rightarrow$ S) A character string representing a request in a server's
1.5 noro 770: user language is sent as {\sl Cstring}.
771: \item (C $\rightarrow$ S) A command {\tt SM\_executeString} is sent.
772: \item The result is pushed to the stack.
773: \item (C $\rightarrow$ S) A command {\tt SM\_popString} is sent.
774: \item (S $\rightarrow$ C) The result is sent in readable form.
775: \end{enumerate}
776:
777: $\Rightarrow$ Communication may be slow, but the client parser may be
778: enough to read the result.
779: \end{slide}
780:
781: %\begin{slide}{}
782: %\fbox{History of development : ---1994}
783: %
784: %\begin{itemize}
785: %\item --1989
786: %
787: %Several subroutines were developed for a Prolog program.
788: %
789: %\item 1989--1992
790: %
791: %\begin{itemize}
1.7 noro 792: %\item Reconfigured as Risa/Asir with a parser and Boehm's conservative GC
1.5 noro 793: %
794: %\item Developed univariate and multivariate factorizers over the rationals.
795: %\end{itemize}
796: %
797: %\item 1992--1994
798: %
799: %\begin{itemize}
800: %\item Started implementation of Buchberger algorithm
801: %
802: %Written in user language $\Rightarrow$ rewritten in C (by Murao)
803: %
1.7 noro 804: %$\Rightarrow$ trace lifting [TRAV88]
1.5 noro 805: %
806: %\item Univariate factorization over algebraic number fields
807: %
808: %Intensive use of successive extension, non-squarefree norms
809: %\end{itemize}
810: %\end{itemize}
811: %
812: %\end{slide}
813: %
814: %\begin{slide}{}
815: %\fbox{History of development : 1994-1996}
816: %
817: %\begin{itemize}
818: %\item Free distribution of binary versions from Fujitsu
819: %
820: %\item Primary ideal decomposition
821: %
822: %\begin{itemize}
1.7 noro 823: %\item Shimoyama-Yokoyama algorithm [SHYO96]
1.5 noro 824: %\end{itemize}
825: %
826: %\item Improvement of Buchberger algorithm
827: %
828: %\begin{itemize}
829: %\item Trace lifting+homogenization
830: %
831: %\item Omitting check by compatible prime
832: %
833: %\item Modular change of ordering, Modular RUR
834: %
1.7 noro 835: %These are joint works with Yokoyama [NOYO99]
1.5 noro 836: %\end{itemize}
837: %\end{itemize}
838: %
839: %\end{slide}
840: %
841: %\begin{slide}{}
842: %\fbox{History of development : 1996-1998}
843: %
844: %\begin{itemize}
1.7 noro 845: %\item Distributed computation
1.5 noro 846: %
847: %\begin{itemize}
848: %\item A prototype of OpenXM
849: %\end{itemize}
850: %
851: %\item Improvement of Buchberger algorithm
852: %
853: %\begin{itemize}
1.7 noro 854: %\item Content reduction during normal form computation
1.5 noro 855: %
856: %\item Its parallelization by the above facility
857: %
1.7 noro 858: %\item Computation of odd order replicable functions [NORO97]
1.5 noro 859: %
860: %Risa/Asir : it took 5days to compute a DRL basis ({\it McKay})
861: %
862: %Faug\`ere FGb : computation of the DRL basis 53sec
863: %\end{itemize}
864: %
865: %
866: %\item Univariate factorization over large finite fields
867: %
868: %\begin{itemize}
869: %\item To implement Schoof-Elkies-Atkin algorithm
870: %
871: %Counting rational points on elliptic curves
872: %
873: %--- not free But related functions are freely available
874: %\end{itemize}
875: %\end{itemize}
876: %
877: %\end{slide}
878: %
879: %\begin{slide}{}
880: %\fbox{History of development : 1998-2000}
881: %\begin{itemize}
882: %\item OpenXM
883: %
884: %\begin{itemize}
885: %\item OpenXM specification was written by Noro and Takayama
886: %
1.7 noro 887: %Borrowed idea on encoding, phrase book from OpenMath
1.5 noro 888: %
889: %\item Functions for distributed computation were rewritten
890: %\end{itemize}
891: %
892: %\item Risa/Asir on Windows
893: %
894: %\begin{itemize}
895: %\item Requirement from a company for which Noro worked
896: %
897: %Written in Visual C++
898: %\end{itemize}
899: %
900: %\item Test implementation of $F_4$
901: %
902: %\begin{itemize}
1.7 noro 903: %\item Implemented according to [FAUG99]
1.5 noro 904: %
905: %\item Over $GF(p)$ : pretty good
906: %
907: %\item Over the rationals : not so good except for {\it McKay}
908: %\end{itemize}
909: %\end{itemize}
910: %\end{slide}
911: %
912: %\begin{slide}{}
913: %\fbox{History of development : 2000-current}
914: %\begin{itemize}
915: %\item The source code is freely available
916: %
917: %\begin{itemize}
918: %\item Noro moved from Fujitsu to Kobe university
919: %
1.7 noro 920: %Started Kobe branch
1.5 noro 921: %\end{itemize}
922: %
1.7 noro 923: %\item OpenXM
1.5 noro 924: %
925: %\begin{itemize}
926: %\item Revising the specification : OX-RFC100, 101, (102)
927: %
928: %\item OX-RFC102 : communications between servers via MPI
929: %\end{itemize}
930: %
931: %\item Weyl algebra
932: %
933: %\begin{itemize}
1.7 noro 934: %\item Buchberger algorithm [TAKA90]
1.5 noro 935: %
1.7 noro 936: %\item $b$-function computation [OAKU97]
1.5 noro 937: %
938: %Minimal polynomial computation by modular method
939: %\end{itemize}
940: %\end{itemize}
941: %
942: %\end{slide}
1.1 noro 943: \begin{slide}{}
944: \end{slide}
945:
946: \begin{slide}{}
947: \end{slide}
948:
949: \begin{slide}{}
950: \end{slide}
951:
952: \begin{slide}{}
953: \end{slide}
954:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to dagb-noro.tex CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM / doc / Papers