Annotation of OpenXM/doc/Papers/dagb-noro.tex, Revision 1.2
1.2 ! noro 1: % $OpenXM: OpenXM/doc/Papers/dagb-noro.tex,v 1.1 2001/10/03 08:32:58 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:
231: \item Rings of differential operators
232:
233: \begin{itemize}
1.2 ! noro 234: \item Buchberger algorithm [Takayama]
1.1 noro 235:
1.2 ! noro 236: \item $b$-function computation [OT]
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:
293: Singular's Groebner basis computation is also several times
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:
! 537: [SY] T. Shimoyama, K. Yokoyama, Localization and Primary Decomposition of Polynomial Ideals. J. Symb. Comp. {\bf 22} (1996), 247-277.
! 538:
! 539: [NY] M. Noro, K. Yokoyama,
! 540: A Modular Method to Compute the Rational Univariate
! 541: Representation of Zero-Dimensional Ideals.
! 542: J. Symb. Comp. {\bf 28}/1 (1999), 243-263.
! 543:
! 544: [OpenMath] {\tt http://www.openmath.org}
! 545:
! 546: [OpenXM] {\tt http://www.openxm.org}
! 547:
! 548: [PARI] {\tt http://www.parigp-home.de}
! 549:
! 550: [Risa/Asir] {\tt http://www.math.kobe-u.ac.jp/Asir/asir.html}
! 551:
! 552: [Rouillier] F. Rouillier,
! 553: R\'esolution des syst\`emes z\'ero-dimensionnels.
! 554: Doctoral Thesis(1996), University of Rennes I, France.
! 555:
! 556: [Traverso] C. Traverso, \gr trace algorithms. Proc. ISSAC '88 (LNCS 358), 125-138.
! 557:
! 558: \end{slide}
! 559:
! 560: \begin{slide}{}
! 561: \begin{center}
! 562: \fbox{\large Part II : Algorithms and implementations in Risa/Asir}
! 563: \end{center}
! 564: \end{slide}
! 565:
! 566: \begin{slide}{}
1.1 noro 567: \fbox{Ground fields}
568:
569: \begin{itemize}
570: \item The rational number field
571: \item Algebraic number fields
572:
573: represented by successive extensions
574: \item Finite fields
575: \begin{itemize}
576: \item $GF(p)$ ($p<2^{30}$); represented by a single word
577: \item $GF(p^n)$ ($p^n < 2^{20}$); represented by a primitive root
578: \item $GF(2^n)$; represented by a bit string
579: \item $GF(p)$ ($p$ : arbitrary prime)
580: \item $GF(p^n)$ ($p$ : arbitrary odd prime)
581: \end{itemize}
582:
583: \item Real and complex number fields
584:
585: \begin{itemize}
586: \item Double float
587: \item PARI bigfloat
588: \end{itemize}
589:
590: \end{itemize}
591: \end{slide}
592:
593: \begin{slide}{}
594: \fbox{Polynomial factorization}
595: \begin{itemize}
596: \item Univariate factorization
597:
598: \begin{itemize}
599: \item Over the rationals
600:
601: Berlekamp-Zassenhaus
602:
603: (classical; knapsack has not yet implemented)
604:
605: \item Over algebraic number fields
606:
607: Trager's algorithm + some improvement
608:
609: \item Over finite fieds
610:
611: DDF + Cantor-Zassenhaus; FFT for large finite fields
612: \end{itemize}
613:
614: \item Multivariate factorization
615:
616: \begin{itemize}
617: \item Over the rationals
618:
619: Classical EZ algorithm
620:
1.2 ! noro 621: \item Over small finite fieds
! 622:
! 623: Modified Bernardin's square free algorithm [Bernardin],
1.1 noro 624:
1.2 ! noro 625: possibly Hensel lifting over extension fields
1.1 noro 626: \end{itemize}
627:
628: \end{itemize}
629: \end{slide}
630:
631: \begin{slide}{}
632: \fbox{Groebner basis computation --- Buchberger algorithm}
633: \begin{itemize}
634: \item Polynomial rings
635: \begin{itemize}
636: \item Over finite fields
637:
638: Any finite field is available as a ground field
639:
640: \item Over the rationals
641:
642: Guess of a groebner basis by detecting zero reduction by modular computation
643: + check (trace lifting)
644:
645: Homogenization+guess+dehomogenization+check
646: \end{itemize}
647:
648: \item Rings of differential operators
649:
650: \begin{itemize}
651: \item Groebner basis of a left ideal
652:
1.2 ! noro 653: Key : an efficient implementation of Leibniz rule
1.1 noro 654: \end{itemize}
655:
656: \end{itemize}
657: \end{slide}
658:
659: \begin{slide}{}
660: \fbox{$F_4$ algorithm}
661: \begin{itemize}
662: \item Over small finite fields ($GF(p)$, $p < 2^{30}$)
663: \begin{itemize}
1.2 ! noro 664: \item More efficient than our Buchberger algorithm implementation
1.1 noro 665:
666: but less efficient than FGb by Faugere
667: \end{itemize}
668:
669: \item Over the rationals
670:
671: \begin{itemize}
672: \item Very naive implementation
673:
1.2 ! noro 674: Modular computation + CRT + Checking the result at each degree
! 675:
1.1 noro 676: \item Less efficient than Buchberger algorithm
677:
1.2 ! noro 678: except for one example (={\it McKay})
1.1 noro 679: \end{itemize}
680:
681: \end{itemize}
682: \end{slide}
683:
684: \begin{slide}{}
1.2 ! noro 685: \fbox{Change of ordering for zero-dimensional ideals}
1.1 noro 686:
687: \begin{itemize}
688: \item Any ordering to lex ordering
689:
690: \begin{itemize}
691: \item Modular change of ordering
692:
693: Guess of the support by modular FGLM
694:
695: + solving linear systems by Hensel lifting
696:
697: \end{itemize}
698:
699: \item RUR (generalized shape lemma)
700:
701: \begin{itemize}
702: \item Modular RUR (only implemented on the shape base case)
703:
704: Almost the same as modular change of ordering
705: \end{itemize}
706:
707: \end{itemize}
708: \end{slide}
709:
710: \begin{slide}{}
711: \fbox{Primary decomposition --- Shimoyama-Yokoyama algorithm}
712:
713: \begin{itemize}
714: \item Only implemented over the rationals
715:
716: Finite field version will soon be available
717:
718: \item Pseudo primary ideal
719:
720: An ideal whose radical is prime
721:
722: \item Prime decomp. of the radical $\Rightarrow$ pseudo primary decomp.
723:
724: \item Extraction of embedded components
725:
726: \end{itemize}
727:
728: \end{slide}
729:
730: \begin{slide}{}
731: \fbox{Computation of $b$-function}
732:
733: $D$ : the ring of differential operators
734:
735: $b(s)$ : a polynomial of the smallest degree s.t.
736: there exists $P(s) \in D[s]$, $P(s)f^{s+1}=b(s)f^s$
737:
738: $b(s)$ : $b$-function of a polynomial $f$
739:
740: $\Rightarrow$ $b(s)$ can be computed by Oaku's algorithm
741:
742: On Risa/Asir : $b(s)$ is computed by
743:
744: A groebner basis $\Rightarrow$ guess of $\deg(b(s))$ by modular
745: computation $\Rightarrow$ solving a linear system
746: \end{slide}
747:
748: \begin{slide}{}
749: \fbox{Interface to PARI library}
750:
751: \begin{itemize}
752: \item Data conversion
753:
754: \begin{itemize}
755:
756: \item Only primitive data can be passed to PARI
757:
758: Rational number, bignum, bigfloat, polynomial,
759: vector, matrix
760:
761: \item Results are converted to Risa objects
762:
763: \end{itemize}
764:
765: \item Evaluation of transcendental functions
766:
767: \begin{itemize}
768: \item Most of univariate functions in PARI can be
769: evaluated by {\tt eval()}
770: \end{itemize}
771:
772: \item Calling PARI functions
773:
774: \begin{itemize}
775: \item One can call PARI functions by {\tt pari({\it parifunction},{\it args})}
776:
777: The knapsack factorization is available via {\tt pari(factor,{\it poly})}
778: \end{itemize}
779: \end{itemize}
780: \end{slide}
781:
782: \begin{slide}{}
783: \end{slide}
784:
785: \begin{slide}{}
786: \end{slide}
787:
788: \begin{slide}{}
789: \end{slide}
790:
791: \begin{slide}{}
792: \end{slide}
793:
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