Annotation of OpenXM/doc/Papers/dag-noro-proc.tex, Revision 1.9
1.9 ! noro 1: % $OpenXM: OpenXM/doc/Papers/dag-noro-proc.tex,v 1.8 2001/11/30 02:08:46 noro Exp $
1.1 noro 2: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3: % This is a sample input file for your contribution to a multi-
4: % author book to be published by Springer Verlag.
5: %
6: % Please use it as a template for your own input, and please
7: % follow the instructions for the formal editing of your
8: % manuscript as described in the file "1readme".
9: %
10: % Please send the Tex and figure files of your manuscript
11: % together with any additional style files as well as the
12: % PS file to the editor of your book.
13: %
14: % He or she will collect all contributions for the planned
15: % book, possibly compile them all in one go and pass the
16: % complete set of manuscripts on to Springer.
17: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
18:
19:
20:
21: %RECOMMENDED%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
22:
23: \documentclass[runningheads]{cl2emult}
24:
25: \usepackage{makeidx} % allows index generation
26: \usepackage{graphicx} % standard LaTeX graphics tool
27: % for including eps-figure files
28: \usepackage{subeqnar} % subnumbers individual equations
29: % within an array
30: \usepackage{multicol} % used for the two-column index
31: \usepackage{cropmark} % cropmarks for pages without
32: % pagenumbers
33: \usepackage{math} % placeholder for figures
34: \makeindex % used for the subject index
35: % please use the style sprmidx.sty with
36: % your makeindex program
37:
38: %upright Greek letters (example below: upright "mu")
39: \newcommand{\euler}[1]{{\usefont{U}{eur}{m}{n}#1}}
40: \newcommand{\eulerbold}[1]{{\usefont{U}{eur}{b}{n}#1}}
41: \newcommand{\umu}{\mbox{\euler{\char22}}}
42: \newcommand{\umub}{\mbox{\eulerbold{\char22}}}
43:
44: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
45:
46:
47: %OPTIONAL%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
48: %
49: %\usepackage{amstex} % useful for coding complex math
50: %\mathindent\parindent % needed in case "Amstex" is used
51: %
52: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
53:
54: %AUTHOR_STYLES_AND_DEFINITIONS%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
55: %
56: %Please reduce your own definitions and macros to an absolute
57: %minimum since otherwise the editor will find it rather
58: %strenuous to compile all individual contributions to a
59: %single book file
60: \usepackage{epsfig}
61: \def\cont{{\rm cont}}
62: \def\GCD{{\rm GCD}}
63: %
64: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
65:
66: \begin{document}
67: %
68: \title*{A Computer Algebra System Risa/Asir and OpenXM}
69: %
70: %
71: \toctitle{A Computer Algebra System Risa/Asir and OpenXM}
72: % allows explicit linebreak for the table of content
73: %
74: %
75: \titlerunning{Risa/Asir and OpenXM}
76: % allows abbreviation of title, if the full title is too long
77: % to fit in the running head
78: %
1.7 noro 79: \author{Masayuki Noro}
1.1 noro 80: %
81: %\authorrunning{Masayuki Noro}
82: % if there are more than two authors,
83: % please abbreviate author list for running head
84: %
85: %
86: \institute{Kobe University, Rokko, Kobe 657-8501, Japan}
87:
88: \maketitle % typesets the title of the contribution
89:
90: \begin{abstract}
1.7 noro 91: Risa/Asir is software for polynomial computation. It has been
92: developed for testing experimental polynomial algorithms, and now it
93: acts also as a main component in the OpenXM package \cite{OPENXM}.
94: OpenXM is an infrastructure for exchanging mathematical
1.1 noro 95: data. It defines a client-server architecture for parallel and
1.7 noro 96: distributed computation. In this article we present an overview of
97: Risa/Asir and review several techniques for improving performances of
98: Groebner basis computation over {\bf Q}. We also show Risa/Asir's
99: OpenXM interfaces and their usages.
1.1 noro 100: \end{abstract}
101:
102: \section{A computer algebra system Risa/Asir}
103:
104: \subsection{What is Risa/Asir?}
105:
106: Risa/Asir \cite{RISA} is software mainly for polynomial
107: computation. Its major functions are polynomial factorization and
108: Groebner basis computation, whose core parts are implemented as
1.5 noro 109: built-in functions. Some higher algorithms such as primary ideal
1.1 noro 110: decomposition or Galois group computation are built on them by the
1.5 noro 111: user language called Asir language. Asir language can be regarded as C
112: language without type declaration of variables, with list processing,
113: and with automatic garbage collection. A built-in {\tt gdb}-like user
1.7 noro 114: language debugger is available. Risa/Asir is open source and the
115: source code and binaries are available via {\tt ftp} or {\tt CVS}.
116: Risa/Asir is not only a standalone computer algebra system but also a
117: main component in OpenXM package \cite{OPENXM}, which is a collection
118: of various software compliant to OpenXM protocol specification.
119: OpenXM is an infrastructure for exchanging mathematical data and
120: Risa/Asir has three kinds of OpenXM interfaces : as a client, as a
121: server, and as a subroutine library. Our goals of developing Risa/Asir
1.5 noro 122: are as follows:
1.1 noro 123:
124: \begin{enumerate}
1.5 noro 125: \item Providing a platform for testing new algorithms
1.1 noro 126:
127: Risa/Asir has been a platform for testing experimental algorithms in
1.7 noro 128: polynomial factorization, Groebner basis computation,
1.1 noro 129: cryptography and quantifier elimination. As to Groebner basis, we have
130: been mainly interested in problems over {\bf Q} and we tried applying
131: various modular techniques to overcome difficulties caused by huge
132: intermediate coefficients. We have had several results and they have
1.7 noro 133: been implemented in Risa/Asir with other known methods.
1.1 noro 134:
1.5 noro 135: \item General purpose open system
1.1 noro 136:
137: We need a lot of functions to make Risa/Asir a general purpose
1.7 noro 138: computer algebra system. In recent years we can make use of various high
1.1 noro 139: performance applications or libraries as free software. We wrapped
140: such software as OpenXM servers and we started to release a collection
1.5 noro 141: of such servers and clients as the OpenXM package in 1997. Risa/Asir
142: is now a main client in the package.
1.1 noro 143:
144: \item Environment for parallel and distributed computation
145:
1.7 noro 146: The ancestor of OpenXM is a protocol designed for doing parallel
147: distributed computations by connecting multiple Risa/Asir's over
148: TCP/IP. OpenXM is also designed to provide an environment for
149: efficient parallel distributed computation. Currently only
150: client-server communication is available, but we are preparing a
151: specification OpenXM-RFC 102 allowing client-client communication,
152: which will enable us to execute wider range of parallel algorithms
153: requiring collective operations efficiently.
1.1 noro 154: \end{enumerate}
155:
156: \subsection{Groebner basis and the related computation}
157:
158: Currently Risa/Asir can only deal with polynomial ring. Operations on
159: modules over polynomial rings have not yet supported. However, both
160: commutative polynomial rings and Weyl algebra are supported and one
1.7 noro 161: can compute Groebner basis in both rings over {\bf Q}, fields of
1.1 noro 162: rational functions and finite fields. In the early stage of our
163: development, our effort was mainly devoted to improve the efficiency
1.7 noro 164: of computation over {\bf Q}. Our main tool is modular
1.1 noro 165: computation. For Buchberger algorithm we adopted the trace lifting
166: algorithm by Traverso \cite{TRAV} and elaborated it by applying our
167: theory on a correspondence between Groebner basis and its modular
168: image \cite{NOYO}. We also combine the trace lifting with
169: homogenization to stabilize selection strategies, which enables us to
1.7 noro 170: compute several examples efficiently which are hard to compute without
1.1 noro 171: such a combination. Our modular method can be applied to the change
1.7 noro 172: of ordering algorithm\cite{FGLM} and rational univariate
173: representation \cite{RUR}. We also made a test implementation of
174: $F_4$ algorithm \cite{F4}. In the later section we will show timing
175: data on Groebner basis computation.
1.1 noro 176:
177: \subsection{Polynomial factorization}
178:
179: Here we briefly review functions on polynomial factorization. For
180: univariate factorization over {\bf Q}, the classical
181: Berlekamp-Zassenhaus algorithm is implemented. Efficient algorithms
1.7 noro 182: recently proposed have not yet implemented. For univariate
183: factorization over algebraic number fields, Trager's algorithm
184: \cite{TRAGER} is implemented with some modifications. Its major
185: applications are splitting field and Galois group computation of
186: polynomials over {\bf Q} \cite{ANY}. For such purpose a tower of
187: simple extensions are suitable because factors represented over a
188: simple extension often have huge coefficients. For univariate
189: factorization over finite fields, equal degree factorization and
190: Cantor-Zassenhaus algorithm are implemented. We can use various
191: representation of finite fields: $GF(p)$ with a machine integer prime
192: $p$, $GF(p)$ and $GF(p^n)$ with any odd prime $p$, $GF(2^n)$ with a
193: bit-array representation of polynomials over $GF(2)$ and $GF(p^n)$
194: with small $p^n$ represented by a primitive root. For multivariate
195: factorization over {\bf Q}, the classical EZ(Extended
196: Zassenhaus) type algorithm is implemented.
1.1 noro 197:
198: \subsection{Other functions}
199: By applying Groebner basis computation and polynomial factorization,
200: we have implemented several higher level algorithms. A typical
201: application is primary ideal decomposition of polynomial ideals over
202: {\bf Q}, which needs both functions. Shimoyama-Yokoyama algorithm
1.5 noro 203: \cite{SY} for primary decomposition is written in the user language.
204: Splitting field and Galois group computation \cite{ANY} are closely
205: related and are also important applications of polynomial
206: factorization.
1.1 noro 207:
208: \section{Techniques for efficient Groebner basis computation over {\bf Q}}
209: \label{gbtech}
210:
211: In this section we review several practical techniques to improve
212: Groebner basis computation over {\bf Q}, which are easily
213: implemented but may not be well known.
214: We use the following notations.
215: \begin{description}
1.9 ! noro 216: \item $<$ : a term order in the set of monomials. It is a total order such that
! 217:
! 218: $\forall t, 1 \le t$ and $\forall s, t, u, s<t \Rightarrow us<ut$.
! 219: \item $Id(F)$ : a polynomial ideal generated by a polynomial set $F$.
! 220: \item $HT(f)$ : the head term of a polynomial with respect to a term order.
! 221: \item $HC(f)$ : the head coefficient of a polynomial with respect to a term order.
! 222: \item $T(f)$ : terms with non zero coefficients in $f$.
! 223: \item $Spoly(f,g)$ : the S-polynomial of $\{f,g\}$
! 224:
! 225: $Spoly(f,g) = T_{f,g}/HT(f)\cdot f/HC(f) -T_{f,g}/HT(g)\cdot g/HC(g)$, where
! 226: $T_{f,g} = LCM(HT(f),HT(g))$.
! 227: \item $\phi_p$ : the canonical projection from ${\bf Z}$ onto $GF(p)$.
1.1 noro 228: \end{description}
1.9 ! noro 229:
! 230: \subsection{Groebner basis computation and its improvements}
! 231:
! 232: A Groebner basis of an ideal $Id(F)$ can be computed by the Buchberger
! 233: algorithm. The key oeration in the algorithm is the following
! 234: division by a polynomial set.
! 235: \begin{tabbing}
! 236: while \= $\exists g \in G$, $\exists t \in T(f)$ such that $HT(g)|t$ do\\
! 237: \> $f \leftarrow f - t/HT(g) \cdot c/HC(g) \cdot g$, \quad
! 238: where $c$ is the coeffcient of $t$ in $f$
! 239: \end{tabbing}
! 240: This division terminates for any term order.
! 241: With this division, we can show the most primitive version of the
! 242: Buchberger algorithm.
! 243: \begin{tabbing}
! 244: Input : a finite polynomial set $F$\\
! 245: Output : a Groebner basis $G$ of $Id(F)$ with respect to a term order $<$\\
! 246: $G \leftarrow F$; \quad $D \leftarrow \{\{f,g\}| f, g \in G, f \neq g \}$\\
! 247: while \= $D \neq \emptyset$ do \\
! 248: \> $\{f,g\} \leftarrow$ an element of $D$; \quad
! 249: $D \leftarrow D \setminus \{P\}$\\
! 250: \> $R \leftarrow$ a remainder of $Spoly(f,g)$ on division by $G$\\
! 251: \> if $R \neq 0$ then $D \leftarrow D \cup \{\{f,R\}| f \in G\}$; \quad
! 252: $G \leftarrow G \cup \{R\}$\\
! 253: end do\\
! 254: return G
! 255: \end{tabbing}
! 256: Though this algorithm gives a Groebner basis of $Id(F)$,
! 257: it is not practical at all. We need lots of techniques to make
! 258: it practical. The following are major improvements:
! 259: \begin{itemize}
! 260: \item Useless pair detection
! 261:
! 262: We don't have to process all the pairs in $D$ and several useful
! 263: criteria for detecting useless pairs were proposed.
! 264:
! 265: \item Selection strategy
! 266:
! 267: The selection of $\{f,g\}$ greatly affects the subsequent computation.
! 268: The typical strategies are the normal startegy and the sugar strategy.
! 269: The latter was proposed for efficient computation under a non
! 270: degree-compatible order.
! 271:
! 272: \item Modular methods
! 273:
! 274: Even if we apply several criteria, it is difficult to detect all pairs
! 275: whose S-polynomials are reduced to zero, and the cost to process them
! 276: often occupies a major part in the whole computation. The trace algorithms
! 277: were proposed to reduce such cost. This will be explained in more detail
! 278: in Section \ref{gbhomo}.
! 279:
! 280: \item Change of ordering
! 281:
! 282: For elimination, we need a Groebner basis with respect to a non
! 283: degree-compatible order, but it is often hard to compute it by
! 284: the Buchberger algorithm. If the ideal is zero dimensional, we
! 285: can apply a change of ordering algorithm for a Groebner basis
! 286: with respect to any order and we can obtain a Groebner basis
! 287: with respect to a desired order.
! 288:
! 289: \end{itemize}
! 290: By implementing these techniques, one can obtain Groebner bases for
! 291: wider range of inputs. Nevertheless there are still intractable
! 292: problems with these classical tools. In the subsequent sections
! 293: we show several methods for further improvements.
1.1 noro 294:
295: \subsection{Combination of homogenization and trace lifting}
1.7 noro 296: \label{gbhomo}
1.1 noro 297:
298: Traverso's trace lifting algorithm can be
1.7 noro 299: formulated in an abstract form as follows (c.f. \cite{FPARA}).
1.1 noro 300: \begin{tabbing}
301: Input : a finite subset $F \subset {\bf Z}[X]$\\
302: Output : a Groebner basis $G$ of $Id(F)$ with respect to a term order $<$\\
303: do \= \\
304: \> $p \leftarrow$ a new prime\\
305: \>Guess \= a Groebner basis candidate $G \subset Id(F)$
306: such that $\phi_p(G)$ \\
307: \>\> is a Groebner basis of $Id(\phi_p(F))$ in ${GF(p)}[X]$\\
308: \>Check that $G$ is a Groebner basis of $Id(G)$ and $F \subset Id(G)$\\
309: \>If $G$ passes the check return $G$\\
310: end do
311: \end{tabbing}
1.5 noro 312: We can apply various methods for {\it guess} part of the above
313: algorithm. In the original algorithm we guess the candidate by
314: replacing zero normal form checks over {\bf Q} with those over $GF(p)$
315: in the Buchberger algorithm, which we call {\it tl\_guess}. In Asir
316: one can specify another method {\it tl\_h\_guess\_dh}, which is a
317: combination of {\it tl\_guess} and homogenization.
1.1 noro 318: \begin{tabbing}
319: $tl\_h\_guess\_dh(F,p)$\\
320: Input : $F\subset {\bf Z}[X]$, a prime $p$\\
321: Output : a Groebner basis candidate\\
322: $F_h \leftarrow$ the homogenization of $F$\\
323: $G_h \leftarrow tl\_guess(F_h,p)$ under an appropriate term order\\
324: $G \leftarrow$ the dehomogenization of $G_h$\\
325: $G \leftarrow G \setminus \{g \in G| \exists h \in G \setminus \{g\}$
326: such that $HT(h)|HT(g)$ \}
327: \end{tabbing}
328: The input is homogenized to suppress intermediate coefficient swells
329: of intermediate basis elements. The number of zero normal forms may
330: increase by the homogenization, but they are detected over
1.5 noro 331: $GF(p)$. Finally, by dehomogenizing the candidate we can expect that
1.7 noro 332: lots of redundant elements can be removed.
1.1 noro 333:
334: \subsection{Minimal polynomial computation by modular method}
1.7 noro 335:
1.1 noro 336: Let $I$ be a zero-dimensional ideal in $R={\bf Q}[x_1,\ldots,x_n]$.
337: Then the minimal polynomial $m(x_i)$ of a variable $x_i$ in $R/I$ can
338: be computed by a partial FGLM \cite{FGLM}, but it often takes long
339: time if one searches $m(x_i)$ incrementally over {\bf Q}. In this
340: case we can apply a simple modular method to compute the minimal
341: polynomial.
342: \begin{tabbing}
343: Input : a Groebner basis $G$ of $I$, a variable $x_i$\\
1.8 noro 344: Output : the minimal polynomial of $x_i$ in $R/I$\\
1.1 noro 345: do \= \\
346: \> $p \leftarrow$ a new prime such that $p \not{|} HC(g)$ for all $g \in G$\\
347: \> $m_p \leftarrow$ the minimal polynomial of $x_i$ in $GF(p)[x_1,\ldots,x_n]/Id(\phi_p(G))$\\
348: \> If there exists $m(x_i) \in I$ such that $\phi_p(m) = m_p$ and $\deg(m)=\deg(m_p)$\\
349: \> then return $m(x_i)$\\
350: end do
351: \end{tabbing}
352: In this algorithm, $m_p$ can be obtained by a partial FGLM over
353: $GF(p)$ because $\phi_p(G)$ is a Groebner basis. Once we know the
354: candidate of $\deg(m(x_i))$, $m(x_i)$ can be determined by solving a
355: system of linear equations via the method of indeterminate
1.7 noro 356: coefficient, and it can be solved efficiently by $p$-adic method.
357: Arguments on \cite{NOYO} ensures that $m(x_i)$ is what we want if it
358: exists. Note that the full FGLM can also be computed by the same
359: method.
1.1 noro 360:
361: \subsection{Integer contents reduction}
1.7 noro 362: \label{gbcont}
1.1 noro 363:
1.5 noro 364: In some cases the cost to remove integer contents during normal form
1.1 noro 365: computations is dominant. We can remove the content of an integral
366: polynomial $f$ efficiently by the following method \cite{REPL}.
367: \begin{tabbing}
368: Input : an integral polynomial $f$\\
369: Output : a pair $(\cont(f),f/\cont(f))$\\
370: $g_0 \leftarrow$ an estimate of $\cont(f)$ such that $\cont(f)|g_0$\\
1.7 noro 371: Write $f$ as $f = g_0q+r$ by division with remainder by $g_0$ for each coefficient\\
1.1 noro 372: If $r = 0$ then return $(g_0,q)$\\
373: else return $(g,g_0/g \cdot q + r/g)$, where $g = \GCD(g_0,\cont(r))$
374: \end{tabbing}
1.5 noro 375: By separating the set of coefficients of $f$ into two subsets and by
1.7 noro 376: computing GCD of sums of the elements in each subset we can estimate
1.1 noro 377: $g_0$ with high accuracy. Then other components are easily computed.
378:
379: %\subsection{Demand loading of reducers}
1.5 noro 380: %An execution of the Buchberger algorithm may produce vary large number
1.1 noro 381: %of intermediate basis elements. In Asir, we can specify that such
382: %basis elements should be put on disk to enlarge free memory space.
383: %This does not reduce the efficiency so much because all basis elements
384: %are not necessarily used in a single normal form computation, and the
385: %cost for reading basis elements from disk is often negligible because
386: %of the cost for coefficient computations.
387:
388: \section{Risa/Asir performance}
389:
1.5 noro 390: We show timing data on Risa/Asir for Groebner basis computation
391: and polynomial factorization. The measurements were made on
1.1 noro 392: a PC with PentiumIII 1GHz and 1Gbyte of main memory. Timings
393: are given in seconds. In the tables `---' means it was not
394: measured.
395:
396: \subsection{Groebner basis computation}
397:
1.5 noro 398: Table \ref{gbmod} and Table \ref{gbq} show timing data for Groebner
399: basis computation over $GF(32003)$ and over {\bf Q} respectively.
1.1 noro 400: $C_n$ is the cyclic $n$ system and $K_n$ is the Katsura $n$ system,
1.5 noro 401: both are famous bench mark problems \cite{BENCH}. We also measured
402: the timing for $McKay$ system over {\bf Q} \cite{REPL}. the term
403: order is graded reverse lexicographic order. In the both tables, the
404: first three rows are timings for the Buchberger algorithm, and the
405: last two rows are timings for $F_4$ algorithm. As to the Buchberger
406: algorithm over $GF(32003)$, Singular\cite{SINGULAR} shows the best
407: performance among the three systems. $F_4$ implementation in Risa/Asir
408: is faster than the Buchberger algorithm implementation in Singular,
409: but it is still several times slower than $F_4$ implementation in FGb
1.7 noro 410: \cite{FGB}. In Table \ref{gbq}, Risa/Asir computed $C_7$ and $McKay$
411: by the Buchberger algorithm with the methods described in Section
412: \ref{gbhomo} and \ref{gbcont}. It is obvious that $F_4$
413: implementation in Risa/Asir over {\bf Q} is too immature. Nevertheless
414: the timing of $McKay$ is greatly reduced. Fig. \ref{f4vsbuch}
415: explains why $F_4$ is efficient in this case. The figure shows that
416: the Buchberger algorithm produces normal forms with huge coefficients
417: for S-polynomials after the 250-th one, which are the computations in
418: degree 16. However, we know that the reduced basis elements have much
419: smaller coefficients after removing contents. As $F_4$ algorithm
420: automatically produces the reduced ones, the degree 16 computation is
421: quite easy in $F_4$.
1.1 noro 422:
423: \begin{table}[hbtp]
424: \begin{center}
425: \begin{tabular}{|c||c|c|c|c|c|c|c|} \hline
426: & $C_7$ & $C_8$ & $K_7$ & $K_8$ & $K_9$ & $K_{10}$ & $K_{11}$ \\ \hline
427: Asir $Buchberger$ & 31 & 1687 & 2.6 & 27 & 294 & 4309 & --- \\ \hline
428: Singular & 8.7 & 278 & 0.6 & 5.6 & 54 & 508 & 5510 \\ \hline
429: CoCoA 4 & 241 & $>$ 5h & 3.8 & 35 & 402 &7021 & --- \\ \hline\hline
430: Asir $F_4$ & 5.3 & 129 & 0.5 & 4.5 & 31 & 273 & 2641 \\ \hline
431: FGb(estimated) & 0.9 & 23 & 0.1 & 0.8 & 6 & 51 & 366 \\ \hline
432: \end{tabular}
433: \end{center}
434: \caption{Groebner basis computation over $GF(32003)$}
435: \label{gbmod}
436: \end{table}
437:
438: \begin{table}[hbtp]
439: \begin{center}
1.5 noro 440: \begin{tabular}{|c||c|c|c|c|c|c|} \hline
441: & $C_7$ & $Homog. C_7$ & $C_8$ & $K_7$ & $K_8$ & $McKay$ \\ \hline
442: Asir $Buchberger$ & 389 & 594 & 54000 & 29 & 299 & 34950 \\ \hline
443: Singular & --- & 15247 & --- & 7.6 & 79 & $>$ 20h \\ \hline
444: CoCoA 4 & --- & 13227 & --- & 57 & 709 & --- \\ \hline\hline
445: Asir $F_4$ & 989 & 456 & --- & 90 & 991 & 4939 \\ \hline
446: FGb(estimated) & 8 &11 & 288 & 0.6 & 5 & 10 \\ \hline
1.1 noro 447: \end{tabular}
448: \end{center}
449: \caption{Groebner basis computation over {\bf Q}}
450: \label{gbq}
451: \end{table}
452:
453: \begin{figure}[hbtp]
454: \begin{center}
455: \epsfxsize=12cm
1.6 noro 456: %\epsffile{../compalg/ps/blenall.ps}
457: \epsffile{blen.ps}
1.1 noro 458: \end{center}
459: \caption{Maximal coefficient bit length of intermediate bases}
460: \label{f4vsbuch}
461: \end{figure}
462:
1.5 noro 463: Table \ref{minipoly} shows timing data for the minimal polynomial
464: computation over {\bf Q}. Singular provides a function {\tt finduni}
465: for computing the minimal polynomial in each variable in ${\bf
466: Q}[x_1,\ldots,x_n]/I$ for zero dimensional ideal $I$. The modular
467: method used in Asir is efficient when the resulting minimal
468: polynomials have large coefficients and we can verify the fact from Table
469: \ref{minipoly}.
470: \begin{table}[hbtp]
471: \begin{center}
472: \begin{tabular}{|c||c|c|c|c|c|} \hline
473: & $C_6$ & $C_7$ & $K_6$ & $K_7$ & $K_8$ \\ \hline
474: Singular & 0.9 & 846 & 307 & 60880 & --- \\ \hline
475: Asir & 1.5 & 182 & 12 & 164 & 3420 \\ \hline
476: \end{tabular}
477: \end{center}
478: \caption{Minimal polynomial computation}
479: \label{minipoly}
480: \end{table}
481:
1.1 noro 482: \subsection{Polynomial factorization}
483:
1.3 noro 484: %Table \ref{unifac} shows timing data for univariate factorization over
485: %{\bf Q}. $N_{i,j}$ is an irreducible polynomial which are hard to
486: %factor by the classical algorithm. $N_{i,j}$ is a norm of a polynomial
487: %and $\deg(N_i) = i$ with $j$ modular factors. Risa/Asir is
488: %disadvantageous in factoring polynomials of this type because the
489: %algorithm used in Risa/Asir has exponential complexity. In contrast,
490: %CoCoA 4\cite{COCOA} and NTL-5.2\cite{NTL} show nice performances
491: %because they implement recently developed algorithms.
492: %
493: %\begin{table}[hbtp]
494: %\begin{center}
495: %\begin{tabular}{|c||c|c|c|c|} \hline
496: % & $N_{105,23}$ & $N_{120,20}$ & $N_{168,24}$ & $N_{210,54}$ \\ \hline
497: %Asir & 0.86 & 59 & 840 & hard \\ \hline
498: %Asir NormFactor & 1.6 & 2.2& 6.1& hard \\ \hline
499: %%Singular& hard? & hard?& hard? & hard? \\ \hline
500: %CoCoA 4 & 0.2 & 7.1 & 16 & 0.5 \\ \hline\hline
501: %NTL-5.2 & 0.16 & 0.9 & 1.4 & 0.4 \\ \hline
502: %\end{tabular}
503: %\end{center}
504: %\caption{Univariate factorization over {\bf Q}}
505: %\label{unifac}
506: %\end{table}
1.1 noro 507:
508: Table \ref{multifac} shows timing data for multivariate
509: factorization over {\bf Q}.
510: $W_{i,j,k}$ is a product of three multivariate polynomials
511: $Wang[i]$, $Wang[j]$, $Wang[k]$ given in a data file
512: {\tt fctrdata} in Asir library directory. It is also included
513: in Risa/Asir source tree and located in {\tt asir2000/lib}.
514: For these examples Risa/Asir shows reasonable performance
515: compared with other famous systems.
516: \begin{table}[hbtp]
517: \begin{center}
518: \begin{tabular}{|c||c|c|c|c|c|} \hline
519: & $W_{1,2,3}$ & $W_{4,5,6}$ & $W_{7,8,9}$ & $W_{10,11,12}$ & $W_{13,14,15}$ \\ \hline
520: variables & 3 & 5 & 5 & 5 & 4 \\ \hline
521: monomials & 905 & 41369 & 51940 & 30988 & 3344 \\ \hline\hline
522: Asir & 0.2 & 4.7 & 14 & 17 & 0.4 \\ \hline
523: %Singular& $>$15min & --- & ---& ---& ---\\ \hline
524: CoCoA 4 & 5.2 & $>$15min & $>$15min & $>$15min & 117 \\ \hline\hline
525: Mathematica 4& 0.2 & 16 & 23 & 36 & 1.1 \\ \hline
526: Maple 7& 0.5 & 18 & 967 & 48 & 1.3 \\ \hline
527: \end{tabular}
528: \end{center}
529: \caption{Multivariate factorization over {\bf Q}}
530: \label{multifac}
531: \end{table}
1.3 noro 532: As to univariate factorization over {\bf Q},
533: the univariate factorizer implements only classical
1.5 noro 534: algorithms and its behavior is what one expects,
1.3 noro 535: that is, it shows average performance in cases
1.5 noro 536: where there are little extraneous factors, but
1.7 noro 537: shows poor performance for hard to factor polynomials with
538: many extraneous factors.
1.3 noro 539:
1.1 noro 540: \section{OpenXM and Risa/Asir OpenXM interfaces}
541:
542: \subsection{OpenXM overview}
543:
544: OpenXM stands for Open message eXchange protocol for Mathematics.
1.5 noro 545: From the viewpoint of protocol design, it can be regarded as a child
546: of OpenMath \cite{OPENMATH}. However our approach is somewhat
547: different. Our main purpose is to provide an environment for
548: integrating {\it existing} mathematical software systems. OpenXM
549: RFC-100 \cite{RFC100} defines a client-server architecture. Under
550: this specification, a client invokes an OpenXM ({\it OX}) server. The
551: client can send OpenXM ({\it OX}) messages to the server. OX messages
552: consist of {\it data} and {\it command}. Data is encoded according to
553: the common mathematical object ({\it CMO}) format which defines
554: serialized representation of mathematical objects. An OX server is a
555: stackmachine. If data is sent as an OX message, the server pushes the
556: data onto its stack. There is a common set of stackmachine commands
557: and each OX server understands its subset. The command set includes
558: stack manipulating commands and requests for execution of a procedure.
559: In addition, a server may accept its own command sequences if the
560: server wraps some interactive software. That is the server may be a
561: hybrid server.
1.1 noro 562:
563: OpenXM RFC-100 also defines methods for session management. In particular
564: the method to reset a server is carefully designed and it provides
565: a robust way of using servers both for interactive and non-interactive
566: purposes.
567:
568: \subsection{OpenXM client interface of {\tt asir}}
569:
570: Risa/Asir is a main client in OpenXM package. The application {\tt
1.5 noro 571: asir} can access to OpenXM servers via several built-in interface
572: functions. and various interfaces to existing OpenXM servers are
573: prepared as user defined functions written in Asir language.
574: We show a typical OpenXM session.
1.1 noro 575:
576: \begin{verbatim}
577: [1] P = ox_launch(); /* invoke an OpenXM asir server */
578: 0
579: [2] ox_push_cmo(P,x^10-y^10);
580: /* push a polynomial onto the stack */
581: 0
582: [3] ox_execute_function(P,"fctr",1); /* call factorizer */
583: 0
584: [4] ox_pop_cmo(P); /* get the result from the stack */
585: [[1,1],[x^4+y*x^3+y^2*x^2+y^3*x+y^4,1],
586: [x^4-y*x^3+y^2*x^2-y^3*x+y^4,1],[x-y,1],[x+y,1]]
587: [5] ox_cmo_rpc(P,"fctr,",x^10000-2^10000*y^10000);
1.7 noro 588: /* call factorizer; a utility function */
1.1 noro 589: 0
590: [6] ox_reset(P); /* reset the computation in the server */
591: 1
592: [7] ox_shutdown(P); /* shutdown the server */
593: 0
594: \end{verbatim}
595:
596: \subsection{OpenXM server {\tt ox\_asir}}
597:
598: An application {\tt ox\_asir} is a wrapper of {\tt asir} and provides
599: all the functions of {\tt asir} to OpenXM clients. It completely
1.7 noro 600: implements the OpenXM reset protocol and also allows remote
1.5 noro 601: debugging of user programs running on the server. As an example we
602: show a program for checking whether a polynomial set is a Groebner
603: basis or not. A client executes {\tt gbcheck()} and servers execute
604: {\tt sp\_nf\_for\_gbcheck()} which is a simple normal form computation
1.7 noro 605: of an S-polynomial. First of all the client collects all critical pairs
1.1 noro 606: necessary for the check. Then the client requests normal form
607: computations to idling servers. If there are no idling servers the
608: clients waits for some servers to return results by {\tt
609: ox\_select()}, which is a wrapper of UNIX {\tt select()}. If we have
1.5 noro 610: large number of critical pairs to be processed, we can expect good
611: load balancing by {\tt ox\_select()}.
1.1 noro 612:
613: \begin{verbatim}
614: def gbcheck(B,V,O,Procs) {
615: map(ox_reset,Procs);
616: dp_ord(O); D = map(dp_ptod,B,V);
617: L = dp_gr_checklist(D); DP = L[0]; Plist = L[1];
618: /* register DP in servers */
619: map(ox_cmo_rpc,Procs,"register_data_for_gbcheck",vtol(DP));
620: /* discard return value in stack */
621: map(ox_pop_cmo,Procs);
622: Free = Procs; Busy = [];
623: while ( Plist != [] || Busy != [] )
624: if ( Free == [] || Plist == [] ) {
625: /* someone is working; wait for data */
626: Ready = ox_select(Busy);
627: /* update Busy list and Free list */
628: Busy = setminus(Busy,Ready); Free = append(Ready,Free);
629: for ( ; Ready != []; Ready = cdr(Ready) )
630: if ( ox_get(car(Ready)) != 0 ) {
631: /* a normal form is non zero */
632: map(ox_reset,Procs); return 0;
633: }
634: } else {
635: /* update Busy list and Free list */
636: Id = car(Free); Free = cdr(Free); Busy = cons(Id,Busy);
637: /* take a pair */
638: Pair = car(Plist); Plist = cdr(Plist);
639: /* request a normal form computation */
640: ox_cmo_rpc(Id,"sp_nf_for_gbcheck",Pair);
641: ox_push_cmd(Id,262); /* 262 = OX_popCMO */
642: }
643: map(ox_reset,Procs); return 1;
644: }
645: \end{verbatim}
646:
647: \subsection{Asir OpenXM library {\tt libasir.a}}
648:
1.7 noro 649: Asir OpenXM library {\tt libasir.a} contains functions simulating the
1.1 noro 650: stack machine commands supported in {\tt ox\_asir}. By linking {\tt
651: libasir.a} an application can use the same functions as in {\tt
1.3 noro 652: ox\_asir} without accessing to {\tt ox\_asir} via TCP/IP. There is
1.7 noro 653: also a stack, which can be manipulated by the library functions. In
1.5 noro 654: order to make full use of this interface, one has to prepare
655: conversion functions between CMO and the data structures proper to the
1.7 noro 656: application itself. A function {\tt asir\_ox\_pop\_string()} is
657: provided to convert CMO to a human readable form, which may be
658: sufficient for a simple use of this interface.
1.1 noro 659:
660: \section{Concluding remarks}
661: We have shown the current status of Risa/Asir and its OpenXM
662: interfaces. As a result of our policy of development, it is true that
663: Risa/Asir does not have abundant functions. However it is a completely
1.5 noro 664: open system and its total performance is not bad. Especially on
665: Groebner basis computation over {\bf Q}, many techniques for improving
666: practical performances have been implemented. As the OpenXM interface
667: specification is completely documented, we can easily add another
668: function to Risa/Asir by wrapping an existing software system as an OX
1.7 noro 669: server, and other clients can call functions in Risa/Asir by
670: implementing the OpenXM client interface. With the remote debugging
671: and the function to reset servers, one will be able to enjoy parallel
672: and distributed computation with OpenXM facilities.
1.1 noro 673: %
674: \begin{thebibliography}{7}
675: %
676: \addcontentsline{toc}{section}{References}
677:
678: \bibitem{ANY}
679: Anay, H., Noro, M., Yokoyama, K. (1996)
680: Computation of the Splitting fields and the Galois Groups of Polynomials.
681: Algorithms in Algebraic geometry and Applications,
682: Birkh\"auser (Proceedings of MEGA'94), 29--50.
683:
684: \bibitem{FPARA}
685: Jean-Charles Faug\`ere (1994)
686: Parallelization of Groebner basis.
687: Proceedings of PASCO'94, 124--132.
688:
689: \bibitem{F4}
690: Jean-Charles Faug\`ere (1999)
691: A new efficient algorithm for computing Groebner bases ($F_4$).
692: Journal of Pure and Applied Algebra (139) 1-3 , 61--88.
693:
694: \bibitem{FGLM}
695: Faug\`ere, J.-C. et al. (1993)
696: Efficient computation of zero-dimensional Groebner bases by change of ordering.
697: Journal of Symbolic Computation 16, 329--344.
698:
699: \bibitem{RFC100}
700: M. Maekawa, et al. (2001)
701: The Design and Implementation of OpenXM-RFC 100 and 101.
702: Proceedings of ASCM2001, World Scientific, 102--111.
703:
704: \bibitem{RISA}
705: Noro, M. et al. (1994-2001)
706: A computer algebra system Risa/Asir.
707: {\tt http://www.openxm.org}, {\tt http://www.math.kobe-u.ac.jp/Asir/asir.html}.
708:
709: \bibitem{REPL}
710: Noro, M., McKay, J. (1997)
711: Computation of replicable functions on Risa/Asir.
712: Proceedings of PASCO'97, ACM Press, 130--138.
713:
714: \bibitem{NOYO}
715: Noro, M., Yokoyama, K. (1999)
716: A Modular Method to Compute the Rational Univariate
717: Representation of Zero-Dimensional Ideals.
718: Journal of Symbolic Computation, 28, 1, 243--263.
719:
720: \bibitem{OPENXM}
721: OpenXM committers (2000-2001)
722: OpenXM package.
723: {\tt http://www.openxm.org}.
1.7 noro 724:
725: \bibitem{RUR}
726: Rouillier, R. (1996)
727: R\'esolution des syst\`emes z\'ero-dimensionnels.
728: Doctoral Thesis(1996), University of Rennes I, France.
1.1 noro 729:
730: \bibitem{SY}
731: Shimoyama, T., Yokoyama, K. (1996)
732: Localization and Primary Decomposition of Polynomial Ideals.
733: Journal of Symbolic Computation, 22, 3, 247--277.
734:
735: \bibitem{TRAGER}
736: Trager, B.M. (1976)
737: Algebraic Factoring and Rational Function Integration.
738: Proceedings of SYMSAC 76, 219--226.
739:
740: \bibitem{TRAV}
741: Traverso, C. (1988)
742: Groebner trace algorithms.
743: LNCS {\bf 358} (Proceedings of ISSAC'88), Springer-Verlag, 125--138.
744:
1.5 noro 745: \bibitem{BENCH}
746: {\tt http://www.math.uic.edu/\~\,jan/demo.html}.
747:
1.1 noro 748: \bibitem{COCOA}
749: {\tt http://cocoa.dima.unige.it/}.
750:
751: \bibitem{FGB}
752: {\tt http://www-calfor.lip6.fr/\~\,jcf/}.
753:
1.5 noro 754: %\bibitem{NTL}
755: %{\tt http://www.shoup.net/}.
1.1 noro 756:
757: \bibitem{OPENMATH}
758: {\tt http://www.openmath.org/}.
759:
760: \bibitem{SINGULAR}
761: {\tt http://www.singular.uni-kl.de/}.
762:
763: \end{thebibliography}
764:
765: %INDEX%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
766: \clearpage
767: \addcontentsline{toc}{section}{Index}
768: \flushbottom
769: \printindex
770: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
771:
772: \end{document}
773:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to dag-noro-proc.tex CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM / doc / Papers