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