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