Annotation of OpenXM/doc/Papers/dagb-noro.tex, Revision 1.5
1.5 ! noro 1: % $OpenXM: OpenXM/doc/Papers/dagb-noro.tex,v 1.4 2001/10/04 08:22:20 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.5 ! noro 102: $\Rightarrow$ serves as an OpenXM server/library
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:
221: Multivariate : not so bad
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.5 ! noro 252: $\Leftarrow$ efficient monomial and polynomial representation
1.2 noro 253:
254: \end{itemize}
255: \end{slide}
256:
257: \begin{slide}{}
1.5 ! noro 258: \fbox{How do we proceed?}
1.2 noro 259:
260: \begin{itemize}
1.5 ! noro 261: \item Developing new OpenXM servers
1.2 noro 262:
1.5 ! noro 263: {ox\_NTL} for univariate factorization,
1.2 noro 264:
1.5 ! noro 265: {ox\_FGb} for Groebner basis computation (is it possible?) etc.
1.2 noro 266:
1.5 ! noro 267: $\Rightarrow$ Risa/Asir can be a front-end of efficient servers
1.2 noro 268:
1.5 ! noro 269: \item Trying to improve our implementation
1.2 noro 270:
1.5 ! noro 271: Computation of $b$-function : still faster than any other system
! 272: (Kan/sm1, Macaulay2) but not satisfactory
1.2 noro 273:
1.5 ! noro 274: $\Rightarrow$ Groebner basis computation in Weyl
! 275: algebra should be improved
1.2 noro 276: \end{itemize}
277:
1.5 ! noro 278: \begin{center}
! 279: \underline{In both cases, OpenXM interface is important}
! 280: \end{center}
1.2 noro 281: \end{slide}
282:
283: \begin{slide}{}
284: \fbox{OpenXM server interface in Risa/Asir}
285:
286: \begin{itemize}
287: \item TCP/IP stream
288:
289: \begin{itemize}
290: \item Launcher
291:
292: A client executes a launcher on a host.
293:
294: The launcher launches a server on the same host.
295:
296: \item Server
297:
1.5 ! noro 298: Reads from the descriptor 3
! 299:
! 300: Writes to the descriptor 4
1.2 noro 301:
302: \end{itemize}
303:
304: \item Subroutine call
305:
1.5 ! noro 306: In Risa/Asir subroutine library {\tt libasir.a}:
! 307:
! 308: OpenXM functionalities are implemented as functon calls
! 309:
! 310: pushing and popping data, executing stack commands etc.
1.2 noro 311: \end{itemize}
312: \end{slide}
313:
314: \begin{slide}{}
315: \fbox{OpenXM client interface in Risa/Asir}
316:
317: \begin{itemize}
318: \item Primitive interface functions
319:
320: Pushing and popping data, sending commands etc.
321:
322: \item Convenient functions
323:
1.5 ! noro 324: Launching servers,
! 325:
! 326: Calling remote functions,
! 327:
! 328: Resetting remote executions etc.
1.2 noro 329:
1.5 ! noro 330: \item Parallel distributed computation
1.2 noro 331:
332: Simple parallelization is practically important
333:
1.5 ! noro 334: Competitive computation is easily realized ($\Rightarrow$ demo)
1.2 noro 335: \end{itemize}
336: \end{slide}
337:
338:
339: %\begin{slide}{}
340: %\fbox{CMO = Serialized representation of mathematical object}
341: %
342: %\begin{itemize}
343: %\item primitive data
344: %\begin{eqnarray*}
345: %\mbox{Integer32} &:& ({\tt CMO\_INT32}, {\sl int32}\ \mbox{n}) \\
346: %\mbox{Cstring}&:& ({\tt CMO\_STRING},{\sl int32}\, \mbox{ n}, {\sl string}\, \mbox{s}) \\
347: %\mbox{List} &:& ({\tt CMO\_LIST}, {\sl int32}\, len, ob[0], \ldots,ob[m-1])
348: %\end{eqnarray*}
349: %
350: %\item numbers and polynomials
351: %\begin{eqnarray*}
352: %\mbox{ZZ} &:& ({\tt CMO\_ZZ},{\sl int32}\, {\rm f}, {\sl byte}\, \mbox{a[1]}, \ldots
353: %{\sl byte}\, \mbox{a[$|$f$|$]} ) \\
354: %\mbox{Monomial32}&:& ({\tt CMO\_MONOMIAL32}, n, \mbox{e[1]}, \ldots, \mbox{e[n]}, \mbox{Coef}) \\
355: %\mbox{Coef}&:& \mbox{ZZ} | \mbox{Integer32} \\
356: %\mbox{Dpolynomial}&:& ({\tt CMO\_DISTRIBUTED\_POLYNOMIAL},\\
357: % & & m, \mbox{DringDefinition}, \mbox{Monomial32}, \ldots)\\
358: %\mbox{DringDefinition}
359: % &:& \mbox{DMS of N variables} \\
360: % & & ({\tt CMO\_RING\_BY\_NAME}, name) \\
361: % & & ({\tt CMO\_DMS\_GENERIC}) \\
362: %\end{eqnarray*}
363: %\end{itemize}
364: %\end{slide}
365: %
366: %\begin{slide}{}
367: %\fbox{Stack based communication}
368: %
369: %\begin{itemize}
370: %\item Data arrived a client
371: %
372: %Pushed to the stack
373: %
374: %\item Result
375: %
376: %Pushd to the stack
377: %
378: %Written to the stream when requested by a command
379: %
380: %\item The reason why we use the stack
381: %
382: %\begin{itemize}
383: %\item Stack = I/O buffer for (possibly large) objects
384: %
385: %Multiple requests can be sent before their exection
386: %
387: %A server does not get stuck in sending results
388: %\end{itemize}
389: %\end{itemize}
390: %\end{slide}
391:
392: \begin{slide}{}
393: \fbox{Example of distributed computation --- $F_4$ vs. $Buchberger$ }
394:
395: \begin{verbatim}
396: /* competitive Gbase computation over GF(M) */
397: /* Cf. A.28 in SINGULAR Manual */
398: /* Process list is specified as an option : grvsf4(...|proc=P) */
399: def grvsf4(G,V,M,O)
400: {
401: P = getopt(proc);
402: if ( type(P) == -1 ) return dp_f4_mod_main(G,V,M,O);
403: P0 = P[0]; P1 = P[1]; P = [P0,P1];
404: map(ox_reset,P);
405: ox_cmo_rpc(P0,"dp_f4_mod_main",G,V,M,O);
406: ox_cmo_rpc(P1,"dp_gr_mod_main",G,V,0,M,O);
407: map(ox_push_cmd,P,262); /* 262 = OX_popCMO */
408: F = ox_select(P); R = ox_get(F[0]);
409: if ( F[0] == P0 ) { Win = "F4"; Lose = P1;}
410: else { Win = "Buchberger"; Lose = P0; }
411: ox_reset(Lose); /* simply resets the loser */
412: return [Win,R];
413: }
414: \end{verbatim}
415: \end{slide}
416:
417: \begin{slide}{}
418: \fbox{References}
419:
420: [Bernardin] L. Bernardin, On square-free factorization of
421: multivariate polynomials over a finite field, Theoretical
422: Computer Science 187 (1997), 105-116.
423:
424: [Boehm] {\tt http://www.hpl.hp.com/personal/Hans\_Boehm/gc}
425:
426: [Faug\`ere] J.C. Faug\`ere,
427: A new efficient algorithm for computing Groebner bases ($F_4$),
428: Journal of Pure and Applied Algebra (139) 1-3 (1999), 61-88.
429:
430: [Hoeij] M. van Heoij, Factoring polynomials and the knapsack problem,
431: to appear in Journal of Number Theory (2000).
432:
1.4 noro 433: [Noro] M. Noro, J. McKay,
434: Computation of replicable functions on Risa/Asir.
435: Proc. of PASCO'97, ACM Press, 130-138 (1997).
436:
1.2 noro 437: [NY] M. Noro, K. Yokoyama,
438: A Modular Method to Compute the Rational Univariate
439: Representation of Zero-Dimensional Ideals.
440: J. Symb. Comp. {\bf 28}/1 (1999), 243-263.
1.4 noro 441: \end{slide}
442:
443: \begin{slide}{}
1.2 noro 444:
1.3 noro 445: [Oaku] T. Oaku, Algorithms for $b$-functions, restrictions and algebraic
446: local cohomology groups of $D$-modules.
447: Advancees in Applied Mathematics, 19 (1997), 61-105.
448:
1.2 noro 449: [OpenMath] {\tt http://www.openmath.org}
450:
451: [OpenXM] {\tt http://www.openxm.org}
452:
453: [PARI] {\tt http://www.parigp-home.de}
454:
455: [Risa/Asir] {\tt http://www.math.kobe-u.ac.jp/Asir/asir.html}
456:
457: [Rouillier] F. Rouillier,
458: R\'esolution des syst\`emes z\'ero-dimensionnels.
459: Doctoral Thesis(1996), University of Rennes I, France.
460:
1.3 noro 461: [SY] T. Shimoyama, K. Yokoyama, Localization and Primary Decomposition of Polynomial Ideals. J. Symb. Comp. {\bf 22} (1996), 247-277.
462:
463: [Singular] {\tt http://www.singular.uni-kl.de}
464:
1.2 noro 465: [Traverso] C. Traverso, \gr trace algorithms. Proc. ISSAC '88 (LNCS 358), 125-138.
466:
467: \end{slide}
468:
469: \begin{slide}{}
470: \begin{center}
471: \fbox{\large Part II : Algorithms and implementations in Risa/Asir}
472: \end{center}
473: \end{slide}
474:
475: \begin{slide}{}
1.1 noro 476: \fbox{Ground fields}
477:
478: \begin{itemize}
479: \item The rational number field
480: \item Algebraic number fields
481:
482: represented by successive extensions
483: \item Finite fields
484: \begin{itemize}
485: \item $GF(p)$ ($p<2^{30}$); represented by a single word
486: \item $GF(p^n)$ ($p^n < 2^{20}$); represented by a primitive root
487: \item $GF(2^n)$; represented by a bit string
488: \item $GF(p)$ ($p$ : arbitrary prime)
489: \item $GF(p^n)$ ($p$ : arbitrary odd prime)
490: \end{itemize}
491:
492: \item Real and complex number fields
493:
494: \begin{itemize}
495: \item Double float
496: \item PARI bigfloat
497: \end{itemize}
498:
499: \end{itemize}
500: \end{slide}
501:
502: \begin{slide}{}
503: \fbox{Polynomial factorization}
504: \begin{itemize}
505: \item Univariate factorization
506:
507: \begin{itemize}
508: \item Over the rationals
509:
510: Berlekamp-Zassenhaus
511:
512: (classical; knapsack has not yet implemented)
513:
514: \item Over algebraic number fields
515:
516: Trager's algorithm + some improvement
517:
518: \item Over finite fieds
519:
520: DDF + Cantor-Zassenhaus; FFT for large finite fields
521: \end{itemize}
522:
523: \item Multivariate factorization
524:
525: \begin{itemize}
526: \item Over the rationals
527:
528: Classical EZ algorithm
529:
1.2 noro 530: \item Over small finite fieds
531:
532: Modified Bernardin's square free algorithm [Bernardin],
1.1 noro 533:
1.2 noro 534: possibly Hensel lifting over extension fields
1.1 noro 535: \end{itemize}
536:
537: \end{itemize}
538: \end{slide}
539:
540: \begin{slide}{}
541: \fbox{Groebner basis computation --- Buchberger algorithm}
542: \begin{itemize}
543: \item Polynomial rings
544: \begin{itemize}
545: \item Over finite fields
546:
547: Any finite field is available as a ground field
548:
549: \item Over the rationals
550:
551: Guess of a groebner basis by detecting zero reduction by modular computation
552: + check (trace lifting)
553:
554: Homogenization+guess+dehomogenization+check
555: \end{itemize}
556:
1.3 noro 557: \item Weyl Algebra
1.1 noro 558:
559: \begin{itemize}
560: \item Groebner basis of a left ideal
561:
1.2 noro 562: Key : an efficient implementation of Leibniz rule
1.1 noro 563: \end{itemize}
564:
565: \end{itemize}
566: \end{slide}
567:
568: \begin{slide}{}
569: \fbox{$F_4$ algorithm}
570: \begin{itemize}
571: \item Over small finite fields ($GF(p)$, $p < 2^{30}$)
572: \begin{itemize}
1.2 noro 573: \item More efficient than our Buchberger algorithm implementation
1.1 noro 574:
575: but less efficient than FGb by Faugere
576: \end{itemize}
577:
578: \item Over the rationals
579:
580: \begin{itemize}
581: \item Very naive implementation
582:
1.2 noro 583: Modular computation + CRT + Checking the result at each degree
584:
1.1 noro 585: \item Less efficient than Buchberger algorithm
586:
1.2 noro 587: except for one example (={\it McKay})
1.1 noro 588: \end{itemize}
589:
590: \end{itemize}
591: \end{slide}
592:
593: \begin{slide}{}
1.2 noro 594: \fbox{Change of ordering for zero-dimensional ideals}
1.1 noro 595:
596: \begin{itemize}
597: \item Any ordering to lex ordering
598:
599: \begin{itemize}
600: \item Modular change of ordering
601:
602: Guess of the support by modular FGLM
603:
604: + solving linear systems by Hensel lifting
605:
606: \end{itemize}
607:
608: \item RUR (generalized shape lemma)
609:
610: \begin{itemize}
611: \item Modular RUR (only implemented on the shape base case)
612:
613: Almost the same as modular change of ordering
614: \end{itemize}
615:
616: \end{itemize}
617: \end{slide}
618:
619: \begin{slide}{}
620: \fbox{Primary decomposition --- Shimoyama-Yokoyama algorithm}
621:
622: \begin{itemize}
623: \item Only implemented over the rationals
624:
625: Finite field version will soon be available
626:
627: \item Pseudo primary ideal
628:
629: An ideal whose radical is prime
630:
631: \item Prime decomp. of the radical $\Rightarrow$ pseudo primary decomp.
632:
633: \item Extraction of embedded components
634:
635: \end{itemize}
636:
637: \end{slide}
638:
639: \begin{slide}{}
640: \fbox{Computation of $b$-function}
641:
1.3 noro 642: $D=K\langle x,\partial \rangle$ : Weyl algebra
1.1 noro 643:
644: $b(s)$ : a polynomial of the smallest degree s.t.
645: there exists $P(s) \in D[s]$, $P(s)f^{s+1}=b(s)f^s$
646:
647: $b(s)$ : $b$-function of a polynomial $f$
648:
649: $\Rightarrow$ $b(s)$ can be computed by Oaku's algorithm
650:
651: On Risa/Asir : $b(s)$ is computed by
652:
653: A groebner basis $\Rightarrow$ guess of $\deg(b(s))$ by modular
654: computation $\Rightarrow$ solving a linear system
655: \end{slide}
656:
657: \begin{slide}{}
658: \fbox{Interface to PARI library}
659:
660: \begin{itemize}
661: \item Data conversion
662:
663: \begin{itemize}
664:
665: \item Only primitive data can be passed to PARI
666:
667: Rational number, bignum, bigfloat, polynomial,
668: vector, matrix
669:
670: \item Results are converted to Risa objects
671:
672: \end{itemize}
673:
674: \item Evaluation of transcendental functions
675:
676: \begin{itemize}
677: \item Most of univariate functions in PARI can be
678: evaluated by {\tt eval()}
679: \end{itemize}
680:
681: \item Calling PARI functions
682:
683: \begin{itemize}
684: \item One can call PARI functions by {\tt pari({\it parifunction},{\it args})}
685:
686: The knapsack factorization is available via {\tt pari(factor,{\it poly})}
687: \end{itemize}
688: \end{itemize}
689: \end{slide}
690:
1.5 ! noro 691: \begin{slide}{}
! 692: \fbox{Executing functions on a server (I) --- {\tt SM\_executeFunction}}
! 693:
! 694: \begin{enumerate}
! 695: \item (C $\rightarrow$ S) Arguments are sent in binary encoded form.
! 696: \item (C $\rightarrow$ S) The number of aruments is sent as {\sl Integer32}.
! 697: \item (C $\rightarrow$ S) A function name is sent as {\sl Cstring}.
! 698: \item (C $\rightarrow$ S) A command {\tt SM\_executeFunction} is sent.
! 699: \item The result is pushed to the stack.
! 700: \item (C $\rightarrow$ S) A command {\tt SM\_popCMO} is sent.
! 701: \item (S $\rightarrow$ C) The result is sent in binary encoded form.
! 702: \end{enumerate}
! 703:
! 704: $\Rightarrow$ Communication is fast, but functions for binary data
! 705: conversion are necessary.
! 706: \end{slide}
! 707:
! 708: \begin{slide}{}
! 709: \fbox{Executing functions on a server (II) --- {\tt SM\_executeString}}
! 710:
! 711: \begin{enumerate}
! 712: \item (C $\rightarrow$ S) A character string represeting a request in a server's
! 713: user language is sent as {\sl Cstring}.
! 714: \item (C $\rightarrow$ S) A command {\tt SM\_executeString} is sent.
! 715: \item The result is pushed to the stack.
! 716: \item (C $\rightarrow$ S) A command {\tt SM\_popString} is sent.
! 717: \item (S $\rightarrow$ C) The result is sent in readable form.
! 718: \end{enumerate}
! 719:
! 720: $\Rightarrow$ Communication may be slow, but the client parser may be
! 721: enough to read the result.
! 722: \end{slide}
! 723:
! 724: %\begin{slide}{}
! 725: %\fbox{History of development : ---1994}
! 726: %
! 727: %\begin{itemize}
! 728: %\item --1989
! 729: %
! 730: %Several subroutines were developed for a Prolog program.
! 731: %
! 732: %\item 1989--1992
! 733: %
! 734: %\begin{itemize}
! 735: %\item Reconfigured as Risa/Asir with a parser and Boehm's conservative GC [Boehm]
! 736: %
! 737: %\item Developed univariate and multivariate factorizers over the rationals.
! 738: %\end{itemize}
! 739: %
! 740: %\item 1992--1994
! 741: %
! 742: %\begin{itemize}
! 743: %\item Started implementation of Buchberger algorithm
! 744: %
! 745: %Written in user language $\Rightarrow$ rewritten in C (by Murao)
! 746: %
! 747: %$\Rightarrow$ trace lifting [Traverso]
! 748: %
! 749: %\item Univariate factorization over algebraic number fields
! 750: %
! 751: %Intensive use of successive extension, non-squarefree norms
! 752: %\end{itemize}
! 753: %\end{itemize}
! 754: %
! 755: %\end{slide}
! 756: %
! 757: %\begin{slide}{}
! 758: %\fbox{History of development : 1994-1996}
! 759: %
! 760: %\begin{itemize}
! 761: %\item Free distribution of binary versions from Fujitsu
! 762: %
! 763: %\item Primary ideal decomposition
! 764: %
! 765: %\begin{itemize}
! 766: %\item Shimoyama-Yokoyama algorithm [SY]
! 767: %\end{itemize}
! 768: %
! 769: %\item Improvement of Buchberger algorithm
! 770: %
! 771: %\begin{itemize}
! 772: %\item Trace lifting+homogenization
! 773: %
! 774: %\item Omitting check by compatible prime
! 775: %
! 776: %\item Modular change of ordering, Modular RUR
! 777: %
! 778: %These are joint works with Yokoyama [NY]
! 779: %\end{itemize}
! 780: %\end{itemize}
! 781: %
! 782: %\end{slide}
! 783: %
! 784: %\begin{slide}{}
! 785: %\fbox{History of development : 1996-1998}
! 786: %
! 787: %\begin{itemize}
! 788: %\item Distributed compuatation
! 789: %
! 790: %\begin{itemize}
! 791: %\item A prototype of OpenXM
! 792: %\end{itemize}
! 793: %
! 794: %\item Improvement of Buchberger algorithm
! 795: %
! 796: %\begin{itemize}
! 797: %\item Content reduction during nomal form computation
! 798: %
! 799: %\item Its parallelization by the above facility
! 800: %
! 801: %\item Computation of odd order replicable functions [Noro]
! 802: %
! 803: %Risa/Asir : it took 5days to compute a DRL basis ({\it McKay})
! 804: %
! 805: %Faug\`ere FGb : computation of the DRL basis 53sec
! 806: %\end{itemize}
! 807: %
! 808: %
! 809: %\item Univariate factorization over large finite fields
! 810: %
! 811: %\begin{itemize}
! 812: %\item To implement Schoof-Elkies-Atkin algorithm
! 813: %
! 814: %Counting rational points on elliptic curves
! 815: %
! 816: %--- not free But related functions are freely available
! 817: %\end{itemize}
! 818: %\end{itemize}
! 819: %
! 820: %\end{slide}
! 821: %
! 822: %\begin{slide}{}
! 823: %\fbox{History of development : 1998-2000}
! 824: %\begin{itemize}
! 825: %\item OpenXM
! 826: %
! 827: %\begin{itemize}
! 828: %\item OpenXM specification was written by Noro and Takayama
! 829: %
! 830: %Borrowed idea on encoding, phrase book from OpenMath [OpenMath]
! 831: %
! 832: %\item Functions for distributed computation were rewritten
! 833: %\end{itemize}
! 834: %
! 835: %\item Risa/Asir on Windows
! 836: %
! 837: %\begin{itemize}
! 838: %\item Requirement from a company for which Noro worked
! 839: %
! 840: %Written in Visual C++
! 841: %\end{itemize}
! 842: %
! 843: %\item Test implementation of $F_4$
! 844: %
! 845: %\begin{itemize}
! 846: %\item Implemented according to [Faug\`ere]
! 847: %
! 848: %\item Over $GF(p)$ : pretty good
! 849: %
! 850: %\item Over the rationals : not so good except for {\it McKay}
! 851: %\end{itemize}
! 852: %\end{itemize}
! 853: %\end{slide}
! 854: %
! 855: %\begin{slide}{}
! 856: %\fbox{History of development : 2000-current}
! 857: %\begin{itemize}
! 858: %\item The source code is freely available
! 859: %
! 860: %\begin{itemize}
! 861: %\item Noro moved from Fujitsu to Kobe university
! 862: %
! 863: %Started Kobe branch [Risa/Asir]
! 864: %\end{itemize}
! 865: %
! 866: %\item OpenXM [OpenXM]
! 867: %
! 868: %\begin{itemize}
! 869: %\item Revising the specification : OX-RFC100, 101, (102)
! 870: %
! 871: %\item OX-RFC102 : communications between servers via MPI
! 872: %\end{itemize}
! 873: %
! 874: %\item Weyl algebra
! 875: %
! 876: %\begin{itemize}
! 877: %\item Buchberger algorithm [Takayama]
! 878: %
! 879: %\item $b$-function computation [Oaku]
! 880: %
! 881: %Minimal polynomial computation by modular method
! 882: %\end{itemize}
! 883: %\end{itemize}
! 884: %
! 885: %\end{slide}
1.1 noro 886: \begin{slide}{}
887: \end{slide}
888:
889: \begin{slide}{}
890: \end{slide}
891:
892: \begin{slide}{}
893: \end{slide}
894:
895: \begin{slide}{}
896: \end{slide}
897:
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