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