Annotation of OpenXM/doc/Papers/dag-noro.tex, Revision 1.3
1.3 ! noro 1: % $OpenXM: OpenXM/doc/Papers/dag-noro.tex,v 1.2 2001/10/10 06:32:10 noro Exp $
! 2: \documentclass{slides}
! 3: \usepackage{color}
! 4: \usepackage{rgb}
! 5: \usepackage{graphicx}
! 6: \usepackage{epsfig}
1.1 noro 7: \newcommand{\qed}{$\Box$}
8: \newcommand{\mred}[1]{\smash{\mathop{\hbox{\rightarrowfill}}\limits_{\scriptstyle #1}}}
9: \newcommand{\tmred}[1]{\smash{\mathop{\hbox{\rightarrowfill}}\limits_{\scriptstyle #1}\limits^{\scriptstyle *}}}
10: \def\gr{Gr\"obner basis }
11: \def\st{\, s.t. \,}
12: \def\ni{\noindent}
13: \def\ve{\vfill\eject}
14: \textwidth 9.2in
15: \textheight 7.2in
16: \columnsep 0.33in
17: \topmargin -1in
18:
1.3 ! noro 19: \title{A computer algebra system Risa/Asir and OpenXM}
1.1 noro 20:
1.3 ! noro 21: \author{Masayuki Noro\\ Kobe University, Japan}
1.1 noro 22: \begin{document}
23: \setlength{\parskip}{10pt}
24: \maketitle
1.3 ! noro 25:
! 26: %\begin{slide}{}
! 27: %\begin{center}
! 28: %\fbox{\large Part I : OpenXM and Risa/Asir --- overview and history}
! 29: %\end{center}
! 30: %\end{slide}
! 31:
! 32: %\begin{slide}{}
! 33: %\fbox{Integration of mathematical software systems}
! 34: %
! 35: %\begin{itemize}
! 36: %\item Data integration
! 37: %
! 38: %\begin{itemize}
! 39: %\item OpenMath ({\tt http://www.openmath.org}) , MP [GRAY98]
! 40: %\end{itemize}
! 41: %
! 42: %Standards for representing mathematical objects
! 43: %
! 44: %\item Control integration
! 45: %
! 46: %\begin{itemize}
! 47: %\item MCP [WANG99], OMEI [LIAO01]
! 48: %\end{itemize}
! 49: %
! 50: %Protocols for remote subroutine calls or session management
! 51: %
! 52: %\item Combination of two integrations
! 53: %
! 54: %\begin{itemize}
! 55: %\item MathLink, OpenMath+MCP, MP+MCP
! 56: %
! 57: %and OpenXM ({\tt http://www.openxm.org})
! 58: %\end{itemize}
! 59: %
! 60: %Both are necessary for practical implementation
! 61: %
! 62: %\end{itemize}
! 63: %\end{slide}
! 64: \begin{slide}{}
! 65: \fbox{A computer algebra system Risa/Asir}
! 66:
! 67: ({\tt http://www.math.kobe-u.ac.jp/Asir/asir.html})
! 68:
! 69: \begin{itemize}
! 70: \item Software mainly for polynomial computation
! 71:
! 72: \item User language with C-like syntax
! 73:
! 74: C language without type declaration, with list processing
! 75:
! 76: \item Builtin {\tt gdb}-like debugger for user programs
! 77:
! 78: \item Open source
! 79:
! 80: Whole source tree is available via CVS
! 81:
! 82: The latest version : see {\tt http://www.openxm.org}
! 83:
! 84: \item OpenXM interface
! 85:
! 86: \begin{itemize}
! 87: \item OpenXM
! 88:
! 89: An infrastructure for exchanging mathematical data
! 90: \item Risa/Asir is a main client in OpenXM package.
! 91: \item An OpenXM server {\tt ox\_asir}
! 92: \item A library with OpenXM library interface {\tt libasir.a}
! 93: \end{itemize}
! 94: \end{itemize}
! 95: \end{slide}
! 96:
! 97: \begin{slide}{}
! 98: \fbox{Goal of developing Risa/Asir}
! 99:
! 100: \begin{itemize}
! 101: \item Testing new algorithms
! 102:
! 103: \begin{itemize}
! 104: \item Development started in Fujitsu labs
! 105:
! 106: Polynomial factorization, Groebner basis related computation,
! 107: cryptosystems , quantifier elimination , $\ldots$
! 108: \end{itemize}
! 109:
! 110: \item To be a general purpose, open system
! 111:
! 112: Since 1997, we have been developing OpenXM package
! 113: containing various servers and clients
! 114:
! 115: Risa/Asir is a component of OpenXM
! 116:
! 117: \item Environment for parallel and distributed computation
! 118:
! 119: \end{itemize}
! 120: \end{slide}
! 121:
! 122: %\begin{slide}{}
! 123: %\fbox{Capability for polynomial computation}
! 124: %
! 125: %\begin{itemize}
! 126: %\item Fundamental polynomial arithmetics
! 127: %
! 128: %recursive representation and distributed representation
! 129: %
! 130: %\item Polynomial factorization
! 131: %
! 132: %\begin{itemize}
! 133: %\item Univariate : over {\bf Q}, algebraic number fields and finite fields
! 134: %
! 135: %\item Multivariate : over {\bf Q}
! 136: %\end{itemize}
! 137: %
! 138: %\item Groebner basis computation
! 139: %
! 140: %\begin{itemize}
! 141: %\item Buchberger and $F_4$ [FAUG99] algorithm
! 142: %
! 143: %\item Change of ordering/RUR [ROUI96] of 0-dimensional ideals
! 144: %
! 145: %\item Primary ideal decomposition
! 146: %
! 147: %\item Computation of $b$-function (in Weyl Algebra)
! 148: %\end{itemize}
! 149: %\end{itemize}
! 150: %\end{slide}
! 151:
! 152: \begin{slide}{}
! 153: \fbox{History of development : Polynomial factorization}
! 154:
! 155: \begin{itemize}
! 156: \item 1989
! 157:
! 158: Start of Risa/Asir with Boehm's conservative GC
! 159:
! 160: ({\tt http://www.hpl.hp.com/personal/Hans\_Boehm/gc})
! 161:
! 162: \item 1989-1992
! 163:
! 164: Univariate and multivariate factorizers over {\bf Q}
! 165:
! 166: \item 1992-1994
! 167:
! 168: Univariate factorization over algebraic number fields
! 169:
! 170: Intensive use of successive extension, non-squarefree norms
! 171:
! 172: \item 1996-1998
! 173:
! 174: Univariate factorization over large finite fields
! 175:
! 176: Motivated by a reseach project in Fujitsu on cryptography
! 177:
! 178: \item 2000-current
! 179:
! 180: Multivariate factorization over small finite fields (in progress)
! 181: \end{itemize}
! 182: \end{slide}
! 183:
! 184: \begin{slide}{}
! 185: \fbox{History of development : Groebner basis}
! 186:
! 187: \begin{itemize}
! 188: \item 1992-1994
! 189:
! 190: User language $\Rightarrow$ C version; trace lifting [TRAV88]
! 191:
! 192: \item 1994-1996
! 193:
! 194: Trace lifting with homogenization
! 195:
! 196: Omitting GB check by compatible prime [NOYO99]
! 197:
! 198: Modular change of ordering/RUR[ROUI96] [NOYO99]
! 199:
! 200: Primary ideal decomposition [SHYO96]
! 201:
! 202: \item 1996-1998
! 203:
! 204: Efficient content reduction during NF computation [NORO97]
! 205: Solved {\it McKay} system for the first time
! 206:
! 207: \item 1998-2000
! 208:
! 209: Test implementation of $F_4$ [FAUG99]
! 210:
! 211: \item 2000-current
! 212:
! 213: Buchberger algorithm in Weyl algebra
! 214:
! 215: Efficient $b$-function computation[OAKU97] by a modular method
! 216: \end{itemize}
! 217: \end{slide}
! 218:
! 219: \begin{slide}{}
! 220: \fbox{Timing data --- Factorization}
! 221:
! 222: \underline{Univariate; over {\bf Q}}
! 223:
! 224: $N_i$ : a norm of a polynomial, $\deg(N_i) = i$
! 225: \begin{center}
! 226: \begin{tabular}{|c||c|c|c|c|} \hline
! 227: & $N_{105}$ & $N_{120}$ & $N_{168}$ & $N_{210}$ \\ \hline
! 228: Asir & 0.86 & 59 & 840 & hard \\ \hline
! 229: Asir NormFactor & 1.6 & 2.2& 6.1& hard \\ \hline
! 230: %Singular& hard? & hard?& hard? & hard? \\ \hline
! 231: CoCoA 4 & 0.2 & 7.1 & 16 & 0.5 \\ \hline\hline
! 232: NTL-5.2 & 0.16 & 0.9 & 1.4 & 0.4 \\ \hline
! 233: \end{tabular}
! 234: \end{center}
! 235:
! 236: \underline{Multivariate; over {\bf Q}}
! 237:
! 238: $W_{i,j,k} = Wang[i]\cdot Wang[j]\cdot Wang[k]$ in {\tt asir2000/lib/fctrdata}
! 239: \begin{center}
! 240: \begin{tabular}{|c||c|c|c|c|c|} \hline
! 241: & $W_{1,2,3}$ & $W_{4,5,6}$ & $W_{7,8,9}$ & $W_{10,11,12}$ & $W_{13,14,15}$ \\ \hline
! 242: Asir & 0.2 & 4.7 & 14 & 17 & 0.4 \\ \hline
! 243: %Singular& $>$15min & --- & ---& ---& ---\\ \hline
! 244: CoCoA 4 & 5.2 & $>$15min & $>$15min & $>$15min & 117 \\ \hline\hline
! 245: Mathematica 4& 0.2 & 16 & 23 & 36 & 1.1 \\ \hline
! 246: Maple 7& 0.5 & 18 & 967 & 48 & 1.3 \\ \hline
! 247: \end{tabular}
! 248: \end{center}
! 249:
! 250: %--- : not tested
! 251: \end{slide}
! 252:
! 253: \begin{slide}{}
! 254: \fbox{Timing data --- DRL Groebner basis computation}
! 255:
! 256: \underline{Over $GF(32003)$}
! 257: \begin{center}
! 258: \begin{tabular}{|c||c|c|c|c|c|c|c|} \hline
! 259: & $C_7$ & $C_8$ & $K_7$ & $K_8$ & $K_9$ & $K_{10}$ & $K_{11}$ \\ \hline
! 260: Asir $Buchberger$ & 31 & 1687 & 2.6 & 27 & 294 & 4309 & --- \\ \hline
! 261: Singular & 8.7 & 278 & 0.6 & 5.6 & 54 & 508 & 5510 \\ \hline
! 262: CoCoA 4 & 241 & $>$ 5h & 3.8 & 35 & 402 &7021 & --- \\ \hline\hline
! 263: Asir $F_4$ & 5.3 & 129 & 0.5 & 4.5 & 31 & 273 & 2641 \\ \hline
! 264: FGb(estimated) & 0.9 & 23 & 0.1 & 0.8 & 6 & 51 & 366 \\ \hline
! 265: \end{tabular}
! 266: \end{center}
! 267:
! 268: \underline{Over {\bf Q}}
! 269:
! 270: \begin{center}
! 271: \begin{tabular}{|c||c|c|c|c|c|} \hline
! 272: & $C_7$ & $Homog. C_7$ & $K_7$ & $K_8$ & $McKay$ \\ \hline
! 273: Asir $Buchberger$ & 389 & 594 & 29 & 299 & 34950 \\ \hline
! 274: Singular & --- & 15247 & 7.6 & 79 & $>$ 20h \\ \hline
! 275: CoCoA 4 & --- & 13227 & 57 & 709 & --- \\ \hline\hline
! 276: Asir $F_4$ & 989 & 456 & 90 & 991 & 4939 \\ \hline
! 277: FGb(estimated) & 8 &11 & 0.6 & 5 & 10 \\ \hline
! 278: \end{tabular}
! 279: \end{center}
! 280: --- : not tested
! 281: \end{slide}
! 282:
! 283: \begin{slide}{}
! 284: \fbox{Summary of performance}
! 285:
! 286: \begin{itemize}
! 287: \item Factorizer
! 288:
! 289: \begin{itemize}
! 290: \item Multivariate : reasonable performance
! 291:
! 292: \item Univariate : obsoleted by M. van Hoeij's new algorithm [HOEI00]
! 293: \end{itemize}
! 294:
! 295: \item Groebner basis computation
! 296:
! 297: \begin{itemize}
! 298: \item Buchberger
! 299:
! 300: Singular shows nice perfomance
! 301:
! 302: Trace lifting is efficient in some cases over {\bf Q}
! 303:
! 304: \item $F_4$
! 305:
! 306: FGb is much faster than Risa/Asir
! 307:
! 308: But we observe that {\it McKay} is computed efficiently by $F_4$
! 309: \end{itemize}
! 310: \end{itemize}
! 311:
! 312: \end{slide}
! 313:
! 314: \begin{slide}{}
! 315: \fbox{What is the merit to use Risa/Asir?}
! 316:
! 317: \begin{itemize}
! 318: \item Total performance is not excellent, but not bad
! 319:
! 320: \item A completely open system
! 321:
! 322: The whole source is available
! 323:
! 324: \item Interface compliant to OpenXM RFC-100
! 325:
! 326: The interface is fully documented
! 327:
! 328: \item It serves as a test bench to try new ideas
! 329:
! 330: Interactive debugger is very useful
! 331: \end{itemize}
! 332:
! 333: \end{slide}
! 334:
! 335:
! 336: %\begin{slide}{}
! 337: %\fbox{CMO = Serialized representation of mathematical object}
! 338: %
! 339: %\begin{itemize}
! 340: %\item primitive data
! 341: %\begin{eqnarray*}
! 342: %\mbox{Integer32} &:& ({\tt CMO\_INT32}, {\sl int32}\ \mbox{n}) \\
! 343: %\mbox{Cstring}&:& ({\tt CMO\_STRING},{\sl int32}\, \mbox{ n}, {\sl string}\, \mbox{s}) \\
! 344: %\mbox{List} &:& ({\tt CMO\_LIST}, {\sl int32}\, len, ob[0], \ldots,ob[m-1])
! 345: %\end{eqnarray*}
! 346: %
! 347: %\item numbers and polynomials
! 348: %\begin{eqnarray*}
! 349: %\mbox{ZZ} &:& ({\tt CMO\_ZZ},{\sl int32}\, {\rm f}, {\sl byte}\, \mbox{a[1]}, \ldots
! 350: %{\sl byte}\, \mbox{a[$|$f$|$]} ) \\
! 351: %\mbox{Monomial32}&:& ({\tt CMO\_MONOMIAL32}, n, \mbox{e[1]}, \ldots, \mbox{e[n]}, \mbox{Coef}) \\
! 352: %\mbox{Coef}&:& \mbox{ZZ} | \mbox{Integer32} \\
! 353: %\mbox{Dpolynomial}&:& ({\tt CMO\_DISTRIBUTED\_POLYNOMIAL},\\
! 354: % & & m, \mbox{DringDefinition}, \mbox{Monomial32}, \ldots)\\
! 355: %\mbox{DringDefinition}
! 356: % &:& \mbox{DMS of N variables} \\
! 357: % & & ({\tt CMO\_RING\_BY\_NAME}, name) \\
! 358: % & & ({\tt CMO\_DMS\_GENERIC}) \\
! 359: %\end{eqnarray*}
! 360: %\end{itemize}
! 361: %\end{slide}
! 362: %
! 363: %\begin{slide}{}
! 364: %\fbox{Stack based communication}
! 365: %
! 366: %\begin{itemize}
! 367: %\item Data arrived a client
! 368: %
! 369: %Pushed to the stack
! 370: %
! 371: %\item Result
! 372: %
! 373: %Pushd to the stack
! 374: %
! 375: %Written to the stream when requested by a command
! 376: %
! 377: %\item The reason why we use the stack
! 378: %
! 379: %\begin{itemize}
! 380: %\item Stack = I/O buffer for (possibly large) objects
! 381: %
! 382: %Multiple requests can be sent before their execution
! 383: %
! 384: %A server does not get stuck in sending results
! 385: %\end{itemize}
! 386: %\end{itemize}
! 387: %\end{slide}
! 388:
! 389: \begin{slide}{}
! 390: \fbox{OpenXM (Open message eXchange protocol for Mathematics) }
! 391:
! 392: \begin{itemize}
! 393: \item An environment for parallel distributed computation
! 394:
! 395: Both for interactive, non-interactive environment
! 396:
! 397: \item OpenXM RFC-100 = Client-server architecture
! 398:
! 399: Client $\Leftarrow$ OX (OpenXM) message $\Rightarrow$ Server
! 400:
! 401: OX (OpenXM) message : command and data
! 402:
! 403: \item Data
! 404:
! 405: Encoding : CMO (Common Mathematical Object format)
! 406:
! 407: Serialized representation of mathematical object
! 408:
! 409: --- Main idea was borrowed from OpenMath
! 410:
! 411: ({\tt http://www.openmath.org})
! 412:
! 413: \item Command
! 414:
! 415: stack machine command --- server is a stackmachine
! 416:
! 417: + server's own command sequences --- hybrid server
! 418: \end{itemize}
! 419: \end{slide}
! 420:
! 421: \begin{slide}{}
! 422: \fbox{Example of distributed computation --- $F_4$ vs. $Buchberger$ }
! 423:
! 424: \begin{verbatim}
! 425: /* competitive Gbase computation over GF(M) */
! 426: /* Cf. A.28 in SINGULAR Manual */
! 427: /* Process list is specified as an option : grvsf4(...|proc=P) */
! 428: def grvsf4(G,V,M,O)
! 429: {
! 430: P = getopt(proc);
! 431: if ( type(P) == -1 ) return dp_f4_mod_main(G,V,M,O);
! 432: P0 = P[0]; P1 = P[1]; P = [P0,P1];
! 433: map(ox_reset,P);
! 434: ox_cmo_rpc(P0,"dp_f4_mod_main",G,V,M,O);
! 435: ox_cmo_rpc(P1,"dp_gr_mod_main",G,V,0,M,O);
! 436: map(ox_push_cmd,P,262); /* 262 = OX_popCMO */
! 437: F = ox_select(P); R = ox_get(F[0]);
! 438: if ( F[0] == P0 ) { Win = "F4"; Lose = P1;}
! 439: else { Win = "Buchberger"; Lose = P0; }
! 440: ox_reset(Lose); /* simply resets the loser */
! 441: return [Win,R];
! 442: }
! 443: \end{verbatim}
! 444: \end{slide}
! 445:
! 446: \begin{slide}{}
! 447: \fbox{References}
! 448:
! 449: [BERN97] L. Bernardin, On square-free factorization of
! 450: multivariate polynomials over a finite field, Theoretical
! 451: Computer Science 187 (1997), 105-116.
! 452:
! 453: [FAUG99] J.C. Faug\`ere,
! 454: A new efficient algorithm for computing Groebner bases ($F_4$),
! 455: Journal of Pure and Applied Algebra (139) 1-3 (1999), 61-88.
! 456:
! 457: [GRAY98] S. Gray et al,
! 458: Design and Implementation of MP, A Protocol for Efficient Exchange of
! 459: Mathematical Expression,
! 460: J. Symb. Comp. {\bf 25} (1998), 213-238.
! 461:
! 462: [HOEI00] M. van Hoeij, Factoring polynomials and the knapsack problem,
! 463: to appear in Journal of Number Theory (2000).
! 464:
! 465: [LIAO01] W. Liao et al,
! 466: OMEI: An Open Mathematical Engine Interface,
! 467: Proc. ASCM2001 (2001), 82-91.
! 468: [NORO97] M. Noro, J. McKay,
! 469: Computation of replicable functions on Risa/Asir.
! 470: Proc. PASCO'97, ACM Press (1997), 130-138.
! 471: \end{slide}
! 472:
! 473: \begin{slide}{}
! 474:
! 475: [NOYO99] M. Noro, K. Yokoyama,
! 476: A Modular Method to Compute the Rational Univariate
! 477: Representation of Zero-Dimensional Ideals.
! 478: J. Symb. Comp. {\bf 28}/1 (1999), 243-263.
! 479:
! 480: [OAKU97] T. Oaku, Algorithms for $b$-functions, restrictions and algebraic
! 481: local cohomology groups of $D$-modules.
! 482: Advances in Applied Mathematics, 19 (1997), 61-105.
! 483:
! 484: [ROUI96] F. Rouillier,
! 485: R\'esolution des syst\`emes z\'ero-dimensionnels.
! 486: Doctoral Thesis(1996), University of Rennes I, France.
! 487:
! 488: [SHYO96] T. Shimoyama, K. Yokoyama, Localization and Primary Decomposition of Polynomial Ideals. J. Symb. Comp. {\bf 22} (1996), 247-277.
! 489:
! 490: [TRAV88] C. Traverso, \gr trace algorithms. Proc. ISSAC '88 (LNCS 358), 125-138.
! 491:
! 492: [WANG99] P. S. Wang,
! 493: Design and Protocol for Internet Accessible Mathematical Computation,
! 494: Proc. ISSAC '99 (1999), 291-298.
! 495: \end{slide}
1.1 noro 496: \end{document}
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to dag-noro.tex CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM / doc / Papers