Check-ins Using Download Hex

Artifact 2906b4a1abea3b51415a9ba4c7079e82831859a9521a80a2456efcc40c854e6c:

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

\documentstyle[11pt]{article}
\date{June 28, 1995}

\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.2.1}

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

\begin{document}

\maketitle

\vfill
Key words:
affine and projective monomial curves,
affine and projective sets of points,
analytic spread,
associated graded ring,
blowup,
border bases,
constructive commutative algebra,
dual bases,
elimination,
equidimensional part,
extended \gr factorizer,
free resolution,
\gr algorithms for ideals and module,
\gr factorizer,
ideal and module operations,
independent sets,
intersections,
lazy standard bases,
local free resolutions,
local standard bases,
minimal generators,
minors,
normal forms,
pfaffians,
polynomial maps,
primary decomposition,
quotients,
symbolic powers,
symmetric algebra,
triangular systems,
weighted Hilbert series,
primality test,
radical,
unmixed radical.

\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 {\tt groebner} package distributed with REDUCE (and rests on ideas
used in the {\tt 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{tcah}, 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 appropriate algorithms
automatically. In v.\ 2.2 we present an unified approach to both
cases, using reduction with bounded ecart for non Noetherian term
orders, see \cite{ala} for details. This allows to have a common
driver for the \gr algorithm in both cases.

CALI extends also the restricted term order facilities of the {\tt
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{tcah}.
\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. An algebraic mode interface accesses (in a more rigid frame)
all important features implemented symbolically and thus
should be favored 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 code 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 (now also weighted) Hilbert series, multiplicities,
independent sets, and dimensions,

\item computing normal forms and representations,

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

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

\item advanced applications of \gr bases (blowup, associated graded
ring, analytic spread, symmetric algebra, monomial curves etc.),

\item applications of linear algebra techniques to zero dimensional
        ideals, as e.g.\ the FGLM change of term orders, border bases
        and affine and projective ideals of sets of points,

\item splitting polynomial systems of equations mixing factorization and
the \gr algorithm, triangular systems, and different versions of the
extended \gr factorizer.

\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}, \cite{CLO} and \cite{Mishra} or the survey papers
\cite{B1}, \cite{B2} and \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.1 to v.\ 2.2. and 2.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.}

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 responds with a message containing the
version number and the last update of the distribution.

\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 developed (and are still developing)
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 semantical 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 use, and \ind{global
procedures}, exported by CALI into the general (algebraic or
symbolic) environment of REDUCE. A header \ind{module 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}
There are also symbolic mode equivalents without trailing asterisk, if
the algebraic procedure is not a {\em psopfn}, but a {\em symbolic
operator}. They transfer data to CALI's internal structure and call
the corresponding procedure with trailing asterisk. CALI 2.2
distinguishes between algebraic and symbolic calls of such a
procedure. In symbolic mode such a procedure calls the corresponding
procedure with trailing asterisk directly without data transfer.
\medskip

CALI 2.2 follows also a more concise concept for global
variables. There are three types of them:
\begin{quote}
True {\em fluid} global variables,

\pbx{that are part of the current data structure, as e.g.\ the current
base ring and the degree vector. They are often locally rebound to be
restored after interrupts.}

Global variables, stored on the property list of the package name {\tt
cali},

\pbx{that reflect the state of the computational model as e.g.\ the
trace level, the output print level or the chosen version of the \gr
basis algorithm. There are several such parameters in the module
\ind{dualbases} to serve the common dual basis driver with
information for different applications.}

{\em Switches,}

\pbx{that allow to choose different branches of algorithms. Note that
this concept interferes with the second one. Different {\em versions}
of algorithms, that apply different functions in a common driver, are
{\em not} implemented through switches.}
\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 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 \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 \ind{module 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 restores the original values of CALI's global variables,
since all intermediate procedures work with local copies of
the global variables.\footnote{Note that 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}

\subsection{New and Improved Facilities in v.\ 2.2}

Version 2.2 (beside bug fixes) incorporates several new facilities of
constructive non linear algebra that we investigated the last two
years, as e.g.\ dual bases, the \gr factorizer, triangular systems, and
local standard bases. Essential changes concern the following topics:
\begin{enumerate}
\item The CALI modules \ind{red} and \ind{groeb} were rewritten and
the \ind{module mora} was removed. This is
due to new theoretical insight into standard bases theory as
e.g.\ described in \cite{tcah} or \cite{ala}. The \gr basis algorithm
is reorganized as a \gr driver with simplifier and base lists, that
involves different versions of polynomial reduction according to the
setting via \ind{gbtestversion}. It applies now to
both noetherian and non noetherian term orders in a unified way.

The switches \ind{binomial} and \ind{lazy} were removed.

\item The \gr factorizer was thoroughly revised, extended along the
lines explained in \cite{fgb}, and collected into a separate
\ind{module groebf}. It now allows a list of constraints also in
algebraic mode. Two versions of an \ind{extended \gr factorizer}
produce \ind{triangular systems},
i.e.\ a decomposition into quasi prime components, see \cite{efgb},
that are well suited for further (numerical) evaluation. There is also
a version of the \gr factorizer that allows a list of problems as
input. This is especially useful, if a system is splitted with respect
to a ``cheap'' (e.g. degrevlex) term order and the pieces are
recomputed with respect to a ``hard'' (e.g. pure lex) term order.

The extended \gr factorizer involves, after change to dimension zero,
the computation of \ind{triangular systems}. The corresponding module
\ind{triang} extends the facilities for zero dimensional ideals and
modules in the \ind{module odim}.

\item A new \ind{module lf} implements the \ind{dual bases} approach
as described in \cite{MMM}. On this basis there are new
implementations of \ind{affine\_points} and \ind{proj\_points}, that
are significantly faster than the old ones. The linear algebra
\ind{change of term orders} \cite{FGLM} is available, too. There are
two versions, one with precomputed \ind{border basis}, the other with
conventional normal forms.

\item \ind{dpmat}s now have a \ind{gb-tag} that indicates, whether the
given ideal or module basis is already a \gr basis. This avoids
certain \gr basis recomputations especially during advanced algorithms
as e.g.\ prime decomposition. In the algebraic interface \gr bases are
computed automatically when needed rather than to issue an error
message as in v.\ 2.1. So one can call \ind{modequalp} or \ind{dim}
etc. not having computed \gr bases in advance. Note that such
automatic computation can be avoided with \ind{setgbasis}.

\item Hilbert series are now \ind{weighted Hilbert series}, since
e.g.\ for blow up rings the generating ideal is multigraded. Usual
Hilbert series are computed as in v.\ 2.1 with respect to the
\ind{ecart vector}. Weighted Hilbert series accept a list of (integer)
weight lists as second parameter.

\item There are some name and conceptual changes to existing
procedures and variables to have a more concise semantic concept. This
concerns
\begin{quote}
\ind{tracing} (the trace parameter is now stored on the property list
of {\tt cali} and should be set with \ind{setcalitrace}),

choosing different versions of the \gr algorithm (through
\ind{gbtestversion}) and the Hilbert series computation (through
\ind{hftestversion}),

some names (\ind{mat2list} replaced \ind{flatten}, \ind{HilbertSeries}
replaced {\em hilbseries}) and

parameter lists of some local and internal procedures (consult {\em
cali.chg} for details).
\end{quote}

\item The \ind{revlex term order} is now the reverse lexicographic
term order on the {\bf reversely} ordered variables. This is consistent
with other computer algebra systems (e.g.\ SINGULAR or
AXIOM)\footnote{But different to the currently distibuted {\tt
groebner} package in REDUCE. Note that the computations in
\cite{fgb} were done {\em before} these changes.} and implies the same
order on the variables for deglex and degrevlex term orders (this was
the main reason to change the definition).

\item Ideals of minors, pfaffians and related stuff are now
implemented as extension of the internal {\tt matrix} package and
collected into a separate \ind{module calimat}. Thus they allow more
general expressions, especially with variable exponents, as general
REDUCE matrices do. So one can define generic ideals as e.g.\ ideals
of minors or pfaffians of matrices, containing generic expressions as
elements. They must be specified for further use in CALI substituting
general exponents by integers.

\end{enumerate}

\subsection{New and Improved Facilities in v.\ 2.2.1\label{221}}

The main change concerns the primary decomposition algorithm, where I
fixed a serious bug for deciding, which embedded primes are really
embedded\footnote{That there must be a bug was pointed out to me by
Shimoyama Takeshi who compared different p.d.\ implementations. The
bug is due to an incorrect test for embedded primes: A (superfluous)
primary component may contain none of the isolated primary components,
but their intersection! Note that neither \cite{GTZ} nor \cite{BKW}
comment on that. Details of the implementation will appear in
\cite{primary}.}. During that remake I incorporated also the \gr
factorizer to compute isolated primes. Since REDUCE has no
multivariate {\em modular} factorizer, the switch \ind{factorprimes}
may be turned off to switch to the former algorithm.



Some minor bugs are fixed, too, e.g.\ the bug that made \ind{radical}
crashing.




\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. In the next
chapter 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
\begin{verbatim}
 setring <ring>
\end{verbatim}
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\footnote{The definition of the revlex term
order changed for version 2.2.}
with respect to the variable order given in {\tt vars}, i.e.\
\[x^a<x^b \quad :\Leftrightarrow \quad
\exists\ j\ \forall\ i<j\ :\ a_i=b_i\quad\mbox{and}\quad a_j<b_j\
\mbox{(lex.)}\]
or
\[x^a<x^b \quad :\Leftrightarrow \quad
\exists\ j\ \forall\ i>j\ :\ a_i=b_i\quad\mbox{and}\quad a_j>b_j\
\mbox{(revlex.)}\]

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 \ind{switch 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).}

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

\verb|blockorder(vars,integerlist)|, \index{blockorder}

\pbx{that returns the list of degree vectors for the block order with
block lengths given in the {\tt integerlist}. Note that these numbers
should sum up to the length of the variable list supplied as the first
argument.}
\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});
tord:=reverse blockorder(vars,{3,3});
                          % Return both {{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 \\[10pt]
\verb|{{t,x,y,z},{{1,1,1,1}},revlex,{1,1,1,1}}|,\\[10pt]
i.e.\ $S=k[t,x,y,z]$ supplied with the degree wise reverse
lexicographic term order.
\begin{quote}
\verb|getring m|\index{getring}

\pbx{returns the ring attached to the object with the identifier
$m$. E.g.\ }

\verb|setring getring m|

\pbx{(re)sets the base ring to the base ring of the formerly defined
object (ideal or module) $m$.}

\verb|getring()|

\pbx{returns the currently active base ring.}
\end{quote}

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{tcah}. In general
the ecart vector is recommended to be chosen in such a way that the
input examples become close to be homogeneous. {\em 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 a
\ind{module term order}, that may be roughly\footnote{The correct
definition is even more difficult.} described as
\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
one dimensional 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{mat2list} 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 denominator free 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 \ind{switch 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 {\tt cali} value {\tt 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 {\tt arnum} package.
Note, that due to the zero decision problem
complicated {\em setrules} based computations may produce wrong
results if base coefficient's pseudo division 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\footnote{A {\em qring}
facility for the computation over quotient rings will be incorporated
into future versions.}.
\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, a trace
facility, and global parameters on the property list of the package
name {\tt cali} to control CALI's computations.
\medskip

\subsubsection*{Switches}

\begin{quote}
\ind{bcsimp}

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

\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{factorprimes}

\pbx{on: Invoke the \gr factorizer during computation of isolated
primes. (Default: on). Note that REDUCE lacks a modular multivariate
factorizer, hence for modular prime decomposition computations this
switch has to be turned 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{lexefgb}

\pbx{on: Use the pure lexicographic term order and \ind{zerosolve}
during reduction to dimension zero in the \ind{extended \gr
factorizer}. This is a single, but possibly hard task compared to the
degrevlex invocation of \ind{zerosolve1}. See \cite{efgb} for a
discussion of different zero dimensional solver strategies.
(Default: off)}

\ind{Noetherian}

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

off: choose algorithms for local term orders.

(Default: on)}

\ind{red\_total}

\pbx{on: compute total normal forms, i.e. apply reduction (Noetherian
term orders) or reduction with bounded ecart (non Noetherian term
orders to tail terms of polynomials, too.

off: Do only top reduction.

(Default: on)}

\end{quote}

\subsubsection*{Tracing}

Different to v.\ 2.1 now intermediate output during the computations
is controlled by the value of the {\tt trace} and {\tt printterms}
entries on the property list of the package name {\tt cali}. The
former value controls the intensity of the intermediate output
(Default: 0, no tracing), the latter the number of terms printed in
such intermediate polynomials (Default: all).
\begin{quote}
\verb|setcalitrace <n>|\index{setcalitrace}

\pbx{changes the trace intensity. Set $n=2$ for a sparse tracing (a
dot for each reduction step).
Other good suggestions are the values 30 or 40 for tracing the \gr
algorithm or $n>70$ for tracing the normal form algorithm. The higher
$n$ the more intermediate information will be given.}

\verb|setcaliprintterms <n>|\index{setcaliprintterms}

\pbx{sets the number of terms that are printed in intermediate
polynomials. Note that this does not affect the output of whole {\em
dpmats}. The output of polynomials with more than $n$ terms ($n>0$)
breaks off and continues with ellipses.}

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

\pbx{clears the {\tt printterms} value forcing full intermediate
output (according to the current trace level).}
\end{quote}

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

\end{quote}

\subsubsection*{Entries on the Property List of {\tt cali}}

This approach is new for v.\ 2.2. Information concerning the state of
the computational model as e.g.\ trace intensity, base coefficient
rules, or algorithm versions are stored as values on the property list
of the package name \ind{cali}. This concerns
\begin{quote}
\ind{trace} and \ind{printterms}

\pbx{see above.}

\ind{efgb}

\pbx{Changed by the \ind{switch lexefgb}.}

\ind{groeb!=rf}

\pbx{Reduction function invoked during the \gr algorithm. It can be
changed with \ind{gbtestversion}\ $<n>$ ($n=1,2,3$, default is 1).}

\ind{hf!=hf}

\pbx{Variant for the computation of the Hilbert series numerator. It
can be changed with \ind{hftestversion}\ $<n>$ ($n=1,2$, default is 1).}

\ind{rules}

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

\ind{evlf}, \ind{varlessp}, \ind{sublist}, \ind{varnames},
\ind{oldborderbasis}, \ind{oldring}, \ind{oldbasis}

\pbx{see \ind{module lf}, implementing the dual bases approach.}
\end{quote}


\section{Basic Data Structures}

In the following we describe the data structure layers underlying the
dpmat representation in CALI and some important (symbolic) procedures
to handle them. We refer to the source code and the comments therein for
a more complete survey about the procedures available for different
data types.

\subsection{The Coefficient Domain}

Base coefficients as implemented in the \ind{module bcsf} are standard
forms in the variables outside the variable list of the current
ring. All computations are executed "denominator free" over the
corresponding quotient field, i.e.\ gcd's are canceled out without
request. To avoid this set the \ind{switch 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.} In the given implementation we use the s.f. procedure {\em
qremf} for effective divisibility test. We had some trouble with it
under {\em on factor}.

Additionally it is possible 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.}
\begin{quote}
\verb|setrules!* r|\index{setrules}

\pbx{converts an algebraic mode rules list $r$ as e.g.\ used in
WHERE statements into the internal CALI format.}
\end{quote}

\subsection{The 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 \ind{module ring} exports among others the selectors
\ind{ring\_names}, \ind{ring\_degrees}, \ind{ring\_tag},
\ind{ring\_ecart}, the test function \ind{ring\_isnoetherian} and the
transfer procedures from/to an (appropriate, printable by
\ind{mathprint}) algebraic prefix form \ind{ring\_from\_a} (including
extensive tests of the supplied parameters for consistency) and
\ind{ring\_2a}.

The following procedures allow 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|setring!* <ring> |\index{setring}

\pbx{sets {\em cali!=basering} and checks for consistency with the
\ind{switch 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!*|, \verb|eliminationorder!*|, and
\verb|blockorder!*|
\index{degreeorder}
\index{localorder}
\index{eliminationorder}
\index{blockorder}
define term order matrices in full analogy to algebraic mode.
\medskip

There are three ring constructors for special purposes:
\begin{quote}
\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|ring_rlp(r,u)|\index{ring\_rlp}

\pbx{$u$ is a subset of the names of the ring $r$. Returns the ring
$r$, but with a term order ``first degrevlex on $u$, then the order on
r''.}

\verb|ring_lp(r,u)|\index{ring\_lp}

\pbx{As $rlp$, but with a term order ``first lex on $u$, then the
order on r''.}
\end{quote}

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

\subsection{Monomials}

The current version uses a place-driven exponent representation
closely related to a vector model. This model handles term orders  on $S$
and module term orders on $S^c$ 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
{\em current ring} (\ind{cali!=basering}) and {\em current (monomial)
weights} of the free generators $e_i, i=1,\ldots,c$, of $S^c$
(\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 as an assoc. list 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}

As procedures there are selectors for the module component, the exponent and
the degree parts, comparison procedures, procedures for the management of
the module component and the degree vector, monomial arithmetic, transfer
from/to prefix form, and more special tools.

\subsection{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{tcah}. Here $ec(t_i)$ denotes the ecart of the term $t_i$, i.e.\
the scalar product of the exponent vector of $t_i$ (including the
monomial weight of the module generator) with the ecart vector of the
current base ring.

As procedures there are selectors, dpoly arithmetic including the management
of the module component, procedures for reordering (and reevaluating)
polynomials wrt.\ new term order degrees, for extracting common base
coefficient or monomial factors, for transfer from/to prefix form and for
homogenization and dehomogenization (wrt.\ the current ecart vector).

Two advanced procedures use ideal theory ingredients:
\begin{quote}
\verb|dp_pseudodivmod(g,f)|\index{dp\_pseudodivmod}

\pbx{returns a dpoly list $\{q,r,z\}$ such that $z\cdot g = q\cdot f +
r$ and $z$ is a dpoly unit (i.e.\ a scalar for Noetherian term
orders). For non Noetherian term orders the necessary modifications
are described in \cite{ala}.

$g, f$ and $r$ belong to the same free module or ideal.
}

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


\subsection{Base Lists}

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 with the following
procedures:
\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}

Further there are procedures for selection and construction of base
elements and for the manipulation of lists of base elements as e.g.\
sorting, renumbering, reordering, simplification, deleting zero base
elements, transfer from/to prefix form, homogenization and dehomogenization.

\subsection{Dpoly Matrices}

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$.

\item New in v.\ 2.2 there is a \ind{gb-tag} (\ind{dpmat\_gbtag} m),
indicating that the given base list is already a \gr basis (under the
given term order).
\end{itemize}

The \ind{module dpmat} contains selectors, constructors, and the
algorithms for the basic management of this data structure as e.g.\
file transfer, transfer from/to algebraic prefix forms, reordering,
simplification, extracting row degrees and leading terms, dpmat matrix
arithmetic, homogenization and dehomogenization.

The modules {\em matop} and {\em quot} collect more advanced procedures
for the algebraic management of dpmats.

\subsection{Extending the REDUCE Matrix Package}

In v.\ 2.2 minors, Jacobian matrix, and Pfaffians are available for
general REDUCE matrices. They are collected in the \ind{module
calimat} and allow to define procedures in more generality, especially
allowing variable exponents in polynomial expressions. Such a
generalization is especially useful for the investigation of whole
classes of examples that may be obtained from a generic one by
specialization. In the following $m$ is a matrix given in algebraic
prefix form.
\begin{quote}
\verb|matjac(m,l)|\index{matjac}

\pbx{returns the Jacobian matrix of the ideal $m$ (given as an
algebraic mode list) with respect to the variable list $l$.}

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

\pbx{returns the matrix of $k$-minors of the matrix $m$.}

\verb|ideal_of_minors(m,k)|\index{ideal\_of\_minors}

\pbx{returns the ideal of the $k$-minors of the matrix $m$.}

\verb|pfaffian m|\index{pfaffian}

\pbx{returns the pfaffian of a skewsymmetric matrix $m$.}

\verb|ideal_of_pfaffians(m,k)|\index{ideal\_of\_pfaffians}

\pbx{returns the ideal of the $2k$-pfaffians of the skewsymmetric
matrix $m$.}

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

\pbx{returns a random linear form in algebraic prefix form in the
supplied variables $vars$ with integer coefficients bounded by the
supplied $bound$.}

\verb|singular_locus!*(m,c)|\index{singular\_locus}

\pbx{returns the singular locus of $m$ (as dpmat). $m$ must be an
ideal of codimension $c$ given as a list of polynomials in prefix
form. {\tt Singular\_locus} computes the ideal generated by the
corresponding Jacobian and $m$ itself.}
\end{quote}

\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 and may be accessed
(symbolically).

\subsection{Normal Form Algorithms}

For v.\ 2.2 we completely revised the implementation of normal form
algorithms due to the insight obtained from our investigations of
normal form procedures for local term orders in \cite{ala} and
\cite{tcah}. It allows a common handling of Noetherian and non
Noetherian term orders already on this level thus making superfluous
the former duplication of reduction procedures in the modules {\em
red} and {\em mora} as in v.\ 2.1.
\medskip

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}. In v.\ 2.2 we
sort solely by the dpoly length, since the introduction of
\ind{red\_TopRedBE}, i.e.\ reduction with bounded ecart, guarantees
termination also for non Noetherian term orders. Overload red\_better
for other reduction strategies.
\medskip

Reduction procedures produce for a given ideal basis $B\subset S$ and
a polynomial $f\in S$ 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. Following up the reduction
steps one can even produce a presentation of $h-u\cdot f$ as a
polynomial combination of the base elements in $B$.

More general, given for $f_i\in B$ and $f$ representations $f_i =
\sum{r_{ik}e_k} = R_i\cdot E^T$ and $f=R\cdot E^T$ as polynomial
combinations wrt.\ a fixed basis $E$ one can produce such a
presentation also for $h$. For this purpose the dpoly $f$ and its
representation are collected into a base element and reduced
simultaneously by the base list $B$, that collects the base elements
and their representations.
\medskip

The main procedures of the newly designed reduction package are the
following:
\begin{quote}
\verb|red_TopRedBE(bas,model)|\index{red\_TopRedBE}

\pbx{Top reduction with bounded ecart of the base element $model$ by
the base list $bas$, i.e.\ only reducing the top term and only with
base elements with ecart bounded by that of $model$.}

\verb|red_TopRed(bas,model)|\index{red\_TopRed}

\pbx{Top reduction of $model$, but without restrictions.}

\verb|red_TailRed(bas,model)|\index{red\_TailRed}

\pbx{Make tail reduction on $model$, i.e.\ top reduction on the tail
terms. For convergence this uses reduction with bounded ecart for non
Noetherian term orders and full reduction otherwise.}
\medskip

There is a common \ind{red\_TailRedDriver} that takes a top reduction
function as parameter. It can be used for experiments with other top
reduction procedure combinations.

\verb|red_TotalRed(bas,model)|\index{red\_TotalRed}

\pbx{A terminating total reduction, i.e. for Noetherian term orders
the classical one and for local term orders using tail reduction with
bounded ecart.}

\verb|red_Straight bas|\index{red\_Straight}

\pbx{Reduce (with {\em red\_TailRed}) the tails of the polynomials in
the base list $bas$.}

\verb|red_TopInterreduce bas|\index{red\_TopInterreduce}

\pbx{Reduces the base list $bas$ with $red\_TopRed$ until it
has pairwise incomparable leading terms, computes correct
representation parts, but does no tail reduction.}

\verb|red_Interreduce bas|\index{red\_Interreduce}

\pbx{Does top and, if {\tt on red\_total}, also tail interreduction on
the base list $bas$.}
\end{quote}

Usually, e.g.\ for ideal generation problems, there is no need to care
about the multiplier $u$. If nevertheless one needs its value, the
base element $f$ may be prepared with \ind{red\_prepare} to collect
this information in the 0-slot of its representation part. Extract
this information with \ind{red\_extract}.
\begin{quote}
\verb|red_redpol(bas,model)|\index{red\_redpol}

\pbx{combines this tool with a total reduction of the base element
$model$ and returns a dotted pair

\centerline{$(<reduced\ model> . <dpoly\ unit\ multiplier>)$.}}
\end{quote}

Advanced applications call the interfacing procedures
\begin{quote}
\verb|interreduce!* m|\index{interreduce}

\pbx{that returns an interreduced basis of the dpmat $m$.}

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

\pbx{that returns the dotted 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{that 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 necessary computational effort. Hence for local term
orders one should try to remove polynomial units as soon as they
are detected. To remove them from base elements in an early stage of
the computation one can either try the (cheap) test, whether $f\in S$
is of the form $\langle monomial\rangle *\langle polynomial\
unit\rangle$  or factor $f$ completely and remove polynomial unit
factors. For base elements this may be done with
\ind{bas\_detectunits} or \ind{bas\_factorunits}.

Moreover there are two switches \ind{detectunits} and
\ind{factorunits}, both off by default, that force such automatic
simplifications during more advanced computations.

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

\subsection{The \gr and Standard Basis Algorithms}

There is now a unique \ind{module groeb} that contains the \gr
resp. standard basis algorithms with syzygy computation facility and
related topics. There are common procedures (working for both
Noetherian and non Noetherian term orders)
\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 outer \gr engine (now also common for both
Noetherian and non Noetherian term orders)
\begin{quote}
\verb|groeb_stbasis(m,mgb,ch,syz)|\index{groeb\_stbasis}
\end{quote}
that returns, applied to the dpmat $m$, three dpmats $g,c,s$ with
\begin{quote}
$g$ --- the minimal reduced \gr basis of $m$ if $mgb=t$,

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

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

The next layer manages the preparation of the representation parts
of the base elements to carry the syzygy information, calls the
{\em general internal driver}, and extracts the relevant information
from the result of that computation. The general internal driver
branches according to different reduction functions into several
versions. Upto now there are three different strategies for the
reduction procedures for the S-polynomial reduction (different
versions may be chosen via \ind{gbtestversion}):
\begin{enumerate}
\item Total reduction with local simplifier lists. For local term
orders this is (almost) Mora's first version for the tangent cone (the
default).

\item Total reduction with global simplifier list. For local term
orders this is (almost) Mora's SimpStBasis, see \cite{MPT}.

\item Total reduction with bounded ecart.
\end{enumerate}
The first two versions (almost) coincide for Noetherian term
orders. The third version reduces only with bounded ecart, thus
forcing more pairs to be treated than necessary, but usually less
expensive to be reduced. It is not yet well understood, whether this
idea is of practical importance.

\ind{groeb\_lazystbasis} calls the lazy standard basis driver instead,
that implements Mora's lazy algorithm, see \cite{MPT}. As
\ind{groeb\_homstbasis}, the computation of \gr and standard bases via
homogenization (Lazard's approach), it is not fully integrated into
the algebraic interface. Use
\begin{quote}
\verb|homstbasis!* m|\index{homstbasis}

\pbx{for the invocation of the homogenization approach to compute a
standard basis of the dpmat $m$ and}

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

\pbx{for the lazy algorithm.}
\end{quote}
Experts commonly agree that the classical approach is better for
``computable'' examples, but computations done by the author
on large examples indicate, that both approaches are in fact
independent.
\medskip

The pair list management uses the sugar strategy, see \cite{GMNRT},
with respect to the current ecart vector. If the input is homogeneous
and the ecart vector 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.

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!* vars|\index{setmonset}

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

The \gr tools as e.g.\ pair criteria, pair list update, pair
management and S-polynomial construction are available.
\begin{quote}
\verb|groeb_mingb m|\index{groeb\_mingb}

\pbx{extracts a minimal \gr basis from the dpmat $m$, removing base
elements with leading terms, divisible by other leading terms.}

\verb|groeb_minimize(bas,syz)|\index{groeb\_minimize}

\pbx{minimizes the dpmat pair $(bas,syz)$ deleting superfluous base
elements from $bas$ using syzygies from $syz$ containing unit
entries.}
\end{quote}

\subsection{The \gr Factorizer}

If $\bar{k}$ is the algebraic closure of $k$,
$B:=\{f_1,\ldots,f_m\}\subset S$ a finite system of polynomials, and
$C:=\{g_1,\ldots,g_k\}$ a set of side conditions define the {\em
relative set of zeroes}
\[Z(B,C):=\{a\in \bar{k}^n : \forall\ f\in B\ f(a)=0\mbox{ and }
\forall g\in C\ g(a)\neq 0\}.\]
Its Zariski closure is the zero set of $I(B):<\prod C>$.

The \gr factorizer solves the following problem:
\begin{quote}
\it Find a collection $(B_\alpha,C_\alpha)$ of \gr bases $B_\alpha$
and side conditions $C_\alpha$ such that
\[Z(B,C) = \bigcup_\alpha Z(B_\alpha,C_\alpha).\]
\end{quote}
The \ind{module groebf} and the \ind{module triang} contain algorithms
related to that problem, triangular systems, and their generalizations
as described in \cite{fgb} and \cite{efgb}. V. 2.2 thus heavily
extends the algorithmic possibilities that were implemented in former
releases of CALI.

Note that, different to v.\ 2.1, we work with constraint {\em lists}.
\begin{quote}
\verb|groebfactor!*(bas,con)|\index{groebfactor}

\pbx{returns for the dpmat ideal $bas$ and the constraint list $con$
(of dpolys) a minimal list of $(dpmat, constraint\ list)$ pairs with
the desired property.}
\end{quote}
During a preprocessing it splits the submitted basis $bas$ 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
processed. 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.
\begin{quote}
\verb|listgroebfactor!* l|\index{listgroebfactor}

\pbx{proceeds a whole list of dpmats (without constraints) at once and
strips off constraints at the end.}
\end{quote}
\medskip

Using the (ordinary) \gr factorizer even components of different
dimension may keep gluing together. The \ind{extended \gr factorizer}
involves a postprocessing, that guarantees a decomposition into
puredimensional components, given by triangular systems instead of \gr
bases. Triangular systems in positive dimension must not be \gr bases
of the underlying ideal. They should be preferred, since they are more
simple but contain all information about the (quasi) prime component
that they represent. The complete \gr basis of the corresponding
component can be obtained by an easy stable quotient computation, see
\cite{efgb}. We refer to the same paper for the definition of
\ind{triangular systems} in positive dimension, that is consistent
with our approach.
\begin{quote}
\verb|extendedgroebfactor!*(bas,c)| and
\verb|extendedgroebfactor1!*(bas,c)|
\index{extendedgroebfactor} \index{extendedgroebfactor1}

\pbx{return a list of results $\{b_i,c_i,v_i\}$ in algebraic prefix
form such that $b_i$ is a triangular set wrt.\ the variables $v_i$ and
$c_i$ is a list of constraints, such that $b_i:<\prod c_i>$ is the
(puredimensional) recontraction of the zerodimensional ideal
$b_i\bigotimes_k k(v_i)$. For  the first version the recontraction is
not computed, hence the output may be not minimal. The second version
computes recontractions to decide superfluous components already
during the algorithm. Note that the stable quotient computation
involved for that purpose may drastically slow down the whole
attempt.}
\end{quote}
The postprocessing involves a change to dimension zero and invokes
(zero dimensional) triangular system computations from the
\ind{module triang}. In a first step \ind{groebf\_zeroprimes1}
incorporates the square free parts of certain univariate polynomials
into these systems and strips off the constraints (since relative sets
of zeroes in dimension zero are Zariski closed), using a splitting
approach analogous to the \gr factorizer. In a second step, according
to the \ind{switch lexefgb}, either \ind{zerosolve!*} or
\ind{zerosolve1!*} converts these intermediate results into lists of
triangular systems in prefix form. If \ind{lexefgb} is {\tt off} (the
default), the zero dimensional term order is degrevlex and
\ind{zerosolve1!*}, the ``slow turn to lex'' is involved, for {\tt on
lexefgb} the pure lexicographic term order and \ind{zerosolve!*},
M\"ollers original approach, see \cite{Moeller}, are used. Note that
for this term order we need only a single \gr basis computation at
this level.

A third version, \ind{zerosolve2!*}, mixes the first approach with the
FGLM change of term orders. It is not incorporated into the extended
\gr factorizer.

\subsection{Basic Operations on Ideals and Modules}

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

\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}.}
\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|idealquotientX!*(M,I)|\index{idealquotient}

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

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

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

\verb|annihilatorX!* 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{rois}, and reflect some properties of the
original ideal/module. Several parameters of the original ideal or
module may be read off from it as e.g.\ dimension and Hilbert series.

The \ind{module 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{rois} for
definitions.}

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

\pbx{returns the dimension of $coker\ m$ as the size of the largest
independent set.}

\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\footnotemark, 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{rois}).}
\footnotetext{This algorithm is of linear time as opposed to the
problem to determine the dimension of an arbitrary monomial ideal,
that is known to be NP-hard in the number of variables, see
\cite{BS}.}
\end{quote}

\subsection{Hilbert Series}

CALI v. 2.2 now offers also \ind{weighted Hilbert series}, i.e.\
series that may reflect multihomogeneity of ideals and modules. For
this purpose
a weighted Hilbert series has a list of (integer) degree vectors
as second parameter, and the ideal(s) of leading terms are evaluated
wrt.\ these weights. For the output and polynomial arithmetic,
involved during the computation of the Hilbert series numerator, the
different weight levels are mapped onto the first variables of the
current ring. If $w$ is such a weight vector list and $I$ is a
monomial ideal in the polynomial ring $S=k[x_v\,:\,v\in V]$ we get
(using multi exponent notation)
\[H(S/I,t) := \sum_{\alpha}{|\{x^a\not\in I\,:\,w(a)=\alpha\}|\cdot
t^\alpha} = \frac{Q(t)}{\prod_{v\in V}{\left(1-t^{w(x_v)}\right)} }\]
for a certain polynomial Hilbert series numerator $Q(t)$. $H(R/I,t)$
is known to be a rational function with pole order at $t=1$ equal to
$dim\ R/I$. Note that \ind{WeightedHilbertSeries} returns a {\em
reduced} rational function where the gcd of numerator and denominator
is canceled out.

(Non weighted) Hilbert series call the weighted Hilbert series
procedure with a single weight vector, the ecart vector of the current
ring.

The Hilbert series numerator $Q(t)$ is computed using (the obvious
generalizations to the weighted case of) the algorithms in \cite{BS}
and \cite{BCRT}. 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. Choose the version with
\ind{hftestversion} $n$, $n=1,\,2$. Bayer/Stillman's approach ($n=1$)
is the default. In the following $m$ is a dpmat and \gr basis.

\begin{quote}
\verb|hf_whilb(m,w)| \index{hf\_whilb}

\pbx{returns the weighted Hilbert series numerator $Q(t)$ of $m$
according to the version chosen with \ind{hftestversion}.}

\verb|WeightedHilbertSeries!*(m,w)| \index{WeightedHilbertSeries}

\pbx{returns the weighted Hilbert series reduced rational function of
$m$ as s.q.}

\verb|HilbertSeries!*(m,w)| \index{HilbertSeries}

\pbx{returns the Hilbert series reduced rational function of $m$ wrt.\
the ecart vector of the current ring as s.q.}

\verb|hf_whilb3(u,w)| and \verb|hf_whs_from_resolution(u,w)|
\index{hf\_whilb3}
\index{hf\_whs\_from\_resolution}

\pbx{compute the weighted Hilbert series numerator and the
corresponding reduced rational function from (the column degrees of) a
given resolution $u$.}

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

\pbx{returns the value of the numerator of the reduced Hilbert series
of $m$ at $t=1$. i.e.\ the sum of its coefficients. For the standard
ecart this is the degree of $coker\ m$.}
\end{quote}

\subsection{Resolutions}

Resolutions of ideals and modules, represented as lists of dpmats, are
computed via repeated syzygy computation with minimization steps
between them to get minimal bases and generators of syzygy
modules. Note that the algorithms apply simultaneously to both
Noetherian and non Noetherian term orders. For compatibility reasons
with further releases v. 2.2 introduces a second parameter to
bound the number of syzygy modules to be computed, since Hilbert's
syzygy theorem applies only to regular rings.
\begin{quote}
\verb|Resolve!*(m,d)| \index{Resolve}

\pbx{computes a minimal resolution of the dpmat $m$, i.e. a list of
dpmats $\{s_0, s_1, s_2,\ldots\}$, where $s_k$ is the $k$-th syzygy
module of $m$, upto part $s_d$.}

\verb|BettiNumbers!* c| and \verb|GradedBettiNumbers!* c|
\index{BettiNumbers}
\index{GradedBettiNumbers}

\pbx{returns the Betti numbers resp.\ the graded Betti numbers of the
resolution $c$, i.e.\ the list of the lengths resp.\ the degree lists
(according to the ecart) themselves of the dpmats in $c$.}
\end{quote}

\subsection{Zero Dimensional Ideals and Modules}

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

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

\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_borderbasis m| \index{odim\_borderbasis}

\pbx{that returns a border basis, see \cite{MMM}, of the
zero dimensional dpmat $m$ as a  list of base elements.}

\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 zero dimensional.}

\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$, that belongs to the
zero dimensional dpmat ideal $m$, using Buchberger's approach
\cite{B1}.}
\end{quote}

\subsection{Primary Decomposition and Related Algorithms}

The algorithms of the \ind{module 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}. Version
2.2.1 fixes a serious bug detecting superfluous embedded primary
components, see section \ref{221}, and contains now a second primary
decomposition algorithm, based on ideal separation, as standard. For a
discussion about embedded primes and the ideal separation approach,
see \cite{primary}.


CALI 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\footnote{\ind{prime!=decompose2} implements this strategy in
the symbolic mode layer.}.

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

\pbx{returns the radical of the zero dimensional 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 zero dimensional, using the (sparse) general position
argument from \cite{KW}.}

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

\pbx{computes the primary components of the zero dimensional dpmat $m$
using prime splitting with the prime ideals of $Ann\ F/M$. It returns
a list of pairs 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 zero dimensional 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 pairs as in
{\em zeroprimarydecomposition!*}.}

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

\pbx{computes the primary components of the dpmat $m$ along the lines
of \cite{GTZ}. 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 \ind{module 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,vars)|\index{affine\_monomial\_curve}

\pbx{$l$ is a list of integers, $vars$ 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,vars)|\index{proj\_monomial\_curve}

\pbx{$l$ is a list of integers, $vars$ 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|minimal_generators!* m| \index{minimal\_generators}

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

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

\pbx{tests whether the dpoly $f$ is a non zero divisor on $coker\
m$. $m$ must be a \gr basis.}

\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.)}

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

\pbx{finds a heuristically optimal variable order by the approach in
\cite{BGK} and returns the corresponding list of variables.}
\end{quote}


\subsection{Dual Bases}


For the general ideas underlying the dual bases approach see e.g.\
\cite{MMM}. This paper explains, that constructive problems from very
different areas of commutative algebra can be formulated in a unified
way as the computation of a basis for the intersection of the kernels
of a finite number of linear functionals generating a dual
$S$-module. Our implementation honours
this point of view, presenting two general drivers \ind{dualbases} and
\ind{dualhbases} for the computation of such bases (even as submodules
of a free module $M=S^m$) with affine resp.\ projective dimension zero.

Such a collection of $N$ linear functionals
\[L\,:\, M=S^m \longrightarrow k^N\]
should be given through values $\{[e_i,L(e_i)], i=1,\ldots,m\}$ on the
generators $e_i$ of $M$ and an evaluation function {\tt
evlf([p,L(p)],x)}, that evaluates $L(p\cdot x)$ from $L(p)$ for $p\in
M$ and the variable $x\in S$.

\ind{dualbases} starts with a list of such generator/value constructs
generating $M$ and performs Gaussian reduction on expressions $[p\cdot
x,L(p\cdot x)]$, where $p$ was already processed, $L(p)\neq 0$, and
$x\in S$ is a variable. These elements are processed in ascending order
wrt.\ the term order on $M$. This guarantees both termination and that
the resulting basis of $ker\ L$ is a \gr basis. The $N$ values of $L$
are attached to $N$ variables, that are ordered linearly. Gaussian
elimination is executed wrt.\ this variable order.

To initialize the dual bases driver one has to supply the basic
generator/value list (through the parameter list; for ideals just the
one element list containing the generator $[1\in S,L(1)]$), the
evaluation function, and the linear algebra variable order. The latter
are supplied via the property list of {\tt cali} as properties {\tt
evlf} and {\tt varlessp}. Different applications need more entries
on the property list of {\tt cali} to manage the communication between
the driver and the calling routine.

\ind{dualhbases} realizes the same idea for (homogeneous) ideals and
modules of (projective) dimension zero. It produces zerodimensional
``slices'' with ascending degree until it reaches a supremum supplied
by the user, see \cite{MMM} for details.
\medskip

Applications concern affine and projective defining ideals of a finite
number of points\footnote{This substitutes the ``brute force'' method
computing the corresponding intersections directly as it was
implemented in v. 2.1. The new approach is significantly faster. The
old stuff is available as \ind{affine\_points1!*} and
\ind{proj\_points1!*}.} and two versions (with and without precomputed
border basis) of term order
changes for zerodimensional ideals and modules as first described in
\cite{FGLM}.
\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. This
procedure returns the defining ideal of the collection of points in
affine space with coordinates given by the rows of $m$. Note that $m$
may contain parameters. In this case $k$ is treated as rational
function field.}

\verb|change_termorder!*(m,r)| and \verb|change_termorder1!*(m,r)|
\index{change\_termorder}
\index{change\_termorder1}

\pbx{$m$ is a \gr basis of a zero dimensional ideal wrt.\ the current
base ring. These procedures change the current ring to $r$ and compute
the \gr basis of $m$ wrt.\ the new ring $r$. The former uses a
precomputed border basis.}

\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. This
procedure returns the defining ideal of the collection of points in
projective space with homogeneous coordinates given by the rows of
$m$. Note that $m$ may as for {\tt affine\_points} contain
parameters.}
\end{quote}

\pagebreak

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

Here we give a short description, ordered alphabetically, of {\bf
algebraic} procedures offered by CALI in the algebraic mode
interface\footnote{It does {\bf not} contain switches, get\ldots\
procedures, setting trace level and related stuff.}.

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\footnote{Different to v. 2.1 a \gr basis will be computed
automatically, if necessary.}, $gbr$ for one with precomputed
resolution. For the mechanism of \ind{bounded identifier} see the
section ``Algebraic Mode Interface''.

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

\pbx{$l$ is a list of integers, $vars$ 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)$.}

\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. This
procedure returns the defining ideal of the collection of points in
affine space with coordinates given by the rows of $m$. Note that $m$
may contain parameters. In this case $k$ is treated as rational
function field.}

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

\pbx{Computes the analytic spread of $m$.}

\verb|annihilator m| \index{annihilator}

\pbx{returns the annihilator of the dpmat $m\subseteq S^c$, i.e.\
$Ann\ S^c/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|bettiNumbers gbr| \index{bettiNumbers}

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

\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|change_termorder(m,r)| and \verb|change_termorder1(m,r)|
\index{change\_termorder}
\index{change\_termorder1}

\pbx{Change the current ring to $r$ and compute the \gr basis of $m$
wrt.\ the new ring $r$ by the FGLM approach. The former uses
internally a precomputed border basis.}

\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 (classical) 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 to 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 \verb|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|easyprimarydecomposition m| \index{easyprimarydecomposition}

\pbx{a short primary decomposition using ideal separation of isolated
primes of $m$, that yields true results only for modules without
embedded components. Returns a list of $\{component, associated\
prime\}$ pairs.}

\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|eqhull m| \index{eqhull}

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

\verb|extendedgroebfactor(m,c)| and \verb|extendedgroebfactor1(m,c)|
\index{extendedgroebfactor} \index{extendedgroebfactor1}

\pbx{return for a polynomial ideal $m$ and a list of (polynomial)
constraints $c$ a list of results $\{b_i,c_i,v_i\}$, where $b_i$ is a
triangular set wrt.\ the variables $v_i$ and $c_i$ is a list of
constraints, such that
$Z(m,c) = \bigcup Z(b_i,c_i)$. For the first version the output may be
not minimal. The second version decides superfluous components already
during the algorithm.}

\verb|gbasis gb| \index{gbasis}

\pbx{returns the \gr resp. local standard basis of $gb$.}

\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|GradedBettinumbers gbr| \index{GradedBettinumbers}

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

\verb|groebfactor(m[,c])|\index{groebfactor}

\pbx{returns for the dpmat ideal $m$ and an optional constraint list
$c$ a (reduced) list of dpmats such that the union of their zeroes is
exactly $Z(m,c)$. Factors all polynomials involved in the \gr
algorithms of the partial results.}

\verb|HilbertSeries gb| \index{HilbertSeries}

\pbx{returns the Hilbert series of $gb$ with respect to the current
ecart vector.}

\verb|homstbasis m| \index{homstbasis}

\pbx{computes the standard basis of $m$ by Lazard's homogenization
approach.}

\verb|ideal2mat m| \index{ideal2mat}

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

\verb|ideal_of_minors(mat,k)| \index{ideal\_of\_minors}

\pbx{computes the generators for the ideal of $k$-minors of the matrix
$mat$.}

\verb|ideal_of_pfaffians(mat,k)| \index{ideal\_of\_pfaffians}

\pbx{computes the generators for the ideal of the $2k$-pfaffians of
the skewsymmetric matrix $mat$.}

\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{rois} for submodules of free modules.}

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

\pbx{initializes 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|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|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|lazystbasis m| \index{lazystbasis}

\pbx{computes the standard basis of $m$ by the lazy algorithm, see
e.g.\ \cite{MPT}.}

\verb|listgroebfactor in| \index{listgroebfactor}

\pbx{computes for the list $in$ of ideal bases a list $out$ of \gr
bases by the \gr factorization method, such that
$\bigcup_{m\in in}Z(m) = \bigcup_{m\in out}Z(m)$.}

\verb|mat2list m| \index{mat2list}

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

\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 {\tt 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}

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

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

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

\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|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 matrix of minors of size $b\times b$ of the matrix
$m$.}

\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|nzdp(f,m)| \index{nzdp}

\pbx{tests whether the dpoly $f$ is a non zero divisor on $coker\
m$.}

\verb|pfaffian mat| \index{pfaffian}

\pbx{returns the pfaffian of a skewsymmetric matrix $mat$.}

\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|primarydecomposition m|
\index{primarydecomposition}

\pbx{returns the primary decomposition of the dpmat $m$ as a list of
$\{component, associated\ prime\}$ pairs.}

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

\pbx{$l$ is a list of integers, $vars$ 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 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. This
procedure returns the defining ideal of the collection of points in
projective space with homogeneous coordinates given by the rows of
$m$. Note that $m$ may as for {\tt affine\_points} contain
parameters.}

\verb|radical m| \index{radical}

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

\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|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|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|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|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 generators
of the ideal of the $c$-minors of the Jacobian of $M$.}

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

\pbx{tests, whether $m$ is a submodule of $gb$ (returns YES or NO).}

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

\verb|unmixedradical m| \index{unmixedradical}

\pbx{returns the unmixed radical of the 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.}

\verb|WeightedHilbertSeries(m,w)| \index{WeightedHilbertSeries}

\pbx{returns the weighted Hilbert series of the dpmat $m$. Note that
$m$ is not a bounded identifier and hence not checked to be a \gr
basis. $w$ is a list of integer weight vectors.}

\verb|zeroprimarydecomposition m| \index{zeroprimarydecomposition}

\pbx{returns the primary decomposition of the zerodimensional dpmat
$m$ as a list of $\{component, associated\ prime\}$ pairs.}

\verb|zeroprimes m| \index{zeroprimes}

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

\verb|zeroradical gb| \index{zeroradical}

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

\verb|zerosolve m|, \verb|zerosolve1 m| and  \verb|zerosolve2 m|
\index{zerosolve}\index{zerosolve1}\index{zerosolve2}

\pbx{Returns for a zerodimensional ideal a list of triangular systems
that cover $Z(m)$. {\tt Zerosolve} needs a pure lex.\ term order for
the ``fast'' turn to lex.\ as described in \cite{Moeller}, {\tt
Zerosolve1} is the ``slow'' turn to lex.\ as described in \cite{efgb},
and {\tt Zerosolve2} incorporated the FGLM term order change into {\tt
Zerosolve1}.}
\end{quote}
\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 & --- & ---\\

groeb & \gr basis algorithm and related ones & --- & ---\\

groebf & the \gr factorizer and its extensions  & --- & ---\\

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

hf & weighted Hilbert series & -- & -- \\

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

intf & Interface to algebraic mode & --- & ---\\

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

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

scripts & Advanced applications  & --- & ---\\

calimat & Extension of the matrix package & --- & ---\\

lf & The dual bases approach & --- & ---\\

triang & (Zero dimensional) triangular systems & --- & ---\\
\hline
\end{tabular}
\vfill
\pagebreak

\begin{theindex}

  \item affine\_monomial\_curve, 33, 36
  \item affine\_points, 7, 35, 36
  \item affine\_points1!*, 35
  \item algebraic numbers, 13
  \item analytic\_spread, 33, 36
  \item annihilator, 28, 36
  \item assgrad, 33, 36

  \indexspace

  \item bas\_detectunits, 23
  \item bas\_factorunits, 23
  \item bas\_getrelations, 20
  \item bas\_removerelations, 20
  \item bas\_setrelations, 20
  \item base coefficients, 13
  \item base elements, 19
  \item base ring, 9, 17
  \item basis, 13
  \item bcsimp, 14
  \item BettiNumbers, 30, 36
  \item binomial, 7
  \item blockorder, 10, 18
  \item blowup, 7, 33, 36
  \item border basis, 8
  \item bounded identifier, 13, 36

  \indexspace

  \item cali, 16
  \item cali!=basering, 9, 16, 18
  \item cali!=degrees, 12, 16, 18
  \item cali!=monset, 16, 25
  \item change of term orders, 7
  \item change\_termorder, 35, 37
  \item change\_termorder1, 35, 37
  \item clearcaliprintterms, 16
  \item codim, 29, 37
  \item column degree, 12

  \indexspace

  \item degree, 30, 37
  \item degree vectors, 9
  \item degreeorder, 10, 18
  \item degsfromresolution, 37
  \item deleteunits, 23, 37
  \item detectunits, 14, 23
  \item dim, 8, 29, 37
  \item dimzerop, 31, 37
  \item directsum, 37
  \item dmode, 13
  \item dp\_pseudodivmod, 14, 19, 28
  \item dpgcd, 19, 37
  \item dpmat, 8, 12, 13, 20
  \item dpmat\_coldegs, 20
  \item dpmat\_cols, 20
  \item dpmat\_gbtag, 20
  \item dpmat\_list, 20
  \item dpmat\_rows, 20
  \item dual bases, 6, 7, 34, 35

  \indexspace

  \item easydim, 26, 29, 37
  \item easyindepset, 29, 37
  \item easyprimarydecomposition, 32, 37
  \item ecart, 3, 19
  \item ecart vector, 8, 11, 40
  \item efgb, 16
  \item eliminate, 7, 27, 38
  \item eliminationorder, 10, 18
  \item eqhull, 32, 38
  \item evlf, 17
  \item extended \gr factorizer, 7, 15, 26
  \item extendedgroebfactor, 26, 38
  \item extendedgroebfactor1, 26, 38

  \indexspace

  \item factorunits, 15, 23
  \item flatten, 8
  \item free identifier, 13

  \indexspace

  \item gb-tag, 8, 20
  \item gbasis, 24, 38
  \item gbtestversion, 7, 8, 16, 24
  \item getdegrees, 12
  \item getecart, 11
  \item getkbase, 31, 38
  \item getleadterms, 38
  \item getring, 11
  \item getrules, 13
  \item global procedures, 5
  \item GradedBettiNumbers, 30
  \item gradedbettinumbers, 38
  \item groeb, 7
  \item groeb!=rf, 16
  \item groeb\_homstbasis, 24
  \item groeb\_lazystbasis, 24
  \item groeb\_mingb, 25
  \item groeb\_minimize, 25
  \item groeb\_stbasis, 24
  \item groebf\_zeroprimes1, 27
  \item groebfactor, 26, 38

  \indexspace

  \item hardzerotest, 15
  \item hf!=hf, 16
  \item hf\_whilb, 30
  \item hf\_whilb3, 30
  \item hf\_whs\_from\_resolution, 30
  \item hftestversion, 8, 16, 30
  \item HilbertSeries, 8, 11, 30, 38
  \item homstbasis, 25, 38

  \indexspace

  \item ideal2mat, 12, 38
  \item ideal\_of\_minors, 21, 38
  \item ideal\_of\_pfaffians, 21, 39
  \item idealpower, 39
  \item idealprod, 39
  \item idealquotient, 27, 28, 39
  \item ideals, 12
  \item idealsum, 39
  \item indepvarsets, 29, 39
  \item initmat, 39
  \item internal procedures, 5
  \item interreduce, 23, 39
  \item isolatedprimes, 32, 39
  \item isprime, 32, 39
  \item iszeroradical, 39

  \indexspace

  \item lazy, 7
  \item lazystbasis, 25, 39
  \item lexefgb, 15, 27
  \item lexicographic, 9
  \item listgroebfactor, 26, 39
  \item listminimize, 6
  \item listtest, 6
  \item local procedures, 5
  \item localorder, 10, 18

  \indexspace

  \item map, 32
  \item mat2list, 8, 12, 39
  \item matappend, 40
  \item mathomogenize, 40
  \item mathprint, 17
  \item matintersect, 7, 27, 40
  \item matjac, 21, 40
  \item matqquot, 28, 40
  \item matquot, 28, 40
  \item matstabquot, 28, 40
  \item matsum, 40
  \item minimal\_generators, 34, 40
  \item minors, 21, 40
  \item mod, 23, 40
  \item modequalp, 8, 27, 40
  \item module
        \subitem bcsf, 17
        \subitem cali, 5
        \subitem calimat, 8, 21
        \subitem dpmat, 20
        \subitem groeb, 24
        \subitem groebf, 7, 26
        \subitem lf, 7, 17
        \subitem moid, 28
        \subitem mora, 7
        \subitem odim, 7, 31
        \subitem prime, 31
        \subitem ring, 17
        \subitem scripts, 7, 32
        \subitem triang, 26, 27
  \item module quotient, 27
  \item module term order, 12
  \item modulequotient, 28, 40
  \item modules, 12
  \item moid\_primes, 29

  \indexspace

  \item Noetherian, 3, 15
  \item normalform, 23, 41
  \item nzdp, 34, 41

  \indexspace

  \item odim\_borderbasis, 31
  \item odim\_parameter, 31
  \item odim\_up, 31
  \item oldbasis, 17
  \item oldborderbasis, 17
  \item oldring, 17

  \indexspace

  \item pfaffian, 21, 41
  \item preimage, 7, 32, 41
  \item primarydecomposition, 7, 41
  \item printterms, 16
  \item proj\_monomial\_curve, 33, 41
  \item proj\_points, 7, 35, 41
  \item proj\_points1!*, 35

  \indexspace

  \item radical, 32, 41
  \item random\_linear\_form, 21, 41
  \item ratpreimage, 33, 41
  \item red, 7
  \item red\_better, 22
  \item red\_extract, 23
  \item red\_Interreduce, 23
  \item red\_prepare, 23
  \item red\_redpol, 23
  \item red\_Straight, 22
  \item red\_TailRed, 22
  \item red\_TailRedDriver, 22
  \item red\_TopInterreduce, 23
  \item red\_TopRed, 22
  \item red\_TopRedBE, 22
  \item red\_total, 15
  \item red\_TotalRed, 22
  \item Resolve, 7, 30, 42
  \item reverse lexicographic, 8, 9
  \item ring, 13
  \item ring\_2a, 17
  \item ring\_define, 17
  \item ring\_degrees, 17
  \item ring\_ecart, 17
  \item ring\_from\_a, 17
  \item ring\_isnoetherian, 17
  \item ring\_lp, 18
  \item ring\_names, 17
  \item ring\_rlp, 18
  \item ring\_sum, 18
  \item ring\_tag, 17
  \item rules, 16

  \indexspace

  \item savemat, 42
  \item setcaliprintterms, 16
  \item setcalitrace, 8, 15
  \item setdegrees, 12, 16
  \item setgbasis, 8, 42
  \item setideal, 13, 14
  \item setkorder, 18
  \item setmodule, 13, 14
  \item setmonset, 16, 25
  \item setring, 7, 9, 11, 14, 16, 18
  \item setrules, 13, 14, 16, 17, 19
  \item sieve, 42
  \item singular\_locus, 21, 42
  \item stable quotient, 27
  \item sublist, 17
  \item submodulep, 27, 42
  \item switch
        \subitem bcsimp, 17
        \subitem hardzerotest, 13
        \subitem lexefgb, 16, 27
        \subitem Noetherian, 10, 18
  \item sym, 7, 34, 42
  \item symbolic\_power, 34, 42
  \item syzygies, 24, 42
  \item syzygies1, 24

  \indexspace

  \item tangentcone, 42
  \item term, 19
  \item trace, 16
  \item tracing, 8
  \item triang, 7
  \item triangular systems, 7, 26

  \indexspace

  \item unmixedradical, 32, 42

  \indexspace

  \item varlessp, 17
  \item varnames, 17
  \item varopt, 34, 43

  \indexspace

  \item WeightedHilbertSeries, 8, 29, 30, 43

  \indexspace

  \item zeroprimarydecomposition, 31, 32, 43
  \item zeroprimes, 31, 43
  \item zeroradical, 31, 43
  \item zerosolve, 15, 27, 43
  \item zerosolve1, 15, 27, 43
  \item zerosolve2, 27, 43

\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. In: Proc. AAECC-10,
LNCS 673 (1993), 76 - 88.
\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. LNCS 296 (1988), 52 - 80.
\bibitem{CLO} D. Cox, J. Little, D. O'Shea: Ideals, varieties, and
algorithms.  Undergraduate Texts in Math., Springer, New York 1992.
\bibitem{E} D. Eisenbud: Commutative algebra with a view toward
algebraic geometry. Springer, 1995.
\bibitem{FGLM} Faugere, Gianni, Lazard, Mora: Efficient computations
of zerodimensional \gr bases by change of ordering. {\it
J. Symb. Comp. \bf 16} (1993), 329 - 344.
\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{rois} H.-G. Gr\"abe: Two remarks on independent sets.
{\it J. Alg. Comb. \bf 2} (1993), 137 - 145.
\bibitem{tcah} H.-G. Gr\"abe: The tangent cone algorithm and
homogenization. {\it J. Pure Applied Alg.\bf 97} (1994), 303 - 312.

\bibitem{ala} H.-G. Gr\"abe: Algorithms in local algebra. To appear

\bibitem{fgb} H.-G. Gr\"abe: On factorized \gr bases. Report Nr. 6
(1994), Inst. f. Informatik, Univ. Leipzig.

To appear in: Proc. ``Computer Algebra in Science and Engineering'',
Bielefeld 1994.

\bibitem{efgb} H.-G. Gr\"abe: Triangular systems and factorized \gr
bases. Report Nr. 7 (1995), Inst. f. Informatik, Univ. Leipzig.

\bibitem{primary} H.-G. Gr\"abe: Factorized \gr bases and primary
decomposition. 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{MMM} M. Marinari, H.-M. M\"oller, T. Mora: \gr bases of
ideals given by dual bases. In: Proc. ISSAC'91, ACM Press 1991, 55 -
63.
\bibitem{Mishra} B. Mishra: Algorithmic Algebra. Springer, New York
1993.
\bibitem{MM} H.-M. M\"oller, F. Mora: New constructive methods in
classical ideal theory. {\it J. Alg. \bf 100} (1986), 138 -178.
\bibitem{Moeller} H.-M. M\"oller: On decomposing systems of polynomial
equations with finitely many solutions. {\em J. AAECC \bf 4} (1993),
217 - 230.
\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. In: {\em Issues in non-linear geometry and
robotics, C.M. Hoffman ed.}, JAI Press.
\bibitem{Ro} L. Robbiano: Computer algebra and commutative algebra.
LNCS 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}
REDUCE Historical
[ REDUCE Sourceforge Project | Historical SVN Repository | GitHub Mirror | SourceHut Mirror | NotABug Mirror | Chisel Mirror | Chisel RSS ]