Annotation of OpenXM/doc/Papers/dag-noro-proc.tex, Revision 1.1
1.1 ! noro 1: % $OpenXM$
! 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
! 381: \epsffile{blenall.ps}
! 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:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to dag-noro-proc.tex CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM / doc / Papers