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