Artifact 7c41c16897ef2813b395c44f6d4db514a18d1aab11a0bb35f923b296a9cf0ace:
- File
r36/doc/CALI.TEX
— part of check-in
[152fb3bdbb]
at
2011-10-17 17:58:33
on branch master
— svn:eol-style, svn:executable and line endings for files
in historical/r36 treegit-svn-id: https://svn.code.sf.net/p/reduce-algebra/code/trunk/historical@1480 2bfe0521-f11c-4a00-b80e-6202646ff360 (user: schoepf@users.sourceforge.net, size: 115824) [annotate] [blame] [check-ins using] [more...]
% 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}