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