Annotation of OpenXM/doc/Papers/dag-noro-suppl.tex, Revision 1.1
1.1 ! noro 1: % $OpenXM$
! 2: \documentclass{slides}
! 3: \usepackage{color}
! 4: \usepackage{rgb}
! 5: \usepackage{graphicx}
! 6: \usepackage{epsfig}
! 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: \begin{document}
! 19: \setlength{\parskip}{10pt}
! 20: %\begin{slide}{}
! 21: %\begin{center}
! 22: %\fbox{\large Part II : Algorithms and implementations in Risa/Asir}
! 23: %\end{center}
! 24: %\end{slide}
! 25:
! 26: \begin{slide}{}
! 27: \fbox{Ground fields}
! 28:
! 29: \begin{itemize}
! 30: \item The rational number field
! 31: \item Algebraic number fields
! 32:
! 33: represented by successive extensions
! 34: \item Finite fields
! 35: \begin{itemize}
! 36: \item $GF(p)$ ($p<2^{30}$); represented by a single word
! 37: \item $GF(p^n)$ ($p^n < 2^{20}$); represented by a primitive root
! 38: \item $GF(2^n)$; represented by a bit string
! 39: \item $GF(p)$ ($p$ : arbitrary prime)
! 40: \item $GF(p^n)$ ($p$ : arbitrary odd prime)
! 41: \end{itemize}
! 42:
! 43: \item Real and complex number fields
! 44:
! 45: \begin{itemize}
! 46: \item Double float
! 47: \item PARI bigfloat
! 48: \end{itemize}
! 49:
! 50: \end{itemize}
! 51: \end{slide}
! 52:
! 53: \begin{slide}{}
! 54: \fbox{Polynomial factorization}
! 55: \begin{itemize}
! 56: \item Univariate factorization
! 57:
! 58: \begin{itemize}
! 59: \item Over the rationals
! 60:
! 61: Berlekamp-Zassenhaus
! 62:
! 63: (classical; knapsack has not yet implemented)
! 64:
! 65: \item Over algebraic number fields
! 66:
! 67: Trager's algorithm + some improvement
! 68:
! 69: \item Over finite fields
! 70:
! 71: DDF + Cantor-Zassenhaus; FFT for large finite fields
! 72: \end{itemize}
! 73:
! 74: \item Multivariate factorization
! 75:
! 76: \begin{itemize}
! 77: \item Over the rationals
! 78:
! 79: Classical EZ algorithm
! 80:
! 81: \item Over small finite fields
! 82:
! 83: Modified Bernardin's square free algorithm [BERN97],
! 84:
! 85: possibly Hensel lifting over extension fields
! 86: \end{itemize}
! 87:
! 88: \end{itemize}
! 89: \end{slide}
! 90:
! 91: \begin{slide}{}
! 92: \fbox{Groebner basis computation --- Buchberger algorithm}
! 93: \begin{itemize}
! 94: \item Polynomial rings
! 95: \begin{itemize}
! 96: \item Over finite fields
! 97:
! 98: Any finite field is available as a ground field
! 99:
! 100: \item Over the rationals
! 101:
! 102: Guess of a groebner basis by detecting zero reduction by modular computation
! 103: + check (trace lifting)
! 104:
! 105: Homogenization+guess+dehomogenization+check
! 106: \end{itemize}
! 107:
! 108: \item Weyl Algebra
! 109:
! 110: \begin{itemize}
! 111: \item Groebner basis of a left ideal
! 112:
! 113: Key : an efficient implementation of Leibniz rule
! 114: \end{itemize}
! 115:
! 116: \end{itemize}
! 117: \end{slide}
! 118:
! 119: \begin{slide}{}
! 120: \fbox{$F_4$ algorithm}
! 121: \begin{itemize}
! 122: \item Over small finite fields ($GF(p)$, $p < 2^{30}$)
! 123: \begin{itemize}
! 124: \item More efficient than our Buchberger algorithm implementation
! 125:
! 126: but less efficient than FGb by Faug\`ere
! 127: \end{itemize}
! 128:
! 129: \item Over the rationals
! 130:
! 131: \begin{itemize}
! 132: \item Very naive implementation
! 133:
! 134: Modular computation + CRT + Checking the result at each degree
! 135:
! 136: \item Less efficient than Buchberger algorithm
! 137:
! 138: except for one example (={\it McKay})
! 139: \end{itemize}
! 140:
! 141: \end{itemize}
! 142: \end{slide}
! 143:
! 144: \begin{slide}{}
! 145: \fbox{Change of ordering for zero-dimensional ideals}
! 146:
! 147: \begin{itemize}
! 148: \item Any ordering to lex ordering
! 149:
! 150: \begin{itemize}
! 151: \item Modular change of ordering
! 152:
! 153: Guess of the support by modular FGLM
! 154:
! 155: + solving linear systems by Hensel lifting
! 156:
! 157: \end{itemize}
! 158:
! 159: \item RUR (generalized shape lemma)
! 160:
! 161: \begin{itemize}
! 162: \item Modular RUR (only implemented on the shape base case)
! 163:
! 164: Almost the same as modular change of ordering
! 165: \end{itemize}
! 166:
! 167: \end{itemize}
! 168: \end{slide}
! 169:
! 170: \begin{slide}{}
! 171: \fbox{Primary decomposition --- Shimoyama-Yokoyama algorithm}
! 172:
! 173: \begin{itemize}
! 174: \item Only implemented over the rationals
! 175:
! 176: Finite field version will soon be available
! 177:
! 178: \item Pseudo primary ideal
! 179:
! 180: An ideal whose radical is prime
! 181:
! 182: \item Prime decomp. of the radical $\Rightarrow$ pseudo primary decomp.
! 183:
! 184: \item Extraction of embedded components
! 185:
! 186: \end{itemize}
! 187:
! 188: \end{slide}
! 189:
! 190: \begin{slide}{}
! 191: \fbox{Computation of $b$-function}
! 192:
! 193: $D=K\langle x,\partial \rangle$ : Weyl algebra
! 194:
! 195: $b(s)$ : a polynomial of the smallest degree s.t.
! 196: there exists $P(s) \in D[s]$, $P(s)f^{s+1}=b(s)f^s$
! 197:
! 198: $b(s)$ : $b$-function of a polynomial $f$
! 199:
! 200: $\Rightarrow$ $b(s)$ can be computed by Oaku's algorithm
! 201:
! 202: On Risa/Asir : $b(s)$ is computed by
! 203:
! 204: A groebner basis $\Rightarrow$ guess of $\deg(b(s))$ by modular
! 205: computation $\Rightarrow$ solving a linear system
! 206: \end{slide}
! 207:
! 208: \begin{slide}{}
! 209: \fbox{Interface to PARI library}
! 210:
! 211: \begin{itemize}
! 212: \item Data conversion
! 213:
! 214: \begin{itemize}
! 215:
! 216: \item Only primitive data can be passed to PARI
! 217:
! 218: Rational number, bignum, bigfloat, polynomial,
! 219: vector, matrix
! 220:
! 221: \item Results are converted to Risa objects
! 222:
! 223: \end{itemize}
! 224:
! 225: \item Evaluation of transcendental functions
! 226:
! 227: \begin{itemize}
! 228: \item Most of univariate functions in PARI can be
! 229: evaluated by {\tt eval()}
! 230: \end{itemize}
! 231:
! 232: \item Calling PARI functions
! 233:
! 234: \begin{itemize}
! 235: \item One can call PARI functions by {\tt pari({\it parifunction},{\it args})}
! 236:
! 237: The knapsack factorization is available via {\tt pari(factor,{\it poly})}
! 238: \end{itemize}
! 239: \end{itemize}
! 240: \end{slide}
! 241:
! 242: \begin{slide}{}
! 243: \fbox{OpenXM server interface in Risa/Asir}
! 244:
! 245: \begin{itemize}
! 246: \item TCP/IP stream
! 247:
! 248: \begin{itemize}
! 249: \item Launcher
! 250:
! 251: A client executes a launcher on a host.
! 252:
! 253: The launcher launches a server on the same host.
! 254:
! 255: \item Server
! 256:
! 257: Reads from the descriptor 3
! 258:
! 259: Writes to the descriptor 4
! 260:
! 261: \end{itemize}
! 262:
! 263: \item Subroutine call
! 264:
! 265: In Risa/Asir subroutine library {\tt libasir.a}:
! 266:
! 267: OpenXM functionalities are implemented as function calls
! 268:
! 269: pushing and popping data, executing stack commands etc.
! 270: \end{itemize}
! 271: \end{slide}
! 272:
! 273: \begin{slide}{}
! 274: \fbox{OpenXM client interface in Risa/Asir}
! 275:
! 276: \begin{itemize}
! 277: \item Primitive interface functions
! 278:
! 279: Pushing and popping data, sending commands etc.
! 280:
! 281: \item Convenient functions
! 282:
! 283: Launching servers,
! 284:
! 285: Calling remote functions,
! 286:
! 287: Resetting remote executions etc.
! 288:
! 289: \item Parallel distributed computation
! 290:
! 291: Simple parallelization is practically important
! 292:
! 293: Competitive computation is easily realized ($\Rightarrow$ demo)
! 294: \end{itemize}
! 295: \end{slide}
! 296:
! 297: \begin{slide}{}
! 298: \fbox{Executing functions on a server (I) --- {\tt SM\_executeFunction}}
! 299:
! 300: \begin{enumerate}
! 301: \item (C $\rightarrow$ S) Arguments are sent in binary encoded form.
! 302: \item (C $\rightarrow$ S) The number of arguments is sent as {\sl Integer32}.
! 303: \item (C $\rightarrow$ S) A function name is sent as {\sl Cstring}.
! 304: \item (C $\rightarrow$ S) A command {\tt SM\_executeFunction} is sent.
! 305: \item The result is pushed to the stack.
! 306: \item (C $\rightarrow$ S) A command {\tt SM\_popCMO} is sent.
! 307: \item (S $\rightarrow$ C) The result is sent in binary encoded form.
! 308: \end{enumerate}
! 309:
! 310: $\Rightarrow$ Communication is fast, but functions for binary data
! 311: conversion are necessary.
! 312: \end{slide}
! 313:
! 314: \begin{slide}{}
! 315: \fbox{Executing functions on a server (II) --- {\tt SM\_executeString}}
! 316:
! 317: \begin{enumerate}
! 318: \item (C $\rightarrow$ S) A character string representing a request in a server's
! 319: user language is sent as {\sl Cstring}.
! 320: \item (C $\rightarrow$ S) A command {\tt SM\_executeString} is sent.
! 321: \item The result is pushed to the stack.
! 322: \item (C $\rightarrow$ S) A command {\tt SM\_popString} is sent.
! 323: \item (S $\rightarrow$ C) The result is sent in readable form.
! 324: \end{enumerate}
! 325:
! 326: $\Rightarrow$ Communication may be slow, but the client parser may be
! 327: enough to read the result.
! 328: \end{slide}
! 329:
! 330: %\begin{slide}{}
! 331: %\fbox{History of development : ---1994}
! 332: %
! 333: %\begin{itemize}
! 334: %\item --1989
! 335: %
! 336: %Several subroutines were developed for a Prolog program.
! 337: %
! 338: %\item 1989--1992
! 339: %
! 340: %\begin{itemize}
! 341: %\item Reconfigured as Risa/Asir with a parser and Boehm's conservative GC
! 342: %
! 343: %\item Developed univariate and multivariate factorizers over the rationals.
! 344: %\end{itemize}
! 345: %
! 346: %\item 1992--1994
! 347: %
! 348: %\begin{itemize}
! 349: %\item Started implementation of Buchberger algorithm
! 350: %
! 351: %Written in user language $\Rightarrow$ rewritten in C (by Murao)
! 352: %
! 353: %$\Rightarrow$ trace lifting [TRAV88]
! 354: %
! 355: %\item Univariate factorization over algebraic number fields
! 356: %
! 357: %Intensive use of successive extension, non-squarefree norms
! 358: %\end{itemize}
! 359: %\end{itemize}
! 360: %
! 361: %\end{slide}
! 362: %
! 363: %\begin{slide}{}
! 364: %\fbox{History of development : 1994-1996}
! 365: %
! 366: %\begin{itemize}
! 367: %\item Free distribution of binary versions from Fujitsu
! 368: %
! 369: %\item Primary ideal decomposition
! 370: %
! 371: %\begin{itemize}
! 372: %\item Shimoyama-Yokoyama algorithm [SHYO96]
! 373: %\end{itemize}
! 374: %
! 375: %\item Improvement of Buchberger algorithm
! 376: %
! 377: %\begin{itemize}
! 378: %\item Trace lifting+homogenization
! 379: %
! 380: %\item Omitting check by compatible prime
! 381: %
! 382: %\item Modular change of ordering, Modular RUR
! 383: %
! 384: %These are joint works with Yokoyama [NOYO99]
! 385: %\end{itemize}
! 386: %\end{itemize}
! 387: %
! 388: %\end{slide}
! 389: %
! 390: %\begin{slide}{}
! 391: %\fbox{History of development : 1996-1998}
! 392: %
! 393: %\begin{itemize}
! 394: %\item Distributed computation
! 395: %
! 396: %\begin{itemize}
! 397: %\item A prototype of OpenXM
! 398: %\end{itemize}
! 399: %
! 400: %\item Improvement of Buchberger algorithm
! 401: %
! 402: %\begin{itemize}
! 403: %\item Content reduction during normal form computation
! 404: %
! 405: %\item Its parallelization by the above facility
! 406: %
! 407: %\item Computation of odd order replicable functions [NORO97]
! 408: %
! 409: %Risa/Asir : it took 5days to compute a DRL basis ({\it McKay})
! 410: %
! 411: %Faug\`ere FGb : computation of the DRL basis 53sec
! 412: %\end{itemize}
! 413: %
! 414: %
! 415: %\item Univariate factorization over large finite fields
! 416: %
! 417: %\begin{itemize}
! 418: %\item To implement Schoof-Elkies-Atkin algorithm
! 419: %
! 420: %Counting rational points on elliptic curves
! 421: %
! 422: %--- not free But related functions are freely available
! 423: %\end{itemize}
! 424: %\end{itemize}
! 425: %
! 426: %\end{slide}
! 427: %
! 428: %\begin{slide}{}
! 429: %\fbox{History of development : 1998-2000}
! 430: %\begin{itemize}
! 431: %\item OpenXM
! 432: %
! 433: %\begin{itemize}
! 434: %\item OpenXM specification was written by Noro and Takayama
! 435: %
! 436: %Borrowed idea on encoding, phrase book from OpenMath
! 437: %
! 438: %\item Functions for distributed computation were rewritten
! 439: %\end{itemize}
! 440: %
! 441: %\item Risa/Asir on Windows
! 442: %
! 443: %\begin{itemize}
! 444: %\item Requirement from a company for which Noro worked
! 445: %
! 446: %Written in Visual C++
! 447: %\end{itemize}
! 448: %
! 449: %\item Test implementation of $F_4$
! 450: %
! 451: %\begin{itemize}
! 452: %\item Implemented according to [FAUG99]
! 453: %
! 454: %\item Over $GF(p)$ : pretty good
! 455: %
! 456: %\item Over the rationals : not so good except for {\it McKay}
! 457: %\end{itemize}
! 458: %\end{itemize}
! 459: %\end{slide}
! 460: %
! 461: %\begin{slide}{}
! 462: %\fbox{History of development : 2000-current}
! 463: %\begin{itemize}
! 464: %\item The source code is freely available
! 465: %
! 466: %\begin{itemize}
! 467: %\item Noro moved from Fujitsu to Kobe university
! 468: %
! 469: %Started Kobe branch
! 470: %\end{itemize}
! 471: %
! 472: %\item OpenXM
! 473: %
! 474: %\begin{itemize}
! 475: %\item Revising the specification : OX-RFC100, 101, (102)
! 476: %
! 477: %\item OX-RFC102 : communications between servers via MPI
! 478: %\end{itemize}
! 479: %
! 480: %\item Weyl algebra
! 481: %
! 482: %\begin{itemize}
! 483: %\item Buchberger algorithm [TAKA90]
! 484: %
! 485: %\item $b$-function computation [OAKU97]
! 486: %
! 487: %Minimal polynomial computation by modular method
! 488: %\end{itemize}
! 489: %\end{itemize}
! 490: %
! 491: %\end{slide}
! 492: \begin{slide}{}
! 493: \end{slide}
! 494:
! 495: \begin{slide}{}
! 496: \end{slide}
! 497:
! 498: \begin{slide}{}
! 499: \end{slide}
! 500:
! 501: \begin{slide}{}
! 502: \end{slide}
! 503: \end{document}
! 504:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to dag-noro-suppl.tex CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM / doc / Papers