Return to dag-noro-proc.tex CVS log

Up to [local] / OpenXM / doc / Papers

Annotation of OpenXM/doc/Papers/dag-noro-proc.tex, Revision 1.2

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