Annotation of OpenXM/src/asir-doc/papers/risa-asir.tex, Revision 1.2
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),
1.2 ! noro 296: {\tt modfctr}, {\tt fctr\_ff } (univariate factorization over finite fields),
1.1 noro 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),
1.2 ! noro 332: {\tt eval}, {\tt deval} (evaluation of a formula containing transcendental functions
1.1 noro 333: such as
334: {\tt sin}, {\tt cos}, {\tt tan}, {\tt exp},
335: {\tt log})
1.2 ! noro 336: {\tt pari(roots)} (finding all roots of a univariate polynomial),
! 337: {\tt pari(lll)} (computation of an LLL-reduced basis of a lattice).
1.1 noro 338:
339: \item $D$-modules ($D$ is the Weyl algebra)
340:
1.2 ! noro 341: {\tt sm1.gb } (Gr\"obner basis),
! 342: {\tt sm1.syz} (syzygy),
! 343: %{\tt annfs} (Annhilating ideal of $f^s$),
! 344: {\tt ann} (Annhilating ideal of $f^s$),\\
! 345: {\tt sm1.bfunction},{\tt bfunction} (the global $b$-function of a polynomial)\\
! 346: %{\tt schreyer} (free resolution by the Schreyer method),
! 347: %{\tt vMinRes} (V-minimal free resolution),\\
! 348: %{\tt characteristic} (Characteristic variety),
! 349: {\tt sm1.restriction} in the derived category of $D$-modules,
! 350: %{\tt integration} in the derived category,
! 351: %{\tt tensor} in the derived category,
! 352: %{\tt dual} (Dual as a D-module),
! 353: {\tt sm1.slope}.
1.1 noro 354:
355: \item Cohomology groups
356:
357: {\tt deRham} (The de Rham cohomology groups of
358: ${\bf C}^n \setminus V(f)$,
359: {\tt ext} (Ext modules for a holonomic $D$-module $M$
360: and the ring of formal power series).
361:
362: \item Differential equations
363:
364: Helping to derive and prove {\tt combinatorial} and
365: {special function identities},
1.2 ! noro 366: {\tt sm1.gkz} (GKZ hypergeometric differential equations),
! 367: {\tt sm1.appell1}, {\tt sm1.appell4} (Appell's hypergeometric differential equations),
! 368: %{\tt indicial} (indicial equations),
! 369: {\tt sm1.generalized\_bfunction} (indicial equations),
! 370: {\tt sm1.rank} (Holonomic rank),
! 371: {\tt sm1.rrank} (Holonomic rank of regular holonomic systems),
! 372: %{\tt dsolv} (series solutions of holonomic systems).
! 373: {\tt dsolv\_dual}, {\tt dsolv\_starting\_terms} (series solutions of holonomic systems).
1.1 noro 374:
375: \item OpenMATH support
376:
377: {\tt om\_xml} (CMO to OpenMATH XML),
378: {\tt om\_xml\_to\_cmo} (OpenMATH XML to CMO).
379:
380: \item Homotopy Method
381:
1.2 ! noro 382: {\tt phc.phc} (Solving systems of algebraic equations by
1.1 noro 383: numerical and polyhedral homotopy methods).
384:
385: \item Toric ideal
386:
1.2 ! noro 387: {\tt tigers.tigers} (Enumerate all Gr\"obner basis of a toric ideal.
1.1 noro 388: Finding test sets for integer program),
1.2 ! noro 389: %{\tt arithDeg} (Arithmetic degree of a monomial ideal),
! 390: %{\tt stdPair} (Standard pair decomposition of a monomial ideal).
1.1 noro 391:
392: \item Communications
393:
394: {\tt ox\_launch} (starting a server),
395: {\tt ox\_launch\_nox},
396: {\tt ox\_shutdown},
397: {\tt ox\_launch\_generic},\\
398: {\tt generate\_port},
399: {\tt try\_bind\_listen},
400: {\tt try\_connect},
401: {\tt try\_accept},
402: {\tt register\_server},\\
403: {\tt ox\_rpc},
404: {\tt ox\_cmo\_rpc},
405: {\tt ox\_execute\_string},
406: {\tt ox\_reset} (reset the server),
407: {\tt ox\_intr},\\
408: {\tt register\_handler},
409: {\tt ox\_push\_cmo},
410: {\tt ox\_push\_local},
411: {\tt ox\_pop\_cmo},
412: {\tt ox\_pop\_local},\\
413: {\tt ox\_push\_cmd},
414: {\tt ox\_sync},
415: {\tt ox\_get},
416: {\tt ox\_pops},
417: {\tt ox\_select},
418: {\tt ox\_flush},
419: {\tt ox\_get\_serverinfo}
420:
421: \end{itemize}
422:
423: \begin{thebibliography}{99}
424: \bibitem{NORO}
425: M. Noro, A Computer Algebra System Risa/Asir. Algebra, Geometry and Software, M. Joswig and N. Takayama (eds.), Springer, 147-162 (2002).
426: \bibitem{MAEKAWA}
427: M. Maekawa, M. Noro, N. Takayama and Y. Tamura
428: The Design and Implementation of OpenXM-RFC 100 and 101.
429: Computer Mathematics (Proc. ASCM2001), World Scientific, 102-111 (2001).
430: \end{thebibliography}
431:
432: \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