File r35/lib/cali.tex artifact 258a3c12f2 on branch master

%       CALI user documentation
%       H.-G. Graebe | Univ. Leipzig | Version 2.1 


\documentstyle[12pt]{article}
\date{Oct. 20, 1993}


\textheight 21cm
\textwidth 15cm 
\voffset -60pt
\hoffset -45pt

\newcommand{\gr}{Gr\"obner }
\newcommand{\x}{{\bf x}}
\newcommand{\ind}[1]{{\em #1}\index{#1}}
\newcommand{\pbx}[1]{\mbox{}\hfill \parbox[t]{12cm}{#1} \pagebreak[3]}
\newcommand{\nl}{\newline \hspace*{5mm}}

%\makeindex

\title{CALI\\[20pt] A REDUCE Package for \\ 
    Commutative Algebra \\Version 2.1}

\author{
Hans-Gert Gr\"abe \\[15pt]
Universit\"at Leipzig\\ 
Fachbereich Mathematik/Informatik \\
Augustusplatz 10 -- 11\\
04109 Leipzig / Germany\\[20pt]
email : graebe@informatik.uni-leipzig.d400.de}

\begin{document}

\maketitle

\vfill
Key words : \gr algorithms for ideals and modules, free resolution,
local standard bases, Hilbert series, independent sets, primary
decomposition, constructive commutative algebra

\pagebreak

\tableofcontents

\pagebreak

\section{Introduction}

This package contains algorithms for computations in commutative
algebra closely related to the \gr algorithm for ideals and modules.
Its heart is a new implementation of the \gr algorithm\footnote{ The
data representation even for polynomials is different from that given
in the groebner package distributed with REDUCE (and rests on ideas
used in the dipoly package)} that allows the computation of syzygies,
too. This implementation is also applicable to submodules of free
modules with generators represented as rows of a matrix.

Moreover CALI contains facilities for local computations, using a
modern implementation of Mora's standard basis algorithm, see
\cite{MPT} and \cite{Gr23}, that works for arbitrary term orders.
The full analogy between modules over the local ring \linebreak[1]
$k[x_v:v\in H]_{\bf m}$ and homogeneous (in fact H-local) modules
over $k[x_v:v\in H]$ is reflected through the switch
\ind{noetherian}.  Turn it on (\gr basis, the default) or off (local
standard basis) to choose the right standard basis algorithm
automatically.

CALI extends also the restricted term order facilities of the
groebner package, defining term orders by degree vector lists, and
the rigid implementation of the sugar idea, by a more flexible
\ind{ecart} vector, in particular useful for local computations, see
\cite{Gr23}. 
\medskip

The package was designed mainly as a symbolic mode programming
environment extending the build-in facilities of REDUCE for the
computational approach to problems arising naturally in commutative
algebra. But an algebraic mode interface allows to access (in a more
rigid frame) all important features implemented symbolically and thus
should be favoured for short sample computations.

On the other hand, tedious computations are strongly recommended to
be done symbolically since this allows considerably more flexibility
and avoids unnecessary translations of intermediate results from
CALI's internal data representation to the algebraic mode and vice
versa. Moreover, one can easily extend the package with new symbolic
mode scripts, or do more difficult interactive computations. For all
these purposes the symbolic mode interface offers substantially more
facilities than the algebraic one.
\medskip

For a detailed description of special symbolic mode procedures one
should consult the source text and the comments therein. In this
manual we can give only a brief description of the main ideas
incorporated into the package CALI. We concentrate on the data
structure design and the description of the more advanced algorithms.
For sample computations from several fields of commutative algebra
the reader may consult also the {\em cali.tst} file.
\medskip

As main topics CALI contains facilities for
\begin{itemize}
\item defining rings, ideals and modules,

\item computing \gr bases and local standard bases,

\item computing syzygies, resolutions and (graded) Betti numbers,

\item computing Hilbert series, multiplicities, independent sets,
dimensions.

\item computing normal forms and representations,

\item computing sums, products, intersections, quotients, elimination
ideals etc.

\item primality tests, radicals, unmixed parts, primary decompositions 
etc. of ideals and modules. 

\item scripts for advanced applications of \gr bases (blowup,
associated graded ring, analytic spread, symmetric algebra, 
monomial curves etc.)
\end{itemize}

Below we will use freely without further explanation the notions
common for text books and papers about constructive commutative
algebra, assuming the reader to be familiar with the corresponding
ideas and concepts. For further references see e.g. the text books
\cite{BKW} and \cite{CLO} or the survey papers \cite{B1}, \cite{B2},
\cite{Ro}. 

\subsection{Description of the Documents Distributed with CALI}

The CALI package contains the following files~:
\begin{quote}
cali.chg

\pbx{a detailed report of changes from v. 2.0 to v. 2.1.}

cali.log

\pbx{the output file, that cali.tst should produce with
\begin{quote} \tt
load\_package cali;

out "logfile"\$

in "cali.tst";

shut "logfile"\$
\end{quote}}

cali.red

\pbx{the CALI source file. It should be compiled (see below) in the
usual way and added to the REDUCE fast load file system or be
accessible in the current path.}

cali.tex

\pbx{this manual.}

cali.tst

\pbx{a test file with various examples and applications of CALI.}

\end{quote}

CALI should be precompiled as usual, i.e. either using the {\em
makefasl} utility of REDUCE or ``by hand'' via
\begin{verbatim}
    faslout "cali"$
    in "cali.red"$
    faslend$
\end{verbatim}
and then loaded via
\begin{verbatim}
    load_package cali;
\end{verbatim}
Upon successful loading CALI responses with a message containing the
version number and the last update of the distribution. 

There may be some trouble on smaller machines to compile CALI in the
described way since it goes beyond the 100k limit for source code
recommended by the REDUCE system's administration. In this case one
can try to load the compiler previously and to extend the BPS space~:
\begin{verbatim}
    load compiler;
    lisp set!-bps!-size 1000000;
    faslout "cali"$
    in "cali.red"$
    faslend$
\end{verbatim}
\begin{center}
\fbox{\parbox{12cm}{Feel free to contact me by email if You have
problems to get CALI started. Also comments, hints, bug reports etc.
are welcome.}}
\end{center}

\subsection{CALI's Language Concept}

From a certain point of view one of the major disadvantage of the
current RLISP (and the underlying PSL) language is the fact
that it supports modularity and data encapsulation only in a
rudimentary way.  Since all parts of code loaded into a session are
visible all the time name conflicts between different packages may
occur, will occur (even not issuing a warning message), and are hard
to prevent, since packages are developped (and are still developping)
by different research groups at different places and different time.

A (yet rudimentary) concept of REDUCE packages and modules indicates the
direction into what the REDUCE designers are looking for a solution
for this general problem.
\medskip

CALI (2.0 and higher) follows a name concept for internal procedures
to mimick data encapsulation at a syntactical level. We hope this way
on the one hand to resolve the conflicts described above at least for
the internal part of CALI and on the other hand to anticipate a
desirable future and already foregoing development of REDUCE towards
a true modularity.

The package CALI is divided into several modules, each of them
introducing either a single new data type together with basic
facilities, constructors, and selectors or a collection of algorithms
subject to a common problem. Each module contains \ind{internal
procedures}, conceptually hidden by this module, \ind{local
procedures}, designed for a CALI wide usage, and \ind{global
procedures}, exported by CALI into the general (algebraic or
symbolic) environment of REDUCE. A header module \ind{cali} contains
all (fluid) global variables and switches defined by the pacakge
CALI.

Along these lines the CALI procedures available in symbolic mode are
divided into three types with the following naming convention~:
\begin{quote}
\verb|module!=procedure| 

\pbx{internal to the given module.}

\verb|module_procedure| 

\pbx{exported by the given module into the local CALI environment.} 

\verb|procedure!*| 

\pbx{a global procedure usually having a semantically equivalent
procedure (possibly with another parameter list) without trailing
asterisk in algebraic mode.}
\end{quote}

\subsection{New and Improved Facilities in V. 2.1}

The major changes in v. 2.1. reflect the experience we've got from the
use of CALI 2.0. The following changes are worth mentioning
explicitely~:
\begin{enumerate}
\item The \ind{ecart} handled globally in v. 2.0. now became local to
each base ring.

\item The algebraic rule concept was adapted to CALI. It allows to
supply rule based coefficient domains. This is a more efficient way
to deal with (easy) algebraic numbers than through the {\em arnum
package}.

\item The \gr factorization algorithm was seriously improved.

\item The local standard basis part was improved~:
        \begin{enumerate}
        
        \item Base elements without reductum are handled separately
        to do full (and not only lead term) reduction with respect to
        them.
        
        \item Switches \ind{detectunits} and \ind{factorunits} allow
        to remove polynomial unit factors in an early stage of the
        computation.

        \item \ind{lazy} now switches between Mora's (lazy) and
        Lazard's approaches rather than between the lazy and the
        global versions of Mora's approach.
        \end{enumerate}

\item \ind{listtest} and \ind{listminimize} provide an unified
concept for different list operations previously scattered in the
source text.

\item There are several new quotient algorithms at the symbolic level
(both the general element and the intersection approaches are
available) and new features for the computation of equidimensional
hull and equidimensional radical.

\item A new module \ind{scripts} offers advanced applications of \gr
bases.

\item Several advanced procedures initialize a \gr basis computation
over a certain intermediate base ring or term order as e.g.
\ind{eliminate}, \ind{resolve}, \ind{matintersect} or all
\ind{primary decomposition} procedures. Interrupting a computation in
v. 2.1. now the original values of CALI's global variables should be
restored, since all intermediate procedures work with local copies of
the global variables only.\footnote{Note that not all REDUCE versions
support this environment recovering. Moreover recovering the base
ring this way may cause some trouble since the intermediate ring,
installed with \ind{setring}, changed possibly the internal variable
order set by {\em setkorder}.} This doesn't apply to advanced
procedures that change the current base ring as e.g. \ind{blowup},
\ind{preimage}, \ind{sym} etc.

\end{enumerate}

\section{The Computational Model}

This section gives a short introduction into the data type design of
CALI at different levels. First (\S 1 and 2) we describe CALI's way
of algorithmic translation of the abstract algebraic objects {\em
ring of polynomials, ideal} and (finitely generated) {\em module}.
Then (\S 3 and 4) we describe the algebraic mode interface of CALI
and the switches and global variables to drive a session. Finally (\S
5) we give a more detailed overview of the basic (symbolic mode) data
structures involved with CALI. We refer to the appendix for a short
summary of the commands available in algebraic mode.

\subsection{The Base Ring}

A polynomial ring consists in CALI of the following data~:
\begin{quote}
a list of variable names 

\pbx{All variables not occuring in the list of ring names are treated
as parameters. Computations are executed denominatorfree, but the
results are valid only over the corresponding parameter {\em field}
extension.}

a term order and a term order tag

\pbx{They describe the way in which the terms in each polynomial (and
polynomial vector) are ordered.}

an ecart vector

\pbx{A list of positive integers corresponding to the variable
names.}
\end{quote}

A \ind{base ring} may be defined (in algebraic mode) through the
command \newline
\verb| setring ring | with ring ::= \{vars,tord,tag[,ecart]\} resp.
\begin{verbatim}
 setring(vars, tord, tag [,ecart])
\end{verbatim}
\index{setring}
This sets the global (symbolic) variable \ind{cali!=basering}. Here
{\tt vars} is the list of variable names, {\tt tord} a (possibly
empty) list of weight lists, the \ind{degree vectors}, and {\tt tag}
the tag LEX or REVLEX. Optionally one can supply {\tt ecart}, a list 
of positive integers of the same length as {\tt vars}, to set an ecart
vector different from the default one (see below).

The degree vectors must have the same length as {\tt vars}. If $(w_1\
\ldots\ w_k)$ is the list of degree vectors then 
\[x^a<x^b \qquad :\Leftrightarrow \qquad 
\parbox[t]{8cm}{either\hfill 
\parbox[t]{6cm}{$w_j(x^a)=w_j(x^b)$\hfill for $j<i$ \hfill and \\[8pt]
$w_i(x^a)<w_i(x^b)$} \\[10pt] or\hfill 
\parbox[t]{6cm}{$w_j(x^a)=w_j(x^b)$\hfill for all $j$ \hfill and \\[8pt]
$x^a<_{lex}x^b$ resp. $x^a<_{revlex}x^b$}}
\]
Here $<_{lex}$ resp. $<_{revlex}$ denote the
\ind{lexicographic} (tag=LEX) resp. \ind{reverse lexicographic}
(tag=REVLEX) term orders with respect to the variable order given in
{\tt vars}, i.e. 
\[x^a<x^b \qquad :\Leftrightarrow \qquad 
\parbox[t]{7cm}{\centering 
$\exists\ j\ \forall\ i<j\ :\ a_i=b_i$\hfill \\[8pt] and\\[8pt]
$a_j<b_j$\ (lex.)\hfill or\hfill $a_j>b_j$\ (rev.-lex.)\\}
\]
Every term order can be represented in such a way, see \cite{MR88}.

During the ring setting the term order will be checked to be
noetherian (i.e. to fulfill the descending chain condition) provided
the switch \ind{noetherian} is on (the default). The same applies
turning {\em noetherian on}~: If the term order of the underlying
base ring isn't noetherian the switch can't be turned over. Hence,
starting from a non noetherian term order, one should define {\em
first} a new ring and {\em then} turn the switch on. 

Useful term orders can be defined by the procedures
\begin{quote}
\verb|degreeorder vars|, \index{degreeorder}

\pbx{that returns $tord=\{\{1,\ldots ,1\}\}$,}

\verb|localorder vars|, \index{localorder}

\pbx{that returns $tord=\{\{-1,\ldots ,-1\}\}$ (a non noetherian term
order for computations in local rings) or}

\verb|eliminationorder(vars,elimvars)|, \index{eliminationorder}

\pbx{that returns a term order for elimination of the variables in
{\tt elimvars}, a subset of all {\tt vars}. It's recommended to
combine it with the tag REVLEX.}
\end{quote}

\noindent Examples :
\begin{verbatim}
vars:={x,y,z};
tord:=degreeorder vars;   % Returns {{1,1,1}}
setring(vars,tord,lex);   % GRADLEX in the groebner package.

% or

setring({a,b,c,d},{},lex); % LEX in the groebner package.

% or

vars:={a,b,c,x,y,z};
tord:=eliminationorder(vars,{x,y,z}) 
                          % Returns {{0,0,0,1,1,1},{1,1,1,0,0,0}}
setring(vars,tord,revlex);                          
\end{verbatim}
\pagebreak[2]

The base ring is initialized with \newline
\verb|{{t,x,y,z},{{1,1,1,1}},revlex,{1,1,1,1}}|,\newline 
i.e. $S=k[t,x,y,z]$ supplied with the degreewise reverse
lexicographic term order.
\medskip

\noindent\verb|getring m|\index{getring} returns the ring attached to
the object with the identifier {\tt m}. E.g.
\begin{verbatim}
setring getring m;
\end{verbatim}
(re)sets the base ring to the base ring of the formerly defined
object (ideal or module)~{\tt m}.
\begin{verbatim}
getring();
\end{verbatim}
returns the currently active base ring.

CALI defines also an \ind{ecart vector}, attaching to each variable a
positive weight with respect to that homogenizations and related
algorithms are executed. It may be set optionally by the user during
the \ind{setring} command.  (Default~: If the term order is a
(positive) degree order then the ecart is the first degree vector,
otherwise each ecart equals 1).

The ecart vector is used in several places for efficiency reason (\gr
basis computation with the sugar strategy) or for termination (local
standard bases). If the input is homogeneous the ecart vector should
reflect this homogeneity rather than the first degree vector to
obtain the best possible performance. For a discussion of local
computations with encoupled ecart vector see \cite{Gr23}. In general
the ecart vector is recommended to be chosen in such a way that the
input examples become close to be homogeneous. \ind{Homogenizations}
and \ind{Hilbert series} are computed with respect to this ecart
vector.
\medskip

\noindent \verb|getecart()|\index{getecart} returns the ecart vector
currently set.


\subsection{Ideals and Modules}

If $S=k[x_v,\ v \in H]$ is a polynomial ring, a matrix $M$ of size
$r\times c$ defines a map
\[f\ :\ S^r \longrightarrow S^c\]
by the following rule
\[ f(v):=v\cdot M \qquad \mbox{ for } v \in S^r.\]
There are two modules, connected with such a map, $im\ f$, the
submodule of $S^c$ generated by the rows of $M$, and $coker\ f\
(=S^c/im\ f)$. Conceptually we will identify $M$ with $im\ f$ for the
basic algebra, and with $coker\ f$ for more advanced topics of
commutative algebra (Hilbert series, dimension, resolution etc.)
following widely accepted conventions.

With respect to a fixed basis $\{e_1,\ldots ,e_c\}$ one can define
module term orders on $S^c$, \gr bases of submodules of $S^c$ etc.
They generalize the corresponding notions for ideal bases. See
\cite{E} or \cite{MM} for a detailed introduction to this area of
computational commutative algebra. This allows to define joint
facilities for both ideals and submodules of free modules. Moreover
computing syzygies the latter come in in a natural way.

CALI handles ideal and module bases in a unique way representing them
as rows of a \ind{dpmat} ({\bf d}istributive {\bf p}olynomial {\bf
mat}rix). It attaches to each unit vector $e_i$ a monomial $x^{a_i}$,
the $i$-th \ind{column degree} and represents the rows of a dpmat $M$
as lists of module terms $x^ae_i$, sorted with respect to the
following \ind{module term order}
\bigskip

\begin{tabular}{cccp{6cm}}
$x^ae_i<x^be_j$ & $:\Leftrightarrow$ & either &
{\centering $x^ax^{a_i}<x^bx^{a_j}$ in $S$\\}\\ 
& & or &
{\centering $x^ax^{a_i}=x^bx^{a_j}$ \\ and \\
$i<j$ (lex.) resp. $i>j$ (revlex.)\\}
\end{tabular}

Every dpmat $M$ has its own column degrees (no default !).  They are
managed through a global (symbolic) variable \ind{cali!=degrees}.
\begin{quote}
\verb|getdegrees m| \index{getdegrees}

\pbx{returns the column degrees of the object with identifier m.}

\verb|getdegrees()| 

\pbx{returns the current setting of {\em cali!=degrees}.}

\verb|setdegrees <list of monomials>| \index{setdegrees} 

\pbx{sets {\em cali!=degrees} correspondingly. Use this command
before executing {\em setmodule} to give a dpmat prescribed column
degrees since cali!=degrees has no default value and changes during
computations. A good guess is to supply the empty list (i.e. all
column degrees are equal to $\x^0$). Be careful defining modules
without prescribed column degrees.}
\end{quote}

To distinguish between \ind{ideals} and \ind{modules} the former are
represented as a \ind{dpmat} with $c=0$ (and hence without column
degrees).  If $I \subset S$ is such an ideal one has to distinguish
between the ideal $I$ (with $c=0$, allowing special ideal operations
as e.g. ideal multiplication) and the submodule $I$ of the free
onedimensional module $S^1$ (with $c=1$, allowing matrix operations
as e.g.  transposition, matrix multiplication etc.). \ind{ideal2mat}
converts an (algebraic) list of polynomials into an (algebraic)
matrix column whereas \ind{flatten} collects all matrix entries into
a list.

\subsection{The Algebraic Mode Interface}

Corresponding to CALI's general philosophy explained in the
introduction the algebraic mode interface translates algebraic input
into CALI's internal data representation, calls the corresponding
symbolic functions, and retranslates the result back into algebraic
mode. Since \gr basis computations may be very tedious even on small
examples, one should find a well balance between the storage of
results computed earlier and the unavoidable time overhead and memory
request associated with the management of these results.

Therefore CALI distinguishes between {\em free} and {\em bounded}
\index{free identifier}\index{bounded identifier} identifiers. Free
identifiers stand only for their value whereas to bounded identifiers
several internal information is attached to their property list for
later use.
\medskip

After the initialization of the {\em base ring} bounded identifiers
for ideals or modules should be declared via
\begin{verbatim}
setmodule(name,matrix value)
\end{verbatim}
resp.
\begin{verbatim}
setideal(name,list of polynomials)
\end{verbatim}
\index{setmodule}\index{setideal} 
This way the corresponding internal representation (as \ind{dpmat})
is attached to {\tt name} as the property \ind{basis}, the prefix
form as its value and the current base ring as the property
\ind{ring}.

Performing any algebraic operation on objects defined this way their
ring will be compared with the current base ring (including the term
order). If they are different an error message occurs. If {\tt m} is
a valid name, after resetting the base ring
\begin{verbatim}
setmodule(m1,m)
\end{verbatim}
reevaluates {\tt m} with respect to the new base ring (since the
{\em value} of {\tt m} is its prefix form) and assigns the reordered
dpmat to {\tt m1} clearing all information previously computed for
{\tt m1} ({\tt m1} and {\tt m} may coincide).

All computations are performed with respect to the ring $S=k[x_v\in
{\tt vars}]$ over the field $k$. Nevertheless by efficiency reasons
\ind{base coefficients} are represented in a denominatorfree way as
standard forms. Hence the computational properties of the base
coefficient domain depend on the \ind{dmode} and also on auxiliary
variables, contained in the expressions, but not in the variable
list. They are assumed to be parameters. 

Best performance will be obtained with integer or modular domain
modes, but one can also try \ind{algebraic numbers} as coefficients
as e.g. generated by {\tt sqrt} or the {\tt arnum} package. To avoid
an unnecessary slow-down connected with the management of simplified
algebraic expressions there is a switch \ind{hardzerotest} (default~:
off) that may be turned on to force an additional simplification of
algebraic coefficients during each zero test. It should be turned on
only for domain modes without canonical representations as e.g.
mixtures of arnums and square roots. We remind the general zero
decision problem for such domains. 

Alternatively, CALI offers the possibility to define a set of
algebraic substitution rules that will affect CALI's base coefficient
arithmetic only. 
\begin{quote}
\verb|setrules <rule list>|\index{setrules}

\pbx{transfers the (algebraic) rule list into the internal
representation stored at the global variable \ind{cali!=rules}.

In particular, {\tt setrules \{\}} clears the rules previously set.} 

\verb|getrules()|\index{getrules}

\pbx{returns the internal CALI rules list in algebraic form.}
\end{quote}

We recommend to use \ind{setrules} for computations with algebraic 
numbers since they are better adapted to the data structure of CALI 
than the algebraic numbers provided by the REDUCE's arnum package. 
Note, that due to the zero decision problem
complicated {\em setrules} based computations may produce wrong
results if base coefficient's pseudodivision is involved (as e.g.
with \ind{dp\_pseudodivmod}). In this case we recommend to enlarge
the variable set and add the defining equations of the algebraic
numbers to the equations of the problem.
\medskip

The standard domain (Integer) doesn't allow denominators for input.
\ind{setideal} clears automatically the common denominator of each
input expression whereas a polynomial matrix with true rational
coefficients will be rejected by \ind{setmodule}.
\medskip

One can save/initialize ideal and module bases together with their
accompanying data (base ring, degrees) to/from a file~:
\begin{verbatim}
savemat(m,name)
\end{verbatim}
resp.
\begin{verbatim}
initmat name
\end{verbatim} execute the file transfer from/to disk files with the
specified file {\tt name}. E.g.
\begin{verbatim}
savemat(m,"myfile");
\end{verbatim}
saves the base ring and the ideal basis of $m$ to the file ``myfile''
whereas
\begin{verbatim}
setideal(m,initmat "myfile");
\end{verbatim}
sets the current base ring (via a call to \ind{setring}) to the base
ring of $m$ saved at ``myfile'' and then recovers the basis of $m$
from the same file.

\subsection{Switches and Global Variables}

There are several switches, (fluid) global variables, and a trace
facility to control CALI's computations.
\medskip

\subsubsection*{Switches}

\begin{quote}
\ind{bcsimp}

\pbx{on : Cancel out gcd's of base coefficients. (Default : on)}

\ind{binomial}

\pbx{on : cause the system to do multireductions on ideals defined by
binomials. Not applicable to syzygy and relations computation.
(Default : off)}

\ind{detectunits}

\pbx{on : replace polynomials of the form \newline 
$\langle monomial\rangle * 
\langle polynomial\ unit\rangle $ by $\langle monomial\rangle$ 
during interreductions and standard basis computations.

Affects only local computations. (Default : off)}

\ind{factorunits}

\pbx{on : factor polynomials and remove polynomial unit factors
during interreductions and standard basis computations.

Affects only local computations. (Default : off)}

\ind{hardzerotest}

\pbx{on : try an additional algebraic simplification of base
coefficients at each base coefficient's zero test. Useful only for
advanced base coefficient domains without canonical REDUCE
representation. May slow down the computation drastically.
(Default~: off)}

\ind{lazy}

\pbx{on : choose Mora's lazy standard basis algorithm.

off : choose Lazard's standard basis approach (homogenizing base
elements).

Affects only local computations. (Default : on)}

\ind{noetherian}

\pbx{on : choose algorithms for noetherian term orders.

off : choose algorithms for local term orders. 

(Default : on)}

\ind{red\_total}

\pbx{on : apply normal form algorithms iteratively also to the
reductum.

off : reduce only until leading terms are standard. 

Affects only noetherian term orders. (Default : on)}

\end{quote}

\subsubsection*{Tracing}

Intermediate output during the computations is controlled by the
global (symbolic) variable \ind{cali!=trace} (Default : 0, no
tracing).
\begin{verbatim}
lisp (cali!=trace:=..);
\end{verbatim}
changes the current value. Set it equal to 2 for a sparce tracing (a dot for
each reduction step).
Other good suggestions are the values 30 or 40 for tracing the \gr
algorithm or $>70$ for tracing the normal form algorithm. The higher
\ind{cali!=trace} the more intermediate information will be given.

\subsubsection*{Global Variables}

\begin{quote}
\ind{cali!=basering}

\pbx{The currently active base ring initialized e.g. by
\ind{setring}.}

\ind{cali!=degrees}

\pbx{The currently active module component degrees initialized e.g.
by \ind{setdegrees}.}

\ind{cali!=monset}

\pbx{A list of variable names considered as non zero divisors during
\gr basis computations initialized e.g. by \ind{setmonset}. Useful
e.g. for binomial ideals defining monomial varieties or other prime
ideals.}

\ind{cali!=rules}

\pbx{Algebraic ``replaceby'' rules introduced to CALI with the
\ind{setrules} command.}

\ind{cali!=trace}

\pbx{A symbolic variable managing the output of intermediate
information to the screen.}

\end{quote}

\subsection{The Basic Data Structures}

In the following we describe the most important (symbolic) data
structure layers underlying the dpmat representation in CALI.

\subsubsection*{Base Coefficients}

Base coefficients are standard forms in the variables outside the
variable list of the current ring. Although standard forms form an
integral domain, all computations are executed "denominatorfree" over
the corresponding quotient field, i.e. gcd's are canceled out without
request. To avoid this set the switch \ind{bcsimp} off.\footnote{This
induces a rapid base coefficient's growth and doesn't yield {\bf
Z}-\gr bases in the sense of \cite{GTZ} since the S-pair criteria are
different.}

The base coefficient domain is assumed to be a gcd-domain with
effective divisibility test. In the given implementation we use the
s.f. procedure {\em qremf}. We had some trouble with it under {\em on
factor}.

CALI v. 2.1. offers additionally the possibility to supply the
parameters occuring as base coefficients with a (global) set of
algebraic rules.\footnote{This is different from the LET rule
mechanism since they must be present in symbolic mode. Hence for a
simultaneous application of the same rules in algebraic mode outside
CALI they must additionally be declared in the usual way.}
\ind{setrules} converts an algebraic mode rules list as e.g. used in
WHERE statements into the internal CALI format.

\subsubsection*{Base Ring}

The \ind{base ring} is defined by its {\tt name list}, the {\tt
degree matrix} (a list of lists of integers), the {\tt ring tag} (LEX
or REVLEX), and the {\tt ecart}. The name list contains a phantom
name {\tt cali!=mk} for the module component at place 0.
\medskip

The module {\bf ring} exports among others the following procedures
to define a base ring~:
\begin{quote}
\verb|ring_define(name list, degree matrix, ring tag, ecart)|
\index{ring\_define}

\pbx{combines the given parameters to a ring.}

\verb|ring_sum(a,b)|\index{ring\_sum}

\pbx{returns a ring, that is constructed in the following way : Its
variable list is the union of the (disjoint) lists of the variables
of the rings $a$ and $b$ (in this order) whereas the degree list is
the union of the (appropriately shifted) degree lists of $b$ and $a$
(in this order). The ring tag is that of $a$. Hence it returns
(essentially) the ring $b\bigoplus a$ if $b$ has a degree part (e.g.
useful for elimination problems, introducing ``big'' new variables) 
and the ring $a\bigoplus b$ if $b$ has no degree part (introducing 
``small'' new variables).}

\verb|setring!* <ring> |\index{setring}

\pbx{sets {\em cali!=basering} and {\em cali!=ecart} and checks for
consistency with the switch \ind{noetherian}. It also sets through
\ind{setkorder} the current variable list as main variables. It is
strongly recommended to use {\em setring!* \ldots} instead of {\em
cali!=basering:=\ldots}.}
\end{quote}
\verb|degreeorder!*| , \verb|localorder!*| and  \verb|eliminationorder!*|
\index{degreeorder} 
\index{localorder} 
\index{eliminationorder} 
define term order matrices in full analogy to algebraic mode.
\medskip

\noindent Example :
\begin{verbatim}
vars:='(x y z)
setring!* ring_define(vars,degreeorder!* vars,'lex,'(1 1 1));   
                        % GRADLEX in the groebner package.
\end{verbatim}

\subsubsection*{Monomials}

The current version uses a place-driven exponent representation
closely related to a vector model. This model handles term orders and
module term orders in a unique way. The zero component of the
exponent list of a monomial contains its module component ($>0$) or 0
(ring element). All computations are executed with respect to a
\ind{current ring} (\ind{cali!=basering}) and a \ind{current module}
(\ind{cali!=degrees}). For efficiency reasons every monomial has a
precomputed degree part that should be reevaluated if {\tt
cali!=basering} (i.e. the term order) or {\tt cali!=degrees} were
changed. {\tt cali!=degrees} contains the list of column degrees of
the current module and will be set automatically by (almost) all
dpmat procedure calls. Since monomial operations use the degree list
that was precomputed with respect to fixed column degrees (and base ring)
\begin{quote}\bf
watch carefully for {\tt cali!=degrees} programming at the monomial 
or dpoly level !
\end{quote}

\subsubsection*{Polynomials and Polynomial Vectors}

CALI uses a distributive representation as a list of terms for both
polynomials and polynomial vectors, where a \ind{term} is a dotted
pair
\[(monomial\ .\ base\ coefficient).\] 
The \ind{ecart} of a polynomial (vector) $f=\sum{t_i}$ with (module)
terms $t_i$ is defined as \[max(ec(t_i))-ec(lt(t_i)),\] see
\cite{Gr23}. Here $ec(t_i)$ denotes the ecart of the term $t_i$.

\subsubsection*{Ideal Bases}

Ideal bases are one of the main ingredients for dpmats. They are
represented as lists of \ind{base elements} and contain together with
each dpoly entry the following information~:
\begin{itemize}
\item a number (the row number of the polynomial vector in the
corresponding dpmat).

\item the dpoly, its ecart (as the main sort criterion), and length. 

\item a representation part, that may contain a representation of the
given dpoly in terms of a certain fixed basis (default : empty).
\end{itemize}

The representation part is managed during normal form computations
and other row arithmetic of dpmats appropriately.
\begin{quote}
\verb|bas_setrelations b|\index{bas\_setrelations} 

\pbx{sets the relation part of the base element $i$ in the base list
$b$ to $e_i$.}

\verb|bas_removerelations b|\index{bas\_removerelations} 

\pbx{removes all relations, i.e. replaces them with the zero
polynomial vector.}

\verb|bas_getrelations b|\index{bas\_getrelations} 

\pbx{gets the relation part of $b$ as a separate base list.}
\end{quote}


\subsubsection*{Ideals, Matrices, and Matrix Operations}

Ideals and matrices, represented as \ind{dpmat}s, are the central
data type of the CALI package, as already explained above. Every
dpmat $m$ combines the following information~:
\begin{itemize}
\item its size (\ind{dpmat\_rows} m,\ind{dpmat\_cols} m),

\item its base list (\ind{dpmat\_list} m) and

\item its column degrees as an assoc. list of monomials
(\ind{dpmat\_coldegs} m). If this list is empty, all degrees are
assumed to be equal to $x^0$.
\end{itemize}

The module {\bf dpmat} contains the algorithms for the basic
management of this data structure whereas the modules {\bf matop} and
{\bf quot} collect procedures for the algebraic management of dpmats
with analogous semantics as their algebraic mode counterparts as e.g.
\begin{center}
\parbox{14cm}
{\ind{annihilator1!*}, \ind{idealpower!*}, \ind{matqquot!*},
\ind{matquot!*}, \ind{modequalp!*}, \ind{modulequotient1!*},
\ind{submodulep!*}.}
\end{center}
The following procedures take a list of dpmats as their (single)
argument~: 
\begin{center}
\parbox{14cm}
{\ind{directsum!*}, \ind{idealprod!*}, \ind{matappend!*},
\ind{matsum!*}, \ind{matintersect!*}.}
\end{center}


\section{About the Algorithms Implemented in CALI}

Below we give a short explanation of the main algorithmic ideas of
CALI and the way they are implemented (symbolically).

\subsection{Normal Form Algorithms}

Normal form algorithms reduce polynomials (or polynomial vectors)
with respect to a given finite set of generators of an ideal or
module. The result is not unique except for a total normal form with
respect to a \gr basis. Furthermore different reduction strategies
may yield significant differences in computing time.

CALI reduces by first matching, usually keeping base lists sorted
with respect to the sort predicate \ind{red\_better}, sorting at
first by ascending ecart and then by ascending length. This order is
good for both noetherian and non noetherian term orders.

Overload red\_better for other reduction strategies.
\medskip

There are different reduction procedures for noetherian and non
noetherian term orders according to the general theory. For a given
ideal basis $B\subset S$ and a polynomial $f\in S$ they produce a
(pseudo) normal form $h\in S$ such that $h\equiv u\cdot f\ mod\ B$
where $u\in S$ is a polynomial unit, i.e. a (polynomially
represented) non zero domain element in the noetherian case
(pseudodivision of $f$ by $B$) or a polynomial with a scalar as
leading term in the non noetherian case. 

Advanced applications of normal form algorithms and \gr /standard
bases may be build up from these different sources in an unified
manner, \cite{Gr23} and \cite{ala}. This is reflected through the
switch \ind{noetherian}.  Turning it on (the default) or off causes
CALI to refer automatically to the \gr or local standard basis
methods (defined in the modules {\bf red} and {\bf mora} resp.).
This applies to the interfacing procedures \ind{interreduce!*},
\ind{gbasis!*}, \ind{syzygies!*}, \ind{normalform!*} and \ind{mod!*}
and to more advanced applications derived from them. They branch
according to it either to the global or the local normal form
procedures \ind{red\_interreduce}, \ind{mora\_interreduce} etc.

\begin{quote}
\verb|interreduce!* m|\index{interreduce}

\pbx{returns an interreduced basis of the dpmat $m$, i.e. the leading
terms of the result are not divisible by each other.}

\verb|mod!*(f,m)|\index{mod}

\pbx{returns the pair $(h.u)$ where $h$ is the pseudo normal form of
the dpoly $f$ modulo the dpmat $m$ and $u$ the corresponding
polynomial unit multiplier.}

\verb|normalform!*(a,b)|\index{normalform}

\pbx{Returns $\{a_1,r,z\}$ with $a_1=z*a-r*b$ where the rows of the
dpmat $a_1$ are the normalforms of the rows of the dpmat $a$ with
respect to the dpmat $b$.}

\end{quote}

For local standard bases the ideal generated by the basic polynomials
may have components not passing through the origin. Although they do
not contribute to the ideal in $Loc(S)=S_{\bf m}$ they usually 
heavily increase the computational effort needed for the standard basis 
computation, interreduction etc.. Hence for local
term orders one should try to remove polynomial units as soon as they
are detected. To remove them in an early stage of the computations
one can either try the (cheap) test, whether $f\in S$ is of the form
$\langle monomial\rangle *\langle polynomial\ unit\rangle$ (switch
\ind{detectunits}, def.: off) or factor $f$ completely and remove
polynomial unit factors (switch \ind{factorunits}, def.: off).

The procedure \ind{deleteunits!*} tries to factor basis polynomials
and removes polynomial units occuring as one of the factors.

\subsection{The Standard Basis Algorithms}

The modules {\bf groeb} and {\bf mora} contain the \gr resp. standard
basis algorithms with syzygy computation facility and related
algorithms.  

As described above there are common procedures
\begin{quote}
\verb|gbasis!* m|\index{gbasis}

\pbx{that returns a minimal \gr or standard basis of the dpmat $m$,}

\verb|syzygies!* m|\index{syzygies}

\pbx{that returns an interreduced basis of the first syzygy module of
the dpmat $m$ and}

\verb|syzygies1!* m|\index{syzygies1}

\pbx{that returns a (not yet interreduced) basis of the syzygy module
of the dpmat $m$.}
\end{quote}

These procedures start the general \gr resp. standard basis
calculation
\begin{verbatim}
groeb_stbasis(m,t,t,t,cali!=monset);

or

mora_stbasis(m,t,t,t,cali!=monset);
\end{verbatim}\index{groeb\_stbasis}\index{mora\_stbasis}
that returns, applied to the dpmat $m$, three dpmats $g,c,s$ with
\begin{quote}
$g$ --- the minimal reduced \gr basis of $m$,

$c$ --- the transition matrix $g=c\cdot m$, and

$s$ --- the (not yet interreduced) syzygy matrix of $m$.
\end{quote}

The pair list management uses the sugar strategy, see \cite{GMNRT},
with respect to the ecart vector \ind{cali!=ecart}. If the input is
homogeneous and \ind{cali!=ecart} reflects this homogeneity then
pairs are sorted by ascending degree. Hence no superfluous base
elements will be computed in this case. In general the sugar strategy
performs best if the ecart vector is chosen to make the input close
to be homogeneous.

If requested, the change matrix or the syzygy matrix will be computed
through the representation part of the involved base elements. For
this purpose it will be set appropriately at the beginning of {\em
\ldots\_stbasis} to trace up the reduction steps of the algorithm. At
the end these results are split up and relations are removed.

There is another global variable \ind{cali!=monset} that may contain
a list of variable names (a subset of the variable names of the
current base ring). During the "pure" \gr algorithm (without syzygy
and representation computations) common monomial factors, containing
only these variables will be canceled out. This shortcut is useful if
some of the variables are known to be non zero divisors as e.g. in
most implicitation problems.
\begin{quote}
\verb|setmonset!* m|\index{setmonset}

\pbx{initializes {\em cali!=monset} with a given list of variables
$m$.} 
\end{quote}

Local standard bases can essentially be computed in two different
ways. The switch \ind{lazy} drives CALI to branch into Mora's (on,
the default) or Lazard's (off) approach, respectively. There are
several versions of Mora's normal form algorithm published in
\cite{MPT}.  {\em lazy} refers to the lazy version as the most
effective one, but without the early termination test, since this
test is available only for zerodimensional ideals.

Experts commonly agree that Mora's approach is better for
``computable'' examples, but sample computations done by the author
on large examples indicate, that both approaches are in fact
independent. The speedup of the latter seems to depend mainly on the
fact that in Lazard's approach {\em total} normal forms are available
during intermediate computations.
\medskip

Beginning with version 2.0 CALI contains also its own \gr
factorization facility~: 
\begin{quote}
\verb|groebfactor!*(m,c)|\index{groebfactor}\footnote{{\em
groebfactorize} in v.  2.0., but this collides with the REDUCE
groebner package}.

\pbx{Returns for the dpmat ideal $m$ and the constraint polynomial
$c$ a minimal list of \gr bases $G_a$ such that $V(m)\bigcap
D(c)=\bigcup_a V(G_a)\bigcap D(c)$, where $V(G)$ is the set of common
zeroes of the ideal $G$ and $D(c)$ the set of points where $c$
doesn't vanish.}
\end{quote}
During a preprocessing it splits the submitted basis $m$ by a
recursive factorization of polynomials and interreduction of bases
into a (reduced) list of smaller subproblems consisting of a partly
computed \gr basis, a constraint list, and a list of pairs not yet
proceeded. The main procedure forces the next subproblem to be
processed until another factorization is possible. Then the
subproblem splits into subsubproblems, and the subproblem list will
be updated. Subproblems are kept sorted with respect to their
expected dimension \ind{easydim} forcing this way a {\em depth first}
recursion.  Returned and not yet interreduced \gr bases are, after
interreduction, subject to another call of the preprocessor since
interreduced polynomials may factor anew.
\medskip

\subsection{Basic Algorithms in Ideal Theory}

\gr and local standard bases are the heart of several basic
algorithms in ideal theory, see e.g. \cite[6.2.]{BKW}. CALI offers
the following facilities~:
\begin{quote}
\verb|submodulep!*(m,n)|\index{submodulep}

\pbx{tests the dpmat $m$ for being a submodule of the dpmat $n$
reducing the basis elements of $m$ with respect to $n$. The result
will be correct provided $n$ is a \gr basis.}

\verb|modequalp!*(m,n)|\index{modequalp}

\pbx{ = submodulep!*(m,n) and submodulep!*(n,m).}

\verb|eliminate!*(m,<variable list>)| \index{eliminate}

\pbx{computes the elimination ideal/module eliminating the variables
in the given variable list (a subset of the variables of the current
base ring). Changes temporarily the term order to degrevlex. For {\em
monset} see \ind{cali!=monset}.}

\verb|matintersect!* l|\index{matintersect}
\footnote{This can be done for ideals and
modules in an unique way. Hence {\em idealintersect!*} has been
removed in v. 2.1.}

\pbx{computes the intersection of the dpmats in the dpmat list $l$
along \cite[6.20]{BKW}.}

\verb|dpgcd!*(a,b)| \index{dpgcd}

\pbx{computes the gcd of two dpolys $a$ and $b$ by the syzygy method~:
The syzygy module of $\{a,b\}$ is generated by a single element
$[-b_0\ \ a_0]$ with $a=ga_0, b=gb_0$, where $g$ is the gcd of $a$
and $b$. Since it uses dpoly pseudodivision it may work not properly
with \ind{setrules}.}
\end{quote}

CALI offers several quotient algorithms. They rest on the computation
of quotients by a single element of the following kind~: Assume
$M\subset S^c, v\in S^c, f\in S$. Then there are
\begin{quote}
the \ind{module quotient} $M : (v) = \{g\in S\ |\ gv\in M\}$,

the \ind{ideal quotient} $M : (f) = \{w\in S^c\ |\ fw\in M\}$, and

the \ind{stable quotient} $M : (f)^\infty = \{w\in S^c\ |\ \exists\,
n\, :\, f^nw\in M\}$.
\end{quote}
CALI uses the elimination approach \cite[4.4.]{CLO} and
\cite[6.38]{BKW} for their computation~:
\begin{quote}
\verb|matquot!*(M,f)|\index{matquot}

\pbx{returns the module or ideal quotient $M:(f)$ depending on $f$.}

\verb|matqquot!*(M,f)|\index{matqquot}

\pbx{returns the stable quotient $M:(f)^\infty$.}
\end{quote}
\ind{matquot!*} calls the pseudo division with remainder
\begin{quote}
\verb|dp_pseudodivmod(g,f)|\index{dp\_pseudodivmod}

\pbx{that returns a dpoly list $\{q,r,z\}$ such that $z\cdot g =
q\cdot f + r$ with a dpoly unit $z$.\ ($g, f$ and $r$ must belong to
the same free module). This is done uniformly for noetherian and
local term orders with an extended normal form algorithm as described
in \cite{ala}.}
\end{quote}
\medskip

In the same way one defines the quotient of a module by another
module (both embedded in a common free module $S^c$), the quotient of
a module by an ideal, and the stable quotient of a module by an
ideal. Algorithms for their computation can be obtained from the
corresponding algorithms for a single element as divisor either by
the generic element method \cite{E} or as an intersection 
\cite[6.31]{BKW}. CALI offers both approaches (\_x=1 or 2 below) at
the symbolic level, but for true quotients only the latter one is 
integrated into the algebraic mode interface.
\begin{quote}
\verb|idealquotient_x!*(M,I)|\index{idealquotient}

\pbx{returns the ideal quotient $M:I$ of the dpmat $M$ by the dpmat
ideal $I$.}

\verb|modulequotient_x!*(M,N)|\index{modulequotient}

\pbx{returns the module quotient $M:N$ of the dpmat $M$ by the dpmat
$N$.}

\verb|annihilator_x!* M|\index{annihilator}

\pbx{returns the annihilator of $coker\ M$, i.e. the module quotient
$S^c:M$, if $M$ is a submodule of $S^c$.}

\verb|matstabquot!*(M,I)|\index{matstabquot}

\pbx{returns the stable quotient $M:I^\infty$ (only by the general element
method).}
\end{quote}


\subsection{Monomial Ideals}

Monomial ideals occur as ideals of leading terms of (ideal's) \gr
bases and also as components of leading term modules of submodules of
free modules, see \cite{GrI}, and reflect some properties of the
original ideal/module. Several parameters of the original ideal may
be read off from it as e.g. dimension and Hilbert series. 

The module {\bf moid} contains the corresponding algorithms on
monomial ideals. Monomial ideals are lists of monomials, kept sorted
by descending lexicographic order as proposed in \cite{BS}. 

\begin{quote}
\verb|moid_primes u| \index{moid\_primes}

\pbx{returns the minimal primes (as a list of lists of variable
names) of the monomial ideal $u$ using an adaption of the algorithm,
proposed in \cite{BS} for the computation of the codimension.}

\verb|indepvarsets!* m| \index{indepvarsets} 

\pbx{returns (based on {\em moid\_primes}) the list of strongly
independent sets of $m$, see \cite{KW} and \cite{GrI} for
definitions.}

\verb|dim!* m| \index{dim}

\pbx{returns the dimension of $coker\ m$ as the size of the largest
independent set.\footnotemark}
\footnotetext{The problem of the determination of the
dimension of an arbitrary monomial ideal is NP-hard in the number of
variables, \cite{BS}.}

\verb|codim!* m| \index{codim}

\pbx{returns the codimension of $coker\ m$.}

\verb|easyindepset!* m| \index{easyindepset}

\pbx{returns a maximal with respect to inclusion independent set of
$m$.}

\verb|easydim!* m| \index{easydim}

\pbx{is a fast dimension algorithm (based on {\em easyindepset}), that
will be correct if $m$ is (radically) unmixed. Since it is
significantly faster than the general dimension algorithm, it should
be used, if all maximal independent sets are known to be of equal
cardinality (as e.g. for prime or unmixed ideals, see \cite{GrI}).}
\end{quote}

\pagebreak[3]

Hilbert series are computed with respect to the \ind{ecart vector},
i.e. for a monomial ideal $I$ in the polynomial ring $R$
\[H(R/I,t) := \sum_{i\geq 0}{|\{x^a:ec(a)=i\}|\cdot t^i} =
\frac{Q(t)}{\prod_x{\left(1-t^{ec(x)}\right)} }.\]
$H(R/I,t)$ is known to be a rational function with pole order at
$t=1$ equal to $dim\ R/I$. 

\begin{quote}

\verb|hilb1 m   or   hilb2 m| \index{hilb1} \index{hilb2}

\pbx{returns the Hilbert series numerator $Q(t)$ using different
algorithms, see \cite{BS} for {\em hilb1} and \cite{BCRT} for {\em
hilb2}.  Experiments suggest that the former is better for few
generators of high degree whereas the latter has to be preferred for
many generators of low degree.}

\verb|hilbseries1 m   or   hilbseries2 m| \index{hilbseries1}
\index{hilbseries2}

\pbx{returns the reduced Hilbert series (i.e. with relative prime
numerator and denominator) as a standard quotient.}

\verb|degree!* m| \index{degree}

\pbx{returns the value of the numerator of the reduced Hilbert series
representation at $t=1$. For the standard ecart this is the degree of
$coker\ m$.}

\end{quote}

\subsection{Zerodimensional Ideals and Modules}

There are several algorithms that either force the reduction of a
given problem to dimension zero or work only for zerodimensional
ideals or modules.  The CALI module {\bf odim} offers such
algorithms. It contains, e.g.
\begin{quote}
\verb|dimzerop!* m| \index{dimzerop}

\pbx{that tests a dpmat $m$ for being zerodimensional.}

\verb|getkbase!* m| \index{getkbase}

\pbx{that returns a (monomial) k-vector space basis of $Coker\ m$
provided $m$ is a \gr basis.}

\verb|odim_parameter m| \index{odim\_parameter}

\pbx{that returns a parameter of the dpmat $m$, i.e. a variable $x
\in vars$ such that $k[x]\bigcap Ann\ S^c/m=(0)$, or {\em nil} if $m$
is zerodimensional.}

\verb|odim_up(a,m)| \index{odim\_up}

\pbx{that returns an univariate polynomial (of smallest possible
degree if $m$ is a gbasis) in the variable $a$ inside the
zerodimensional dpmat ideal $m$ using Buchberger's approach,
\cite{B1}.}
\end{quote}

\subsection{Primary Decomposition and Related Algorithms}

The algorithms of the module {\bf prime} implement the ideas of
\cite{GTZ} with modifications along \cite{Kr} and their natural
generalizations to modules as e.g. explained in \cite{Ru}. It
contains also algorithms for the computation of the unmixed part of a
given module and the unmixed radical of a given ideal (along the same
lines). We followed the stepwise recursion decreasing dimension in
each step by 1 as proposed in (the final version of) \cite{GTZ}
rather than the ``one step'' method described in \cite{BKW} since
handling leading coefficients, i.e. standard forms, depending on
several variables is a quite hard job for REDUCE.

In the following procedures $m$ must be a \gr basis.
\begin{quote}
\verb|zeroradical!* m| \index{zeroradical}

\pbx{returns the radical of the zerodimensional ideal $m$, using
squarefree decomposition of univariate polynomials.}

\verb|zeroprimes!* m| \index{zeroprimes}

\pbx{computes as in \cite{GTZ} the list of prime ideals of $Ann\ F/M$
if $m$ is zerodimensional, using the (sparse) general position
argument from \cite{KW}.}

\verb|zeroprimarydecomposition!* m| \index{zeroprimarydecomposition}

\pbx{computes the primary components of the zerodimensional dpmat $m$
using prime splitting with the prime ideals of $Ann\ F/M$. It returns
a list of two-element lists with first entry the primary component
and second entry the corresponding associated prime ideal.}

\verb|isprime!* m| \index{isprime}

\pbx{a (one step) primality test for ideals, extracted from
\cite{GTZ}.} 

\verb|isolatedprimes!* m| \index{isolatedprimes}

\pbx{computes (only) the isolated prime ideals of $Ann\ F/M$.}

\verb|radical!* m| \index{radical}

\pbx{computes the radical of the dpmat ideal $m$, reducing as in
\cite{GTZ} to the zerodimensional case.}

\verb|easyprimarydecomposition!* m| \index{easyprimarydecomposition}

\pbx{computes the primary components of the dpmat $m$, if it has no
embedded components. The algorithm uses prime splitting with the
isolated prime ideals of $Ann\ F/M$. It returns a list of two-element
lists as in {\em zeroprimarydecomposition!*}.}

\verb|primarydecomposition!* m| \index{zeroprimarydecomposition}

\pbx{computes the primary components of the zerodimensional dpmat $m$
using prime splitting with the prime ideals of $Ann\ F/M$. It returns
a list of two-element lists as in {\em zeroprimarydecomposition!*}.}

\verb|unmixedradical!* m| \index{unmixedradical}

\pbx{returns the unmixed radical, i.e. the intersection of the
isolated primes of top dimension, associated to the dpmat ideal $m$.}

\verb|eqhull!* m| \index{eqhull}

\pbx{returns the equidimensional hull, i.e. the intersection of the 
 top dimensional primary components of the dpmat $m$.}
\end{quote}

\subsection{Advanced Algorithms}

The module {\bf scripts} just under further development offers some
advanced topics of the \gr bases theory. It introduces the new data
structure of a \ind{map} between base rings~:
\medskip

A ring map 
\[ \phi\ :\ R\longrightarrow S\]
for $R=k[r_i], S=k[s_j]$ is represented in symbolic mode as a list
\[   \{preimage\_ring\ R,\ image\_ring\ S, subst\_list\},\]
where {\tt subst\_list} is a substitution list $\{r_1=\phi_1(s),
r_2=\phi_2(s),\ldots \}$ in algebraic prefix form, i.e. looks like
{\tt (list (equal var image) \ldots )}. 

The central tool for several applications is the computation of the
preimage $\phi^{-1}(I)\subset R$ of an ideal $I\subset S$ either
under a polynomial map $\phi$ or its closure in $R$ under a rational
map $\phi$, see \cite[7.69 and 7.71]{BKW}.
\begin{quote}
\verb|preimage!*(m,map)| \index{preimage}

\pbx{computes the preimage of the ideal $m$ in algebraic prefix form
under the given polynomial map and sets the current base ring to the
preimage ring. Returns the result also in algebraic prefix form.}

\verb|ratpreimage!*(m,map)| \index{ratpreimage}

\pbx{computes the closure of the preimage of the ideal $m$ in
algebraic prefix form under the given rational map and sets the
current base ring to the preimage ring. Returns the result also in
algebraic prefix form.}

\end{quote}

Derived applications are
\begin{quote}
\verb|affine_monomial_curve!*(l,R)|\index{affine\_monomial\_curve}

\pbx{$l$ is a list of integers, $R$ a list of variable names of the
same length as $l$. The procedure sets the current base ring and
returns the defining ideal of the affine monomial curve with generic
point $(t^i\ :\ i\in l)$ computing the corresponding preimage.}

\verb|analytic_spread!* M|\index{analytic\_spread}

\pbx{Computes the analytic spread of $M$, i.e. the dimension of the
exceptional fiber ${\cal R}(M)/m{\cal R}(M)$ of the blowup along $M$ 
over the irrelevant ideal $m$ of the current base ring.}
       
\verb|assgrad!*(M,N,vars)|\index{assgrad}

\pbx{Computes the associated graded ring \[gr_R(N):=
(R/N\oplus N/N^2\oplus\ldots)={\cal R}(N)/N{\cal R}(N)\] over the ring
$R=S/M$, where $M$ and
$N$ are dpmat ideals defined over the current base ring $S$. {\tt
vars} is a list of new variable names one for each generator of $N$.
They are used to create a second ring $T$ with degree order
corresponding to the ecart of the row degrees of $N$ and a ring map
\[\phi : S\oplus T\longrightarrow S.\]
It returns a dpmat ideal $J$ such that $(S\oplus T)/J$ is  a 
presentation of the
desired associated graded ring over the new current base ring
$S\oplus T$.}
       
\verb|blowup!*(M,N,vars)|\index{blowup}

\pbx{Computes the blow up ${\cal R}(N):=R[N\cdot t]$ of $N$ over
the ring $R=S/M$, where $M$ and $N$ are dpmat ideals defined over the
current base ring $S$. {\tt vars} is a list of new variable names one
for each generator of $N$. They are used to create a second ring $T$
with degree order corresponding to the ecart of the row degrees of
$N$ and a ring map
\[\phi : S\oplus T\longrightarrow S.\]
It returns a dpmat ideal $J$ such that $(S\oplus T)/J$ is 
a presentation of the
desired blowup ring over the new current base ring $S\oplus T$.}
       
\verb|proj_monomial_curve!*(l,R)|\index{proj\_monomial\_curve}

\pbx{$l$ is a list of integers, $R$ a list of variable names of the
same length as $l$. The procedure set the current base ring and
returns the defining ideal of the projective monomial curve with
generic point \mbox{$(s^{d-i}\cdot t^i\ :\ i\in l)$} in $R$, where 
\mbox{$d=max\{ x\, :\, x\in l\}$}, computing the corresponding preimage.}

\verb|sym!*(M,vars)|\index{sym}

\pbx{Computes the symmetric algebra $Sym(M)$ where $M$ is a dpmat ideal
defined over the current base ring $S$. {\tt vars} is a list of new
variable names one for each generator of $M$. They are used to create
a second ring $R$ with degree order corresponding to the ecart of the
row degrees of $N$ and a ring map
\[\phi : S\oplus R\longrightarrow S.\]
It returns a dpmat ideal $J$ such that $(S\oplus R)/J$ is the
desired symmetric algebra over the new current base ring $S\oplus R$.}
       
\end{quote}


There are several other applications~:
\begin{quote}
\verb|affine_points!* m| \index{affine\_points}

\pbx{$m$ is a matrix of domain elements (in algebraic prefix form)
with as many columns as the current base ring has ring variables.
Its rows represent the affine coordinates of a collection of points.
This procedure returns the intersection of the maximal ideals
corresponding to these points.}

\verb|minimal_generators!* m| \index{minimal\_generators}

\pbx{returns a set of minimal generators of the dpmat $m$ inspecting
the first syzygy module.}

\verb|proj_points!* m| \index{proj\_points}

\pbx{$m$ is a matrix of domain elements (in algebraic prefix form)
with as many columns as the current base ring has ring variables.
Its rows represent the homogeneous coordinates of a collection of
points in projective space. This procedure returns the intersection
of the maximal homogeneous ideals corresponding to these points.}

\verb|symbolic_power!*(m,d)| \index{symbolic\_power}

\pbx{returns the d'th symbolic power of the prime dpmat ideal $m$ as
the equidimensional hull of the d'th true power. (Hence applies also
to unmixed ideals.)}

\end{quote}

\pagebreak

\appendix
\section{A Short Description of Procedures Available in Algebraic
Mode} 

Here we give a short description, ordered alphabetically, of the
procedures offered by CALI in the algebraic mode interface.

If not stated explicitely procedures take (algebraic mode) polynomial
matrices ($c>0$) or polynomial lists ($c=0$) $m,m1,m2,\ldots $ as
input and return results of the same type. $gb$ stands for a bounded
identifier with precomputed \gr basis, $gbr$ for one with precomputed
resolution. For the mechanism of \ind{bounded identifiers} see the
section ``Algebraic Mode Interface''.

\subsection{Basic Algorithms}

\begin{quote}
\verb|annihilator m| \index{annihilator}

\pbx{returns the annihilator of the dpmat $m\subseteq S^c$, i.e.
$Ann\ S^c/M$.}

\verb|bettinumbers gbr| \index{bettinumbers}

\pbx{extracts the list of Betti numbers from the resolution of $gbr$.}

\verb|codim gb| \index{codim}

\pbx{returns the codimension of $S^c/gb$.}

\verb|degree gb| \index{degree}

\pbx{returns the multiplicity of $gb$ as the sum of the coefficients
of the Hilbert series numerator.}

\verb|degsfromresolution gbr| \index{degsfromresolution}

\pbx{returns the list of column degrees from the minimal resolution
of $gbr$.}

\verb|deleteunits m| \index{deleteunits}

\pbx{factors each basis element of the dpmat ideal $m$ and removes
factors that are polynomial units. Applies only for non noetherian
term orders.}

\verb|dim gb| \index{dim}

\pbx{returns the dimension of $S^c/gb$.}

\verb|dimzerop gb| \index{dimzerop}

\pbx{tests whether $S^c/gb$ is zerodimensional.}

\verb|directsum(m1,m2,...)| \index{directsum}

\pbx{returns the direct sum of the modules $m1,m2,\ldots$, embedded
into the direct sum of the corresponding free modules.}

\verb|dpgcd(f,g)| \index{dpgcd}

\pbx{returns the gcd of two polynomials $f$ and $g$, computed by the
syzygy method.}

\verb|easydim m and easyindepset m| \index{easydim}\index{easyindepset}

\pbx{ If the given ideal or module is unmixed (e.g. prime) then all
maximal strongly independent sets are of equal size and one can look
for a maximal with respect to inclusion rather than size strongly
independent set. These procedures don't test the input for being a
\gr basis or unmixed, but construct a maximal with respect to
inclusion independent set of the basic leading terms resp. detect
from this (an approximation for) the dimension.}

\verb|eliminate(m,<variable list>)| \index{eliminate}

\pbx{computes the elimination ideal/module eliminating the variables
in the given variable list (a subset of the variables of the current
base ring). Changes temporarily the term order to degrevlex.}

\verb|gbasis m| \index{gbasis}

\pbx{returns the \gr resp. local standard basis of the bounded
identifier $m$.}

\verb|getdegrees() or getdegrees m| \index{getdegrees}

\pbx{returns the currently active column degrees, i.e. the value of
\ind{cali!=degrees} converted to algebraic mode, or those of the
bounded identifier $m$.}

\verb|getecart()| \index{getecart}

\pbx{returns the currently active ecart vector converted to algebraic
mode.}

\verb|getkbase gb| \index{getkbase}

\pbx{returns a k-vector space basis of $S^c/gb$, consisting of module
terms, provided $gb$ is zerodimensional.}

\verb|getleadterms gb| \index{getleadterms}

\pbx{returns the dpmat of leading terms of a \gr resp. local standard
basis of $gb$.} 

\verb|getmonset()| \index{getmonset}

\pbx{returns the value of \ind{cali!=monset}.}

\verb|getrules()| \index{getrules}

\pbx{returns the currently active rule list, introduced with
\ind{setrules}.} 

\verb|gradedbettinumbers gbr| \index{gradedbettinumbers}

\pbx{extracts the list of degree lists of the free summands in a
minimal resolution of $gbr$.}

\verb|groebfactor m|\footnote{{\em groebfactorize} in v. 2.0., but
this conflicts with the groebner package of REDUCE} \index{groebfactor}

\pbx{returns for the dpmat ideal $m$ a (reduced) list of dpmats such
that the union of their zeroes is exactly the zero set of $m$.
Factors all polynomials involved in the \gr algorithms of the partial
results.}

\verb|hilbseries gb| \index{hilbseries}

\pbx{returns the Hilbert series of $gb$ with denominator $(1-x)^d$,
where $d$ is the dimension of $gb$ (if the term order is a
degreeorder with default ecart).}

\verb|idealpower(m,n)| \index{idealpower}

\pbx{returns the interreduced basis of the ideal power $m^n$ with
respect to the integer $n\geq 0$.}

\verb|idealprod(m1,m2,...)| \index{idealprod}

\pbx{returns the interreduced basis of the ideal product 
\mbox{$m1\cdot m2\cdot \ldots$} of the ideals $m1,m2,\ldots$.}

\verb|idealquotient(m1,m2)| \index{idealquotient}

\pbx{returns the ideal quotient $m1:m2$ of the module $m1\subseteq
S^c$ by the ideal $m2$.}

\verb|idealsum(m1,m2,...)| \index{idealsum}

\pbx{returns the interreduced basis of the ideal sum $m1+m2+\ldots$.}

\verb|indepvarsets gb| \index{indepvarsets}

\pbx{returns the list of strongly independent sets of $gb$ with
respect to the current term order, see \cite{KW} for a definition in
the case of ideals and \cite{GrI} for submodules of free modules.}

\verb|initmat(m,<file name>| \index{initmat}

\pbx{initialize the dpmat $m$ together with its base ring, term order
and column degrees from a file.}

\verb|interreduce m| \index{interreduce}

\pbx{returns the interreduced module basis given by the rows of $m$,
i.e. a basis with pairwise indivisible leading terms.}

\verb|matappend(m1,m2,...)| \index{matappend}

\pbx{collects the rows of the dpmats $m1,m2,\ldots $ to a common
matrix. $m1,m2,\ldots$ must be submodules of the same free module,
i.e. have equal column degrees (and size).}

\verb|mathomogenize(m,var)| \index{mathomogenize}
\footnote{Dehomogenize with \verb|sub(z=1,m)| if $z$ is the
homogenizing variable.}

\pbx{returns the result obtained by homogenization of the rows of m
with respect to the variable {\tt var} and the current \ind{ecart
vector}.}

\verb|matintersect(m1,m2,...)| \index{matintersect}
\footnote{It works also for ideals, hence {\em
idealintersect} was removed in v. 2.1.}

\pbx{returns the interreduced basis of the intersection $m1\bigcap
m2\bigcap \ldots$.}

\verb|matqquot(m,f)| \index{matqquot}

\pbx{returns the stable quotient $m:(f)^\infty$ of the dpmat $m$ by
the polynomial $f\in S$.}

\verb|matquot(m,f)| \index{matquot}

\pbx{returns the quotient $m:(f)$ of the dpmat $m$ by the polynomial
$f\in S$.}

\verb|matstabquot(m1,id)| \index{matstabquot}

\pbx{returns the stable quotient $m1:id^infty$ of the dpmat $m1$ by
the ideal $id$.}

\verb|matsum(m1,m2,...)| \index{matsum}

\pbx{returns the interreduced basis of the module sum $m1+m2+\ldots$
in a common free module.}

\verb|a mod m| \index{mod}

\pbx{computes the (true) normal form(s), i.e. a standard quotient
representation, of $a$ modulo the dpmat $m$. $a$ may be either a
polynomial or a polynomial list ($c=0$) or a matrix ($c>0$) of the
correct number of columns.} 

\verb|modequalp(gb1,gb2)| \index{modequalp}

\pbx{tests, whether $gb1$ and $gb2$ are equal (returns YES or NO).}

\verb|modulequotient(m1,m2)| \index{modulequotient}

\pbx{returns the module quotient $m1:m2$ of two dpmats $m1,m2$ in a
common free module.}

\verb|normalform(m1,m2)| \index{normalform}

\pbx{returns a list of three dpmats $\{m3,r,z\}$, where $m3$ is the
normalform of $m1$ modulo $m2$, $z$ a scalar matrix of polynomial
units (i.e. polynomials of degree 0 in the noetherian case and
polynomials with leading term of degree 0 in the tangent cone case),
and $r$ the relation matrix, such that \[m3=z*m1+r*m2.\]}

\verb|resolve(m[,d])| \index{resolve}

\pbx{returns the first $d$ members of the minimal resolution of the
bounded identifier $m$ as a list of matrices. If the resolution has
less than $d$ non zero members, only those are collected. (Default~:
$d=100$)}

\verb|savemat(m,<file name>| \index{savemat}

\pbx{save the dpmat $m$ together with the settings of it base ring,
term order and column degrees to a file.}

\verb|setdegrees <list of monomials>| \index{setdegrees}

\pbx{set \ind{cali!=degrees}.}

\verb|setgbasis m| \index{setgbasis}

\pbx{declares the rows of the bounded identifier $m$ to be already a
\gr resp. local standard basis thus avoiding a possibly time
consuming \gr or standard basis computation.}

\verb|setrules <rule list>| \index{setrules}

\pbx{introduces an algebraic rule list to CALI.}

\verb|sieve(m,<variable list>)| \index{sieve}

\pbx{sieves out all base elements with leading terms having a factor
contained in the specified variable list (a subset of the variables
of the current base ring). Useful for elimination problems solved
``by hand''.}

\verb|submodulep(m,gb)| \index{submodulep}

\pbx{tests, whether $m$ is a submodule of $gb$ (returns YES or NO).
$gb$ must be a bounded identifier with precomputed \gr basis.}

\verb|syzygies m| \index{syzygies}

\pbx{returns the first syzygy module of the bounded identifier $m$.}

\verb|tangentcone gb| \index{tangentcone}

\pbx{returns the tangent cone part, i.e. the homogeneous part of
highest degree with respect to the first degree vector of the term
order from the \gr basis elements of the dpmat $gb$. The term order
must be a degree order.}

\end{quote}

\subsection{Primary Decomposition and Related Problems}

\begin{quote}
\verb|isprime gb| \index{isprime}

\pbx{tests the ideal $gb$ to be prime.}

\verb|iszeroradical gb| \index{iszeroradical}

\pbx{tests the zerodimensional ideal $gb$ to be radical.}

\verb|zeroradical gb| \index{zeroradical}

\pbx{returns the radical of the zerodimensional ideal $gb$.}

\end{quote}

The following procedures don't assume that $m$ is a \gr basis, since
the algorithm needs several \gr basis computations anyway.  They
return either lists of ideals (primes of the dpmat $m$ under
consideration) or lists of pairs consisting of the primary
components of $m$ and their associated primes.

\begin{quote}
\verb|easyprimarydecomposition m| \index{easyprimarydecomposition} 

\pbx{a short primary decomposition using ideal separation of isolated
primes of $m$. Yields true results only for modules without embedded
components.} 

\verb|eqhull m| \index{eqhull}

\pbx{returns the equidimensional hull of the dpmat $m$.}

\verb|isolatedprimes m| \index{isolatedprimes}

\pbx{returns the list of isolated primes of the dpmat $m$, i.e. the
isolated primes of $Ann\ S^c/m$.}

\verb|primarydecomposition m| \index{primarydecomposition}

\pbx{returns the primary decomposition of the dpmat $m$.}

\verb|radical m| \index{radical}

\pbx{returns the radical of the dpmat ideal $m$.}

\verb|unmixedradical m| \index{unmixedradical}

\pbx{returns the unmixed radical of the dpmat ideal $m$.}

\verb|zeroprimarydecomposition m| \index{zeroprimarydecomposition}

\pbx{returns the primary decomposition of the zerodimensional dpmat
$m$.}

\verb|zeroprimes m| \index{zeroprimes}

\pbx{returns the list of primes of the zerodimensional dpmat $m$.}

\end{quote}

\subsection{Scripts}

\begin{quote}
\verb|affine_monomial_curve(l,R)|\index{affine\_monomial\_curve}

\pbx{$l$ is a list of integers, $R$ a list of variable names of the
same length as $l$. The procedure set the current base ring and
returns the defining ideal of the affine monomial curve with generic
point $(t^i\ :\ i\in l)$.}

\verb|affine_points m| \index{affine\_points}

\pbx{$m$ is a matrix of domain elements (in algebraic prefix form)
with as many columns as the current base ring has ring variables.
Its rows represent the affine coordinates of a collection of points.
This procedure returns the intersection of the maximal ideals
corresponding to these points.}

\verb|analytic_spread M|\index{analytic\_spread}

\pbx{Computes the analytic spread of $M$.}
       
\verb|assgrad(M,N,vars)|\index{assgrad}

\pbx{Computes the associated graded ring $gr_R(N)$ over $R=S/M$, where 
$S$ is the current
base ring. {\tt vars} is a list of new variable names one for
each generator of $N$.  They are used to create a second ring $T$
to return an ideal $J$ such that $(S\oplus T)/J$ is the desired
associated graded ring over the new current base ring $S\oplus T$.}
       
\verb|blowup(M,N,vars)|\index{blowup}

\pbx{Computes the blow up ${\cal R}(N)$ of $N$ over the ring $R=S/M$,
where $S$ is the current base ring. {\tt vars} is a list of new
variable names one for each generator of $N$. They are used to create
a second ring $T$ to return an ideal $J$ such that $(S\oplus T)/J$ is
the desired blowup ring over the new current base ring $S\oplus T$.}
       
\verb|flatten m| \index{flatten}

\pbx{converts the matrix $m$ into a list of its entries.}

\verb|ideal2mat m| \index{ideal2mat}

\pbx{converts the ideal (=list of polynomials) $m$ into a column
vector.} 

\verb|matjac(m,<variable list>)| \index{matjac}

\pbx{returns the Jacobian matrix of the ideal m with respect to the 
supplied variable list}

\verb|minimal_generators m| \index{minimal\_generators}

\pbx{returns a set of minimal generators of the dpmat $m$.}

\verb|minors(m,b)| \index{minors}

\pbx{returns the list of minors of size $b\times b$ of the dpmat
$m$.} 

\verb|preimage(m,map)| \index{preimage}

\pbx{computes the preimage of the ideal $m$ under the given
polynomial map and sets the current base ring to the preimage ring.}

\verb|proj_monomial_curve(l,R)|\index{proj\_monomial\_curve}

\pbx{$l$ is a list of integers, $R$ a list of variable names of the
same length as $l$. The procedure set the current base ring and
returns the defining ideal of the projective monomial curve with
generic point \mbox{$(s^{d-i}\cdot t^i\ :\ i\in l)$} in $R$ where $d=max\{
x\, :\, x\in l\}$.}

\verb|proj_points m| \index{proj\_points}

\pbx{$m$ is a matrix of domain elements (in algebraic prefix form)
with as many columns as the current base ring has ring variables.
Its rows represent the homogeneous coordinates of a collection of
points in projective space. This procedure returns the intersection
of the maximal homogeneous ideals corresponding to these points.}

\verb|random_linear_form(vars,bound)| \index{random\_linear\_form}

\pbx{returns a random linear form in the variables {\tt vars} with integer
coefficients less than the supplied {\tt bound}.}

\verb|ratpreimage(m,map)| \index{ratpreimage}

\pbx{computes the closure of the preimage of the ideal $m$ under the
given rational map and sets the current base ring to the preimage
ring.}

\verb|singular_locus(M,c)| \index{singular\_locus}

\pbx{returns the defining ideal of the singular locus of $Spec\ S/M$
where $M$ is an ideal of codimension $c$, adding to $M$ the ideal of
the $c$-minors of the Jacobian of $M$.}

\verb|sym(M,vars)|\index{sym}

\pbx{Computes the symmetric algebra $Sym(M)$ where $M$ is an ideal
defined over the current base ring $S$. {\tt vars} is a list of new
variable names one for each generator of $M$. They are used to create
a second ring $R$ to return an ideal $J$ such that $(S\oplus R)/J$ is
the desired symmetric algebra over the new current base ring $S\oplus
R$.}
       
\verb|symbolic_power(m,d)| \index{symbolic\_power}

\pbx{returns the d'th symbolic power of the prime dpmat ideal $m$.} 

\verb|varopt m| \index{varopt}

\pbx{finds a heuristically optimal variable order, see \cite{BGK}. 
\[\tt vars:=varopt\ m;\ setring(vars,\{\},lex);\ setideal(m,m);\]
changes to the lexicographic term order with heuristically best
performance for a lexicographic \gr basis computation.}


\end{quote}

\pagebreak

\section{Algebraic Mode vs. Symbolic Mode}

Here is a summary of algebraic mode procedures and their symbolic
mode equivalents.
\bigskip

\begin{tabular}{|p{6cm}|p{7cm}|}
\hline
algebraic mode & symbolic mode\\
\hline
affine\_monomial\_curve(l,R)&affine\_monomial\_curve!*(l,R)\\
affine\_points m& affine\_points!* m\\
analytic\_spread M&analytic\_spread!* M\\
annihilator m& annihilator1(2)!* m\\ 
assgrad(M,N,vars)&assgrad!*(M,N,vars)\\
bettinumbers m& bettinumbers!*(resolution)\\
blowup(M,N,vars)&blowup!*(M,N,vars)\\
codim m&codim!* m\\
degsfromresolution m &\\
degree m& degree!* m \\
degreeorder vars & degreeorder!* vars\\
deleteunits m& deleteunits!* m\\
dim m& dim!* m \\
dimzerop m& dimzerop!* m\\
directsum(m1,m2,\ldots )& directsum!*(list of dpmats)\\
dpgcd(f,g) & dpgcd!*(f,g)\\
easydim m& easydim!* m\\
easyindepset m& easyindepset!* m\\
easyprimarydecomposition m& easyprimarydecomposition!* m\\
eliminate(m, list of var. names)& eliminate!*(m, list of var. names)\\
eliminationorder vars & eliminationorder!* vars \\
eqhull m& eqhull!* m\\
flatten m& flatten!* m\\
gbasis m& gbasis!* m\\
getdegrees() or getdegrees m& dpmat\_coldegs m\\
getecart() & ring\_ecart cali!=basering\\
getkbase m& getkbase!* m\\
getleadterms gb & getleadterms!* m\\
getmonset()&cali!=monset\\
getring() or getring m& cali!=basering\\
\end{tabular}

\begin{tabular}{|p{6cm}|p{7cm}|}
getrules()& cali!=rules\\
gradedbettinumbers m& gradedbettinumbers!*(resolution)\\
groebfactor m& groebfactor!*(m,con)\\
hilbseries m& 
    hilbseries1 m \nl or hilbseries2 m \nl or hilbseries3(resolution)\\
idealpower(m,n)& idealpower!*(m,n)\\
idealprod(m1,m2,\ldots )& idealprod!*(list of dpmats) or \nl
    idealprod2(a,b)\\
idealquotient(m,n)& idealquotient1(2)!*(m,n)\\
idealsum(m1,m2,\ldots )& matsum!*(list of dpmats)\\
ideal2mat m&ideal2mat!* m\\
indepvarsets m& indepvarsets!* m \\
initmat(file name)& initmat!*(file name)\\
interreduce m& interreduce!* m\\ 
isolatedprimes m& isolatedprimes!* m\\
isprime m& isprime!* m\\
iszeroradical m& iszeroradical!* m\\
localorder vars & localorder!* vars\\
matappend(m1,m2,\ldots )& matappend!*(list of dpmats)\\
mathomogenize(m,var. name)& mathomogenize!*(m,var. name)\\
matintersect(m1,m2,\ldots )& matintersect!*(list of dpmats)\\
matjac(m,list of var. names)&\\ 
matquot(m,f)& matquot!*(m,f)\\
matqquot(m,f)& matqquot!*(m,f)\\
matstabquot(m,n)& matstabquot!*(m,n)\\
matsum(m1,m2,\ldots )& matsum!*(list of dpmats)\\
minimal\_generators m& minimal\_generators!* m\\
minors(m,k)&minors!*(m,k)\\
mod(a,m) or a mod m & mod!*(a,m)\\
modequalp(m1,m2)& modequalp!*(m1,m2)\\
modulequotient(m,n)& modulequotient1(2)!*(m,n)\\
\end{tabular}

\begin{tabular}{|p{6cm}|p{7cm}|}
normalform(m1,m2)& normalform!*(m1,m2)\\
preimage(m,map)& preimage!*(m,map)\\
primarydecomposition m& primarydecomposition!* m\\
proj\_monomial\_curve(l,R)&proj\_monomial\_curve!*(l,R)\\
proj\_points m& proj\_points!* m\\
radical m& radical!* m\\
random\_linear\_form(vars,bound)&\\
ratpreimage(m,map)& ratpreimage!*(m,map)\\
resolve(m[,d])& resolve!*(m,d)\\
savemat(m,file name)& savemat!*(m,file name)\\
setdegrees(list of monomials) & 
    cali!=degrees:=\nl assoc. list of monomials\\
setecart(list of integer) & setecart!*(list of integers) \\
setgbasis m&\\
setideal(id, list of polynomials) &dpmat\_from\_a(alg. prefix form)\\
setmodule(id,matrix) & dpmat\_from\_a(alg. prefix form)\\
setmonset(var. list)& setmonset!*(var. list)\\
setring(vars,\nl term order,tag[,ecart]) & 
        setring!* \nl ring\_define(vars,tord,tag,ecart)\\
setrules(rules list)& setrules!*(rules list)\\
sieve(m,list of var. names) & dpmat\_sieve(m,list of var. names)\\
singular\_locus(M,c)& \\
submodulep(m1,m2)& submodulep!*(m1,m2)\\
sym(M,vars)&sym!*(M,vars)\\
symbolic\_power(m,d)& symbolic\_power!*(m,d)\\
syzygies m& syzygies!* m or syzygies1!* m\\
tangentcone gb& tangentcone!* m\\
unmixedradical m& unmixedradical!* m\\
varopt m& varopt!* m\\
zeroprimarydecomposition m& zeroprimarydecomposition!* m\\
zeroprimes m& zeroprimes!* m\\
zeroradical m& zeroradical!* m\\
\hline
\end{tabular}

\pagebreak

\section{The CALI Module Structure}
\vfill

\begin{tabular}{|p{1.5cm}||p{5.5cm}|p{2cm}|p{4cm}|}
\hline
\sloppy

name & subject & data type & representation \\
\hline

cali & Header module, contains \linebreak 
global variables, switches etc. & --- & ---\\

bcsf & Base coefficient arithmetic & base coeff. & standard forms \\ 

ring & Base ring setting, definition of the term order & base ring &
special type RING\\

mo & monomial arithmetic & monomials & (exp. list . degree list)\\

dpoly & Polynomial and vector arith\-metic & dpolys & list of terms\\

bas & Operations on base lists & base list & list of base elements \\

dpmat & Operations on polynomial matrices, the central data type of
CALI & dpmat & special type DPMAT\\

red & Normal form algorithms for noetherian term orders & --- & ---\\

groeb & \gr basis algorithm and related ones for noetherian term
orders & --- & ---\\

mora & Modifications for non noetherian term orders & --- & ---\\

matop & Operations on (lists of) \linebreak dpmats that correspond to
ideal/module operations & --- & ---\\

quot & Different quotient algorithms & --- & --- \\

moid & Monomial ideal algorithms & monomial ideal & list of monomials \\

res & Resolutions of dpmats & resolution & list of dpmats \\

interf & Interface to algebraic mode & --- & ---\\

odim & Algorithms for zerodimensional ideals and modules & --- & ---\\ 

prime & Primary decomposition and related questions & --- & ---\\

scripts & Advanced applications  & --- & ---\\
\hline
\end{tabular}
\vfill
\pagebreak

\begin{theindex}

  \item affine\_monomial\_curve, 27, 36
  \item affine\_points, 28, 36
  \item algebraic numbers, 12
  \item analytic\_spread, 27, 36
  \item annihilator, 23, 30
  \item annihilator1, 18
  \item assgrad, 27, 36

  \indexspace

  \item bas\_getrelations, 18
  \item bas\_removerelations, 17
  \item bas\_setrelations, 17
  \item base coefficients, 12
  \item base elements, 17
  \item base ring, 8, 16
  \item basis, 12
  \item bcsimp, 13, 15
  \item bettinumbers, 30
  \item binomial, 13
  \item blowup, 7, 27, 36
  \item bounded identifier, 11
  \item bounded identifiers, 30

  \indexspace

  \item cali, 6
  \item cali!=basering, 8, 14, 16
  \item cali!=degrees, 10, 15, 16, 31, 34
  \item cali!=ecart, 20
  \item cali!=monset, 15, 20, 22, 31
  \item cali!=rules, 12, 15
  \item cali!=trace, 14, 15
  \item codim, 24, 30
  \item column degree, 10
  \item current module, 16
  \item current ring, 16

  \indexspace

  \item degree, 24, 30
  \item degree vectors, 8
  \item degreeorder, 8, 16
  \item degsfromresolution, 30
  \item deleteunits, 19, 30
  \item detectunits, 6, 13, 19
  \item dim, 23, 30
  \item dimzerop, 25, 30
  \item directsum, 18, 30
  \item dmode, 12
  \item dp\_pseudodivmod, 12, 22
  \item dpgcd, 22, 31
  \item dpmat, 10--12, 18
  \item dpmat\_coldegs, 18
  \item dpmat\_cols, 18
  \item dpmat\_list, 18
  \item dpmat\_rows, 18

  \indexspace

  \item easydim, 21, 24, 31
  \item easyindepset, 24, 31
  \item easyprimarydecomposition, 26, 35
  \item ecart, 3, 6, 17
  \item ecart vector, 9, 24, 33
  \item eliminate, 7, 22, 31
  \item eliminationorder, 9, 16
  \item eqhull, 26, 35

  \indexspace

  \item factorunits, 6, 14, 19
  \item flatten, 11, 36
  \item free identifier, 11

  \indexspace

  \item gbasis, 19, 20, 31
  \item getdegrees, 11, 31
  \item getecart, 10, 31
  \item getkbase, 25, 31
  \item getleadterms, 31
  \item getmonset, 31
  \item getring, 9
  \item getrules, 12, 31
  \item global procedures, 6
  \item gradedbettinumbers, 32
  \item groeb\_stbasis, 20
  \item groebfactor, 21, 32

  \indexspace

  \item hardzerotest, 12, 14
  \item hilb1, 24
  \item hilb2, 24
  \item Hilbert series, 10
  \item hilbseries, 32
  \item hilbseries1, 24
  \item hilbseries2, 24
  \item Homogenizations, 10

  \indexspace

  \item ideal quotient, 22
  \item ideal2mat, 11, 36
  \item idealpower, 18, 32
  \item idealprod, 18, 32
  \item idealquotient, 23, 32
  \item ideals, 11
  \item idealsum, 32
  \item indepvarsets, 23, 32
  \item initmat, 32
  \item internal procedures, 6
  \item interreduce, 19, 32
  \item isolatedprimes, 26, 35
  \item isprime, 25, 35
  \item iszeroradical, 35

  \indexspace

  \item lazy, 6, 14, 21
  \item lexicographic, 8
  \item listminimize, 7
  \item listtest, 7
  \item local procedures, 6
  \item localorder, 9, 16

  \indexspace

  \item map, 26
  \item matappend, 18, 33
  \item mathomogenize, 33
  \item matintersect, 7, 18, 22, 33
  \item matjac, 37
  \item matqquot, 18, 22, 33
  \item matquot, 18, 22, 33
  \item matstabquot, 23, 33
  \item matsum, 18, 33
  \item minimal\_generators, 28, 37
  \item minors, 37
  \item mod, 19, 33
  \item modequalp, 18, 22, 33
  \item module quotient, 22
  \item module term order, 10
  \item modulequotient, 23, 33
  \item modulequotient1, 18
  \item modules, 11
  \item moid\_primes, 23
  \item mora\_interreduce, 19
  \item mora\_stbasis, 20

  \indexspace

  \item noetherian, 3, 8, 14, 16, 19
  \item normalform, 19, 34

  \indexspace

  \item odim\_parameter, 25
  \item odim\_up, 25

  \indexspace

  \item preimage, 7, 27, 37
  \item primary decomposition, 7
  \item primarydecomposition, 35
  \item proj\_monomial\_curve, 28, 37
  \item proj\_points, 29, 37

  \indexspace

  \item radical, 26, 35
  \item random\_linear\_form, 37
  \item ratpreimage, 27, 37
  \item red\_better, 18
  \item red\_interreduce, 19
  \item red\_total, 14
  \item resolve, 7, 34
  \item reverse lexicographic, 8
  \item ring, 12
  \item ring\_define, 16
  \item ring\_sum, 16

  \indexspace

  \item savemat, 34
  \item scripts, 7
  \item setdegrees, 11, 15, 34
  \item setgbasis, 34
  \item setideal, 12, 13
  \item setkorder, 16
  \item setmodule, 12, 13
  \item setmonset, 15, 21
  \item setring, 7--9, 13, 14, 16
  \item setrules, 12, 15, 22, 31, 34
  \item sieve, 34
  \item singular\_locus, 37
  \item stable quotient, 22
  \item submodulep, 18, 21, 34
  \item sym, 7, 28, 37
  \item symbolic\_power, 29, 38
  \item syzygies, 19, 20, 34
  \item syzygies1, 20

  \indexspace

  \item tangentcone, 35
  \item term, 17

  \indexspace

  \item unmixedradical, 26, 35

  \indexspace

  \item varopt, 38

  \indexspace

  \item zeroprimarydecomposition, 25, 26, 36
  \item zeroprimes, 25, 36
  \item zeroradical, 25, 35

\end{theindex}
\pagebreak

\begin{thebibliography}{xxx}
\bibitem{BS} D. Bayer, M. Stillman : Computation of Hilbert
functions, {\it J. Symb. Comp. \bf 14} (1992), 31 - 50.
\bibitem{BKW} T. Becker, H. Kredel, V. Weispfenning : \gr bases. A
computational approach to commutative algebra. Grad. Texts in Math.
141, Springer, New York 1993.
\bibitem{BCRT} A. M. Bigatti, P. Conti, L. Robbiano, C. Traverso : A
divide and conquer algorithm for Hilbert-Poincare series,
multiplicity and dimension of monomial ideals, to appear.
\bibitem{BGK} W. Boege, R. Gebauer, H. Kredel : Some examples for
solving systems of algebraic equations by calculating \gr bases. {\it
J. Symb. Comp. \bf 2} (1986), 83 - 98.
\bibitem{B1} B. Buchberger : \gr bases : An algorithmic method in
polynomial ideal theory. In : Recent trends in multidimensional
system theory (N.~K.~Bose ed), Reidel, Dortrecht 1985, 184 - 232.
\bibitem{B2} B. Buchberger : Applications of \gr bases in non-linear
computational geometry. L.N.C.S. 296 (1988), 52 - 80.
\bibitem{CLO} D. Cox, J. Little, D. O'Shea : Ideals, varieties, and
algorithms.  Undergrad. Texts in Math., Springer, New York 1992.
\bibitem{E} D. Eisenbud : \gr bases. A chapter from :
Commutative algebra with a view toward algebraic geometry.
A book in preparation.
\bibitem{GTZ} P. Gianni, B. Trager, G. Zacharias : \gr bases and
primary decomposition of polynomial ideals, {\it J. Symb. Comp. \bf
6} (1988), 149 - 167.
\bibitem{GMNRT} A. Giovini, T. Mora, G. Niesi, L. Robbiano \& C.
Traverso : "One sugar cube, please" or Selection strategies in the
Buchberger algorithm. In : Proceedings of the ISSAC'91, ACM Press
1991, 49 - 54.
\bibitem{GrI} H.-G. Gr\"abe : Two remarks on independent sets, 
{\it J. Alg. Comb. \bf 2} (1993), 137 - 145. 
\bibitem{Gr23} H.-G. Gr\"abe : The tangent cone algorithm and
homogenization. To appear
\bibitem{ala} H.-G. Gr\"abe : Algorithms in local algebra. To appear
\bibitem{Kr} H. Kredel : Primary ideal decomposition, in : Proc.
EUROCAL'87, Lecture Notes in Comp. Sci. 378 (1986), 270 - 281.
\bibitem{KW} H. Kredel, V. Weispfenning : Computing dimension and
independent sets for polynomial ideals, {\it J. Symb. Comp. \bf 6} 
(1988), 231 - 247.
\bibitem{MM} H.-M. M\"oller, F. Mora : New constructive methods in
classical ideal theory, {\it J. Alg. \bf 100} (1986), 138 -178.
\bibitem{MR88} T. Mora, L. Robbiano : The Gr\"obner fan of an ideal.
{\it J. Symb. Comp. \bf 6} (1988), 183 - 208.
\bibitem{Mo88} T. Mora : Seven variations on standard bases. 
Preprint, Univ. Genova, 1988.
\bibitem{MPT} T. Mora, G. Pfister, C. Traverso : An introduction to
the tangent cone algorithm, to appear
\bibitem{Ro} L. Robbiano : Computer algebra and commutative algebra.
L.N.C.S. 357 (1989), 31 - 44.
\bibitem{Ru} E. W. Rutman : \gr bases and primary decomposition of
modules. {\it J. Symb. Comp. \bf 14} (1992), 483 - 503.

\end{thebibliography}

\end{document}