Annotation of OpenXM/src/asir-doc/papers/risa-asir.tex, Revision 1.1
1.1 ! noro 1: \documentclass[12pt]{article}
! 2: \textheight 9.5in
! 3: \textwidth 6.5in
! 4: \topmargin -0.5in
! 5: \oddsidemargin -0.2in
! 6: \evensidemargin -0.2in
! 7: \usepackage{makeidx} % allows index generation
! 8: \usepackage{graphicx} % standard LaTeX graphics tool
! 9: % for including eps-figure files
! 10: \usepackage{subeqnar} % subnumbers individual equations
! 11: % within an array
! 12: \usepackage{multicol} % used for the two-column index
! 13: \usepackage{cropmark} % cropmarks for pages without
! 14: % pagenumbers
! 15: \usepackage{math} % placeholder for figures
! 16: \makeindex % used for the subject index
! 17: % please use the style sprmidx.sty with
! 18: % your makeindex program
! 19:
! 20: %upright Greek letters (example below: upright "mu")
! 21: \newcommand{\euler}[1]{{\usefont{U}{eur}{m}{n}#1}}
! 22: \newcommand{\eulerbold}[1]{{\usefont{U}{eur}{b}{n}#1}}
! 23: \newcommand{\umu}{\mbox{\euler{\char22}}}
! 24: \newcommand{\umub}{\mbox{\eulerbold{\char22}}}
! 25:
! 26: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
! 27:
! 28: %\twocolumn
! 29: %OPTIONAL%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
! 30: %
! 31: %\usepackage{amstex} % useful for coding complex math
! 32: %\mathindent\parindent % needed in case "Amstex" is used
! 33: %
! 34: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
! 35:
! 36: %AUTHOR_STYLES_AND_DEFINITIONS%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
! 37: %
! 38: %Please reduce your own definitions and macros to an absolute
! 39: %minimum since otherwise the editor will find it rather
! 40: %strenuous to compile all individual contributions to a
! 41: %single book file
! 42: \usepackage{epsfig}
! 43: \def\cont{{\rm cont}}
! 44: \def\GCD{{\rm GCD}}
! 45: \def\Q{{\bf Q}}
! 46: %
! 47: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
! 48:
! 49: \begin{document}
! 50: %
! 51: %\title*{A Computer Algebra System : Risa/Asir}
! 52: %
! 53: %
! 54: \title{A Computer Algebra System : Risa/Asir \footnote{This article is
! 55: a summary of two papers\cite{NORO}\cite{MAEKAWA}.}}
! 56: % allows explicit linebreak for the table of content
! 57: %
! 58: %
! 59: %\titlerunning{Risa/Asir}
! 60: % allows abbreviation of title, if the full title is too long
! 61: % to fit in the running head
! 62: %
! 63: \author{Masayuki Noro}
! 64: \date{}
! 65: %Kobe University, Rokko, Kobe 657-8501, Japan\\
! 66: %E-mail:noro@math.kobe-u.ac.jp}
! 67: %
! 68: %\authorrunning{Masayuki Noro}
! 69: % if there are more than two authors,
! 70: % please abbreviate author list for running head
! 71: %
! 72: %
! 73: %\institute{Kobe University, Rokko, Kobe 657-8501, Japan\\
! 74: %E-mail:noro@math.kobe-u.ac.jp}
! 75:
! 76: \maketitle % typesets the title of the contribution
! 77:
! 78:
! 79: \section{An overview of Risa/Asir}
! 80:
! 81: Risa/Asir is a tool for performing various computations in
! 82: mathematics and engineering applications.
! 83: The development of Risa/Asir started in 1989 at FUJITSU
! 84: and now the source code is also available at no cost.
! 85: Currently, Kobe distribution
! 86: is the most active branch in the development of Risa/Asir.
! 87: Risa/Asir is characterized as follows:
! 88:
! 89: \begin{enumerate}
! 90: \item An environment for large scale and efficient polynomial computation.
! 91:
! 92: Risa/Asir consists of the Risa engine for performing operations on
! 93: mathematical objects and an interpreter for programs written in
! 94: the Asir user language. In Risa/Asir, polynomials are
! 95: represented in two different internal forms:
! 96: the recursive representation and the distributed representation.
! 97: Polynomial factorization and GCD are based on the former representation,
! 98: and computations related to the Gr\"obner basis are based on the latter
! 99: representation.
! 100: %Ground fields of polynomial rings can be composed of the field of rationals,
! 101: %algebraic number fields and finite fields.
! 102: Ground fields of polynomial rings can be composed of
! 103: The field of rationals, algebraic number fields and finite fields
! 104: are available as ground fields of polynomial rings.
! 105:
! 106: \item A platform for parallel and distributed computation.
! 107:
! 108: In order to combine mathematical software systems,
! 109: we previously proposed the OpenXM
! 110: (Open Message eXchange for Mathematics)
! 111: protocol.
! 112: Risa/Asir acts as both an OpenXM client and an OpenXM server.
! 113: The Risa/Asir OpenXM client API provides a way to call
! 114: functions in external OpenXM servers.
! 115: Using multiple Risa/Asir OpenXM servers,
! 116: one can perform parallel and distributed computation
! 117: in an attempt to achieve linear speedup.
! 118: Conversely, other OpenXM clients can call functions in the Risa/Asir
! 119: server.
! 120:
! 121: \item Open source software.
! 122:
! 123: The source code of Risa/Asir is completely open, and algorithms and
! 124: implementations can be verified if necessary. The addition of new
! 125: codes is simple.
! 126: \end{enumerate}
! 127:
! 128: Risa/Asir runs on various platforms such as Linux, FreeBSD, Sun and
! 129: Windows. The whole source code is available from
! 130: {\tt http://www.math.kobe-u.ac.jp/OpenXM}.
! 131: The on-line help is available from the Risa/Asir command line or
! 132: from the menu bar on Windows. Manuals are located at
! 133: {\tt http://www.math.kobe-u.ac.jp/OpenXM/Current/doc/index-doc.html}.
! 134:
! 135: \section{Functionality of Risa/Asir}
! 136:
! 137: Among various functions on algebraic computation,
! 138: we explain the implementations of two main functions: polynomial
! 139: factorization and Gr\"obner basis computation over various ground
! 140: fields.
! 141:
! 142: \subsection{Operations over fields of characteristic 0}
! 143:
! 144: Polynomial arithmetics, polynomial GCD and factorization are
! 145: implemented over our own implementation of integer and rational number
! 146: arithmetics. In multivariate factorization, we implemented a
! 147: simplified version of Wang method to estimate the leading coefficient
! 148: of a factor to avoid the leading coefficient problem.
! 149:
! 150: Risa/Asir provides a univariate factorization over algebraic number
! 151: fields represented by a successive extension. As an application, the
! 152: splitting field computation of a univariate polynomial is implemented.
! 153: The impelented algorithm is an improvement of the algorithm proposed
! 154: by Trager. In the present algorithm, we utilize non square-free norms
! 155: to obtain partial (not necessarily irreducible) factorization. The
! 156: algorithm finally requires univariate factorization of a polynomial
! 157: over the rationals, however this factorization is often difficult
! 158: because the polynomial contains many spurious factors. At present,
! 159: Risa/Asir is not optimized to factor polynomials of this type. In
! 160: this case, a factorization in the PARI library implementing the
! 161: knapsack factorization algorithm can be used, and the splitting field
! 162: can be computed efficiently even in such cases
! 163: \footnote{A special configure option is required for linking the new version
! 164: of PARI library.}.
! 165:
! 166: \subsection{Computation over finite fields}
! 167:
! 168: In Risa/Asir finite fields are represented in several ways.
! 169: \begin{enumerate}
! 170: \item $GF(p)$ ($p$: a prime $p < 2^{29})$
! 171: \item $GF(p)$ ($p$: an arbitrary prime)
! 172: \item $GF(2^n)$ ($n$: small)
! 173: \item $GF(p^n)$ ($p$: an arbitrary prime, $n$: small integer)
! 174: \item $GF(p^s)$ ($p$: a small prime, $p^s < 2^{16})$
! 175: \end{enumerate}
! 176: The type 1 is used internally in various modular algorithms. The type
! 177: 2, 3 and 4 are general purpose representations. Multiplication in
! 178: $GF(2^n)$ is implemented using Karatsuba algorithm extensively. The
! 179: type 5 has been introduced for efficient implementation of
! 180: multivariate factorization over finite fields of small characteristic.
! 181: When we attempt to factor a polynomial over such a field, we often
! 182: have insufficient evaluation points. In this case we have to extend
! 183: the ground field. If the ground field and its extension are both
! 184: represented by a type 5 representation, we can expect that field
! 185: arithmetics are performed efficiently in both fields. We presented a
! 186: new polynomial time algorithm to factor bivariate polynomials over a
! 187: finite field is presented. A combination of the Berlekamp-Hensel
! 188: method and the new algorithm under a type 5 representation enables us
! 189: to efficiently factor a certain class of polynomials, including
! 190: hard-to-factor polynomials.
! 191:
! 192: \subsection{Gr\"obner basis computation}
! 193:
! 194: We have incorporated various algorithms and improvements for Gr\"obner
! 195: basis computation. For the Buchberger algorithm, we have implemented
! 196: well-known criteria to detect unnecessary pairs, the sugar strategy,
! 197: trace algorithms by modular computation, stabilization of strategy by
! 198: combining homogenization and the trace algorithm, and efficient
! 199: content reduction during normal form computation. We also have an
! 200: experimental implementation of $F_4$ algorithm. Furthermore, we
! 201: implemented several types of change of ordering algorithms. Among
! 202: these, {\tt tolex()} implements a modular FGLM algorithm, which avoids
! 203: intermediate coefficient swells during the ordinary FGLM algorithm and
! 204: realizes efficient computation of lexicographic Gr\"obner bases for
! 205: zero-dimensional ideals.
! 206:
! 207: By supplying an option {\tt Demand} with a directory name, generated
! 208: basis elements are placed in the directory. Although this requires
! 209: additional cost in order to read the basis elements required for
! 210: normal form computations, the total amount of memory is smaller than
! 211: the case in which all basis elements are placed in memory, which may
! 212: enable a very large computation, generating numerous intermediate
! 213: basis elements.
! 214:
! 215: As an application of Gr\"obner basis computation and polynomial
! 216: factorization, we implemented primary ideal decomposition and prime
! 217: decomposition of the radical of an ideal. These functions can be used
! 218: to decompose solutions of systems of algebraic equations into
! 219: irreducible components.
! 220:
! 221: We implemented fundamental arithmetics, the Buchberger algorithm and
! 222: the minimal polynomial computation over Weyl algebra, the ring of
! 223: differential operators having polynomial coefficients. Using these
! 224: arithmetics we implemented an efficient algorithm for computing the
! 225: $b$-function of a polynomial.
! 226:
! 227: \subsection{Parallel and distributed computation via OpenXM}
! 228:
! 229: Risa/Asir provides OpenXM API for executing funtions on other
! 230: mathematical software. In OpenXM, mathematical software systems are
! 231: wrapped as server stack machines. As an OpenXM client, Risa/Asir
! 232: dispatches a request to a server and receives the result. Inputs and
! 233: outputs are represented as CMO (Common Mathematical Object format)
! 234: objects. The set of stack machine commands also contains various
! 235: control operations, such as server invocation, termination,
! 236: interruption and restarting. Usually, each mathematical software
! 237: system has its own user language. OpenXM provides stack machine
! 238: commands for executing a command string and receiving a result as a
! 239: human readable character string, thus wrapping a mathematical software
! 240: system as an OpenXM server is relatively easy. OpenXM protocol is
! 241: completely open, and any program can implement the protocol. OpenXM
! 242: specifies a procedure for robust interruption and restarting of
! 243: execution, which enables clients to be reset safely from any state.
! 244:
! 245: Communication between an OpenXM server and a client can be realized by various
! 246: methods: files, TCP/IP, MPI, PVM, RPC and linking a subroutine library.
! 247: The Risa/Asir subroutine library {\tt libasir.a} contains functions
! 248: simulating the stack machine commands supported in {\tt ox\_asir},
! 249: the OpenXM asir server.
! 250:
! 251: \subsection{Integration of Risa/Asir and other OpenXM servers}
! 252:
! 253: Asir OpenXM contrib (asir-contrib) is a collection of wrappers of
! 254: functions in external OpenXM servers. Using asir-contrib,
! 255: an external function can be called
! 256: from Asir without knowing that the function is located in
! 257: an external server. Currently, the following functions (including
! 258: Asir built-in functions) are provided
! 259: in OpenXM:
! 260:
! 261: \begin{itemize}
! 262: \item Operations on Integers
! 263:
! 264: {\tt idiv},{\tt irem} (division with remainder),
! 265: {\tt ishift} (bit shifting),
! 266: {\tt iand},{\tt ior},{\tt ixor} (logical operations),
! 267: {\tt igcd},(GCD by various methods such as Euclid's algorithm and
! 268: the accelerated GCD algorithm),
! 269: {\tt fac} (factorial),
! 270: {\tt inv} (inverse modulo an integer),
! 271: {\tt random} (random number generator by the Mersenne twister algorithm).
! 272:
! 273: \item Ground Fields
! 274:
! 275: Arithmetics on various fields: the rationals,
! 276: ${\bf Q}(\alpha_1,\alpha_2,\ldots,\alpha_n)$
! 277: ($\alpha_i$ is algebraic over ${\bf Q}(\alpha_1,\ldots,\alpha_{\tt i-1})$),
! 278: $GF(p)$ ($p$ is a prime of arbitrary size), $GF(2^n)$.
! 279:
! 280: \item Operations on Polynomials
! 281:
! 282: {\tt sdiv }, {\tt srem } (division with remainder),
! 283: {\tt ptozp } (removal of the integer content),
! 284: {\tt diff } (differentiation),
! 285: {\tt gcd } (GCD over the rationals),
! 286: {\tt res } (resultant),
! 287: {\tt subst } (substitution),
! 288: {\tt umul} (fast multiplication of dense univariate polynomials
! 289: by a hybrid method with Karatsuba and FFT+Chinese remainder),
! 290: {\tt urembymul\_precomp} (fast dense univariate polynomial
! 291: division with remainder by the fast multiplication and
! 292: the precomputed inverse of a divisor),
! 293:
! 294: \item Polynomial Factorization
! 295: {\tt fctr } (factorization over the rationals),
! 296: {\tt fctr\_ff } (univariate factorization over finite fields),
! 297: {\tt af } (univariate factorization over algebraic number fields),
! 298: {\tt sp} (splitting field computation).
! 299:
! 300: \item Groebner basis
! 301:
! 302: {\tt dp\_gr\_main }, {\tt nd\_gr\_trace} (Groebner basis computation of a polynomial ideal
! 303: over the rationals by the trace lifting),
! 304: {\tt dp\_gr\_mod\_main }, {\tt nd\_gr} (Groebner basis over small finite fields),
! 305: {\tt tolex } (Modular change of ordering for a zero-dimensional ideal),
! 306: {\tt tolex\_gsl } (Modular rational univariate representation
! 307: for a zero-dimensional ideal),
! 308: {\tt dp\_f4\_main}, {\tt dp\_f4\_mod\_main}, {\tt nd\_f4}
! 309: ($F_4$ over the rationals and small finite fields).
! 310:
! 311: \item Ideal Decomposition
! 312:
! 313: {\tt primedec}, {\tt primedec\_mod} (Prime decomposition of the radical),
! 314: {\tt primadec} (Primary decomposition of ideals by Shimoyama/Yokoyama algorithm).
! 315:
! 316: \item Quantifier Elimination
! 317:
! 318: {\tt qe} (real quantifier elimination in a linear and
! 319: quadratic first-order formula),
! 320: {\tt simpl} (heuristic simplification of a first-order formula).
! 321:
! 322: \item Visualization of curves
! 323:
! 324: {\tt plot} (plotting of a univariate function),
! 325: {\tt ifplot} (plotting zeros of a bivariate polynomial),
! 326: {\tt conplot} (contour plotting of a bivariate polynomial function).
! 327:
! 328: \item Miscellaneous functions
! 329:
! 330: {\tt det} (determinant),
! 331: {\tt qsort} (sorting of an array by the quick sort algorithm),
! 332: {\tt eval} (evaluation of a formula containing transcendental functions
! 333: such as
! 334: {\tt sin}, {\tt cos}, {\tt tan}, {\tt exp},
! 335: {\tt log})
! 336: {\tt roots} (finding all roots of a univariate polynomial),
! 337: {\tt lll} (computation of an LLL-reduced basis of a lattice).
! 338:
! 339: \item $D$-modules ($D$ is the Weyl algebra)
! 340:
! 341: {\tt gb } (Gr\"obner basis),
! 342: {\tt syz} (syzygy),
! 343: {\tt annfs} (Annhilating ideal of $f^s$),
! 344: {\tt bfunction},\\
! 345: {\tt schreyer} (free resolution by the Schreyer method),
! 346: {\tt vMinRes} (V-minimal free resolution),\\
! 347: {\tt characteristic} (Characteristic variety),
! 348: {\tt restriction} in the derived category of $D$-modules,
! 349: {\tt integration} in the derived category,
! 350: {\tt tensor} in the derived category,
! 351: {\tt dual} (Dual as a D-module),
! 352: {\tt slope}.
! 353:
! 354: \item Cohomology groups
! 355:
! 356: {\tt deRham} (The de Rham cohomology groups of
! 357: ${\bf C}^n \setminus V(f)$,
! 358: {\tt ext} (Ext modules for a holonomic $D$-module $M$
! 359: and the ring of formal power series).
! 360:
! 361: \item Differential equations
! 362:
! 363: Helping to derive and prove {\tt combinatorial} and
! 364: {special function identities},
! 365: {\tt gkz} (GKZ hypergeometric differential equations),
! 366: {\tt appell} (Appell's hypergeometric differential equations),
! 367: {\tt indicial} (indicial equations),
! 368: {\tt rank} (Holonomic rank),
! 369: {\tt rrank} (Holonomic rank of regular holonomic systems),
! 370: {\tt dsolv} (series solutions of holonomic systems).
! 371:
! 372: \item OpenMATH support
! 373:
! 374: {\tt om\_xml} (CMO to OpenMATH XML),
! 375: {\tt om\_xml\_to\_cmo} (OpenMATH XML to CMO).
! 376:
! 377: \item Homotopy Method
! 378:
! 379: {\tt phc} (Solving systems of algebraic equations by
! 380: numerical and polyhedral homotopy methods).
! 381:
! 382: \item Toric ideal
! 383:
! 384: {\tt tigers} (Enumerate all Gr\"obner basis of a toric ideal.
! 385: Finding test sets for integer program),
! 386: {\tt arithDeg} (Arithmetic degree of a monomial ideal),
! 387: {\tt stdPair} (Standard pair decomposition of a monomial ideal).
! 388:
! 389: \item Communications
! 390:
! 391: {\tt ox\_launch} (starting a server),
! 392: {\tt ox\_launch\_nox},
! 393: {\tt ox\_shutdown},
! 394: {\tt ox\_launch\_generic},\\
! 395: {\tt generate\_port},
! 396: {\tt try\_bind\_listen},
! 397: {\tt try\_connect},
! 398: {\tt try\_accept},
! 399: {\tt register\_server},\\
! 400: {\tt ox\_rpc},
! 401: {\tt ox\_cmo\_rpc},
! 402: {\tt ox\_execute\_string},
! 403: {\tt ox\_reset} (reset the server),
! 404: {\tt ox\_intr},\\
! 405: {\tt register\_handler},
! 406: {\tt ox\_push\_cmo},
! 407: {\tt ox\_push\_local},
! 408: {\tt ox\_pop\_cmo},
! 409: {\tt ox\_pop\_local},\\
! 410: {\tt ox\_push\_cmd},
! 411: {\tt ox\_sync},
! 412: {\tt ox\_get},
! 413: {\tt ox\_pops},
! 414: {\tt ox\_select},
! 415: {\tt ox\_flush},
! 416: {\tt ox\_get\_serverinfo}
! 417:
! 418: \end{itemize}
! 419:
! 420: \begin{thebibliography}{99}
! 421: \bibitem{NORO}
! 422: M. Noro, A Computer Algebra System Risa/Asir. Algebra, Geometry and Software, M. Joswig and N. Takayama (eds.), Springer, 147-162 (2002).
! 423: \bibitem{MAEKAWA}
! 424: M. Maekawa, M. Noro, N. Takayama and Y. Tamura
! 425: The Design and Implementation of OpenXM-RFC 100 and 101.
! 426: Computer Mathematics (Proc. ASCM2001), World Scientific, 102-111 (2001).
! 427: \end{thebibliography}
! 428:
! 429: \end{document}
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to risa-asir.tex CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM / src / asir-doc / papers