% $OpenXM: OpenXM/doc/Papers/dag-noro-proc.tex,v 1.11 2002/02/25 01:02:14 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 $B$O(B, $B?t(B, $BB?9`<0$J$I$KBP$9$k1i;;$r<BAu$9$k(B engine, 
%$B%f!<%68@8l$r<BAu$9$k(B parser and interpreter $B$*$h$S(B,
%$BB>$N(B application $B$H$N(B interaction $B$N$?$a$N(B OpenXM interface $B$+$i$J$k(B
%computer algebra system $B$G$"$k(B. 
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 a communication interface called OpenXM API for
interaction with other applications.
%engine $B$G$O(B, $B?t(B, $BB?9`<0$J$I$N(B arithmetics $B$*$h$S(B, $BB?9`<0(B 
%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
%$B$H$7$F%f!<%68@8l$+$i8F$S=P$5$l$k(B.  
The engine implements fundamental arithmetics on numbers and polynomials,
polynomial GCD, polynomial factorizations and Groebner basis computations,
etc. These can be called from the user language as builtin functions.
%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
%$B$J$$(B, $B%j%9%H=hM}$*$h$S<+F0(B garbage collection $B$D$-$N%$%s%?%W%j%?(B
%$B8@8l$G$"$k(B. $B%f!<%68@8l%W%m%0%i%`$O(B parser $B$K$h$jCf4V8@8l$K(B
%$BJQ49$5$l(B, interpreter $B$K$h$j2r<a<B9T$5$l$k(B. interpreter $B$K$O(B
%gdb $BIw$N(B debugger $B$,AH$_9~$^$l$F$$$k(B. 
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.
%$B$3$l$i$N5!G=$O(B OpenXM interface $B$rDL$7$FB>$N(B application $B$+$i$b;HMQ2D(B
%$BG=$G$"$k(B. OpenXM \cite{noro:RFC100} $B$O?t3X%=%U%H%&%'%"$N(B client-server 
%$B7?$NAj8_8F$S=P$7$N$?$a$N(B $B%W%m%H%3%k$G$"$k(B.
These functions can be called from other applications via OpenXM API.
OpenXM \cite{noro:RFC100} is a protocol for client-server
communications between mathematical software.  We are distributing
OpenXM package \cite{noro:OPENXM}, which is a collection of various
clients and servers comlient to the OpenXM protocol specification.

%Risa/Asir $B$OB?9`<00x?tJ,2r(B, $B%,%m%"727W;;(B \cite{noro:ANY}, $B%0%l%V%J4pDl(B
%$B7W;;(B \cite{noro:NM,noro:NY}, $B=`AG%$%G%"%kJ,2r(B \cite{noro:SY}, $B0E9f(B 
%\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
%$B%U%)!<%`$H$7$F3+H/$5$l$F$-$?(B. $B$^$?(B, OpenXM API $B$rMQ$$$F(B parallel
%distributed computation $B$N<B83$K$bMQ$$$i$l$F$$$k(B.  $B:,44$r$J$9$N$OB?9`(B
%$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
%$B7W;;$K4X$7$F(B, $B$=$N4pK\$*$h$S(B {\bf Q} $B>e$G$N7W;;$N:$Fq$r9nI~$9$k$?$a$N(B
%$B$5$^$6$^$J9)IW$*$h$S$=$N8z2L$K$D$$$F=R$Y$k(B.  $B$^$?(B, Risa/Asir $B$O(B OpenXM
%package $B$K$*$1$k<gMW$J(B component $B$N0l$D$G$"$k(B. Risa/Asir $B$r(B client $B$"(B
%$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.
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 the important
funtions are polynomial factorization and Groebner basis
computation. 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<t \Rightarrow us<ut$.
\item $Id(F)$ : a polynomial ideal generated by a polynomial set $F$.
\item $HT(f)$ : the head term of a polynomial with respect to a term order.
\item $HC(f)$ : the head coefficient of a polynomial with respect to a term order.
\item $T(f)$ : terms with non zero coefficients in $f$.
\item $Spoly(f,g)$ : the S-polynomial of $\{f,g\}$ 

$Spoly(f,g) = T_{f,g}/HT(f)\cdot f/HC(f) -T_{f,g}/HT(g)\cdot g/HC(g)$, where
$T_{f,g} = LCM(HT(f),HT(g))$.
\item $\phi_p$ : the canonical projection from ${\bf Z}$ onto $GF(p)$.
\end{description}

\subsection{Groebner basis computation and its improvements}

A Groebner basis of an ideal $Id(F)$ can be computed by the Buchberger
algorithm. The key oeration in the algorithm is the following 
division by a polynomial set.
\begin{tabbing}
while \= $\exists g \in G$, $\exists t \in T(f)$ such that $HT(g)|t$ do\\
      \> $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}
Though this algorithm gives a Groebner basis of $Id(F)$, 
it is not practical at all. We need lots of techniques to make
it practical. The following are major improvements:
\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 \cite{noro:BUCH}
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 the
Buchberger algorithm. If the ideal is zero dimensional, we can apply a
change of ordering algorithm \cite{noro:FGLM} for a Groebner basis
with respect to any order and we can obtain a Groebner basis with
respect to a desired order.

\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 number of zero normal forms may
increase by the homogenization, but they are detected over
$GF(p)$. Finally, by dehomogenizing the candidate we can expect that
lots of redundant elements can be removed.

\subsection{Minimal polynomial computation by 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 a partial FGLM \cite{noro:FGLM}, 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}

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 `---' means it was
not measured.  $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}.  In Risa/Asir we have a test implemention of $F_4$ algorithm
\cite{noro:F4} and we also show its current performance.  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.
\ref{tab:gbq} also shows timings of minimal polynomial
computation for 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}.
Though $F_4$ implementation in Risa/Asir over {\bf Q} is still
experimental, the timing of $McKay$ is greatly reduced.
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 are
the computations in degree 16.  However, we know that the reduced
basis elements have much smaller coefficients after removing contents.
As $F_4$ algorithm automatically produces the reduced ones, the degree
16 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 & --- \\ \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
TR+Homo+Cont & 389 & 54000 & 29 & 299 & 34950 \\ \hline
TR+Homo & --- & --- & --- & --- & --- \\ \hline
TR & --- & --- & --- & --- & --- \\ \hline \hline
Minipoly & --- & --- & --- & --- & N/A \\ \hline
%Singular & --- & 15247 & --- & 7.6 & 79 & $>$ 20h \\ \hline
%CoCoA 4 & --- & 13227 & --- & 57 & 709 & --- \\ \hline\hline
%Asir $F_4$ 	&  989 & 456 & --- & 90 & 991 & 4939 \\ \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.  A function {\tt
asir\_ox\_pop\_string()} is provided to convert CMO to a human
readable form, which may be sufficient for a simple use of this
interface.

\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: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: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}

