% $OpenXM: OpenXM/doc/Papers/dag-noro-proc.tex,v 1.12 2002/02/25 07:56:16 noro Exp $ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % This is a sample input file for your contribution to a multi- % author book to be published by Springer Verlag. % % Please use it as a template for your own input, and please % follow the instructions for the formal editing of your % manuscript as described in the file "1readme". % % Please send the Tex and figure files of your manuscript % together with any additional style files as well as the % PS file to the editor of your book. % % He or she will collect all contributions for the planned % book, possibly compile them all in one go and pass the % complete set of manuscripts on to Springer. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %RECOMMENDED%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \documentclass[runningheads]{cl2emult} \usepackage{makeidx} % allows index generation \usepackage{graphicx} % standard LaTeX graphics tool % for including eps-figure files \usepackage{subeqnar} % subnumbers individual equations % within an array \usepackage{multicol} % used for the two-column index \usepackage{cropmark} % cropmarks for pages without % pagenumbers \usepackage{math} % placeholder for figures \makeindex % used for the subject index % please use the style sprmidx.sty with % your makeindex program %upright Greek letters (example below: upright "mu") \newcommand{\euler}[1]{{\usefont{U}{eur}{m}{n}#1}} \newcommand{\eulerbold}[1]{{\usefont{U}{eur}{b}{n}#1}} \newcommand{\umu}{\mbox{\euler{\char22}}} \newcommand{\umub}{\mbox{\eulerbold{\char22}}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %OPTIONAL%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % %\usepackage{amstex} % useful for coding complex math %\mathindent\parindent % needed in case "Amstex" is used % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %AUTHOR_STYLES_AND_DEFINITIONS%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % %Please reduce your own definitions and macros to an absolute %minimum since otherwise the editor will find it rather %strenuous to compile all individual contributions to a %single book file \usepackage{epsfig} \def\cont{{\rm cont}} \def\GCD{{\rm GCD}} \def\Q{{\bf Q}} % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} % \title*{A Computer Algebra System Risa/Asir and OpenXM} % % \toctitle{A Computer Algebra System Risa/Asir and OpenXM} % allows explicit linebreak for the table of content % % \titlerunning{Risa/Asir and OpenXM} % allows abbreviation of title, if the full title is too long % to fit in the running head % \author{Masayuki Noro} % %\authorrunning{Masayuki Noro} % if there are more than two authors, % please abbreviate author list for running head % % \institute{Kobe University, Rokko, Kobe 657-8501, Japan} \maketitle % typesets the title of the contribution %\begin{abstract} %Risa/Asir is software for polynomial computation. It has been %developed for testing experimental polynomial algorithms, and now it %acts also as a main component in the OpenXM package \cite{noro:OPENXM}. %OpenXM is an infrastructure for exchanging mathematical %data. It defines a client-server architecture for parallel and %distributed computation. In this article we present an overview of %Risa/Asir and review several techniques for improving performances of %Groebner basis computation over {\bf Q}. We also show Risa/Asir's %OpenXM interfaces and their usages. %\end{abstract} \section{Introduction} %Risa/Asir は, 数, 多項式などに対する演算を実装する engine, %ユーザ言語を実装する parser and interpreter および, %他の application との interaction のための OpenXM interface からなる %computer algebra system である. Risa/Asir is a computer algebra system which consists of an engine for operations on numbers and polynomials, a parser and an interpreter for the user language, and OpenXM API, a communication interface for interaction with other applications. %engine では, 数, 多項式などの arithmetics および, 多項式 %GCD, 因数分解, グレブナ基底計算が実装されている. これらは組み込み関数 %としてユーザ言語から呼び出される. The engine implements fundamental arithmetics on numbers and polynomials, polynomial GCD, polynomial factorizations and Groebner basis computations, etc. %Risa/Asir のユーザ言語は C 言語 like な文法をもち, 変数の型宣言が %ない, リスト処理および自動 garbage collection つきのインタプリタ %言語である. ユーザ言語プログラムは parser により中間言語に %変換され, interpreter により解釈実行される. interpreter には %gdb 風の debugger が組み込まれている. The user language has C-like syntax, without type declarations of variables, with list processing and with automatic garbage collection. The interpreter is equipped with a {\tt gdb}-like debugger. %これらの機能は OpenXM interface を通して他の application からも使用可 %能である. OpenXM \cite{noro:RFC100} は数学ソフトウェアの client-server %型の相互呼び出しのための プロトコルである. All these functions can be called from other applications via OpenXM API. OpenXM \cite{noro:RFC100} is a protocol for client-server communications for mathematical software systems. We are distributing OpenXM package \cite{noro:OPENXM}, which is a collection of various clients and servers compliant to the OpenXM protocol specification. %Risa/Asir は多項式因数分解, ガロア群計算 \cite{noro:ANY}, グレブナ基底 %計算 \cite{noro:NM,noro:NY}, 準素イデアル分解 \cite{noro:SY}, 暗号 %\cite{noro:IKNY} における実験的アルゴリズム をテストするためのプラット %フォームとして開発されてきた. また, OpenXM API を用いて parallel %distributed computation の実験にも用いられている. 根幹をなすのは多項 %式因数分解およびグレブナ基底計算である. 本稿では, 特に, グレブナ基底 %計算に関して, その基本および {\bf Q} 上での計算の困難を克服するための %さまざまな工夫およびその効果について述べる. また, Risa/Asir は OpenXM %package における主要な component の一つである. Risa/Asir を client あ %るいは server として用いる分散並列計算について, 実例をもとに解説する. Risa/Asir has been used for implementing and testing experimental algorithms such as polynomial factorizations, splitting field and Galois group computations \cite{noro:ANY}, Groebner basis computations \cite{noro:REPL,noro:NOYO}, primary ideal decomposition \cite{noro:SY} and cryptgraphy \cite{noro:IKNY}. In these applications two major functions of Risa/Asir, polynomial factorization and Groebner basis computation play important roles. We focus on Groebner basis computation and we review its fundamentals and vaious efforts for improving efficiency especially over $\Q$. Risa/Asir is also a main component of OpenXM package and it has been used for parallel distributed computation with OpenXM API. We will explain how one can execute parallel distributed computation by using Risa/Asir as a client or a server. \section{Efficient Groebner basis computation over {\bf Q}} \label{tab:gbtech} In this section we review several practical techniques to improve Groebner basis computation over {\bf Q}, which are easily implemented but may not be well known. We use the following notations. \begin{description} \item $<$ : a term order in the set of monomials. It is a total order such that $\forall t, 1 \le t$ and $\forall s, t, u, s $f \leftarrow f - t/HT(g) \cdot c/HC(g) \cdot g$, \quad where $c$ is the coeffcient of $t$ in $f$ \end{tabbing} This division terminates for any term order. With this division, we can show the most primitive version of the Buchberger algorithm. \begin{tabbing} Input : a finite polynomial set $F$\\ Output : a Groebner basis $G$ of $Id(F)$ with respect to a term order $<$\\ $G \leftarrow F$; \quad $D \leftarrow \{\{f,g\}| f, g \in G, f \neq g \}$\\ while \= $D \neq \emptyset$ do \\ \> $\{f,g\} \leftarrow$ an element of $D$; \quad $D \leftarrow D \setminus \{P\}$\\ \> $R \leftarrow$ a remainder of $Spoly(f,g)$ on division by $G$\\ \> if $R \neq 0$ then $D \leftarrow D \cup \{\{f,R\}| f \in G\}$; \quad $G \leftarrow G \cup \{R\}$\\ end do\\ return G \end{tabbing} From the practical point of view, the above algorithm is too naive to compute real problems and lots of improvements have been proposed. The following are major ones: \begin{itemize} \item Useless pair detection We don't have to process all the pairs in $D$ and several useful criteria for detecting useless pairs were proposed (cf. \cite{noro:BW}). \item Selection strategy The selection of $\{f,g\}$ greatly affects the subsequent computation. The typical strategies are the normal startegy and the sugar strategy \cite{noro:SUGAR}. The latter was proposed for efficient computation under a non degree-compatible order. \item Modular methods Even if we apply several criteria, it is difficult to detect all pairs whose S-polynomials are reduced to zero, and the cost to process them often occupies a major part in the whole computation. The trace algorithms \cite{noro:TRAV} were proposed to reduce such cost. This will be explained in more detail in Section \ref{sec:gbhomo}. \item Change of ordering For elimination, we need a Groebner basis with respect to a non degree-compatible order, but it is often hard to compute it by a direct application of the Buchberger algorithm. If the ideal is zero dimensional, we can apply a change of ordering algorithm called FGLM \cite{noro:FGLM}. First of all we compute a Groebner basis with respect to some order. Then we can obtain a Groebner basis with respect to a desired order by a linear algebraic method. \end{itemize} By implementing these techniques, one can obtain Groebner bases for wider range of inputs. Nevertheless there are still intractable problems with these classical tools. In the subsequent sections we show several methods for further improvements. \subsection{Combination of homogenization and trace lifting} \label{sec:gbhomo} The trace lifting algorithm can be formulated in an abstract form as follows (c.f. \cite{noro:FPARA}). \begin{tabbing} Input : a finite subset $F \subset {\bf Z}[X]$\\ Output : a Groebner basis $G$ of $Id(F)$ with respect to a term order $<$\\ do \= \\ \> $p \leftarrow$ a new prime\\ \>Guess \= a Groebner basis candidate $G \subset Id(F)$ such that $\phi_p(G)$ \\ \>\> is a Groebner basis of $Id(\phi_p(F))$ in ${GF(p)}[X]$\\ \>Check that $G$ is a Groebner basis of $Id(G)$ and $F \subset Id(G)$\\ \>If $G$ passes the check return $G$\\ end do \end{tabbing} We can apply various methods for {\it guess} part of the above algorithm. In the original algorithm we guess the candidate by replacing zero normal form checks over {\bf Q} with those over $GF(p)$ in the Buchberger algorithm, which we call {\it tl\_guess}. In Asir one can specify another method {\it tl\_h\_guess\_dh}, which is a combination of {\it tl\_guess} and homogenization. \begin{tabbing} $tl\_h\_guess\_dh(F,p)$\\ Input : $F\subset {\bf Z}[X]$, a prime $p$\\ Output : a Groebner basis candidate\\ $F_h \leftarrow$ the homogenization of $F$\\ $G_h \leftarrow tl\_guess(F_h,p)$ under an appropriate term order\\ $G \leftarrow$ the dehomogenization of $G_h$\\ $G \leftarrow G \setminus \{g \in G| \exists h \in G \setminus \{g\}$ such that $HT(h)|HT(g)$ \} \end{tabbing} The input is homogenized to suppress intermediate coefficient swells of intermediate basis elements. The homogenization may increase the number of normal forms reduced to zero, but they can be detected over by the computations over $GF(p)$. Finally, by dehomogenizing the candidate we can expect that lots of redundant elements are removed and the subsequent check are made easy. \subsection{Minimal polynomial computation by a modular method} Let $I$ be a zero-dimensional ideal in $R={\bf Q}[x_1,\ldots,x_n]$. Then the minimal polynomial $m(x_i)$ of a variable $x_i$ in $R/I$ can be computed by applying FGLM partially, but it often takes long time if one searches $m(x_i)$ incrementally over {\bf Q}. In this case we can apply a simple modular method to compute the minimal polynomial. \begin{tabbing} Input : a Groebner basis $G$ of $I$, a variable $x_i$\\ Output : the minimal polynomial of $x_i$ in $R/I$\\ do \= \\ \> $p \leftarrow$ a new prime such that $p \not{|} HC(g)$ for all $g \in G$\\ \> $m_p \leftarrow$ the minimal polynomial of $x_i$ in $GF(p)[x_1,\ldots,x_n]/Id(\phi_p(G))$\\ \> If there exists $m(x_i) \in I$ such that $\phi_p(m) = m_p$ and $\deg(m)=\deg(m_p)$\\ \> then return $m(x_i)$\\ end do \end{tabbing} In this algorithm, $m_p$ can be obtained by a partial FGLM over $GF(p)$ because $\phi_p(G)$ is a Groebner basis. Once we know the candidate of $\deg(m(x_i))$, $m(x_i)$ can be determined by solving a system of linear equations via the method of indeterminate coefficient, and it can be solved efficiently by $p$-adic method. Arguments on \cite{noro:NOYO} ensures that $m(x_i)$ is what we want if it exists. Note that the full FGLM can also be computed by the same method. \subsection{Integer contents reduction} \label{sec:gbcont} In some cases the cost to remove integer contents during normal form computations is dominant. We can remove the content of an integral polynomial $f$ efficiently by the following method \cite{noro:REPL}. \begin{tabbing} Input : an integral polynomial $f$\\ Output : a pair $(\cont(f),f/\cont(f))$\\ $g_0 \leftarrow$ an estimate of $\cont(f)$ such that $\cont(f)|g_0$\\ Write $f$ as $f = g_0q+r$ by division with remainder by $g_0$ for each coefficient\\ If $r = 0$ then return $(g_0,q)$\\ else return $(g,g_0/g \cdot q + r/g)$, where $g = \GCD(g_0,\cont(r))$ \end{tabbing} By separating the set of coefficients of $f$ into two subsets and by computing GCD of sums of the elements in each subset we can estimate $g_0$ with high accuracy. Then other components are easily computed. %\subsection{Demand loading of reducers} %An execution of the Buchberger algorithm may produce vary large number %of intermediate basis elements. In Asir, we can specify that such %basis elements should be put on disk to enlarge free memory space. %This does not reduce the efficiency so much because all basis elements %are not necessarily used in a single normal form computation, and the %cost for reading basis elements from disk is often negligible because %of the cost for coefficient computations. \subsection{Performances of Groebner basis computation} All the improvements in this sections have been implemented in Risa/Asir. Besides we have a test implemention of $F_4$ algorithm \cite{noro:F4}, which is a new algorithm for computing Groebner basis by various methods. We show timing data on Risa/Asir for Groebner basis computation. The measurements were made on a PC with PentiumIII 1GHz and 1Gbyte of main memory. Timings are given in seconds. In the tables `exhasut' means memory exhastion. $C_n$ is the cyclic $n$ system and $K_n$ is the Katsura $n$ system, both are famous bench mark problems \cite{noro:BENCH}. $McKay$ \cite{noro:REPL} is a system whose Groebner basis is hard to compute over {\bf Q}. The term order is graded reverse lexicographic order. Table \ref{tab:gbmod} shows timing data for Groebner basis computation over $GF(32003)$. $F_4$ implementation in Risa/Asir outperforms Buchberger algorithm implementation, but it is still several times slower than $F_4$ implementation in FGb \cite{noro:FGB}. Table \ref{tab:gbq} shows timing data for Groebner basis computation over $\Q$, where we compare the timing data under various configuration of algorithms. {\bf TR}, {\bf Homo}, {\bf Cont} means trace lifting, homogenization and contents reduction respectively. Table \ref{tab:gbq} also shows timings of minimal polynomial computation for $C_7$, $K_7$ and $K_8$, which are zero-dimensional ideals. Table \ref{tab:gbq} shows that it is difficult or practically impossible to compute Groebner bases of $C_7$, $C_8$ and $McKay$ without the methods described in Section \ref{sec:gbhomo} and \ref{sec:gbcont}. Here we mension a result of $F_4$ over $\Q$. Though $F_4$ implementation in Risa/Asir over {\bf Q} is still experimental and its performance is poor in general, it can compute $McKay$ in 4939 seconds. Fig. \ref{tab:f4vsbuch} explains why $F_4$ is efficient in this case. The figure shows that the Buchberger algorithm produces normal forms with huge coefficients for S-polynomials after the 250-th one, which make subsequent computation hard. Whereas $F_4$ algorithm automatically produces the reduced basis elements, and the reduced basis elements have much smaller coefficients after removing contents. Therefore the corresponding computation is quite easy in $F_4$. \begin{table}[hbtp] \begin{center} \begin{tabular}{|c||c|c|c|c|c|c|c|} \hline & $C_7$ & $C_8$ & $K_7$ & $K_8$ & $K_9$ & $K_{10}$ & $K_{11}$ \\ \hline Asir $Buchberger$ & 31 & 1687 & 2.6 & 27 & 294 & 4309 & $>$ 3h \\ \hline %Singular & 8.7 & 278 & 0.6 & 5.6 & 54 & 508 & 5510 \\ \hline %CoCoA 4 & 241 & $>$ 5h & 3.8 & 35 & 402 &7021 & --- \\ \hline\hline Asir $F_4$ & 5.3 & 129 & 0.5 & 4.5 & 31 & 273 & 2641 \\ \hline FGb(estimated) & 0.9 & 23 & 0.1 & 0.8 & 6 & 51 & 366 \\ \hline \end{tabular} \end{center} \caption{Groebner basis computation over $GF(32003)$} \label{tab:gbmod} \end{table} \begin{table}[hbtp] \begin{center} \begin{tabular}{|c||c|c|c|c|c|} \hline & $C_7$ & $C_8$ & $K_7$ & $K_8$ & $McKay$ \\ \hline {\bf TR}+{\bf Homo}+{\bf Cont} & 389 & 54000 & 35 & 351 & 34950 \\ \hline {\bf TR}+{\bf Homo} & 1346 & exhaust & 35 & 352 & exhaust \\ \hline {\bf TR} & $> 3h $ & $>$ 1day & 36 & 372 & $>$ 1day \\ \hline %Asir $F_4$ & 989 & 456 & --- & 90 & 991 & 4939 \\ \hline \hline {\bf Minipoly} & 14 & positive dim & 14 & 286 & positive dim \\ \hline %Singular & --- & 15247 & --- & 7.6 & 79 & $>$ 20h \\ \hline %CoCoA 4 & --- & 13227 & --- & 57 & 709 & --- \\ \hline\hline %FGb(estimated) & 8 &11 & 288 & 0.6 & 5 & 10 \\ \hline \end{tabular} \end{center} \caption{Groebner basis and minimal polynomial computation over {\bf Q}} \label{tab:gbq} \end{table} \begin{figure}[hbtp] \begin{center} \epsfxsize=12cm %\epsffile{../compalg/ps/blenall.ps} \epsffile{blen.ps} \end{center} \caption{Maximal coefficient bit length of intermediate bases} \label{tab:f4vsbuch} \end{figure} %Table \ref{minipoly} shows timing data for the minimal polynomial %computations of all variables over {\bf Q} by the modular method. %\begin{table}[hbtp] %\begin{center} %\begin{tabular}{|c||c|c|c|c|c|} \hline % & $C_6$ & $C_7$ & $K_6$ & $K_7$ & $K_8$ \\ \hline %Singular & 0.9 & 846 & 307 & 60880 & --- \\ \hline %Asir & 1.5 & 182 & 12 & 164 & 3420 \\ \hline %\end{tabular} %\end{center} %\caption{Minimal polynomial computation} %\label{minipoly} %\end{table} %\subsection{Polynomial factorization} % %Table \ref{unifac} shows timing data for univariate factorization over %{\bf Q}. $N_{i,j}$ is an irreducible polynomial which are hard to %factor by the classical algorithm. $N_{i,j}$ is a norm of a polynomial %and $\deg(N_i) = i$ with $j$ modular factors. Risa/Asir is %disadvantageous in factoring polynomials of this type because the %algorithm used in Risa/Asir has exponential complexity. In contrast, %CoCoA 4\cite{noro:COCOA} and NTL-5.2\cite{noro:NTL} show nice performances %because they implement recently developed algorithms. % %\begin{table}[hbtp] %\begin{center} %\begin{tabular}{|c||c|c|c|c|} \hline % & $N_{105,23}$ & $N_{120,20}$ & $N_{168,24}$ & $N_{210,54}$ \\ \hline %Asir & 0.86 & 59 & 840 & hard \\ \hline %Asir NormFactor & 1.6 & 2.2& 6.1& hard \\ \hline %%Singular& hard? & hard?& hard? & hard? \\ \hline %CoCoA 4 & 0.2 & 7.1 & 16 & 0.5 \\ \hline\hline %NTL-5.2 & 0.16 & 0.9 & 1.4 & 0.4 \\ \hline %\end{tabular} %\end{center} %\caption{Univariate factorization over {\bf Q}} %\label{unifac} %\end{table} % %Table \ref{multifac} shows timing data for multivariate factorization %over {\bf Q}. $W_{i,j,k}$ is a product of three multivariate %polynomials $Wang[i]$, $Wang[j]$, $Wang[k]$ given in a data file {\tt %fctrdata} in Asir library directory. It is also included in Risa/Asir %source tree and located in {\tt asir2000/lib}. These examples have %leading coefficients of large degree which vanish at 0 which tend to %cause so-called the leading coefficient problem the bad zero %problem. Risa/Asir's implementation carefully treats such cases and it %shows reasonable performance compared with other famous systems. %\begin{table}[hbtp] %\begin{center} %\begin{tabular}{|c||c|c|c|c|c|} \hline % & $W_{1,2,3}$ & $W_{4,5,6}$ & $W_{7,8,9}$ & $W_{10,11,12}$ & $W_{13,14,15}$ \\ \hline %variables & 3 & 5 & 5 & 5 & 4 \\ \hline %monomials & 905 & 41369 & 51940 & 30988 & 3344 \\ \hline\hline %Asir & 0.2 & 4.7 & 14 & 17 & 0.4 \\ \hline %Singular& $>$15min & --- & ---& ---& ---\\ \hline %CoCoA 4 & 5.2 & $>$15min & $>$15min & $>$15min & 117 \\ \hline\hline %Mathematica 4& 0.2 & 16 & 23 & 36 & 1.1 \\ \hline %Maple 7& 0.5 & 18 & 967 & 48 & 1.3 \\ \hline %\end{tabular} %\end{center} %\caption{Multivariate factorization over {\bf Q}} %\label{multifac} %\end{table} %As to univariate factorization over {\bf Q}, the univariate factorizer %implements old algorithms and its behavior is what one expects, %that is, it shows average performance in cases where there are little %extraneous factors, but shows poor performance for hard to factor %polynomials with many extraneous factors. \section{OpenXM and Risa/Asir OpenXM interfaces} \subsection{OpenXM overview} OpenXM stands for Open message eXchange protocol for Mathematics. From the viewpoint of protocol design, it can be regarded as a child of OpenMath \cite{noro:OPENMATH}. However our approach is somewhat different. Our main purpose is to provide an environment for integrating {\it existing} mathematical software systems. OpenXM RFC-100 \cite{noro:RFC100} defines a client-server architecture. Under this specification, a client invokes an OpenXM ({\it OX}) server. The client can send OpenXM ({\it OX}) messages to the server. OX messages consist of {\it data} and {\it command}. Data is encoded according to the common mathematical object ({\it CMO}) format which defines serialized representation of mathematical objects. An OX server is a stackmachine. If data is sent as an OX message, the server pushes the data onto its stack. There is a common set of stackmachine commands and each OX server understands its subset. The command set includes stack manipulating commands and requests for execution of a procedure. In addition, a server may accept its own command sequences if the server wraps some interactive software. That is the server may be a hybrid server. OpenXM RFC-100 also defines methods for session management. In particular the method to reset a server is carefully designed and it provides a robust way of using servers both for interactive and non-interactive purposes. \subsection{OpenXM API in Risa/Asir user language} Risa/Asir is a main client in OpenXM package. The application {\tt asir} can access to OpenXM servers via several built-in interface functions. and various interfaces to existing OpenXM servers are prepared as user defined functions written in Asir language. We show a typical OpenXM session. \begin{verbatim} [1] P = ox_launch(); /* invoke an OpenXM asir server */ 0 [2] ox_push_cmo(P,x^10-y^10); /* push a polynomial onto the stack */ 0 [3] ox_execute_function(P,"fctr",1); /* call factorizer */ 0 [4] ox_pop_cmo(P); /* get the result from the stack */ [[1,1],[x^4+y*x^3+y^2*x^2+y^3*x+y^4,1], [x^4-y*x^3+y^2*x^2-y^3*x+y^4,1],[x-y,1],[x+y,1]] [5] ox_cmo_rpc(P,"fctr,",x^10000-2^10000*y^10000); /* call factorizer; a utility function */ 0 [6] ox_reset(P); /* reset the computation in the server */ 1 [7] ox_shutdown(P); /* shutdown the server */ 0 \end{verbatim} \subsection{OpenXM server {\tt ox\_asir}} An application {\tt ox\_asir} is a wrapper of {\tt asir} and provides all the functions of {\tt asir} to OpenXM clients. It completely implements the OpenXM reset protocol and also allows remote debugging of user programs running on the server. As an example we show a program for checking whether a polynomial set is a Groebner basis or not. A client executes {\tt gbcheck()} and servers execute {\tt sp\_nf\_for\_gbcheck()} which is a simple normal form computation of an S-polynomial. First of all the client collects all critical pairs necessary for the check. Then the client requests normal form computations to idling servers. If there are no idling servers the clients waits for some servers to return results by {\tt ox\_select()}, which is a wrapper of UNIX {\tt select()}. If we have large number of critical pairs to be processed, we can expect good load balancing by {\tt ox\_select()}. \begin{verbatim} def gbcheck(B,V,O,Procs) { map(ox_reset,Procs); dp_ord(O); D = map(dp_ptod,B,V); L = dp_gr_checklist(D); DP = L[0]; Plist = L[1]; /* register DP in servers */ map(ox_cmo_rpc,Procs,"register_data_for_gbcheck",vtol(DP)); /* discard return value in stack */ map(ox_pop_cmo,Procs); Free = Procs; Busy = []; while ( Plist != [] || Busy != [] ) if ( Free == [] || Plist == [] ) { /* someone is working; wait for data */ Ready = ox_select(Busy); /* update Busy list and Free list */ Busy = setminus(Busy,Ready); Free = append(Ready,Free); for ( ; Ready != []; Ready = cdr(Ready) ) if ( ox_get(car(Ready)) != 0 ) { /* a normal form is non zero */ map(ox_reset,Procs); return 0; } } else { /* update Busy list and Free list */ Id = car(Free); Free = cdr(Free); Busy = cons(Id,Busy); /* take a pair */ Pair = car(Plist); Plist = cdr(Plist); /* request a normal form computation */ ox_cmo_rpc(Id,"sp_nf_for_gbcheck",Pair); ox_push_cmd(Id,262); /* 262 = OX_popCMO */ } map(ox_reset,Procs); return 1; } \end{verbatim} \subsection{OpenXM C language API in {\tt libasir.a}} Risa/Asir subroutine library {\tt libasir.a} contains functions simulating the stack machine commands supported in {\tt ox\_asir}. By linking {\tt libasir.a} an application can use the same functions as in {\tt ox\_asir} without accessing to {\tt ox\_asir} via TCP/IP. There is also a stack, which can be manipulated by the library functions. In order to make full use of this interface, one has to prepare conversion functions between CMO and the data structures proper to the application itself. However, if the application linking {\tt libasir.a} can parse human readable outputs, a function {\tt asir\_ox\_pop\_string()} will be sufficient for receiving results. The following program shows its usage. \begin{verbatim} /* $OpenXM: OpenXM/doc/oxlib/test.c,v 1.3 2002/02/25 07:24:33 noro Exp $ */ #include main() { char ibuf[BUFSIZ]; char *obuf; int len,len0; asir_ox_init(1); /* Use the network byte order */ len0 = BUFSIZ; obuf = (char *)malloc(len0); while ( 1 ) { printf("Input> "); fgets(ibuf,BUFSIZ,stdin); if ( !strncmp(ibuf,"bye",3) ) exit(0); /* the string in ibuf is executed, and the result is pushed onto the stack */ asir_ox_execute_string(ibuf); /* estimate the string length of the result */ len = asir_ox_peek_cmo_string_length(); if ( len > len0 ) { len0 = len; obuf = (char *)realloc(obuf,len0); } /* write the result to obuf as a string */ asir_ox_pop_string(obuf,len0); printf("Output> %s\n",obuf); } } \end{verbatim} In this program, \verb+asir_ox_execute_string()+ executes an Asir command line in {\tt ibuf} and the result is pushed onto the stack as a CMO data. Then we prepare a buffer sufficient to hold the result and call \verb+asir_ox_pop_string()+, which pops the result from the stack and convert it to a human readable form. Here is an example of execution: \begin{verbatim} % cc test.c OpenXM/lib/libasir.a OpenXM/lib/libasir-gc.a -lm % a.out Input> A = -z^31-w^12*z^20+y^18-y^14+x^2*y^2+x^21+w^2; Output> x^21+y^2*x^2+y^18-y^14-z^31-w^12*z^20+w^2 Input> B = 29*w^4*z^3*x^12+21*z^2*x^3+3*w^15*y^20-15*z^16*y^2; Output> 29*w^4*z^3*x^12+21*z^2*x^3+3*w^15*y^20-15*z^16*y^2 Input> fctr(A*B); Output> [[1,1],[29*w^4*z^3*x^12+21*z^2*x^3+3*w^15*y^20 -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]] \end{verbatim} \section{Concluding remarks} %We have shown the current status of Risa/Asir and its OpenXM %interfaces. As a result of our policy of development, it is true that %Risa/Asir does not have abundant functions. However it is a completely %open system and its total performance is not bad. Especially on %Groebner basis computation over {\bf Q}, many techniques for improving %practical performances have been implemented. As the OpenXM interface %specification is completely documented, we can easily add another %function to Risa/Asir by wrapping an existing software system as an OX %server, and other clients can call functions in Risa/Asir by %implementing the OpenXM client interface. With the remote debugging %and the function to reset servers, one will be able to enjoy parallel %and distributed computation with OpenXM facilities. % We have shown that many techniques for improving practical performances are implemented in Risa/Asir's Groebner basis engine. Though another important function, the polynomial factorizer only implements classical algorithms, its performance is comparable with or superior to that of Maple or Mathematica and is still practically useful. By preparing OpenXM interface or simply linking the Asir OpenXM library, one can call these efficient functions from any application. Risa/Asir is a completely open system. It is open source software and the OpenXM interface specification is completely documented, one can easily write interfaces to call functions in Risa/Asir and one will be able to enjoy parallel and distributed computation. \begin{thebibliography}{7} % \addcontentsline{toc}{section}{References} \bibitem{noro:ANY} Anay, H., Noro, M., Yokoyama, K. (1996) Computation of the Splitting fields and the Galois Groups of Polynomials. Algorithms in Algebraic geometry and Applications, Birkh\"auser (Proceedings of MEGA'94), 29--50. \bibitem{noro:BW} Becker, T., and Weispfenning, V. (1993) Groebner Bases. Graduate Texts in Math {\bf 141}. Springer-Verlag. \bibitem{noro:FPARA} Jean-Charles Faug\`ere (1994) Parallelization of Groebner basis. Proceedings of PASCO'94, 124--132. \bibitem{noro:F4} Jean-Charles Faug\`ere (1999) A new efficient algorithm for computing Groebner bases ($F_4$). Journal of Pure and Applied Algebra (139) 1-3 , 61--88. \bibitem{noro:FGLM} Faug\`ere, J.-C. et al. (1993) Efficient computation of zero-dimensional Groebner bases by change of ordering. Journal of Symbolic Computation 16, 329--344. \bibitem{noro:SUGAR} Giovini, A., Mora, T., Niesi, G., Robbiano, L., and Traverso, C. (1991). ``One sugar cube, please'' OR Selection strategies in the Buchberger algorithm. In Proc. ISSAC'91, ACM Press, 49--54. \bibitem{noro:IKNY} Izu, T., Kogure, J., Noro, M., Yokoyama, K. (1998) Efficient implementation of Schoof's algorithm. LNCS 1514 (Proc. ASIACRYPT'98), Springer, 66--79. \bibitem{noro:RFC100} M. Maekawa, et al. (2001) The Design and Implementation of OpenXM-RFC 100 and 101. Proceedings of ASCM2001, World Scientific, 102--111. \bibitem{noro:RISA} Noro, M. et al. (1994-2001) A computer algebra system Risa/Asir. {\tt http://www.openxm.org}, {\tt http://www.math.kobe-u.ac.jp/Asir/asir.html}. \bibitem{noro:REPL} Noro, M., McKay, J. (1997) Computation of replicable functions on Risa/Asir. Proceedings of PASCO'97, ACM Press, 130--138. \bibitem{noro:NOYO} Noro, M., Yokoyama, K. (1999) A Modular Method to Compute the Rational Univariate Representation of Zero-Dimensional Ideals. Journal of Symbolic Computation, 28, 1, 243--263. \bibitem{noro:OPENXM} OpenXM committers (2000-2001) OpenXM package. {\tt http://www.openxm.org}. \bibitem{noro:RUR} Rouillier, R. (1996) R\'esolution des syst\`emes z\'ero-dimensionnels. Doctoral Thesis(1996), University of Rennes I, France. \bibitem{noro:SY} Shimoyama, T., Yokoyama, K. (1996) Localization and Primary Decomposition of Polynomial Ideals. Journal of Symbolic Computation, 22, 3, 247--277. \bibitem{noro:TRAGER} Trager, B.M. (1976) Algebraic Factoring and Rational Function Integration. Proceedings of SYMSAC 76, 219--226. \bibitem{noro:TRAV} Traverso, C. (1988) Groebner trace algorithms. LNCS {\bf 358} (Proceedings of ISSAC'88), Springer-Verlag, 125--138. \bibitem{noro:BENCH} {\tt http://www.math.uic.edu/\~\,jan/demo.html}. \bibitem{noro:COCOA} {\tt http://cocoa.dima.unige.it/}. \bibitem{noro:FGB} {\tt http://www-calfor.lip6.fr/\~\,jcf/}. %\bibitem{noro:NTL} %{\tt http://www.shoup.net/}. \bibitem{noro:OPENMATH} {\tt http://www.openmath.org/}. \bibitem{noro:SINGULAR} {\tt http://www.singular.uni-kl.de/}. \end{thebibliography} %INDEX%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \clearpage \addcontentsline{toc}{section}{Index} \flushbottom \printindex %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{document}