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