Return to dag-noro.tex CVS log

Up to [local] / OpenXM / doc / Papers

Coverted the file to latex2e slides style.
Separated the latter half as another set of slides.

% $OpenXM: OpenXM/doc/Papers/dag-noro.tex,v 1.3 2001/10/12 02:22:17 noro Exp $
\documentclass{slides}
\usepackage{color}
\usepackage{rgb}
\usepackage{graphicx}
\usepackage{epsfig}
\newcommand{\qed}{$\Box$}
\newcommand{\mred}[1]{\smash{\mathop{\hbox{\rightarrowfill}}\limits_{\scriptstyle #1}}}
\newcommand{\tmred}[1]{\smash{\mathop{\hbox{\rightarrowfill}}\limits_{\scriptstyle #1}\limits^{\scriptstyle *}}}
\def\gr{Gr\"obner basis }
\def\st{\, s.t. \,}
\def\ni{\noindent} 
\def\ve{\vfill\eject} 
\textwidth 9.2in
\textheight 7.2in
\columnsep 0.33in
\topmargin -1in

\title{A computer algebra system Risa/Asir and OpenXM}

\author{Masayuki Noro\\ Kobe University, Japan}
\begin{document}
\setlength{\parskip}{10pt}
\maketitle

%\begin{slide}{}
%\begin{center}
%\fbox{\large Part I : OpenXM and Risa/Asir --- overview and history}
%\end{center}
%\end{slide}

%\begin{slide}{}
%\fbox{Integration of mathematical software systems}
%
%\begin{itemize}
%\item Data integration
%
%\begin{itemize}
%\item OpenMath ({\tt http://www.openmath.org}) , MP [GRAY98]
%\end{itemize}
%
%Standards for representing mathematical objects
%
%\item Control integration
%
%\begin{itemize}
%\item MCP [WANG99], OMEI [LIAO01]
%\end{itemize}
%
%Protocols for remote subroutine calls or session management
%
%\item Combination of two integrations
%
%\begin{itemize}
%\item MathLink, OpenMath+MCP, MP+MCP
%
%and OpenXM ({\tt http://www.openxm.org})
%\end{itemize}
%
%Both are necessary for practical implementation
%
%\end{itemize}
%\end{slide}
\begin{slide}{}
\fbox{A computer algebra system Risa/Asir}

({\tt http://www.math.kobe-u.ac.jp/Asir/asir.html})

\begin{itemize}
\item Software mainly for polynomial computation

\item User language with C-like syntax

C language without type declaration, with list processing

\item Builtin {\tt gdb}-like debugger for user programs

\item Open source

Whole source tree is available via CVS

The latest version : see {\tt http://www.openxm.org}

\item OpenXM interface

\begin{itemize}
\item OpenXM 

An infrastructure for exchanging mathematical data
\item Risa/Asir is a main client in OpenXM package.
\item An OpenXM server {\tt ox\_asir}
\item A library with OpenXM library interface {\tt libasir.a}
\end{itemize}
\end{itemize}
\end{slide}

\begin{slide}{}
\fbox{Goal of developing Risa/Asir}

\begin{itemize}
\item Testing new algorithms

\begin{itemize}
\item Development started in Fujitsu labs

Polynomial factorization, Groebner basis related computation,
cryptosystems , quantifier elimination , $\ldots$
\end{itemize}

\item To be a general purpose, open system

Since 1997, we have been developing OpenXM package
containing various servers and clients

Risa/Asir is a component of OpenXM

\item Environment for parallel and distributed computation

\end{itemize}
\end{slide}

%\begin{slide}{}
%\fbox{Capability for polynomial computation}
%
%\begin{itemize}
%\item Fundamental polynomial arithmetics
%
%recursive representation and distributed representation
%
%\item Polynomial factorization
%
%\begin{itemize}
%\item Univariate : over {\bf Q}, algebraic number fields and finite fields
%
%\item Multivariate : over {\bf Q}
%\end{itemize}
%
%\item Groebner basis computation
%
%\begin{itemize}
%\item Buchberger and $F_4$ [FAUG99] algorithm
%
%\item Change of ordering/RUR [ROUI96] of 0-dimensional ideals
%
%\item Primary ideal decomposition
%
%\item Computation of $b$-function (in Weyl Algebra)
%\end{itemize}
%\end{itemize}
%\end{slide}

\begin{slide}{}
\fbox{History of development : Polynomial factorization}

\begin{itemize}
\item 1989

Start of Risa/Asir with Boehm's conservative GC 

({\tt http://www.hpl.hp.com/personal/Hans\_Boehm/gc})

\item 1989-1992

Univariate and multivariate factorizers over {\bf Q}

\item 1992-1994

Univariate factorization over algebraic number fields

Intensive use of successive extension, non-squarefree norms

\item 1996-1998

Univariate factorization over large finite fields

Motivated by a reseach project in Fujitsu on cryptography

\item 2000-current 

Multivariate factorization over small finite fields (in progress)
\end{itemize}
\end{slide}

\begin{slide}{}
\fbox{History of development : Groebner basis}

\begin{itemize}
\item 1992-1994

User language $\Rightarrow$ C version; trace lifting [TRAV88]

\item 1994-1996

Trace lifting with homogenization

Omitting GB check by compatible prime [NOYO99]

Modular change of ordering/RUR[ROUI96] [NOYO99]

Primary ideal decomposition [SHYO96]

\item 1996-1998

Efficient content reduction during NF computation [NORO97]
Solved {\it McKay} system for the first time

\item 1998-2000

Test implementation of $F_4$ [FAUG99]

\item 2000-current

Buchberger algorithm in Weyl algebra

Efficient $b$-function computation[OAKU97] by a modular method
\end{itemize}
\end{slide}

\begin{slide}{}
\fbox{Timing data --- Factorization}

\underline{Univariate; over {\bf Q}}

$N_i$ : a norm of a polynomial, $\deg(N_i) = i$
\begin{center}
\begin{tabular}{|c||c|c|c|c|} \hline
		& $N_{105}$ & $N_{120}$ & $N_{168}$ & $N_{210}$ \\ \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}

\underline{Multivariate; over {\bf Q}}

$W_{i,j,k} = Wang[i]\cdot Wang[j]\cdot Wang[k]$ in {\tt asir2000/lib/fctrdata}
\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
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}

%--- : not tested
\end{slide}

\begin{slide}{}
\fbox{Timing data --- DRL Groebner basis computation}

\underline{Over $GF(32003)$}
\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}

\underline{Over {\bf Q}}

\begin{center}
\begin{tabular}{|c||c|c|c|c|c|} \hline
		& $C_7$ & $Homog. C_7$ & $K_7$ & $K_8$ & $McKay$ \\ \hline
Asir $Buchberger$ 	& 389 & 594 & 29 & 299 & 34950 \\ \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 & 0.6 & 5 & 10 \\ \hline
\end{tabular}
\end{center}
--- : not tested
\end{slide}

\begin{slide}{}
\fbox{Summary of performance}

\begin{itemize}
\item Factorizer

\begin{itemize}
\item Multivariate : reasonable performance

\item Univariate : obsoleted by M. van Hoeij's new algorithm [HOEI00]
\end{itemize}

\item Groebner basis computation

\begin{itemize}
\item Buchberger

Singular shows nice perfomance

Trace lifting is efficient in some cases over {\bf Q}

\item $F_4$

FGb is much faster than Risa/Asir

But we observe that {\it McKay} is computed efficiently by $F_4$
\end{itemize}
\end{itemize}

\end{slide}

\begin{slide}{}
\fbox{What is the merit to use Risa/Asir?}

\begin{itemize}
\item Total performance is not excellent, but not bad

\item A completely open system

The whole source is available

\item Interface compliant to OpenXM RFC-100

The interface is fully documented

\item It serves as a test bench to try new ideas

Interactive debugger is very useful
\end{itemize}

\end{slide}


%\begin{slide}{}
%\fbox{CMO = Serialized representation of mathematical object}
%
%\begin{itemize}
%\item primitive data
%\begin{eqnarray*}
%\mbox{Integer32} &:& ({\tt CMO\_INT32}, {\sl int32}\ \mbox{n}) \\
%\mbox{Cstring}&:& ({\tt CMO\_STRING},{\sl int32}\,  \mbox{ n}, {\sl string}\, \mbox{s}) \\
%\mbox{List} &:& ({\tt CMO\_LIST}, {\sl int32}\, len, ob[0], \ldots,ob[m-1])
%\end{eqnarray*}
%
%\item numbers and polynomials
%\begin{eqnarray*}
%\mbox{ZZ}         &:& ({\tt CMO\_ZZ},{\sl int32}\, {\rm f}, {\sl byte}\, \mbox{a[1]}, \ldots
%{\sl byte}\, \mbox{a[$|$f$|$]} ) \\
%\mbox{Monomial32}&:& ({\tt CMO\_MONOMIAL32}, n, \mbox{e[1]}, \ldots, \mbox{e[n]}, \mbox{Coef}) \\
%\mbox{Coef}&:& \mbox{ZZ} | \mbox{Integer32} \\
%\mbox{Dpolynomial}&:& ({\tt CMO\_DISTRIBUTED\_POLYNOMIAL},\\
%                  & & m, \mbox{DringDefinition}, \mbox{Monomial32}, \ldots)\\
%\mbox{DringDefinition}
%                  &:& \mbox{DMS of N variables} \\
%                  & & ({\tt CMO\_RING\_BY\_NAME}, name) \\
%                  & & ({\tt CMO\_DMS\_GENERIC}) \\
%\end{eqnarray*}
%\end{itemize}
%\end{slide}
%
%\begin{slide}{}
%\fbox{Stack based communication}
%
%\begin{itemize}
%\item Data arrived a client
%
%Pushed to the stack
%
%\item Result
%
%Pushd to the stack
%
%Written to the stream when requested by a command
%
%\item The reason why we use the stack
%
%\begin{itemize}
%\item Stack = I/O buffer for (possibly large) objects
%
%Multiple requests can be sent before their execution
%
%A server does not get stuck in sending results
%\end{itemize}
%\end{itemize}
%\end{slide}

\begin{slide}{}
\fbox{OpenXM (Open message eXchange protocol for Mathematics) }

\begin{itemize}
\item An environment for parallel distributed computation

Both for interactive, non-interactive environment

\item OpenXM RFC-100 = Client-server architecture

Client $\Leftarrow$ OX (OpenXM) message $\Rightarrow$ Server

OX (OpenXM) message : command and data

\item Data

Encoding : CMO (Common Mathematical Object format)

Serialized representation of mathematical object

--- Main idea was borrowed from OpenMath 

({\tt http://www.openmath.org})

\item Command

stack machine command --- server is a stackmachine

+ server's own command sequences --- hybrid server
\end{itemize}
\end{slide}

\begin{slide}{}
\fbox{Example of distributed computation --- $F_4$ vs. $Buchberger$ }

\begin{verbatim}
/* competitive Gbase computation over GF(M) */
/* Cf. A.28 in SINGULAR Manual */
/* Process list is specified as an option : grvsf4(...|proc=P) */
def grvsf4(G,V,M,O)
{
  P = getopt(proc);
  if ( type(P) == -1 ) return dp_f4_mod_main(G,V,M,O);
  P0 = P[0]; P1 = P[1]; P = [P0,P1];
  map(ox_reset,P);
  ox_cmo_rpc(P0,"dp_f4_mod_main",G,V,M,O);
  ox_cmo_rpc(P1,"dp_gr_mod_main",G,V,0,M,O);
  map(ox_push_cmd,P,262); /* 262 = OX_popCMO */
  F = ox_select(P); R = ox_get(F[0]);
  if ( F[0] == P0 ) { Win = "F4"; Lose = P1;}
  else { Win = "Buchberger"; Lose = P0; }
  ox_reset(Lose); /* simply resets the loser */
  return [Win,R];
}
\end{verbatim}
\end{slide}

\begin{slide}{}
\fbox{References}

[BERN97] L. Bernardin, On square-free factorization of 
multivariate polynomials over a finite field, Theoretical
Computer Science 187 (1997), 105-116.

[FAUG99] J.C. Faug\`ere,
A new efficient algorithm for computing Groebner bases  ($F_4$),
Journal of Pure and Applied Algebra (139) 1-3 (1999), 61-88.

[GRAY98] S. Gray et al,
Design and Implementation of MP, A Protocol for Efficient Exchange of
Mathematical Expression,
J. Symb. Comp. {\bf 25} (1998), 213-238.

[HOEI00] M. van Hoeij, Factoring polynomials and the knapsack problem,
to appear in Journal of Number Theory (2000).

[LIAO01] W. Liao et al,
OMEI: An Open Mathematical Engine Interface,
Proc. ASCM2001 (2001), 82-91.
[NORO97] M. Noro, J. McKay,
Computation of replicable functions on Risa/Asir.
Proc. PASCO'97, ACM Press (1997), 130-138.
\end{slide}

\begin{slide}{}

[NOYO99] M. Noro, K. Yokoyama, 
A Modular Method to Compute the Rational Univariate
Representation of Zero-Dimensional Ideals.
J. Symb. Comp. {\bf 28}/1 (1999), 243-263.

[OAKU97] T. Oaku, Algorithms for $b$-functions, restrictions and algebraic
local cohomology groups of $D$-modules.
Advances in Applied Mathematics, 19 (1997), 61-105.

[ROUI96] F. Rouillier,
R\'esolution des syst\`emes z\'ero-dimensionnels. 
Doctoral Thesis(1996), University of Rennes I, France.

[SHYO96] T. Shimoyama, K. Yokoyama, Localization and Primary Decomposition of Polynomial Ideals.  J. Symb. Comp. {\bf 22} (1996), 247-277.

[TRAV88] C. Traverso, \gr trace algorithms. Proc. ISSAC '88 (LNCS 358), 125-138.

[WANG99] P. S. Wang,
Design and Protocol for Internet Accessible Mathematical Computation,
Proc. ISSAC '99 (1999), 291-298.
\end{slide}
\end{document}