1% CALI user documentation 2% H.-G. Graebe | Univ. Leipzig | Version 2.2.1 3 4\documentstyle[11pt]{article} 5\date{June 28, 1995} 6 7\textheight 21cm 8\textwidth 15cm 9\voffset -60pt 10\hoffset -45pt 11 12\newcommand{\gr}{Gr\"obner } 13\newcommand{\x}{{\bf x}} 14\newcommand{\ind}[1]{{\em #1}\index{#1}} 15\newcommand{\pbx}[1]{\mbox{}\hfill \parbox[t]{12cm}{#1} \pagebreak[3]} 16\newcommand{\nl}{\newline \hspace*{5mm}} 17 18\makeindex 19 20\title{CALI\\[20pt] A REDUCE Package for \\ 21 Commutative Algebra \\Version 2.2.1} 22 23\author{ 24Hans-Gert Gr\"abe \\[15pt] 25Universit\"at Leipzig\\ 26Institut f\"ur Informatik \\ 27Augustusplatz 10 -- 11\\ 2804109 Leipzig / Germany\\[20pt] 29email: graebe@informatik.uni-leipzig.de} 30 31\begin{document} 32 33\maketitle 34 35\vfill 36Key words: 37affine and projective monomial curves, 38affine and projective sets of points, 39analytic spread, 40associated graded ring, 41blowup, 42border bases, 43constructive commutative algebra, 44dual bases, 45elimination, 46equidimensional part, 47extended \gr factorizer, 48free resolution, 49\gr algorithms for ideals and module, 50\gr factorizer, 51ideal and module operations, 52independent sets, 53intersections, 54lazy standard bases, 55local free resolutions, 56local standard bases, 57minimal generators, 58minors, 59normal forms, 60pfaffians, 61polynomial maps, 62primary decomposition, 63quotients, 64symbolic powers, 65symmetric algebra, 66triangular systems, 67weighted Hilbert series, 68primality test, 69radical, 70unmixed radical. 71 72\pagebreak 73 74\tableofcontents 75 76\pagebreak 77 78\section{Introduction} 79 80This package contains algorithms for computations in commutative 81algebra closely related to the \gr algorithm for ideals and modules. 82Its heart is a new implementation of the \gr algorithm\footnote{The 83data representation even for polynomials is different from that given 84in the {\tt groebner} package distributed with REDUCE (and rests on ideas 85used in the {\tt dipoly} package).} that allows the computation of 86syzygies, too. This implementation is also applicable to submodules of 87free modules with generators represented as rows of a matrix. 88 89Moreover CALI contains facilities for local computations, using a 90modern implementation of Mora's standard basis algorithm, see 91\cite{MPT} and \cite{tcah}, that works for arbitrary term orders. 92The full analogy between modules over the local ring \linebreak[1] 93$k[x_v:v\in H]_{\bf m}$ and homogeneous (in fact H-local) modules 94over $k[x_v:v\in H]$ is reflected through the switch 95\ind{Noetherian}. Turn it on (\gr basis, the default) or off (local 96standard basis) to choose appropriate algorithms 97automatically. In v.\ 2.2 we present an unified approach to both 98cases, using reduction with bounded ecart for non Noetherian term 99orders, see \cite{ala} for details. This allows to have a common 100driver for the \gr algorithm in both cases. 101 102CALI extends also the restricted term order facilities of the {\tt 103groebner} package, defining term orders by degree vector lists, and 104the rigid implementation of the sugar idea, by a more flexible 105\ind{ecart} vector, in particular useful for local computations, see 106\cite{tcah}. 107\medskip 108 109The package was designed mainly as a symbolic mode programming 110environment extending the build-in facilities of REDUCE for the 111computational approach to problems arising naturally in commutative 112algebra. An algebraic mode interface accesses (in a more rigid frame) 113all important features implemented symbolically and thus 114should be favored for short sample computations. 115 116On the other hand, tedious computations are strongly recommended to 117be done symbolically since this allows considerably more flexibility 118and avoids unnecessary translations of intermediate results from 119CALI's internal data representation to the algebraic mode and vice 120versa. Moreover, one can easily extend the package with new symbolic 121mode scripts, or do more difficult interactive computations. For all 122these purposes the symbolic mode interface offers substantially more 123facilities than the algebraic one. 124\medskip 125 126For a detailed description of special symbolic mode procedures one 127should consult the source code and the comments therein. In this 128manual we can give only a brief description of the main ideas 129incorporated into the package CALI. We concentrate on the data 130structure design and the description of the more advanced algorithms. 131For sample computations from several fields of commutative algebra 132the reader may consult also the {\em cali.tst} file. 133\medskip 134 135As main topics CALI contains facilities for 136\begin{itemize} 137\item defining rings, ideals and modules, 138 139\item computing \gr bases and local standard bases, 140 141\item computing syzygies, resolutions and (graded) Betti numbers, 142 143\item computing (now also weighted) Hilbert series, multiplicities, 144independent sets, and dimensions, 145 146\item computing normal forms and representations, 147 148\item computing sums, products, intersections, quotients, stable 149quotients, elimination ideals etc., 150 151\item primality tests, computation of radicals, unmixed radicals, 152equidimensional parts, primary decompositions etc. of ideals and 153modules, 154 155\item advanced applications of \gr bases (blowup, associated graded 156ring, analytic spread, symmetric algebra, monomial curves etc.), 157 158\item applications of linear algebra techniques to zero dimensional 159 ideals, as e.g.\ the FGLM change of term orders, border bases 160 and affine and projective ideals of sets of points, 161 162\item splitting polynomial systems of equations mixing factorization and 163the \gr algorithm, triangular systems, and different versions of the 164extended \gr factorizer. 165 166\end{itemize} 167 168Below we will use freely without further explanation the notions 169common for text books and papers about constructive commutative 170algebra, assuming the reader to be familiar with the corresponding 171ideas and concepts. For further references see e.g.\ the text books 172\cite{BKW}, \cite{CLO} and \cite{Mishra} or the survey papers 173\cite{B1}, \cite{B2} and \cite{Ro}. 174 175\subsection{Description of the Documents Distributed with CALI} 176 177The CALI package contains the following files: 178\begin{quote} 179cali.chg 180 181\pbx{a detailed report of changes from v.\ 2.1 to v.\ 2.2. and 2.2.1} 182 183cali.log 184 185\pbx{the output file, that cali.tst should produce with 186\begin{quote} \tt 187load\_package cali; 188 189out "logfile"\$ 190 191in "cali.tst"; 192 193shut "logfile"\$ 194\end{quote}} 195 196cali.red 197 198\pbx{the CALI source file.} 199 200cali.tex 201 202\pbx{this manual.} 203 204cali.tst 205 206\pbx{a test file with various examples and applications of CALI.} 207 208\end{quote} 209 210CALI should be precompiled as usual, i.e.\ either using the {\em 211makefasl} utility of REDUCE or ``by hand'' via 212\begin{verbatim} 213 faslout "cali"$ 214 in "cali.red"$ 215 faslend$ 216\end{verbatim} 217and then loaded via 218\begin{verbatim} 219 load_package cali; 220\end{verbatim} 221Upon successful loading CALI responds with a message containing the 222version number and the last update of the distribution. 223 224\begin{center} 225\fbox{\parbox{12cm}{Feel free to contact me by email if You have 226problems to get CALI started. Also comments, hints, bug reports etc. 227are welcome.}} 228\end{center} 229 230\subsection{CALI's Language Concept} 231 232From a certain point of view one of the major disadvantage of the 233current RLISP (and the underlying PSL) language is the fact 234that it supports modularity and data encapsulation only in a 235rudimentary way. Since all parts of code loaded into a session are 236visible all the time, name conflicts between different packages may 237occur, will occur (even not issuing a warning message), and are hard 238to prevent, since packages are developed (and are still developing) 239by different research groups at different places and different time. 240 241A (yet rudimentary) concept of REDUCE packages and modules indicates the 242direction into what the REDUCE designers are looking for a solution 243for this general problem. 244\medskip 245 246CALI (2.0 and higher) follows a name concept for internal procedures 247to mimick data encapsulation at a semantical level. We hope this way 248on the one hand to resolve the conflicts described above at least for 249the internal part of CALI and on the other hand to anticipate a 250desirable future and already foregoing development of REDUCE towards 251a true modularity. 252 253The package CALI is divided into several modules, each of them 254introducing either a single new data type together with basic 255facilities, constructors, and selectors or a collection of algorithms 256subject to a common problem. Each module contains \ind{internal 257procedures}, conceptually hidden by this module, \ind{local 258procedures}, designed for a CALI wide use, and \ind{global 259procedures}, exported by CALI into the general (algebraic or 260symbolic) environment of REDUCE. A header \ind{module cali} contains 261all (fluid) global variables and switches defined by the pacakge 262CALI. 263 264Along these lines the CALI procedures available in symbolic mode are 265divided into three types with the following naming convention: 266\begin{quote} 267\verb|module!=procedure| 268 269\pbx{internal to the given module.} 270 271\verb|module_procedure| 272 273\pbx{exported by the given module into the local CALI environment.} 274 275\verb|procedure!*| 276 277\pbx{a global procedure usually having a semantically equivalent 278procedure (possibly with another parameter list) without trailing 279asterisk in algebraic mode.} 280\end{quote} 281There are also symbolic mode equivalents without trailing asterisk, if 282the algebraic procedure is not a {\em psopfn}, but a {\em symbolic 283operator}. They transfer data to CALI's internal structure and call 284the corresponding procedure with trailing asterisk. CALI 2.2 285distinguishes between algebraic and symbolic calls of such a 286procedure. In symbolic mode such a procedure calls the corresponding 287procedure with trailing asterisk directly without data transfer. 288\medskip 289 290CALI 2.2 follows also a more concise concept for global 291variables. There are three types of them: 292\begin{quote} 293True {\em fluid} global variables, 294 295\pbx{that are part of the current data structure, as e.g.\ the current 296base ring and the degree vector. They are often locally rebound to be 297restored after interrupts.} 298 299Global variables, stored on the property list of the package name {\tt 300cali}, 301 302\pbx{that reflect the state of the computational model as e.g.\ the 303trace level, the output print level or the chosen version of the \gr 304basis algorithm. There are several such parameters in the module 305\ind{dualbases} to serve the common dual basis driver with 306information for different applications.} 307 308{\em Switches,} 309 310\pbx{that allow to choose different branches of algorithms. Note that 311this concept interferes with the second one. Different {\em versions} 312of algorithms, that apply different functions in a common driver, are 313{\em not} implemented through switches.} 314\end{quote} 315 316\subsection{New and Improved Facilities in v.\ 2.1} 317 318The major changes in v.\ 2.1 reflect the experience we've got from the 319use of CALI 2.0. The following changes are worth mentioning 320explicitely: 321\begin{enumerate} 322\item The algebraic rule concept was adapted to CALI. It allows to 323supply rule based coefficient domains. This is a more efficient way 324to deal with (easy) algebraic numbers than through the {\em arnum 325package}. 326 327\item \ind{listtest} and \ind{listminimize} provide an unified 328concept for different list operations previously scattered in the 329source text. 330 331\item There are several new quotient algorithms at the symbolic level 332(both the general element and the intersection approaches are 333available) and new features for the computation of equidimensional 334hull and equidimensional radical. 335 336\item A new \ind{module scripts} offers advanced applications of \gr 337bases. 338 339\item Several advanced procedures initialize a \gr basis computation 340over a certain intermediate base ring or term order as e.g.\ 341\ind{eliminate}, \ind{resolve}, \ind{matintersect} or all 342\ind{primary decomposition} procedures. Interrupting a computation in 343v.\ 2.1 now restores the original values of CALI's global variables, 344since all intermediate procedures work with local copies of 345the global variables.\footnote{Note that recovering the base 346ring this way may cause some trouble since the intermediate ring, 347installed with \ind{setring}, changed possibly the internal variable 348order set by {\em setkorder}.} This doesn't apply to advanced 349procedures that change the current base ring as e.g.\ \ind{blowup}, 350\ind{preimage}, \ind{sym} etc. 351 352\end{enumerate} 353 354\subsection{New and Improved Facilities in v.\ 2.2} 355 356Version 2.2 (beside bug fixes) incorporates several new facilities of 357constructive non linear algebra that we investigated the last two 358years, as e.g.\ dual bases, the \gr factorizer, triangular systems, and 359local standard bases. Essential changes concern the following topics: 360\begin{enumerate} 361\item The CALI modules \ind{red} and \ind{groeb} were rewritten and 362the \ind{module mora} was removed. This is 363due to new theoretical insight into standard bases theory as 364e.g.\ described in \cite{tcah} or \cite{ala}. The \gr basis algorithm 365is reorganized as a \gr driver with simplifier and base lists, that 366involves different versions of polynomial reduction according to the 367setting via \ind{gbtestversion}. It applies now to 368both noetherian and non noetherian term orders in a unified way. 369 370The switches \ind{binomial} and \ind{lazy} were removed. 371 372\item The \gr factorizer was thoroughly revised, extended along the 373lines explained in \cite{fgb}, and collected into a separate 374\ind{module groebf}. It now allows a list of constraints also in 375algebraic mode. Two versions of an \ind{extended \gr factorizer} 376produce \ind{triangular systems}, 377i.e.\ a decomposition into quasi prime components, see \cite{efgb}, 378that are well suited for further (numerical) evaluation. There is also 379a version of the \gr factorizer that allows a list of problems as 380input. This is especially useful, if a system is splitted with respect 381to a ``cheap'' (e.g. degrevlex) term order and the pieces are 382recomputed with respect to a ``hard'' (e.g. pure lex) term order. 383 384The extended \gr factorizer involves, after change to dimension zero, 385the computation of \ind{triangular systems}. The corresponding module 386\ind{triang} extends the facilities for zero dimensional ideals and 387modules in the \ind{module odim}. 388 389\item A new \ind{module lf} implements the \ind{dual bases} approach 390as described in \cite{MMM}. On this basis there are new 391implementations of \ind{affine\_points} and \ind{proj\_points}, that 392are significantly faster than the old ones. The linear algebra 393\ind{change of term orders} \cite{FGLM} is available, too. There are 394two versions, one with precomputed \ind{border basis}, the other with 395conventional normal forms. 396 397\item \ind{dpmat}s now have a \ind{gb-tag} that indicates, whether the 398given ideal or module basis is already a \gr basis. This avoids 399certain \gr basis recomputations especially during advanced algorithms 400as e.g.\ prime decomposition. In the algebraic interface \gr bases are 401computed automatically when needed rather than to issue an error 402message as in v.\ 2.1. So one can call \ind{modequalp} or \ind{dim} 403etc. not having computed \gr bases in advance. Note that such 404automatic computation can be avoided with \ind{setgbasis}. 405 406\item Hilbert series are now \ind{weighted Hilbert series}, since 407e.g.\ for blow up rings the generating ideal is multigraded. Usual 408Hilbert series are computed as in v.\ 2.1 with respect to the 409\ind{ecart vector}. Weighted Hilbert series accept a list of (integer) 410weight lists as second parameter. 411 412\item There are some name and conceptual changes to existing 413procedures and variables to have a more concise semantic concept. This 414concerns 415\begin{quote} 416\ind{tracing} (the trace parameter is now stored on the property list 417of {\tt cali} and should be set with \ind{setcalitrace}), 418 419choosing different versions of the \gr algorithm (through 420\ind{gbtestversion}) and the Hilbert series computation (through 421\ind{hftestversion}), 422 423some names (\ind{mat2list} replaced \ind{flatten}, \ind{HilbertSeries} 424replaced {\em hilbseries}) and 425 426parameter lists of some local and internal procedures (consult {\em 427cali.chg} for details). 428\end{quote} 429 430\item The \ind{revlex term order} is now the reverse lexicographic 431term order on the {\bf reversely} ordered variables. This is consistent 432with other computer algebra systems (e.g.\ SINGULAR or 433AXIOM)\footnote{But different to the currently distibuted {\tt 434groebner} package in REDUCE. Note that the computations in 435\cite{fgb} were done {\em before} these changes.} and implies the same 436order on the variables for deglex and degrevlex term orders (this was 437the main reason to change the definition). 438 439\item Ideals of minors, pfaffians and related stuff are now 440implemented as extension of the internal {\tt matrix} package and 441collected into a separate \ind{module calimat}. Thus they allow more 442general expressions, especially with variable exponents, as general 443REDUCE matrices do. So one can define generic ideals as e.g.\ ideals 444of minors or pfaffians of matrices, containing generic expressions as 445elements. They must be specified for further use in CALI substituting 446general exponents by integers. 447 448\end{enumerate} 449 450\subsection{New and Improved Facilities in v.\ 2.2.1\label{221}} 451 452The main change concerns the primary decomposition algorithm, where I 453fixed a serious bug for deciding, which embedded primes are really 454embedded\footnote{That there must be a bug was pointed out to me by 455Shimoyama Takeshi who compared different p.d.\ implementations. The 456bug is due to an incorrect test for embedded primes: A (superfluous) 457primary component may contain none of the isolated primary components, 458but their intersection! Note that neither \cite{GTZ} nor \cite{BKW} 459comment on that. Details of the implementation will appear in 460\cite{primary}.}. During that remake I incorporated also the \gr 461factorizer to compute isolated primes. Since REDUCE has no 462multivariate {\em modular} factorizer, the switch \ind{factorprimes} 463may be turned off to switch to the former algorithm. 464 465 466 467Some minor bugs are fixed, too, e.g.\ the bug that made \ind{radical} 468crashing. 469 470 471 472 473\section{The Computational Model} 474 475This section gives a short introduction into the data type design of 476CALI at different levels. First (\S 1 and 2) we describe CALI's way 477of algorithmic translation of the abstract algebraic objects {\em 478ring of polynomials, ideal} and (finitely generated) {\em module}. 479Then (\S 3 and 4) we describe the algebraic mode interface of CALI 480and the switches and global variables to drive a session. In the next 481chapter we give a more detailed overview of the basic (symbolic mode) data 482structures involved with CALI. We refer to the appendix for a short 483summary of the commands available in algebraic mode. 484 485\subsection{The Base Ring} 486 487A polynomial ring consists in CALI of the following data: 488\begin{quote} 489a list of variable names 490 491\pbx{All variables not occuring in the list of ring names are treated 492as parameters. Computations are executed denominatorfree, but the 493results are valid only over the corresponding parameter {\em field} 494extension.} 495 496a term order and a term order tag 497 498\pbx{They describe the way in which the terms in each polynomial (and 499polynomial vector) are ordered.} 500 501an ecart vector 502 503\pbx{A list of positive integers corresponding to the variable 504names.} 505\end{quote} 506 507A \ind{base ring} may be defined (in algebraic mode) through the 508command 509\begin{verbatim} 510 setring <ring> 511\end{verbatim} 512with $<ring>$ ::= \{\, vars,\,tord,\,tag\,[,\,ecart\,]\,\} resp. 513\begin{verbatim} 514 setring(vars, tord, tag [,ecart]) 515\end{verbatim} 516\index{setring} 517This sets the global (symbolic) variable \ind{cali!=basering}. Here 518{\tt vars} is the list of variable names, {\tt tord} a (possibly 519empty) list of weight lists, the \ind{degree vectors}, and {\tt tag} 520the tag LEX or REVLEX. Optionally one can supply {\tt ecart}, a list 521of positive integers of the same length as {\tt vars}, to set an ecart 522vector different from the default one (see below). 523 524The degree vectors must have the same length as {\tt vars}. If $(w_1\ 525\ldots\ w_k)$ is the list of degree vectors then 526\[x^a<x^b \qquad :\Leftrightarrow \qquad 527\parbox[t]{8cm}{either\hfill 528\parbox[t]{6cm}{$w_j(x^a)=w_j(x^b)$\hfill for $j<i$ \hfill and \\[8pt] 529$w_i(x^a)<w_i(x^b)$} \\[10pt] or\hfill 530\parbox[t]{6cm}{$w_j(x^a)=w_j(x^b)$\hfill for all $j$ \hfill and \\[8pt] 531$x^a<_{lex}x^b$ resp. $x^a<_{revlex}x^b$}} 532\] 533Here $<_{lex}$ resp. $<_{revlex}$ denote the 534\ind{lexicographic} (tag=LEX) resp. \ind{reverse lexicographic} 535(tag=REVLEX) term orders\footnote{The definition of the revlex term 536order changed for version 2.2.} 537with respect to the variable order given in {\tt vars}, i.e.\ 538\[x^a<x^b \quad :\Leftrightarrow \quad 539\exists\ j\ \forall\ i<j\ :\ a_i=b_i\quad\mbox{and}\quad a_j<b_j\ 540\mbox{(lex.)}\] 541or 542\[x^a<x^b \quad :\Leftrightarrow \quad 543\exists\ j\ \forall\ i>j\ :\ a_i=b_i\quad\mbox{and}\quad a_j>b_j\ 544\mbox{(revlex.)}\] 545 546Every term order can be represented in such a way, see \cite{MR88}. 547 548During the ring setting the term order will be checked to be 549Noetherian (i.e.\ to fulfill the descending chain condition) provided 550the \ind{switch Noetherian} is on (the default). The same applies 551turning {\em noetherian on}: If the term order of the underlying 552base ring isn't Noetherian the switch can't be turned over. Hence, 553starting from a non Noetherian term order, one should define {\em 554first} a new ring and {\em then} turn the switch on. 555 556Useful term orders can be defined by the procedures 557\begin{quote} 558\verb|degreeorder vars|, \index{degreeorder} 559 560\pbx{that returns $tord=\{\{1,\ldots ,1\}\}$.} 561 562\verb|localorder vars|, \index{localorder} 563 564\pbx{that returns $tord=\{\{-1,\ldots ,-1\}\}$ (a non Noetherian term 565order for computations in local rings).} 566 567\verb|eliminationorder(vars,elimvars)|, \index{eliminationorder} 568 569\pbx{that returns a term order for elimination of the variables in 570{\tt elimvars}, a subset of all {\tt vars}. It's recommended to 571combine it with the tag REVLEX.} 572 573\verb|blockorder(vars,integerlist)|, \index{blockorder} 574 575\pbx{that returns the list of degree vectors for the block order with 576block lengths given in the {\tt integerlist}. Note that these numbers 577should sum up to the length of the variable list supplied as the first 578argument.} 579\end{quote} 580 581\noindent Examples: 582\begin{verbatim} 583vars:={x,y,z}; 584tord:=degreeorder vars; % Returns {{1,1,1}}. 585setring(vars,tord,lex); % GRADLEX in the groebner package. 586 587% or 588 589setring({a,b,c,d},{},lex); % LEX in the groebner package. 590 591% or 592 593vars:={a,b,c,x,y,z}; 594tord:=eliminationorder(vars,{x,y,z}); 595tord:=reverse blockorder(vars,{3,3}); 596 % Return both {{0,0,0,1,1,1},{1,1,1,0,0,0}}. 597setring(vars,tord,revlex); 598\end{verbatim} 599\pagebreak[2] 600 601The base ring is initialized with \\[10pt] 602\verb|{{t,x,y,z},{{1,1,1,1}},revlex,{1,1,1,1}}|,\\[10pt] 603i.e.\ $S=k[t,x,y,z]$ supplied with the degree wise reverse 604lexicographic term order. 605\begin{quote} 606\verb|getring m|\index{getring} 607 608\pbx{returns the ring attached to the object with the identifier 609$m$. E.g.\ } 610 611\verb|setring getring m| 612 613\pbx{(re)sets the base ring to the base ring of the formerly defined 614object (ideal or module) $m$.} 615 616\verb|getring()| 617 618\pbx{returns the currently active base ring.} 619\end{quote} 620 621CALI defines also an \ind{ecart vector}, attaching to each variable a 622positive weight with respect to that homogenizations and related 623algorithms are executed. It may be set optionally by the user during 624the \ind{setring} command. (Default: If the term order is a 625(positive) degree order then the ecart is the first degree vector, 626otherwise each ecart equals 1). 627 628The ecart vector is used in several places for efficiency reason (\gr 629basis computation with the sugar strategy) or for termination (local 630standard bases). If the input is homogeneous the ecart vector should 631reflect this homogeneity rather than the first degree vector to 632obtain the best possible performance. For a discussion of local 633computations with encoupled ecart vector see \cite{tcah}. In general 634the ecart vector is recommended to be chosen in such a way that the 635input examples become close to be homogeneous. {\em Homogenizations} 636and \ind{Hilbert series} are computed with respect to this ecart 637vector. 638\medskip 639 640\noindent \verb|getecart()|\index{getecart} returns the ecart vector 641currently set. 642 643 644\subsection{Ideals and Modules} 645 646If $S=k[x_v,\ v \in H]$ is a polynomial ring, a matrix $M$ of size 647$r\times c$ defines a map 648\[f\ :\ S^r \longrightarrow S^c\] 649by the following rule 650\[ f(v):=v\cdot M \qquad \mbox{ for } v \in S^r.\] 651There are two modules, connected with such a map, $im\ f$, the 652submodule of $S^c$ generated by the rows of $M$, and $coker\ f\ 653(=S^c/im\ f)$. Conceptually we will identify $M$ with $im\ f$ for the 654basic algebra, and with $coker\ f$ for more advanced topics of 655commutative algebra (Hilbert series, dimension, resolution etc.) 656following widely accepted conventions. 657 658With respect to a fixed basis $\{e_1,\ldots ,e_c\}$ one can define 659module term orders on $S^c$, \gr bases of submodules of $S^c$ etc. 660They generalize the corresponding notions for ideal bases. See 661\cite{E} or \cite{MM} for a detailed introduction to this area of 662computational commutative algebra. This allows to define joint 663facilities for both ideals and submodules of free modules. Moreover 664computing syzygies the latter come in in a natural way. 665 666CALI handles ideal and module bases in a unique way representing them 667as rows of a \ind{dpmat} ({\bf d}istributive {\bf p}olynomial {\bf 668mat}rix). It attaches to each unit vector $e_i$ a monomial $x^{a_i}$, 669the $i$-th \ind{column degree} and represents the rows of a dpmat $M$ 670as lists of module terms $x^ae_i$, sorted with respect to a 671\ind{module term order}, that may be roughly\footnote{The correct 672definition is even more difficult.} described as 673\bigskip 674 675\begin{tabular}{cccp{6cm}} 676$x^ae_i<x^be_j$ & $:\Leftrightarrow$ & either & 677{\centering $x^ax^{a_i}<x^bx^{a_j}$ in $S$\\}\\ 678& & or & 679{\centering $x^ax^{a_i}=x^bx^{a_j}$ \\ and \\ 680$i<j$ (lex.) resp. $i>j$ (revlex.)\\} 681\end{tabular} 682 683Every dpmat $M$ has its own column degrees (no default !). They are 684managed through a global (symbolic) variable \ind{cali!=degrees}. 685\begin{quote} 686\verb|getdegrees m| \index{getdegrees} 687 688\pbx{returns the column degrees of the object with identifier m.} 689 690\verb|getdegrees()| 691 692\pbx{returns the current setting of {\em cali!=degrees}.} 693 694\verb|setdegrees <list of monomials>| \index{setdegrees} 695 696\pbx{sets {\em cali!=degrees} correspondingly. Use this command 697before executing {\em setmodule} to give a dpmat prescribed column 698degrees since cali!=degrees has no default value and changes during 699computations. A good guess is to supply the empty list (i.e.\ all 700column degrees are equal to $\x^0$). Be careful defining modules 701without prescribed column degrees.} 702\end{quote} 703 704To distinguish between \ind{ideals} and \ind{modules} the former are 705represented as a \ind{dpmat} with $c=0$ (and hence without column 706degrees). If $I \subset S$ is such an ideal one has to distinguish 707between the ideal $I$ (with $c=0$, allowing special ideal operations 708as e.g.\ ideal multiplication) and the submodule $I$ of the free 709one dimensional module $S^1$ (with $c=1$, allowing matrix operations 710as e.g.\ transposition, matrix multiplication etc.). \ind{ideal2mat} 711converts an (algebraic) list of polynomials into an (algebraic) 712matrix column whereas \ind{mat2list} collects all matrix entries into 713a list. 714 715\subsection{The Algebraic Mode Interface} 716 717Corresponding to CALI's general philosophy explained in the 718introduction the algebraic mode interface translates algebraic input 719into CALI's internal data representation, calls the corresponding 720symbolic functions, and retranslates the result back into algebraic 721mode. Since \gr basis computations may be very tedious even on small 722examples, one should find a well balance between the storage of 723results computed earlier and the unavoidable time overhead and memory 724request associated with the management of these results. 725 726Therefore CALI distinguishes between {\em free} and {\em bounded} 727\index{free identifier}\index{bounded identifier} identifiers. Free 728identifiers stand only for their value whereas to bounded identifiers 729several internal information is attached to their property list for 730later use. 731\medskip 732 733After the initialization of the {\em base ring} bounded identifiers 734for ideals or modules should be declared via 735\begin{verbatim} 736setmodule(name,matrix value) 737\end{verbatim} 738resp. 739\begin{verbatim} 740setideal(name,list of polynomials) 741\end{verbatim} 742\index{setmodule}\index{setideal} 743This way the corresponding internal representation (as \ind{dpmat}) 744is attached to {\tt name} as the property \ind{basis}, the prefix 745form as its value and the current base ring as the property 746\ind{ring}. 747 748Performing any algebraic operation on objects defined this way their 749ring will be compared with the current base ring (including the term 750order). If they are different an error message occurs. If {\tt m} is 751a valid name, after resetting the base ring 752\begin{verbatim} 753setmodule(m1,m) 754\end{verbatim} 755reevaluates {\tt m} with respect to the new base ring (since the 756{\em value} of {\tt m} is its prefix form) and assigns the reordered 757dpmat to {\tt m1} clearing all information previously computed for 758{\tt m1} ({\tt m1} and {\tt m} may coincide). 759 760All computations are performed with respect to the ring $S=k[x_v\in 761{\tt vars}]$ over the field $k$. Nevertheless by efficiency reasons 762\ind{base coefficients} are represented in a denominator free way as 763standard forms. Hence the computational properties of the base 764coefficient domain depend on the \ind{dmode} and also on auxiliary 765variables, contained in the expressions, but not in the variable 766list. They are assumed to be parameters. 767 768Best performance will be obtained with integer or modular domain 769modes, but one can also try \ind{algebraic numbers} as coefficients 770as e.g.\ generated by {\tt sqrt} or the {\tt arnum} package. To avoid 771an unnecessary slow-down connected with the management of simplified 772algebraic expressions there is a \ind{switch hardzerotest} (default: 773off) that may be turned on to force an additional simplification of 774algebraic coefficients during each zero test. It should be turned on 775only for domain modes without canonical representations as e.g.\ 776mixtures of arnums and square roots. We remind the general zero 777decision problem for such domains. 778 779Alternatively, CALI offers the possibility to define a set of 780algebraic substitution rules that will affect CALI's base coefficient 781arithmetic only. 782\begin{quote} 783\verb|setrules <rule list>|\index{setrules} 784 785\pbx{transfers the (algebraic) rule list into the internal 786representation stored at the {\tt cali} value {\tt rules}. 787 788In particular, {\tt setrules \{\}} clears the rules previously set.} 789 790\verb|getrules()|\index{getrules} 791 792\pbx{returns the internal CALI rules list in algebraic form.} 793\end{quote} 794 795We recommend to use \ind{setrules} for computations with algebraic 796numbers since they are better adapted to the data structure of CALI 797than the algebraic numbers provided by the {\tt arnum} package. 798Note, that due to the zero decision problem 799complicated {\em setrules} based computations may produce wrong 800results if base coefficient's pseudo division is involved (as e.g.\ 801with \ind{dp\_pseudodivmod}). In this case we recommend to enlarge 802the variable set and add the defining equations of the algebraic 803numbers to the equations of the problem\footnote{A {\em qring} 804facility for the computation over quotient rings will be incorporated 805into future versions.}. 806\medskip 807 808The standard domain (Integer) doesn't allow denominators for input. 809\ind{setideal} clears automatically the common denominator of each 810input expression whereas a polynomial matrix with true rational 811coefficients will be rejected by \ind{setmodule}. 812\medskip 813 814One can save/initialize ideal and module bases together with their 815accompanying data (base ring, degrees) to/from a file: 816\begin{verbatim} 817savemat(m,name) 818\end{verbatim} 819resp. 820\begin{verbatim} 821initmat name 822\end{verbatim} execute the file transfer from/to disk files with the 823specified file {\tt name}. e.g.\ 824\begin{verbatim} 825savemat(m,"myfile"); 826\end{verbatim} 827saves the base ring and the ideal basis of $m$ to the file ``myfile'' 828whereas 829\begin{verbatim} 830setideal(m,initmat "myfile"); 831\end{verbatim} 832sets the current base ring (via a call to \ind{setring}) to the base 833ring of $m$ saved at ``myfile'' and then recovers the basis of $m$ 834from the same file. 835 836\subsection{Switches and Global Variables} 837 838There are several switches, (fluid) global variables, a trace 839facility, and global parameters on the property list of the package 840name {\tt cali} to control CALI's computations. 841\medskip 842 843\subsubsection*{Switches} 844 845\begin{quote} 846\ind{bcsimp} 847 848\pbx{on: Cancel out gcd's of base coefficients. (Default: on)} 849 850\ind{detectunits} 851 852\pbx{on: replace polynomials of the form \newline 853$\langle monomial\rangle * 854\langle polynomial\ unit\rangle $ by $\langle monomial\rangle$ 855during interreductions and standard basis computations. 856 857Affects only local computations. (Default: off)} 858 859\ind{factorprimes} 860 861\pbx{on: Invoke the \gr factorizer during computation of isolated 862primes. (Default: on). Note that REDUCE lacks a modular multivariate 863factorizer, hence for modular prime decomposition computations this 864switch has to be turned off.} 865 866\ind{factorunits} 867 868\pbx{on: factor polynomials and remove polynomial unit factors 869during interreductions and standard basis computations. 870 871Affects only local computations. (Default: off)} 872 873\ind{hardzerotest} 874 875\pbx{on: try an additional algebraic simplification of base 876coefficients at each base coefficient's zero test. Useful only for 877advanced base coefficient domains without canonical REDUCE 878representation. May slow down the computation drastically. 879(Default: off)} 880 881\ind{lexefgb} 882 883\pbx{on: Use the pure lexicographic term order and \ind{zerosolve} 884during reduction to dimension zero in the \ind{extended \gr 885factorizer}. This is a single, but possibly hard task compared to the 886degrevlex invocation of \ind{zerosolve1}. See \cite{efgb} for a 887discussion of different zero dimensional solver strategies. 888(Default: off)} 889 890\ind{Noetherian} 891 892\pbx{on: choose algorithms for Noetherian term orders. 893 894off: choose algorithms for local term orders. 895 896(Default: on)} 897 898\ind{red\_total} 899 900\pbx{on: compute total normal forms, i.e. apply reduction (Noetherian 901term orders) or reduction with bounded ecart (non Noetherian term 902orders to tail terms of polynomials, too. 903 904off: Do only top reduction. 905 906(Default: on)} 907 908\end{quote} 909 910\subsubsection*{Tracing} 911 912Different to v.\ 2.1 now intermediate output during the computations 913is controlled by the value of the {\tt trace} and {\tt printterms} 914entries on the property list of the package name {\tt cali}. The 915former value controls the intensity of the intermediate output 916(Default: 0, no tracing), the latter the number of terms printed in 917such intermediate polynomials (Default: all). 918\begin{quote} 919\verb|setcalitrace <n>|\index{setcalitrace} 920 921\pbx{changes the trace intensity. Set $n=2$ for a sparse tracing (a 922dot for each reduction step). 923Other good suggestions are the values 30 or 40 for tracing the \gr 924algorithm or $n>70$ for tracing the normal form algorithm. The higher 925$n$ the more intermediate information will be given.} 926 927\verb|setcaliprintterms <n>|\index{setcaliprintterms} 928 929\pbx{sets the number of terms that are printed in intermediate 930polynomials. Note that this does not affect the output of whole {\em 931dpmats}. The output of polynomials with more than $n$ terms ($n>0$) 932breaks off and continues with ellipses.} 933 934\verb|clearcaliprintterms()|\index{clearcaliprintterms} 935 936\pbx{clears the {\tt printterms} value forcing full intermediate 937output (according to the current trace level).} 938\end{quote} 939 940\subsubsection*{Global Variables} 941 942\begin{quote} 943\ind{cali!=basering} 944 945\pbx{The currently active base ring initialized e.g.\ by 946\ind{setring}.} 947 948\ind{cali!=degrees} 949 950\pbx{The currently active module component degrees initialized e.g.\ 951by \ind{setdegrees}.} 952 953\ind{cali!=monset} 954 955\pbx{A list of variable names considered as non zero divisors during 956\gr basis computations initialized e.g.\ by \ind{setmonset}. Useful 957e.g.\ for binomial ideals defining monomial varieties or other prime 958ideals.} 959 960\end{quote} 961 962\subsubsection*{Entries on the Property List of {\tt cali}} 963 964This approach is new for v.\ 2.2. Information concerning the state of 965the computational model as e.g.\ trace intensity, base coefficient 966rules, or algorithm versions are stored as values on the property list 967of the package name \ind{cali}. This concerns 968\begin{quote} 969\ind{trace} and \ind{printterms} 970 971\pbx{see above.} 972 973\ind{efgb} 974 975\pbx{Changed by the \ind{switch lexefgb}.} 976 977\ind{groeb!=rf} 978 979\pbx{Reduction function invoked during the \gr algorithm. It can be 980changed with \ind{gbtestversion}\ $<n>$ ($n=1,2,3$, default is 1).} 981 982\ind{hf!=hf} 983 984\pbx{Variant for the computation of the Hilbert series numerator. It 985can be changed with \ind{hftestversion}\ $<n>$ ($n=1,2$, default is 1).} 986 987\ind{rules} 988 989\pbx{Algebraic ``replaceby'' rules introduced to CALI with the 990\ind{setrules} command.} 991 992\ind{evlf}, \ind{varlessp}, \ind{sublist}, \ind{varnames}, 993\ind{oldborderbasis}, \ind{oldring}, \ind{oldbasis} 994 995\pbx{see \ind{module lf}, implementing the dual bases approach.} 996\end{quote} 997 998 999\section{Basic Data Structures} 1000 1001In the following we describe the data structure layers underlying the 1002dpmat representation in CALI and some important (symbolic) procedures 1003to handle them. We refer to the source code and the comments therein for 1004a more complete survey about the procedures available for different 1005data types. 1006 1007\subsection{The Coefficient Domain} 1008 1009Base coefficients as implemented in the \ind{module bcsf} are standard 1010forms in the variables outside the variable list of the current 1011ring. All computations are executed "denominator free" over the 1012corresponding quotient field, i.e.\ gcd's are canceled out without 1013request. To avoid this set the \ind{switch bcsimp} off.\footnote{This 1014induces a rapid base coefficient's growth and doesn't yield {\bf 1015Z}-\gr bases in the sense of \cite{GTZ} since the S-pair criteria are 1016different.} In the given implementation we use the s.f. procedure {\em 1017qremf} for effective divisibility test. We had some trouble with it 1018under {\em on factor}. 1019 1020Additionally it is possible to supply the 1021parameters occuring as base coefficients with a (global) set of 1022algebraic rules.\footnote{This is different from the LET rule 1023mechanism since they must be present in symbolic mode. Hence for a 1024simultaneous application of the same rules in algebraic mode outside 1025CALI they must additionally be declared in the usual way.} 1026\begin{quote} 1027\verb|setrules!* r|\index{setrules} 1028 1029\pbx{converts an algebraic mode rules list $r$ as e.g.\ used in 1030WHERE statements into the internal CALI format.} 1031\end{quote} 1032 1033\subsection{The Base Ring} 1034 1035The \ind{base ring} is defined by its {\tt name list}, the {\tt 1036degree matrix} (a list of lists of integers), the {\tt ring tag} (LEX 1037or REVLEX), and the {\tt ecart}. The name list contains a phantom 1038name {\tt cali!=mk} for the module component at place 0. 1039\medskip 1040 1041The \ind{module ring} exports among others the selectors 1042\ind{ring\_names}, \ind{ring\_degrees}, \ind{ring\_tag}, 1043\ind{ring\_ecart}, the test function \ind{ring\_isnoetherian} and the 1044transfer procedures from/to an (appropriate, printable by 1045\ind{mathprint}) algebraic prefix form \ind{ring\_from\_a} (including 1046extensive tests of the supplied parameters for consistency) and 1047\ind{ring\_2a}. 1048 1049The following procedures allow to define a base ring: 1050\begin{quote} 1051\verb|ring_define(name list, degree matrix, ring tag, ecart)| 1052\index{ring\_define} 1053 1054\pbx{combines the given parameters to a ring.} 1055 1056\verb|setring!* <ring> |\index{setring} 1057 1058\pbx{sets {\em cali!=basering} and checks for consistency with the 1059\ind{switch Noetherian}. It also sets through 1060\ind{setkorder} the current variable list as main variables. It is 1061strongly recommended to use {\em setring!* \ldots} instead of {\em 1062cali!=basering:=\ldots}.} 1063\end{quote} 1064\verb|degreeorder!*| , \verb|localorder!*|, \verb|eliminationorder!*|, and 1065\verb|blockorder!*| 1066\index{degreeorder} 1067\index{localorder} 1068\index{eliminationorder} 1069\index{blockorder} 1070define term order matrices in full analogy to algebraic mode. 1071\medskip 1072 1073There are three ring constructors for special purposes: 1074\begin{quote} 1075\verb|ring_sum(a,b)|\index{ring\_sum} 1076 1077\pbx{returns a ring, that is constructed in the following way: Its 1078variable list is the union of the (disjoint) lists of the variables 1079of the rings $a$ and $b$ (in this order) whereas the degree list is 1080the union of the (appropriately shifted) degree lists of $b$ and $a$ 1081(in this order). The ring tag is that of $a$. Hence it returns 1082(essentially) the ring $b\bigoplus a$ if $b$ has a degree part (e.g.\ 1083useful for elimination problems, introducing ``big'' new variables) 1084and the ring $a\bigoplus b$ if $b$ has no degree part (introducing 1085``small'' new variables).} 1086 1087\verb|ring_rlp(r,u)|\index{ring\_rlp} 1088 1089\pbx{$u$ is a subset of the names of the ring $r$. Returns the ring 1090$r$, but with a term order ``first degrevlex on $u$, then the order on 1091r''.} 1092 1093\verb|ring_lp(r,u)|\index{ring\_lp} 1094 1095\pbx{As $rlp$, but with a term order ``first lex on $u$, then the 1096order on r''.} 1097\end{quote} 1098 1099\noindent Example: 1100\begin{verbatim} 1101vars:='(x y z) 1102setring!* ring_define(vars,degreeorder!* vars,'lex,'(1 1 1)); 1103 % GRADLEX in the groebner package. 1104\end{verbatim} 1105 1106\subsection{Monomials} 1107 1108The current version uses a place-driven exponent representation 1109closely related to a vector model. This model handles term orders on $S$ 1110and module term orders on $S^c$ in a unique way. The zero component of the 1111exponent list of a monomial contains its module component ($>0$) or 0 1112(ring element). All computations are executed with respect to a 1113{\em current ring} (\ind{cali!=basering}) and {\em current (monomial) 1114weights} of the free generators $e_i, i=1,\ldots,c$, of $S^c$ 1115(\ind{cali!=degrees}). For efficiency reasons every monomial has a 1116precomputed degree part that should be reevaluated if {\tt 1117cali!=basering} (i.e.\ the term order) or {\tt cali!=degrees} were 1118changed. {\tt cali!=degrees} contains the list of column degrees of 1119the current module as an assoc. list and will be set automatically by 1120(almost) all dpmat procedure calls. Since monomial operations use the 1121degree list that was precomputed with respect to fixed column degrees 1122(and base ring) 1123\begin{quote}\bf 1124watch carefully for {\tt cali!=degrees} programming at the monomial 1125or dpoly level ! 1126\end{quote} 1127 1128As procedures there are selectors for the module component, the exponent and 1129the degree parts, comparison procedures, procedures for the management of 1130the module component and the degree vector, monomial arithmetic, transfer 1131from/to prefix form, and more special tools. 1132 1133\subsection{Polynomials and Polynomial Vectors} 1134 1135CALI uses a distributive representation as a list of terms for both 1136polynomials and polynomial vectors, where a \ind{term} is a dotted 1137pair 1138\[(<monomial>\ .\ <base\ coefficient>).\] 1139The \ind{ecart} of a polynomial (vector) $f=\sum{t_i}$ with (module) 1140terms $t_i$ is defined as \[max(ec(t_i))-ec(lt(t_i)),\] see 1141\cite{tcah}. Here $ec(t_i)$ denotes the ecart of the term $t_i$, i.e.\ 1142the scalar product of the exponent vector of $t_i$ (including the 1143monomial weight of the module generator) with the ecart vector of the 1144current base ring. 1145 1146As procedures there are selectors, dpoly arithmetic including the management 1147of the module component, procedures for reordering (and reevaluating) 1148polynomials wrt.\ new term order degrees, for extracting common base 1149coefficient or monomial factors, for transfer from/to prefix form and for 1150homogenization and dehomogenization (wrt.\ the current ecart vector). 1151 1152Two advanced procedures use ideal theory ingredients: 1153\begin{quote} 1154\verb|dp_pseudodivmod(g,f)|\index{dp\_pseudodivmod} 1155 1156\pbx{returns a dpoly list $\{q,r,z\}$ such that $z\cdot g = q\cdot f + 1157r$ and $z$ is a dpoly unit (i.e.\ a scalar for Noetherian term 1158orders). For non Noetherian term orders the necessary modifications 1159are described in \cite{ala}. 1160 1161$g, f$ and $r$ belong to the same free module or ideal. 1162} 1163 1164\verb|dpgcd(a,b)| \index{dpgcd} 1165 1166\pbx{computes the gcd of two dpolys $a$ and $b$ by the syzygy method: 1167The syzygy module of $\{a,b\}$ is generated by a single element 1168$[-b_0\ \ a_0]$ with $a=ga_0, b=gb_0$, where $g$ is the gcd of $a$ 1169and $b$. Since it uses dpoly pseudodivision it may work not properly 1170with \ind{setrules}.} 1171\end{quote} 1172 1173 1174\subsection{Base Lists} 1175 1176Ideal bases are one of the main ingredients for dpmats. They are 1177represented as lists of \ind{base elements} and contain together with 1178each dpoly entry the following information: 1179\begin{itemize} 1180\item a number (the row number of the polynomial vector in the 1181corresponding dpmat). 1182 1183\item the dpoly, its ecart (as the main sort criterion), and length. 1184 1185\item a representation part, that may contain a representation of the 1186given dpoly in terms of a certain fixed basis (default: empty). 1187\end{itemize} 1188 1189The representation part is managed during normal form computations 1190and other row arithmetic of dpmats appropriately with the following 1191procedures: 1192\begin{quote} 1193\verb|bas_setrelations b|\index{bas\_setrelations} 1194 1195\pbx{sets the relation part of the base element $i$ in the base list 1196$b$ to $e_i$.} 1197 1198\verb|bas_removerelations b|\index{bas\_removerelations} 1199 1200\pbx{removes all relations, i.e.\ replaces them with the zero 1201polynomial vector.} 1202 1203\verb|bas_getrelations b|\index{bas\_getrelations} 1204 1205\pbx{gets the relation part of $b$ as a separate base list.} 1206\end{quote} 1207 1208Further there are procedures for selection and construction of base 1209elements and for the manipulation of lists of base elements as e.g.\ 1210sorting, renumbering, reordering, simplification, deleting zero base 1211elements, transfer from/to prefix form, homogenization and dehomogenization. 1212 1213\subsection{Dpoly Matrices} 1214 1215Ideals and matrices, represented as \ind{dpmat}s, are the central 1216data type of the CALI package, as already explained above. Every 1217dpmat $m$ combines the following information: 1218\begin{itemize} 1219\item its size (\ind{dpmat\_rows} m,\ind{dpmat\_cols} m), 1220 1221\item its base list (\ind{dpmat\_list} m) and 1222 1223\item its column degrees as an assoc. list of monomials 1224(\ind{dpmat\_coldegs} m). If this list is empty, all degrees are 1225assumed to be equal to $x^0$. 1226 1227\item New in v.\ 2.2 there is a \ind{gb-tag} (\ind{dpmat\_gbtag} m), 1228indicating that the given base list is already a \gr basis (under the 1229given term order). 1230\end{itemize} 1231 1232The \ind{module dpmat} contains selectors, constructors, and the 1233algorithms for the basic management of this data structure as e.g.\ 1234file transfer, transfer from/to algebraic prefix forms, reordering, 1235simplification, extracting row degrees and leading terms, dpmat matrix 1236arithmetic, homogenization and dehomogenization. 1237 1238The modules {\em matop} and {\em quot} collect more advanced procedures 1239for the algebraic management of dpmats. 1240 1241\subsection{Extending the REDUCE Matrix Package} 1242 1243In v.\ 2.2 minors, Jacobian matrix, and Pfaffians are available for 1244general REDUCE matrices. They are collected in the \ind{module 1245calimat} and allow to define procedures in more generality, especially 1246allowing variable exponents in polynomial expressions. Such a 1247generalization is especially useful for the investigation of whole 1248classes of examples that may be obtained from a generic one by 1249specialization. In the following $m$ is a matrix given in algebraic 1250prefix form. 1251\begin{quote} 1252\verb|matjac(m,l)|\index{matjac} 1253 1254\pbx{returns the Jacobian matrix of the ideal $m$ (given as an 1255algebraic mode list) with respect to the variable list $l$.} 1256 1257\verb|minors(m,k)|\index{minors} 1258 1259\pbx{returns the matrix of $k$-minors of the matrix $m$.} 1260 1261\verb|ideal_of_minors(m,k)|\index{ideal\_of\_minors} 1262 1263\pbx{returns the ideal of the $k$-minors of the matrix $m$.} 1264 1265\verb|pfaffian m|\index{pfaffian} 1266 1267\pbx{returns the pfaffian of a skewsymmetric matrix $m$.} 1268 1269\verb|ideal_of_pfaffians(m,k)|\index{ideal\_of\_pfaffians} 1270 1271\pbx{returns the ideal of the $2k$-pfaffians of the skewsymmetric 1272matrix $m$.} 1273 1274\verb|random_linear_form(vars,bound)|\index{random\_linear\_form} 1275 1276\pbx{returns a random linear form in algebraic prefix form in the 1277supplied variables $vars$ with integer coefficients bounded by the 1278supplied $bound$.} 1279 1280\verb|singular_locus!*(m,c)|\index{singular\_locus} 1281 1282\pbx{returns the singular locus of $m$ (as dpmat). $m$ must be an 1283ideal of codimension $c$ given as a list of polynomials in prefix 1284form. {\tt Singular\_locus} computes the ideal generated by the 1285corresponding Jacobian and $m$ itself.} 1286\end{quote} 1287 1288\section{About the Algorithms Implemented in CALI} 1289 1290Below we give a short explanation of the main algorithmic ideas of 1291CALI and the way they are implemented and may be accessed 1292(symbolically). 1293 1294\subsection{Normal Form Algorithms} 1295 1296For v.\ 2.2 we completely revised the implementation of normal form 1297algorithms due to the insight obtained from our investigations of 1298normal form procedures for local term orders in \cite{ala} and 1299\cite{tcah}. It allows a common handling of Noetherian and non 1300Noetherian term orders already on this level thus making superfluous 1301the former duplication of reduction procedures in the modules {\em 1302red} and {\em mora} as in v.\ 2.1. 1303\medskip 1304 1305Normal form algorithms reduce polynomials (or polynomial vectors) 1306with respect to a given finite set of generators of an ideal or 1307module. The result is not unique except for a total normal form with 1308respect to a \gr basis. Furthermore different reduction strategies 1309may yield significant differences in computing time. 1310 1311CALI reduces by first matching, usually keeping base lists sorted 1312with respect to the sort predicate \ind{red\_better}. In v.\ 2.2 we 1313sort solely by the dpoly length, since the introduction of 1314\ind{red\_TopRedBE}, i.e.\ reduction with bounded ecart, guarantees 1315termination also for non Noetherian term orders. Overload red\_better 1316for other reduction strategies. 1317\medskip 1318 1319Reduction procedures produce for a given ideal basis $B\subset S$ and 1320a polynomial $f\in S$ a (pseudo) normal form $h\in S$ such that 1321$h\equiv u\cdot f\ mod\ B$ where $u\in S$ is a polynomial unit, i.e.\ 1322a (polynomially represented) non zero domain element in the Noetherian 1323case (pseudodivision of $f$ by $B$) or a polynomial with a scalar as 1324leading term in the non Noetherian case. Following up the reduction 1325steps one can even produce a presentation of $h-u\cdot f$ as a 1326polynomial combination of the base elements in $B$. 1327 1328More general, given for $f_i\in B$ and $f$ representations $f_i = 1329\sum{r_{ik}e_k} = R_i\cdot E^T$ and $f=R\cdot E^T$ as polynomial 1330combinations wrt.\ a fixed basis $E$ one can produce such a 1331presentation also for $h$. For this purpose the dpoly $f$ and its 1332representation are collected into a base element and reduced 1333simultaneously by the base list $B$, that collects the base elements 1334and their representations. 1335\medskip 1336 1337The main procedures of the newly designed reduction package are the 1338following: 1339\begin{quote} 1340\verb|red_TopRedBE(bas,model)|\index{red\_TopRedBE} 1341 1342\pbx{Top reduction with bounded ecart of the base element $model$ by 1343the base list $bas$, i.e.\ only reducing the top term and only with 1344base elements with ecart bounded by that of $model$.} 1345 1346\verb|red_TopRed(bas,model)|\index{red\_TopRed} 1347 1348\pbx{Top reduction of $model$, but without restrictions.} 1349 1350\verb|red_TailRed(bas,model)|\index{red\_TailRed} 1351 1352\pbx{Make tail reduction on $model$, i.e.\ top reduction on the tail 1353terms. For convergence this uses reduction with bounded ecart for non 1354Noetherian term orders and full reduction otherwise.} 1355\medskip 1356 1357There is a common \ind{red\_TailRedDriver} that takes a top reduction 1358function as parameter. It can be used for experiments with other top 1359reduction procedure combinations. 1360 1361\verb|red_TotalRed(bas,model)|\index{red\_TotalRed} 1362 1363\pbx{A terminating total reduction, i.e. for Noetherian term orders 1364the classical one and for local term orders using tail reduction with 1365bounded ecart.} 1366 1367\verb|red_Straight bas|\index{red\_Straight} 1368 1369\pbx{Reduce (with {\em red\_TailRed}) the tails of the polynomials in 1370the base list $bas$.} 1371 1372\verb|red_TopInterreduce bas|\index{red\_TopInterreduce} 1373 1374\pbx{Reduces the base list $bas$ with $red\_TopRed$ until it 1375has pairwise incomparable leading terms, computes correct 1376representation parts, but does no tail reduction.} 1377 1378\verb|red_Interreduce bas|\index{red\_Interreduce} 1379 1380\pbx{Does top and, if {\tt on red\_total}, also tail interreduction on 1381the base list $bas$.} 1382\end{quote} 1383 1384Usually, e.g.\ for ideal generation problems, there is no need to care 1385about the multiplier $u$. If nevertheless one needs its value, the 1386base element $f$ may be prepared with \ind{red\_prepare} to collect 1387this information in the 0-slot of its representation part. Extract 1388this information with \ind{red\_extract}. 1389\begin{quote} 1390\verb|red_redpol(bas,model)|\index{red\_redpol} 1391 1392\pbx{combines this tool with a total reduction of the base element 1393$model$ and returns a dotted pair 1394 1395\centerline{$(<reduced\ model> . <dpoly\ unit\ multiplier>)$.}} 1396\end{quote} 1397 1398Advanced applications call the interfacing procedures 1399\begin{quote} 1400\verb|interreduce!* m|\index{interreduce} 1401 1402\pbx{that returns an interreduced basis of the dpmat $m$.} 1403 1404\verb|mod!*(f,m)|\index{mod} 1405 1406\pbx{that returns the dotted pair $(h.u)$ where $h$ is the pseudo 1407normal form of the dpoly $f$ modulo the dpmat $m$ and $u$ the 1408corresponding polynomial unit multiplier.} 1409 1410\verb|normalform!*(a,b)|\index{normalform} 1411 1412\pbx{that returns $\{a_1,r,z\}$ with $a_1=z*a-r*b$ where the rows of 1413the dpmat $a_1$ are the normalforms of the rows of the dpmat $a$ with 1414respect to the dpmat $b$.} 1415\end{quote} 1416 1417For local standard bases the ideal generated by the basic polynomials 1418may have components not passing through the origin. Although they do 1419not contribute to the ideal in $Loc(S)=S_{\bf m}$ they usually heavily 1420increase the necessary computational effort. Hence for local term 1421orders one should try to remove polynomial units as soon as they 1422are detected. To remove them from base elements in an early stage of 1423the computation one can either try the (cheap) test, whether $f\in S$ 1424is of the form $\langle monomial\rangle *\langle polynomial\ 1425unit\rangle$ or factor $f$ completely and remove polynomial unit 1426factors. For base elements this may be done with 1427\ind{bas\_detectunits} or \ind{bas\_factorunits}. 1428 1429Moreover there are two switches \ind{detectunits} and 1430\ind{factorunits}, both off by default, that force such automatic 1431simplifications during more advanced computations. 1432 1433The procedure \ind{deleteunits!*} tries explicitely to factor the 1434basis polynomials of a dpmat and to remove polynomial units occuring 1435as one of the factors. 1436 1437\subsection{The \gr and Standard Basis Algorithms} 1438 1439There is now a unique \ind{module groeb} that contains the \gr 1440resp. standard basis algorithms with syzygy computation facility and 1441related topics. There are common procedures (working for both 1442Noetherian and non Noetherian term orders) 1443\begin{quote} 1444\verb|gbasis!* m|\index{gbasis} 1445 1446\pbx{that returns a minimal \gr or standard basis of the dpmat $m$,} 1447 1448\verb|syzygies!* m|\index{syzygies} 1449 1450\pbx{that returns an interreduced basis of the first syzygy module of 1451the dpmat $m$ and} 1452 1453\verb|syzygies1!* m|\index{syzygies1} 1454 1455\pbx{that returns a (not yet interreduced) basis of the syzygy module 1456of the dpmat $m$.} 1457\end{quote} 1458 1459These procedures start the outer \gr engine (now also common for both 1460Noetherian and non Noetherian term orders) 1461\begin{quote} 1462\verb|groeb_stbasis(m,mgb,ch,syz)|\index{groeb\_stbasis} 1463\end{quote} 1464that returns, applied to the dpmat $m$, three dpmats $g,c,s$ with 1465\begin{quote} 1466$g$ --- the minimal reduced \gr basis of $m$ if $mgb=t$, 1467 1468$c$ --- the transition matrix $g=c\cdot m$ if $ch=t$, and 1469 1470$s$ --- the (not yet interreduced) syzygy matrix of $m$ if $syz=t$. 1471\end{quote} 1472 1473The next layer manages the preparation of the representation parts 1474of the base elements to carry the syzygy information, calls the 1475{\em general internal driver}, and extracts the relevant information 1476from the result of that computation. The general internal driver 1477branches according to different reduction functions into several 1478versions. Upto now there are three different strategies for the 1479reduction procedures for the S-polynomial reduction (different 1480versions may be chosen via \ind{gbtestversion}): 1481\begin{enumerate} 1482\item Total reduction with local simplifier lists. For local term 1483orders this is (almost) Mora's first version for the tangent cone (the 1484default). 1485 1486\item Total reduction with global simplifier list. For local term 1487orders this is (almost) Mora's SimpStBasis, see \cite{MPT}. 1488 1489\item Total reduction with bounded ecart. 1490\end{enumerate} 1491The first two versions (almost) coincide for Noetherian term 1492orders. The third version reduces only with bounded ecart, thus 1493forcing more pairs to be treated than necessary, but usually less 1494expensive to be reduced. It is not yet well understood, whether this 1495idea is of practical importance. 1496 1497\ind{groeb\_lazystbasis} calls the lazy standard basis driver instead, 1498that implements Mora's lazy algorithm, see \cite{MPT}. As 1499\ind{groeb\_homstbasis}, the computation of \gr and standard bases via 1500homogenization (Lazard's approach), it is not fully integrated into 1501the algebraic interface. Use 1502\begin{quote} 1503\verb|homstbasis!* m|\index{homstbasis} 1504 1505\pbx{for the invocation of the homogenization approach to compute a 1506standard basis of the dpmat $m$ and} 1507 1508\verb|lazystbasis!* m|\index{lazystbasis} 1509 1510\pbx{for the lazy algorithm.} 1511\end{quote} 1512Experts commonly agree that the classical approach is better for 1513``computable'' examples, but computations done by the author 1514on large examples indicate, that both approaches are in fact 1515independent. 1516\medskip 1517 1518The pair list management uses the sugar strategy, see \cite{GMNRT}, 1519with respect to the current ecart vector. If the input is homogeneous 1520and the ecart vector reflects this homogeneity then pairs are sorted 1521by ascending degree. Hence no superfluous base 1522elements will be computed in this case. In general the sugar strategy 1523performs best if the ecart vector is chosen to make the input close 1524to be homogeneous. 1525 1526There is another global variable \ind{cali!=monset} that may contain 1527a list of variable names (a subset of the variable names of the 1528current base ring). During the ``pure'' \gr algorithm (without syzygy 1529and representation computations) common monomial factors containing 1530only these variables will be canceled out. This shortcut is useful if 1531some of the variables are known to be non zero divisors as e.g.\ in 1532most implicitation problems. 1533\begin{quote} 1534\verb|setmonset!* vars|\index{setmonset} 1535 1536\pbx{initializes {\em cali!=monset} with a given list of variables 1537$vars$.} 1538\end{quote} 1539 1540The \gr tools as e.g.\ pair criteria, pair list update, pair 1541management and S-polynomial construction are available. 1542\begin{quote} 1543\verb|groeb_mingb m|\index{groeb\_mingb} 1544 1545\pbx{extracts a minimal \gr basis from the dpmat $m$, removing base 1546elements with leading terms, divisible by other leading terms.} 1547 1548\verb|groeb_minimize(bas,syz)|\index{groeb\_minimize} 1549 1550\pbx{minimizes the dpmat pair $(bas,syz)$ deleting superfluous base 1551elements from $bas$ using syzygies from $syz$ containing unit 1552entries.} 1553\end{quote} 1554 1555\subsection{The \gr Factorizer} 1556 1557If $\bar{k}$ is the algebraic closure of $k$, 1558$B:=\{f_1,\ldots,f_m\}\subset S$ a finite system of polynomials, and 1559$C:=\{g_1,\ldots,g_k\}$ a set of side conditions define the {\em 1560relative set of zeroes} 1561\[Z(B,C):=\{a\in \bar{k}^n : \forall\ f\in B\ f(a)=0\mbox{ and } 1562\forall g\in C\ g(a)\neq 0\}.\] 1563Its Zariski closure is the zero set of $I(B):<\prod C>$. 1564 1565The \gr factorizer solves the following problem: 1566\begin{quote} 1567\it Find a collection $(B_\alpha,C_\alpha)$ of \gr bases $B_\alpha$ 1568and side conditions $C_\alpha$ such that 1569\[Z(B,C) = \bigcup_\alpha Z(B_\alpha,C_\alpha).\] 1570\end{quote} 1571The \ind{module groebf} and the \ind{module triang} contain algorithms 1572related to that problem, triangular systems, and their generalizations 1573as described in \cite{fgb} and \cite{efgb}. V. 2.2 thus heavily 1574extends the algorithmic possibilities that were implemented in former 1575releases of CALI. 1576 1577Note that, different to v.\ 2.1, we work with constraint {\em lists}. 1578\begin{quote} 1579\verb|groebfactor!*(bas,con)|\index{groebfactor} 1580 1581\pbx{returns for the dpmat ideal $bas$ and the constraint list $con$ 1582(of dpolys) a minimal list of $(dpmat, constraint\ list)$ pairs with 1583the desired property.} 1584\end{quote} 1585During a preprocessing it splits the submitted basis $bas$ by a 1586recursive factorization of polynomials and interreduction of bases 1587into a (reduced) list of smaller subproblems consisting of a partly 1588computed \gr basis, a constraint list, and a list of pairs not yet 1589processed. The main procedure forces the next subproblem to be 1590processed until another factorization is possible. Then the 1591subproblem splits into subsubproblems, and the subproblem list will 1592be updated. Subproblems are kept sorted with respect to their 1593expected dimension \ind{easydim} forcing this way a {\em depth first} 1594recursion. Returned and not yet interreduced \gr bases are, after 1595interreduction, subject to another call of the preprocessor since 1596interreduced polynomials may factor anew. 1597\begin{quote} 1598\verb|listgroebfactor!* l|\index{listgroebfactor} 1599 1600\pbx{proceeds a whole list of dpmats (without constraints) at once and 1601strips off constraints at the end.} 1602\end{quote} 1603\medskip 1604 1605Using the (ordinary) \gr factorizer even components of different 1606dimension may keep gluing together. The \ind{extended \gr factorizer} 1607involves a postprocessing, that guarantees a decomposition into 1608puredimensional components, given by triangular systems instead of \gr 1609bases. Triangular systems in positive dimension must not be \gr bases 1610of the underlying ideal. They should be preferred, since they are more 1611simple but contain all information about the (quasi) prime component 1612that they represent. The complete \gr basis of the corresponding 1613component can be obtained by an easy stable quotient computation, see 1614\cite{efgb}. We refer to the same paper for the definition of 1615\ind{triangular systems} in positive dimension, that is consistent 1616with our approach. 1617\begin{quote} 1618\verb|extendedgroebfactor!*(bas,c)| and 1619\verb|extendedgroebfactor1!*(bas,c)| 1620\index{extendedgroebfactor} \index{extendedgroebfactor1} 1621 1622\pbx{return a list of results $\{b_i,c_i,v_i\}$ in algebraic prefix 1623form such that $b_i$ is a triangular set wrt.\ the variables $v_i$ and 1624$c_i$ is a list of constraints, such that $b_i:<\prod c_i>$ is the 1625(puredimensional) recontraction of the zerodimensional ideal 1626$b_i\bigotimes_k k(v_i)$. For the first version the recontraction is 1627not computed, hence the output may be not minimal. The second version 1628computes recontractions to decide superfluous components already 1629during the algorithm. Note that the stable quotient computation 1630involved for that purpose may drastically slow down the whole 1631attempt.} 1632\end{quote} 1633The postprocessing involves a change to dimension zero and invokes 1634(zero dimensional) triangular system computations from the 1635\ind{module triang}. In a first step \ind{groebf\_zeroprimes1} 1636incorporates the square free parts of certain univariate polynomials 1637into these systems and strips off the constraints (since relative sets 1638of zeroes in dimension zero are Zariski closed), using a splitting 1639approach analogous to the \gr factorizer. In a second step, according 1640to the \ind{switch lexefgb}, either \ind{zerosolve!*} or 1641\ind{zerosolve1!*} converts these intermediate results into lists of 1642triangular systems in prefix form. If \ind{lexefgb} is {\tt off} (the 1643default), the zero dimensional term order is degrevlex and 1644\ind{zerosolve1!*}, the ``slow turn to lex'' is involved, for {\tt on 1645lexefgb} the pure lexicographic term order and \ind{zerosolve!*}, 1646M\"ollers original approach, see \cite{Moeller}, are used. Note that 1647for this term order we need only a single \gr basis computation at 1648this level. 1649 1650A third version, \ind{zerosolve2!*}, mixes the first approach with the 1651FGLM change of term orders. It is not incorporated into the extended 1652\gr factorizer. 1653 1654\subsection{Basic Operations on Ideals and Modules} 1655 1656\gr and local standard bases are the heart of several basic 1657algorithms in ideal theory, see e.g.\ \cite[6.2.]{BKW}. CALI offers 1658the following facilities: 1659\begin{quote} 1660\verb|submodulep!*(m,n)|\index{submodulep} 1661 1662\pbx{tests the dpmat $m$ for being a submodule of the dpmat $n$ 1663reducing the basis elements of $m$ with respect to $n$. The result 1664will be correct provided $n$ is a \gr basis.} 1665 1666\verb|modequalp!*(m,n)|\index{modequalp} 1667 1668\pbx{ = submodulep!*(m,n) and submodulep!*(n,m).} 1669 1670\verb|eliminate!*(m,<variable list>)| \index{eliminate} 1671 1672\pbx{computes the elimination ideal/module eliminating the variables 1673in the given variable list (a subset of the variables of the current 1674base ring). Changes temporarily the term order to degrevlex.} 1675 1676\verb|matintersect!* l|\index{matintersect} 1677\footnote{This can be done for ideals and 1678modules in an unique way. Hence {\em idealintersect!*} has been 1679removed in v.\ 2.1.} 1680 1681\pbx{computes the intersection of the dpmats in the dpmat list $l$ 1682along \cite[6.20]{BKW}.} 1683\end{quote} 1684 1685CALI offers several quotient algorithms. They rest on the computation 1686of quotients by a single element of the following kind: Assume 1687$M\subset S^c, v\in S^c, f\in S$. Then there are 1688\begin{quote} 1689the \ind{module quotient} $M : (v) = \{g\in S\ |\ gv\in M\}$, 1690 1691the \ind{ideal quotient} $M : (f) = \{w\in S^c\ |\ fw\in M\}$, and 1692 1693the \ind{stable quotient} $M : (f)^\infty = \{w\in S^c\ |\ \exists\, 1694n\, :\, f^nw\in M\}$. 1695\end{quote} 1696CALI uses the elimination approach \cite[4.4.]{CLO} and 1697\cite[6.38]{BKW} for their computation: 1698\begin{quote} 1699\verb|matquot!*(M,f)|\index{matquot} 1700 1701\pbx{returns the module or ideal quotient $M:(f)$ depending on $f$.} 1702 1703\verb|matqquot!*(M,f)|\index{matqquot} 1704 1705\pbx{returns the stable quotient $M:(f)^\infty$.} 1706\end{quote} 1707\ind{matquot!*} calls the pseudo division with remainder 1708\begin{quote} 1709\verb|dp_pseudodivmod(g,f)|\index{dp\_pseudodivmod} 1710 1711\pbx{that returns a dpoly list $\{q,r,z\}$ such that $z\cdot g = 1712q\cdot f + r$ with a dpoly unit $z$.\ ($g, f$ and $r$ must belong to 1713the same free module). This is done uniformly for noetherian and 1714local term orders with an extended normal form algorithm as described 1715in \cite{ala}.} 1716\end{quote} 1717\medskip 1718 1719In the same way one defines the quotient of a module by another 1720module (both embedded in a common free module $S^c$), the quotient of 1721a module by an ideal, and the stable quotient of a module by an 1722ideal. Algorithms for their computation can be obtained from the 1723corresponding algorithms for a single element as divisor either by 1724the generic element method \cite{E} or as an intersection 1725\cite[6.31]{BKW}. CALI offers both approaches (X=1 or 2 below) at 1726the symbolic level, but for true quotients only the latter one is 1727integrated into the algebraic mode interface. 1728\begin{quote} 1729\verb|idealquotientX!*(M,I)|\index{idealquotient} 1730 1731\pbx{returns the ideal quotient $M:I$ of the dpmat $M$ by the dpmat 1732ideal $I$.} 1733 1734\verb|modulequotientX!*(M,N)|\index{modulequotient} 1735 1736\pbx{returns the module quotient $M:N$ of the dpmat $M$ by the dpmat 1737$N$.} 1738 1739\verb|annihilatorX!* M|\index{annihilator} 1740 1741\pbx{returns the annihilator of $coker\ M$, i.e.\ the module quotient 1742$S^c:M$, if $M$ is a submodule of $S^c$.} 1743 1744\verb|matstabquot!*(M,I)|\index{matstabquot} 1745 1746\pbx{returns the stable quotient $M:I^\infty$ (only by the general element 1747method).} 1748\end{quote} 1749 1750 1751\subsection{Monomial Ideals} 1752 1753Monomial ideals occur as ideals of leading terms of (ideal's) \gr 1754bases and also as components of leading term modules of submodules of 1755free modules, see \cite{rois}, and reflect some properties of the 1756original ideal/module. Several parameters of the original ideal or 1757module may be read off from it as e.g.\ dimension and Hilbert series. 1758 1759The \ind{module moid} contains the corresponding algorithms on 1760monomial ideals. Monomial ideals are lists of monomials, kept sorted 1761by descending lexicographic order as proposed in \cite{BS}. 1762 1763\begin{quote} 1764\verb|moid_primes u| \index{moid\_primes} 1765 1766\pbx{returns the minimal primes (as a list of lists of variable 1767names) of the monomial ideal $u$ using an adaption of the algorithm, 1768proposed in \cite{BS} for the computation of the codimension.} 1769 1770\verb|indepvarsets!* m| \index{indepvarsets} 1771 1772\pbx{returns (based on {\em moid\_primes}) the list of strongly 1773independent sets of $m$, see \cite{KW} and \cite{rois} for 1774definitions.} 1775 1776\verb|dim!* m| \index{dim} 1777 1778\pbx{returns the dimension of $coker\ m$ as the size of the largest 1779independent set.} 1780 1781\verb|codim!* m| \index{codim} 1782 1783\pbx{returns the codimension of $coker\ m$.} 1784 1785\verb|easyindepset!* m| \index{easyindepset} 1786 1787\pbx{returns a maximal with respect to inclusion independent set of 1788$m$.} 1789 1790\verb|easydim!* m| \index{easydim} 1791 1792\pbx{is a fast dimension algorithm (based on {\em easyindepset}), that 1793will be correct if $m$ is (radically) unmixed. Since it is 1794significantly faster than the general dimension 1795algorithm\footnotemark, it should 1796be used, if all maximal independent sets are known to be of equal 1797cardinality (as e.g.\ for prime or unmixed ideals, see \cite{rois}).} 1798\footnotetext{This algorithm is of linear time as opposed to the 1799problem to determine the dimension of an arbitrary monomial ideal, 1800that is known to be NP-hard in the number of variables, see 1801\cite{BS}.} 1802\end{quote} 1803 1804\subsection{Hilbert Series} 1805 1806CALI v. 2.2 now offers also \ind{weighted Hilbert series}, i.e.\ 1807series that may reflect multihomogeneity of ideals and modules. For 1808this purpose 1809a weighted Hilbert series has a list of (integer) degree vectors 1810as second parameter, and the ideal(s) of leading terms are evaluated 1811wrt.\ these weights. For the output and polynomial arithmetic, 1812involved during the computation of the Hilbert series numerator, the 1813different weight levels are mapped onto the first variables of the 1814current ring. If $w$ is such a weight vector list and $I$ is a 1815monomial ideal in the polynomial ring $S=k[x_v\,:\,v\in V]$ we get 1816(using multi exponent notation) 1817\[H(S/I,t) := \sum_{\alpha}{|\{x^a\not\in I\,:\,w(a)=\alpha\}|\cdot 1818t^\alpha} = \frac{Q(t)}{\prod_{v\in V}{\left(1-t^{w(x_v)}\right)} }\] 1819for a certain polynomial Hilbert series numerator $Q(t)$. $H(R/I,t)$ 1820is known to be a rational function with pole order at $t=1$ equal to 1821$dim\ R/I$. Note that \ind{WeightedHilbertSeries} returns a {\em 1822reduced} rational function where the gcd of numerator and denominator 1823is canceled out. 1824 1825(Non weighted) Hilbert series call the weighted Hilbert series 1826procedure with a single weight vector, the ecart vector of the current 1827ring. 1828 1829The Hilbert series numerator $Q(t)$ is computed using (the obvious 1830generalizations to the weighted case of) the algorithms in \cite{BS} 1831and \cite{BCRT}. Experiments suggest that the former is better for few 1832generators of high degree whereas the latter has to be preferred for 1833many generators of low degree. Choose the version with 1834\ind{hftestversion} $n$, $n=1,\,2$. Bayer/Stillman's approach ($n=1$) 1835is the default. In the following $m$ is a dpmat and \gr basis. 1836 1837\begin{quote} 1838\verb|hf_whilb(m,w)| \index{hf\_whilb} 1839 1840\pbx{returns the weighted Hilbert series numerator $Q(t)$ of $m$ 1841according to the version chosen with \ind{hftestversion}.} 1842 1843\verb|WeightedHilbertSeries!*(m,w)| \index{WeightedHilbertSeries} 1844 1845\pbx{returns the weighted Hilbert series reduced rational function of 1846$m$ as s.q.} 1847 1848\verb|HilbertSeries!*(m,w)| \index{HilbertSeries} 1849 1850\pbx{returns the Hilbert series reduced rational function of $m$ wrt.\ 1851the ecart vector of the current ring as s.q.} 1852 1853\verb|hf_whilb3(u,w)| and \verb|hf_whs_from_resolution(u,w)| 1854\index{hf\_whilb3} 1855\index{hf\_whs\_from\_resolution} 1856 1857\pbx{compute the weighted Hilbert series numerator and the 1858corresponding reduced rational function from (the column degrees of) a 1859given resolution $u$.} 1860 1861\verb|degree!* m| \index{degree} 1862 1863\pbx{returns the value of the numerator of the reduced Hilbert series 1864of $m$ at $t=1$. i.e.\ the sum of its coefficients. For the standard 1865ecart this is the degree of $coker\ m$.} 1866\end{quote} 1867 1868\subsection{Resolutions} 1869 1870Resolutions of ideals and modules, represented as lists of dpmats, are 1871computed via repeated syzygy computation with minimization steps 1872between them to get minimal bases and generators of syzygy 1873modules. Note that the algorithms apply simultaneously to both 1874Noetherian and non Noetherian term orders. For compatibility reasons 1875with further releases v. 2.2 introduces a second parameter to 1876bound the number of syzygy modules to be computed, since Hilbert's 1877syzygy theorem applies only to regular rings. 1878\begin{quote} 1879\verb|Resolve!*(m,d)| \index{Resolve} 1880 1881\pbx{computes a minimal resolution of the dpmat $m$, i.e. a list of 1882dpmats $\{s_0, s_1, s_2,\ldots\}$, where $s_k$ is the $k$-th syzygy 1883module of $m$, upto part $s_d$.} 1884 1885\verb|BettiNumbers!* c| and \verb|GradedBettiNumbers!* c| 1886\index{BettiNumbers} 1887\index{GradedBettiNumbers} 1888 1889\pbx{returns the Betti numbers resp.\ the graded Betti numbers of the 1890resolution $c$, i.e.\ the list of the lengths resp.\ the degree lists 1891(according to the ecart) themselves of the dpmats in $c$.} 1892\end{quote} 1893 1894\subsection{Zero Dimensional Ideals and Modules} 1895 1896There are several algorithms that either force the reduction of a 1897given problem to dimension zero or work only for zero dimensional 1898ideals or modules. The \ind{module odim} offers such 1899algorithms. It contains, e.g.\ 1900\begin{quote} 1901\verb|dimzerop!* m| \index{dimzerop} 1902 1903\pbx{that tests a dpmat $m$ for being zero dimensional.} 1904 1905\verb|getkbase!* m| \index{getkbase} 1906 1907\pbx{that returns a (monomial) k-vector space basis of $Coker\ m$ 1908provided $m$ is a \gr basis.} 1909 1910\verb|odim_borderbasis m| \index{odim\_borderbasis} 1911 1912\pbx{that returns a border basis, see \cite{MMM}, of the 1913zero dimensional dpmat $m$ as a list of base elements.} 1914 1915\verb|odim_parameter m| \index{odim\_parameter} 1916 1917\pbx{that returns a parameter of the dpmat $m$, i.e.\ a variable $x 1918\in vars$ such that $k[x]\bigcap Ann\ S^c/m=(0)$, or {\em nil} if $m$ 1919is zero dimensional.} 1920 1921\verb|odim_up(a,m)| \index{odim\_up} 1922 1923\pbx{that returns an univariate polynomial (of smallest possible 1924degree if $m$ is a gbasis) in the variable $a$, that belongs to the 1925zero dimensional dpmat ideal $m$, using Buchberger's approach 1926\cite{B1}.} 1927\end{quote} 1928 1929\subsection{Primary Decomposition and Related Algorithms} 1930 1931The algorithms of the \ind{module prime} implement the ideas of 1932\cite{GTZ} with modifications along \cite{Kr} and their natural 1933generalizations to modules as e.g.\ explained in \cite{Ru}. Version 19342.2.1 fixes a serious bug detecting superfluous embedded primary 1935components, see section \ref{221}, and contains now a second primary 1936decomposition algorithm, based on ideal separation, as standard. For a 1937discussion about embedded primes and the ideal separation approach, 1938see \cite{primary}. 1939 1940 1941CALI contains also algorithms for the computation of the unmixed part 1942of a given module and the unmixed radical of a given ideal (along the 1943same lines). We followed the stepwise recursion decreasing dimension 1944in each step by 1 as proposed in (the final version of) \cite{GTZ} 1945rather than the ``one step'' method described in \cite{BKW} since 1946handling leading coefficients, i.e.\ standard forms, depending on 1947several variables is a quite hard job for 1948REDUCE\footnote{\ind{prime!=decompose2} implements this strategy in 1949the symbolic mode layer.}. 1950 1951In the following procedures $m$ must be a \gr basis. 1952\begin{quote} 1953\verb|zeroradical!* m| \index{zeroradical} 1954 1955\pbx{returns the radical of the zero dimensional ideal $m$, using 1956squarefree decomposition of univariate polynomials.} 1957 1958\verb|zeroprimes!* m| \index{zeroprimes} 1959 1960\pbx{computes as in \cite{GTZ} the list of prime ideals of $Ann\ F/M$ 1961if $m$ is zero dimensional, using the (sparse) general position 1962argument from \cite{KW}.} 1963 1964\verb|zeroprimarydecomposition!* m| \index{zeroprimarydecomposition} 1965 1966\pbx{computes the primary components of the zero dimensional dpmat $m$ 1967using prime splitting with the prime ideals of $Ann\ F/M$. It returns 1968a list of pairs with first entry the primary component 1969and second entry the corresponding associated prime ideal.} 1970 1971\verb|isprime!* m| \index{isprime} 1972 1973\pbx{a (one step) primality test for ideals, extracted from 1974\cite{GTZ}.} 1975 1976\verb|isolatedprimes!* m| \index{isolatedprimes} 1977 1978\pbx{computes (only) the isolated prime ideals of $Ann\ F/M$.} 1979 1980\verb|radical!* m| \index{radical} 1981 1982\pbx{computes the radical of the dpmat ideal $m$, reducing as in 1983\cite{GTZ} to the zero dimensional case.} 1984 1985\verb|easyprimarydecomposition!* m| \index{easyprimarydecomposition} 1986 1987\pbx{computes the primary components of the dpmat $m$, if it has no 1988embedded components. The algorithm uses prime splitting with the 1989isolated prime ideals of $Ann\ F/M$. It returns a list of pairs as in 1990{\em zeroprimarydecomposition!*}.} 1991 1992\verb|primarydecomposition!* m| \index{primarydecomposition} 1993 1994\pbx{computes the primary components of the dpmat $m$ along the lines 1995of \cite{GTZ}. It returns a list of two-element lists as in {\em 1996zeroprimarydecomposition!*}.} 1997 1998\verb|unmixedradical!* m| \index{unmixedradical} 1999 2000\pbx{returns the unmixed radical, i.e.\ the intersection of the 2001isolated primes of top dimension, associated to the dpmat ideal $m$.} 2002 2003\verb|eqhull!* m| \index{eqhull} 2004 2005\pbx{returns the equidimensional hull, i.e.\ the intersection of the 2006 top dimensional primary components of the dpmat $m$.} 2007\end{quote} 2008 2009\subsection{Advanced Algorithms} 2010 2011The \ind{module scripts} just under further development offers some 2012advanced topics of the \gr bases theory. It introduces the new data 2013structure of a \ind{map} between base rings: 2014\medskip 2015 2016A ring map 2017\[ \phi\ :\ R\longrightarrow S\] 2018for $R=k[r_i], S=k[s_j]$ is represented in symbolic mode as a list 2019\[ \{preimage\_ring\ R,\ image\_ring\ S, subst\_list\},\] 2020where {\tt subst\_list} is a substitution list $\{r_1=\phi_1(s), 2021r_2=\phi_2(s),\ldots \}$ in algebraic prefix form, i.e.\ looks like 2022{\tt (list (equal var image) \ldots )}. 2023 2024The central tool for several applications is the computation of the 2025preimage $\phi^{-1}(I)\subset R$ of an ideal $I\subset S$ either 2026under a polynomial map $\phi$ or its closure in $R$ under a rational 2027map $\phi$, see \cite[7.69 and 7.71]{BKW}. 2028\begin{quote} 2029\verb|preimage!*(m,map)| \index{preimage} 2030 2031\pbx{computes the preimage of the ideal $m$ in algebraic prefix form 2032under the given polynomial map and sets the current base ring to the 2033preimage ring. Returns the result also in algebraic prefix form.} 2034 2035\verb|ratpreimage!*(m,map)| \index{ratpreimage} 2036 2037\pbx{computes the closure of the preimage of the ideal $m$ in 2038algebraic prefix form under the given rational map and sets the 2039current base ring to the preimage ring. Returns the result also in 2040algebraic prefix form.} 2041 2042\end{quote} 2043 2044Derived applications are 2045\begin{quote} 2046\verb|affine_monomial_curve!*(l,vars)|\index{affine\_monomial\_curve} 2047 2048\pbx{$l$ is a list of integers, $vars$ a list of variable names of the 2049same length as $l$. The procedure sets the current base ring and 2050returns the defining ideal of the affine monomial curve with generic 2051point $(t^i\ :\ i\in l)$ computing the corresponding preimage.} 2052 2053\verb|analytic_spread!* M|\index{analytic\_spread} 2054 2055\pbx{Computes the analytic spread of $M$, i.e.\ the dimension of the 2056exceptional fiber ${\cal R}(M)/m{\cal R}(M)$ of the blowup along $M$ 2057over the irrelevant ideal $m$ of the current base ring.} 2058 2059\verb|assgrad!*(M,N,vars)|\index{assgrad} 2060 2061\pbx{Computes the associated graded ring \[gr_R(N):= 2062(R/N\oplus N/N^2\oplus\ldots)={\cal R}(N)/N{\cal R}(N)\] over the ring 2063$R=S/M$, where $M$ and 2064$N$ are dpmat ideals defined over the current base ring $S$. {\tt 2065vars} is a list of new variable names one for each generator of $N$. 2066They are used to create a second ring $T$ with degree order 2067corresponding to the ecart of the row degrees of $N$ and a ring map 2068\[\phi : S\oplus T\longrightarrow S.\] 2069It returns a dpmat ideal $J$ such that $(S\oplus T)/J$ is a 2070presentation of the 2071desired associated graded ring over the new current base ring 2072$S\oplus T$.} 2073 2074\verb|blowup!*(M,N,vars)|\index{blowup} 2075 2076\pbx{Computes the blow up ${\cal R}(N):=R[N\cdot t]$ of $N$ over 2077the ring $R=S/M$, where $M$ and $N$ are dpmat ideals defined over the 2078current base ring $S$. {\tt vars} is a list of new variable names one 2079for each generator of $N$. They are used to create a second ring $T$ 2080with degree order corresponding to the ecart of the row degrees of 2081$N$ and a ring map 2082\[\phi : S\oplus T\longrightarrow S.\] 2083It returns a dpmat ideal $J$ such that $(S\oplus T)/J$ is 2084a presentation of the 2085desired blowup ring over the new current base ring $S\oplus T$.} 2086 2087\verb|proj_monomial_curve!*(l,vars)|\index{proj\_monomial\_curve} 2088 2089\pbx{$l$ is a list of integers, $vars$ a list of variable names of the 2090same length as $l$. The procedure set the current base ring and 2091returns the defining ideal of the projective monomial curve with 2092generic point \mbox{$(s^{d-i}\cdot t^i\ :\ i\in l)$} in $R$, where 2093\mbox{$d=max\{ x\, :\, x\in l\}$}, computing the corresponding preimage.} 2094 2095\verb|sym!*(M,vars)|\index{sym} 2096 2097\pbx{Computes the symmetric algebra $Sym(M)$ where $M$ is a dpmat ideal 2098defined over the current base ring $S$. {\tt vars} is a list of new 2099variable names one for each generator of $M$. They are used to create 2100a second ring $R$ with degree order corresponding to the ecart of the 2101row degrees of $N$ and a ring map 2102\[\phi : S\oplus R\longrightarrow S.\] 2103It returns a dpmat ideal $J$ such that $(S\oplus R)/J$ is the 2104desired symmetric algebra over the new current base ring $S\oplus R$.} 2105 2106\end{quote} 2107 2108 2109There are several other applications: 2110\begin{quote} 2111\verb|minimal_generators!* m| \index{minimal\_generators} 2112 2113\pbx{returns a set of minimal generators of the dpmat $m$ inspecting 2114the first syzygy module.} 2115 2116\verb|nzdp!*(f,m)| \index{nzdp} 2117 2118\pbx{tests whether the dpoly $f$ is a non zero divisor on $coker\ 2119m$. $m$ must be a \gr basis.} 2120 2121\verb|symbolic_power!*(m,d)| \index{symbolic\_power} 2122 2123\pbx{returns the $d$\/th symbolic power of the prime dpmat ideal $m$ as 2124the equidimensional hull of the $d$\/th true power. (Hence applies also 2125to unmixed ideals.)} 2126 2127\verb|varopt!* m| \index{varopt} 2128 2129\pbx{finds a heuristically optimal variable order by the approach in 2130\cite{BGK} and returns the corresponding list of variables.} 2131\end{quote} 2132 2133 2134\subsection{Dual Bases} 2135 2136 2137For the general ideas underlying the dual bases approach see e.g.\ 2138\cite{MMM}. This paper explains, that constructive problems from very 2139different areas of commutative algebra can be formulated in a unified 2140way as the computation of a basis for the intersection of the kernels 2141of a finite number of linear functionals generating a dual 2142$S$-module. Our implementation honours 2143this point of view, presenting two general drivers \ind{dualbases} and 2144\ind{dualhbases} for the computation of such bases (even as submodules 2145of a free module $M=S^m$) with affine resp.\ projective dimension zero. 2146 2147Such a collection of $N$ linear functionals 2148\[L\,:\, M=S^m \longrightarrow k^N\] 2149should be given through values $\{[e_i,L(e_i)], i=1,\ldots,m\}$ on the 2150generators $e_i$ of $M$ and an evaluation function {\tt 2151evlf([p,L(p)],x)}, that evaluates $L(p\cdot x)$ from $L(p)$ for $p\in 2152M$ and the variable $x\in S$. 2153 2154\ind{dualbases} starts with a list of such generator/value constructs 2155generating $M$ and performs Gaussian reduction on expressions $[p\cdot 2156x,L(p\cdot x)]$, where $p$ was already processed, $L(p)\neq 0$, and 2157$x\in S$ is a variable. These elements are processed in ascending order 2158wrt.\ the term order on $M$. This guarantees both termination and that 2159the resulting basis of $ker\ L$ is a \gr basis. The $N$ values of $L$ 2160are attached to $N$ variables, that are ordered linearly. Gaussian 2161elimination is executed wrt.\ this variable order. 2162 2163To initialize the dual bases driver one has to supply the basic 2164generator/value list (through the parameter list; for ideals just the 2165one element list containing the generator $[1\in S,L(1)]$), the 2166evaluation function, and the linear algebra variable order. The latter 2167are supplied via the property list of {\tt cali} as properties {\tt 2168evlf} and {\tt varlessp}. Different applications need more entries 2169on the property list of {\tt cali} to manage the communication between 2170the driver and the calling routine. 2171 2172\ind{dualhbases} realizes the same idea for (homogeneous) ideals and 2173modules of (projective) dimension zero. It produces zerodimensional 2174``slices'' with ascending degree until it reaches a supremum supplied 2175by the user, see \cite{MMM} for details. 2176\medskip 2177 2178Applications concern affine and projective defining ideals of a finite 2179number of points\footnote{This substitutes the ``brute force'' method 2180computing the corresponding intersections directly as it was 2181implemented in v. 2.1. The new approach is significantly faster. The 2182old stuff is available as \ind{affine\_points1!*} and 2183\ind{proj\_points1!*}.} and two versions (with and without precomputed 2184border basis) of term order 2185changes for zerodimensional ideals and modules as first described in 2186\cite{FGLM}. 2187\begin{quote} 2188\verb|affine_points!* m| \index{affine\_points} 2189 2190\pbx{$m$ is a matrix of domain elements (in algebraic prefix form) 2191with as many columns as the current base ring has ring variables. This 2192procedure returns the defining ideal of the collection of points in 2193affine space with coordinates given by the rows of $m$. Note that $m$ 2194may contain parameters. In this case $k$ is treated as rational 2195function field.} 2196 2197\verb|change_termorder!*(m,r)| and \verb|change_termorder1!*(m,r)| 2198\index{change\_termorder} 2199\index{change\_termorder1} 2200 2201\pbx{$m$ is a \gr basis of a zero dimensional ideal wrt.\ the current 2202base ring. These procedures change the current ring to $r$ and compute 2203the \gr basis of $m$ wrt.\ the new ring $r$. The former uses a 2204precomputed border basis.} 2205 2206\verb|proj_points!* m| \index{proj\_points} 2207 2208\pbx{$m$ is a matrix of domain elements (in algebraic prefix form) 2209with as many columns as the current base ring has ring variables. This 2210procedure returns the defining ideal of the collection of points in 2211projective space with homogeneous coordinates given by the rows of 2212$m$. Note that $m$ may as for {\tt affine\_points} contain 2213parameters.} 2214\end{quote} 2215 2216\pagebreak 2217 2218\appendix 2219\section{A Short Description of Procedures Available in Algebraic 2220Mode} 2221 2222Here we give a short description, ordered alphabetically, of {\bf 2223algebraic} procedures offered by CALI in the algebraic mode 2224interface\footnote{It does {\bf not} contain switches, get\ldots\ 2225procedures, setting trace level and related stuff.}. 2226 2227If not stated explicitely procedures take (algebraic mode) polynomial 2228matrices ($c>0$) or polynomial lists ($c=0$) $m,m1,m2,\ldots\ $ as 2229input and return results of the same type. $gb$ stands for a bounded 2230identifier\footnote{Different to v. 2.1 a \gr basis will be computed 2231automatically, if necessary.}, $gbr$ for one with precomputed 2232resolution. For the mechanism of \ind{bounded identifier} see the 2233section ``Algebraic Mode Interface''. 2234 2235\begin{quote} 2236\verb|affine_monomial_curve(l,vars)|\index{affine\_monomial\_curve} 2237 2238\pbx{$l$ is a list of integers, $vars$ a list of variable names of the 2239same length as $l$. The procedure sets the current base ring and 2240returns the defining ideal of the affine monomial curve with generic 2241point $(t^i\ :\ i\in l)$.} 2242 2243\verb|affine_points m| \index{affine\_points} 2244 2245\pbx{$m$ is a matrix of domain elements (in algebraic prefix form) 2246with as many columns as the current base ring has ring variables. This 2247procedure returns the defining ideal of the collection of points in 2248affine space with coordinates given by the rows of $m$. Note that $m$ 2249may contain parameters. In this case $k$ is treated as rational 2250function field.} 2251 2252\verb|analytic_spread m|\index{analytic\_spread} 2253 2254\pbx{Computes the analytic spread of $m$.} 2255 2256\verb|annihilator m| \index{annihilator} 2257 2258\pbx{returns the annihilator of the dpmat $m\subseteq S^c$, i.e.\ 2259$Ann\ S^c/M$.} 2260 2261\verb|assgrad(M,N,vars)|\index{assgrad} 2262 2263\pbx{Computes the associated graded ring $gr_R(N)$ over $R=S/M$, where 2264$S$ is the current 2265base ring. {\tt vars} is a list of new variable names, one for 2266each generator of $N$. They are used to create a second ring $T$ 2267to return an ideal $J$ such that $(S\oplus T)/J$ is the desired 2268associated graded ring over the new current base ring $S\oplus T$.} 2269 2270\verb|bettiNumbers gbr| \index{bettiNumbers} 2271 2272\pbx{extracts the list of Betti numbers from the resolution of $gbr$.} 2273 2274\verb|blowup(M,N,vars)|\index{blowup} 2275 2276\pbx{Computes the blow up ${\cal R}(N)$ of $N$ over the ring $R=S/M$, 2277where $S$ is the current base ring. {\tt vars} is a list of new 2278variable names, one for each generator of $N$. They are used to create 2279a second ring $T$ to return an ideal $J$ such that $(S\oplus T)/J$ is 2280the desired blowup ring over the new current base ring $S\oplus T$.} 2281 2282\verb|change_termorder(m,r)| and \verb|change_termorder1(m,r)| 2283\index{change\_termorder} 2284\index{change\_termorder1} 2285 2286\pbx{Change the current ring to $r$ and compute the \gr basis of $m$ 2287wrt.\ the new ring $r$ by the FGLM approach. The former uses 2288internally a precomputed border basis.} 2289 2290\verb|codim gb| \index{codim} 2291 2292\pbx{returns the codimension of $S^c/gb$.} 2293 2294\verb|degree gb| \index{degree} 2295 2296\pbx{returns the multiplicity of $gb$ as the sum of the coefficients 2297of the (classical) Hilbert series numerator.} 2298 2299\verb|degsfromresolution gbr| \index{degsfromresolution} 2300 2301\pbx{returns the list of column degrees from the minimal resolution 2302of $gbr$.} 2303 2304\verb|deleteunits m| \index{deleteunits} 2305 2306\pbx{factors each basis element of the dpmat ideal $m$ and removes 2307factors that are polynomial units. Applies only to non Noetherian 2308term orders.} 2309 2310\verb|dim gb| \index{dim} 2311 2312\pbx{returns the dimension of $S^c/gb$.} 2313 2314\verb|dimzerop gb| \index{dimzerop} 2315 2316\pbx{tests whether $S^c/gb$ is zerodimensional.} 2317 2318\verb|directsum(m1,m2,...)| \index{directsum} 2319 2320\pbx{returns the direct sum of the modules $m1,m2,\ldots$, embedded 2321into the direct sum of the corresponding free modules.} 2322 2323\verb|dpgcd(f,g)| \index{dpgcd} 2324 2325\pbx{returns the gcd of two polynomials $f$ and $g$, computed by the 2326syzygy method.} 2327 2328\verb|easydim m| and \verb|easyindepset m| 2329\index{easydim}\index{easyindepset} 2330 2331\pbx{ If the given ideal or module is unmixed (e.g.\ prime) then all 2332maximal strongly independent sets are of equal size and one can look 2333for a maximal with respect to inclusion rather than size strongly 2334independent set. These procedures don't test the input for being a 2335\gr basis or unmixed, but construct a maximal with respect to 2336inclusion independent set of the basic leading terms resp.\ detect 2337from this (an approximation for) the dimension.} 2338 2339\verb|easyprimarydecomposition m| \index{easyprimarydecomposition} 2340 2341\pbx{a short primary decomposition using ideal separation of isolated 2342primes of $m$, that yields true results only for modules without 2343embedded components. Returns a list of $\{component, associated\ 2344prime\}$ pairs.} 2345 2346\verb|eliminate(m,<variable list>)| \index{eliminate} 2347 2348\pbx{computes the elimination ideal/module eliminating the variables 2349in the given variable list (a subset of the variables of the current 2350base ring). Changes temporarily the term order to degrevlex.} 2351 2352\verb|eqhull m| \index{eqhull} 2353 2354\pbx{returns the equidimensional hull of the dpmat $m$.} 2355 2356\verb|extendedgroebfactor(m,c)| and \verb|extendedgroebfactor1(m,c)| 2357\index{extendedgroebfactor} \index{extendedgroebfactor1} 2358 2359\pbx{return for a polynomial ideal $m$ and a list of (polynomial) 2360constraints $c$ a list of results $\{b_i,c_i,v_i\}$, where $b_i$ is a 2361triangular set wrt.\ the variables $v_i$ and $c_i$ is a list of 2362constraints, such that 2363$Z(m,c) = \bigcup Z(b_i,c_i)$. For the first version the output may be 2364not minimal. The second version decides superfluous components already 2365during the algorithm.} 2366 2367\verb|gbasis gb| \index{gbasis} 2368 2369\pbx{returns the \gr resp. local standard basis of $gb$.} 2370 2371\verb|getkbase gb| \index{getkbase} 2372 2373\pbx{returns a k-vector space basis of $S^c/gb$, consisting of module 2374terms, provided $gb$ is zerodimensional.} 2375 2376\verb|getleadterms gb| \index{getleadterms} 2377 2378\pbx{returns the dpmat of leading terms of a \gr resp. local standard 2379basis of $gb$.} 2380 2381\verb|GradedBettinumbers gbr| \index{GradedBettinumbers} 2382 2383\pbx{extracts the list of degree lists of the free summands in a 2384minimal resolution of $gbr$.} 2385 2386\verb|groebfactor(m[,c])|\index{groebfactor} 2387 2388\pbx{returns for the dpmat ideal $m$ and an optional constraint list 2389$c$ a (reduced) list of dpmats such that the union of their zeroes is 2390exactly $Z(m,c)$. Factors all polynomials involved in the \gr 2391algorithms of the partial results.} 2392 2393\verb|HilbertSeries gb| \index{HilbertSeries} 2394 2395\pbx{returns the Hilbert series of $gb$ with respect to the current 2396ecart vector.} 2397 2398\verb|homstbasis m| \index{homstbasis} 2399 2400\pbx{computes the standard basis of $m$ by Lazard's homogenization 2401approach.} 2402 2403\verb|ideal2mat m| \index{ideal2mat} 2404 2405\pbx{converts the ideal (=list of polynomials) $m$ into a column 2406vector.} 2407 2408\verb|ideal_of_minors(mat,k)| \index{ideal\_of\_minors} 2409 2410\pbx{computes the generators for the ideal of $k$-minors of the matrix 2411$mat$.} 2412 2413\verb|ideal_of_pfaffians(mat,k)| \index{ideal\_of\_pfaffians} 2414 2415\pbx{computes the generators for the ideal of the $2k$-pfaffians of 2416the skewsymmetric matrix $mat$.} 2417 2418\verb|idealpower(m,n)| \index{idealpower} 2419 2420\pbx{returns the interreduced basis of the ideal power $m^n$ with 2421respect to the integer $n\geq 0$.} 2422 2423\verb|idealprod(m1,m2,...)| \index{idealprod} 2424 2425\pbx{returns the interreduced basis of the ideal product 2426\mbox{$m1\cdot m2\cdot \ldots$} of the ideals $m1,m2,\ldots$.} 2427 2428\verb|idealquotient(m1,m2)| \index{idealquotient} 2429 2430\pbx{returns the ideal quotient $m1:m2$ of the module $m1\subseteq 2431S^c$ by the ideal $m2$.} 2432 2433\verb|idealsum(m1,m2,...)| \index{idealsum} 2434 2435\pbx{returns the interreduced basis of the ideal sum $m1+m2+\ldots$.} 2436 2437\verb|indepvarsets gb| \index{indepvarsets} 2438 2439\pbx{returns the list of strongly independent sets of $gb$ with 2440respect to the current term order, see \cite{KW} for a definition in 2441the case of ideals and \cite{rois} for submodules of free modules.} 2442 2443\verb|initmat(m,<file name>| \index{initmat} 2444 2445\pbx{initializes the dpmat $m$ together with its base ring, term order 2446and column degrees from a file.} 2447 2448\verb|interreduce m| \index{interreduce} 2449 2450\pbx{returns the interreduced module basis given by the rows of $m$, 2451i.e.\ a basis with pairwise indivisible leading terms.} 2452 2453\verb|isolatedprimes m| \index{isolatedprimes} 2454 2455\pbx{returns the list of isolated primes of the dpmat $m$, i.e.\ the 2456isolated primes of $Ann\ S^c/M$.} 2457 2458\verb|isprime gb| \index{isprime} 2459 2460\pbx{tests the ideal $gb$ to be prime.} 2461 2462\verb|iszeroradical gb| \index{iszeroradical} 2463 2464\pbx{tests the zerodimensional ideal $gb$ to be radical.} 2465 2466\verb|lazystbasis m| \index{lazystbasis} 2467 2468\pbx{computes the standard basis of $m$ by the lazy algorithm, see 2469e.g.\ \cite{MPT}.} 2470 2471\verb|listgroebfactor in| \index{listgroebfactor} 2472 2473\pbx{computes for the list $in$ of ideal bases a list $out$ of \gr 2474bases by the \gr factorization method, such that 2475$\bigcup_{m\in in}Z(m) = \bigcup_{m\in out}Z(m)$.} 2476 2477\verb|mat2list m| \index{mat2list} 2478 2479\pbx{converts the matrix $m$ into a list of its entries.} 2480 2481\verb|matappend(m1,m2,...)| \index{matappend} 2482 2483\pbx{collects the rows of the dpmats $m1,m2,\ldots $ to a common 2484matrix. $m1,m2,\ldots$ must be submodules of the same free module, 2485i.e.\ have equal column degrees (and size).} 2486 2487\verb|mathomogenize(m,var)| \index{mathomogenize} 2488\footnote{Dehomogenize with {\tt sub(z=1,m)} if $z$ is the 2489homogenizing variable.} 2490 2491\pbx{returns the result obtained by homogenization of the rows of m 2492with respect to the variable {\tt var} and the current \ind{ecart 2493vector}.} 2494 2495\verb|matintersect(m1,m2,...)| \index{matintersect} 2496 2497\pbx{returns the interreduced basis of the intersection $m1\bigcap 2498m2\bigcap \ldots$.} 2499 2500\verb|matjac(m,<variable list>)| \index{matjac} 2501 2502\pbx{returns the Jacobian matrix of the ideal m with respect to the 2503supplied variable list} 2504 2505\verb|matqquot(m,f)| \index{matqquot} 2506 2507\pbx{returns the stable quotient $m:(f)^\infty$ of the dpmat $m$ by 2508the polynomial $f\in S$.} 2509 2510\verb|matquot(m,f)| \index{matquot} 2511 2512\pbx{returns the quotient $m:(f)$ of the dpmat $m$ by the polynomial 2513$f\in S$.} 2514 2515\verb|matstabquot(m1,id)| \index{matstabquot} 2516 2517\pbx{returns the stable quotient $m1:id^\infty$ of the dpmat $m1$ by 2518the ideal $id$.} 2519 2520\verb|matsum(m1,m2,...)| \index{matsum} 2521 2522\pbx{returns the interreduced basis of the module sum $m1+m2+\ldots$ 2523in a common free module.} 2524 2525\verb|minimal_generators m| \index{minimal\_generators} 2526 2527\pbx{returns a set of minimal generators of the dpmat $m$.} 2528 2529\verb|minors(m,b)| \index{minors} 2530 2531\pbx{returns the matrix of minors of size $b\times b$ of the matrix 2532$m$.} 2533 2534\verb|a mod m| \index{mod} 2535 2536\pbx{computes the (true) normal form(s), i.e.\ a standard quotient 2537representation, of $a$ modulo the dpmat $m$. $a$ may be either a 2538polynomial or a polynomial list ($c=0$) or a matrix ($c>0$) of the 2539correct number of columns.} 2540 2541\verb|modequalp(gb1,gb2)| \index{modequalp} 2542 2543\pbx{tests, whether $gb1$ and $gb2$ are equal (returns YES or NO).} 2544 2545\verb|modulequotient(m1,m2)| \index{modulequotient} 2546 2547\pbx{returns the module quotient $m1:m2$ of two dpmats $m1,m2$ in a 2548common free module.} 2549 2550\verb|normalform(m1,m2)| \index{normalform} 2551 2552\pbx{returns a list of three dpmats $\{m3,r,z\}$, where $m3$ is the 2553normalform of $m1$ modulo $m2$, $z$ a scalar matrix of polynomial 2554units (i.e.\ polynomials of degree 0 in the noetherian case and 2555polynomials with leading term of degree 0 in the tangent cone case), 2556and $r$ the relation matrix, such that \[m3=z*m1+r*m2.\]} 2557 2558\verb|nzdp(f,m)| \index{nzdp} 2559 2560\pbx{tests whether the dpoly $f$ is a non zero divisor on $coker\ 2561m$.} 2562 2563\verb|pfaffian mat| \index{pfaffian} 2564 2565\pbx{returns the pfaffian of a skewsymmetric matrix $mat$.} 2566 2567\verb|preimage(m,map)| \index{preimage} 2568 2569\pbx{computes the preimage of the ideal $m$ under the given 2570polynomial map and sets the current base ring to the preimage ring.} 2571 2572\verb|primarydecomposition m| 2573\index{primarydecomposition} 2574 2575\pbx{returns the primary decomposition of the dpmat $m$ as a list of 2576$\{component, associated\ prime\}$ pairs.} 2577 2578\verb|proj_monomial_curve(l,vars)|\index{proj\_monomial\_curve} 2579 2580\pbx{$l$ is a list of integers, $vars$ a list of variable names of the 2581same length as $l$. The procedure sets the current base ring and 2582returns the defining ideal of the projective monomial curve with 2583generic point \mbox{$(s^{d-i}\cdot t^i\ :\ i\in l)$} in $R$ where $d=max\{ 2584x\, :\, x\in l\}$.} 2585 2586\verb|proj_points m| \index{proj\_points} 2587 2588\pbx{$m$ is a matrix of domain elements (in algebraic prefix form) 2589with as many columns as the current base ring has ring variables. This 2590procedure returns the defining ideal of the collection of points in 2591projective space with homogeneous coordinates given by the rows of 2592$m$. Note that $m$ may as for {\tt affine\_points} contain 2593parameters.} 2594 2595\verb|radical m| \index{radical} 2596 2597\pbx{returns the radical of the dpmat ideal $m$.} 2598 2599\verb|random_linear_form(vars,bound)| \index{random\_linear\_form} 2600 2601\pbx{returns a random linear form in the variables {\tt vars} with integer 2602coefficients less than the supplied {\tt bound}.} 2603 2604\verb|ratpreimage(m,map)| \index{ratpreimage} 2605 2606\pbx{computes the closure of the preimage of the ideal $m$ under the 2607given rational map and sets the current base ring to the preimage 2608ring.} 2609 2610\verb|resolve(m[,d])| \index{resolve} 2611 2612\pbx{returns the first $d$ members of the minimal resolution of the 2613bounded identifier $m$ as a list of matrices. If the resolution has 2614less than $d$ non zero members, only those are collected. (Default: 2615$d=100$)} 2616 2617\verb|savemat(m,<file name>)| \index{savemat} 2618 2619\pbx{save the dpmat $m$ together with the settings of it base ring, 2620term order and column degrees to a file.} 2621 2622\verb|setgbasis m| \index{setgbasis} 2623 2624\pbx{declares the rows of the bounded identifier $m$ to be already a 2625\gr resp. local standard basis thus avoiding a possibly time 2626consuming \gr or standard basis computation.} 2627 2628\verb|sieve(m,<variable list>)| \index{sieve} 2629 2630\pbx{sieves out all base elements with leading terms having a factor 2631contained in the specified variable list (a subset of the variables 2632of the current base ring). Useful for elimination problems solved 2633``by hand''.} 2634 2635\verb|singular_locus(M,c)| \index{singular\_locus} 2636 2637\pbx{returns the defining ideal of the singular locus of $Spec\ S/M$ 2638where $M$ is an ideal of codimension $c$, adding to $M$ the generators 2639of the ideal of the $c$-minors of the Jacobian of $M$.} 2640 2641\verb|submodulep(m,gb)| \index{submodulep} 2642 2643\pbx{tests, whether $m$ is a submodule of $gb$ (returns YES or NO).} 2644 2645\verb|sym(M,vars)|\index{sym} 2646 2647\pbx{Computes the symmetric algebra $Sym(M)$ where $M$ is an ideal 2648defined over the current base ring $S$. {\tt vars} is a list of new 2649variable names, one for each generator of $M$. They are used to create 2650a second ring $R$ to return an ideal $J$ such that $(S\oplus R)/J$ is 2651the desired symmetric algebra over the new current base ring $S\oplus 2652R$.} 2653 2654\verb|symbolic_power(m,d)| \index{symbolic\_power} 2655 2656\pbx{returns the $d$th symbolic power of the prime dpmat ideal $m$.} 2657 2658\verb|syzygies m| \index{syzygies} 2659 2660\pbx{returns the first syzygy module of the bounded identifier $m$.} 2661 2662\verb|tangentcone gb| \index{tangentcone} 2663 2664\pbx{returns the tangent cone part, i.e.\ the homogeneous part of 2665highest degree with respect to the first degree vector of the term 2666order from the \gr basis elements of the dpmat $gb$. The term order 2667must be a degree order.} 2668 2669\verb|unmixedradical m| \index{unmixedradical} 2670 2671\pbx{returns the unmixed radical of the dpmat ideal $m$.} 2672 2673\verb|varopt m| \index{varopt} 2674 2675\pbx{finds a heuristically optimal variable order, see \cite{BGK}. 2676\[\tt vars:=varopt\ m;\ setring(vars,\{\},lex);\ setideal(m,m);\] 2677changes to the lexicographic term order with heuristically best 2678performance for a lexicographic \gr basis computation.} 2679 2680\verb|WeightedHilbertSeries(m,w)| \index{WeightedHilbertSeries} 2681 2682\pbx{returns the weighted Hilbert series of the dpmat $m$. Note that 2683$m$ is not a bounded identifier and hence not checked to be a \gr 2684basis. $w$ is a list of integer weight vectors.} 2685 2686\verb|zeroprimarydecomposition m| \index{zeroprimarydecomposition} 2687 2688\pbx{returns the primary decomposition of the zerodimensional dpmat 2689$m$ as a list of $\{component, associated\ prime\}$ pairs.} 2690 2691\verb|zeroprimes m| \index{zeroprimes} 2692 2693\pbx{returns the list of primes of the zerodimensional dpmat $m$.} 2694 2695\verb|zeroradical gb| \index{zeroradical} 2696 2697\pbx{returns the radical of the zerodimensional ideal $gb$.} 2698 2699\verb|zerosolve m|, \verb|zerosolve1 m| and \verb|zerosolve2 m| 2700\index{zerosolve}\index{zerosolve1}\index{zerosolve2} 2701 2702\pbx{Returns for a zerodimensional ideal a list of triangular systems 2703that cover $Z(m)$. {\tt Zerosolve} needs a pure lex.\ term order for 2704the ``fast'' turn to lex.\ as described in \cite{Moeller}, {\tt 2705Zerosolve1} is the ``slow'' turn to lex.\ as described in \cite{efgb}, 2706and {\tt Zerosolve2} incorporated the FGLM term order change into {\tt 2707Zerosolve1}.} 2708\end{quote} 2709\pagebreak 2710 2711 2712\section{The CALI Module Structure} 2713\vfill 2714 2715\begin{tabular}{|p{1.5cm}||p{5.5cm}|p{2cm}|p{4cm}|} 2716\hline 2717\sloppy 2718 2719name & subject & data type & representation \\ 2720\hline 2721 2722cali & Header module, contains \linebreak 2723global variables, switches etc. & --- & ---\\ 2724 2725bcsf & Base coefficient arithmetic & base coeff. & standard forms \\ 2726 2727ring & Base ring setting, definition of the term order & base ring & 2728special type RING\\ 2729 2730mo & monomial arithmetic & monomials & (exp. list . degree list)\\ 2731 2732dpoly & Polynomial and vector arith\-metic & dpolys & list of terms\\ 2733 2734bas & Operations on base lists & base list & list of base elements \\ 2735 2736dpmat & Operations on polynomial matrices, the central data type of 2737CALI & dpmat & special type DPMAT\\ 2738 2739red & Normal form algorithms & --- & ---\\ 2740 2741groeb & \gr basis algorithm and related ones & --- & ---\\ 2742 2743groebf & the \gr factorizer and its extensions & --- & ---\\ 2744 2745matop & Operations on (lists of) \linebreak dpmats that correspond to 2746ideal/module operations & --- & ---\\ 2747 2748quot & Different quotient algorithms & --- & --- \\ 2749 2750moid & Monomial ideal algorithms & monomial ideal & list of monomials \\ 2751 2752hf & weighted Hilbert series & -- & -- \\ 2753 2754res & Resolutions of dpmats & resolution & list of dpmats \\ 2755 2756intf & Interface to algebraic mode & --- & ---\\ 2757 2758odim & Algorithms for zerodimensional ideals and modules & --- & ---\\ 2759 2760prime & Primary decomposition and related questions & --- & ---\\ 2761 2762scripts & Advanced applications & --- & ---\\ 2763 2764calimat & Extension of the matrix package & --- & ---\\ 2765 2766lf & The dual bases approach & --- & ---\\ 2767 2768triang & (Zero dimensional) triangular systems & --- & ---\\ 2769\hline 2770\end{tabular} 2771\vfill 2772\pagebreak 2773 2774\begin{theindex} 2775 2776 \item affine\_monomial\_curve, 33, 36 2777 \item affine\_points, 7, 35, 36 2778 \item affine\_points1!*, 35 2779 \item algebraic numbers, 13 2780 \item analytic\_spread, 33, 36 2781 \item annihilator, 28, 36 2782 \item assgrad, 33, 36 2783 2784 \indexspace 2785 2786 \item bas\_detectunits, 23 2787 \item bas\_factorunits, 23 2788 \item bas\_getrelations, 20 2789 \item bas\_removerelations, 20 2790 \item bas\_setrelations, 20 2791 \item base coefficients, 13 2792 \item base elements, 19 2793 \item base ring, 9, 17 2794 \item basis, 13 2795 \item bcsimp, 14 2796 \item BettiNumbers, 30, 36 2797 \item binomial, 7 2798 \item blockorder, 10, 18 2799 \item blowup, 7, 33, 36 2800 \item border basis, 8 2801 \item bounded identifier, 13, 36 2802 2803 \indexspace 2804 2805 \item cali, 16 2806 \item cali!=basering, 9, 16, 18 2807 \item cali!=degrees, 12, 16, 18 2808 \item cali!=monset, 16, 25 2809 \item change of term orders, 7 2810 \item change\_termorder, 35, 37 2811 \item change\_termorder1, 35, 37 2812 \item clearcaliprintterms, 16 2813 \item codim, 29, 37 2814 \item column degree, 12 2815 2816 \indexspace 2817 2818 \item degree, 30, 37 2819 \item degree vectors, 9 2820 \item degreeorder, 10, 18 2821 \item degsfromresolution, 37 2822 \item deleteunits, 23, 37 2823 \item detectunits, 14, 23 2824 \item dim, 8, 29, 37 2825 \item dimzerop, 31, 37 2826 \item directsum, 37 2827 \item dmode, 13 2828 \item dp\_pseudodivmod, 14, 19, 28 2829 \item dpgcd, 19, 37 2830 \item dpmat, 8, 12, 13, 20 2831 \item dpmat\_coldegs, 20 2832 \item dpmat\_cols, 20 2833 \item dpmat\_gbtag, 20 2834 \item dpmat\_list, 20 2835 \item dpmat\_rows, 20 2836 \item dual bases, 6, 7, 34, 35 2837 2838 \indexspace 2839 2840 \item easydim, 26, 29, 37 2841 \item easyindepset, 29, 37 2842 \item easyprimarydecomposition, 32, 37 2843 \item ecart, 3, 19 2844 \item ecart vector, 8, 11, 40 2845 \item efgb, 16 2846 \item eliminate, 7, 27, 38 2847 \item eliminationorder, 10, 18 2848 \item eqhull, 32, 38 2849 \item evlf, 17 2850 \item extended \gr factorizer, 7, 15, 26 2851 \item extendedgroebfactor, 26, 38 2852 \item extendedgroebfactor1, 26, 38 2853 2854 \indexspace 2855 2856 \item factorunits, 15, 23 2857 \item flatten, 8 2858 \item free identifier, 13 2859 2860 \indexspace 2861 2862 \item gb-tag, 8, 20 2863 \item gbasis, 24, 38 2864 \item gbtestversion, 7, 8, 16, 24 2865 \item getdegrees, 12 2866 \item getecart, 11 2867 \item getkbase, 31, 38 2868 \item getleadterms, 38 2869 \item getring, 11 2870 \item getrules, 13 2871 \item global procedures, 5 2872 \item GradedBettiNumbers, 30 2873 \item gradedbettinumbers, 38 2874 \item groeb, 7 2875 \item groeb!=rf, 16 2876 \item groeb\_homstbasis, 24 2877 \item groeb\_lazystbasis, 24 2878 \item groeb\_mingb, 25 2879 \item groeb\_minimize, 25 2880 \item groeb\_stbasis, 24 2881 \item groebf\_zeroprimes1, 27 2882 \item groebfactor, 26, 38 2883 2884 \indexspace 2885 2886 \item hardzerotest, 15 2887 \item hf!=hf, 16 2888 \item hf\_whilb, 30 2889 \item hf\_whilb3, 30 2890 \item hf\_whs\_from\_resolution, 30 2891 \item hftestversion, 8, 16, 30 2892 \item HilbertSeries, 8, 11, 30, 38 2893 \item homstbasis, 25, 38 2894 2895 \indexspace 2896 2897 \item ideal2mat, 12, 38 2898 \item ideal\_of\_minors, 21, 38 2899 \item ideal\_of\_pfaffians, 21, 39 2900 \item idealpower, 39 2901 \item idealprod, 39 2902 \item idealquotient, 27, 28, 39 2903 \item ideals, 12 2904 \item idealsum, 39 2905 \item indepvarsets, 29, 39 2906 \item initmat, 39 2907 \item internal procedures, 5 2908 \item interreduce, 23, 39 2909 \item isolatedprimes, 32, 39 2910 \item isprime, 32, 39 2911 \item iszeroradical, 39 2912 2913 \indexspace 2914 2915 \item lazy, 7 2916 \item lazystbasis, 25, 39 2917 \item lexefgb, 15, 27 2918 \item lexicographic, 9 2919 \item listgroebfactor, 26, 39 2920 \item listminimize, 6 2921 \item listtest, 6 2922 \item local procedures, 5 2923 \item localorder, 10, 18 2924 2925 \indexspace 2926 2927 \item map, 32 2928 \item mat2list, 8, 12, 39 2929 \item matappend, 40 2930 \item mathomogenize, 40 2931 \item mathprint, 17 2932 \item matintersect, 7, 27, 40 2933 \item matjac, 21, 40 2934 \item matqquot, 28, 40 2935 \item matquot, 28, 40 2936 \item matstabquot, 28, 40 2937 \item matsum, 40 2938 \item minimal\_generators, 34, 40 2939 \item minors, 21, 40 2940 \item mod, 23, 40 2941 \item modequalp, 8, 27, 40 2942 \item module 2943 \subitem bcsf, 17 2944 \subitem cali, 5 2945 \subitem calimat, 8, 21 2946 \subitem dpmat, 20 2947 \subitem groeb, 24 2948 \subitem groebf, 7, 26 2949 \subitem lf, 7, 17 2950 \subitem moid, 28 2951 \subitem mora, 7 2952 \subitem odim, 7, 31 2953 \subitem prime, 31 2954 \subitem ring, 17 2955 \subitem scripts, 7, 32 2956 \subitem triang, 26, 27 2957 \item module quotient, 27 2958 \item module term order, 12 2959 \item modulequotient, 28, 40 2960 \item modules, 12 2961 \item moid\_primes, 29 2962 2963 \indexspace 2964 2965 \item Noetherian, 3, 15 2966 \item normalform, 23, 41 2967 \item nzdp, 34, 41 2968 2969 \indexspace 2970 2971 \item odim\_borderbasis, 31 2972 \item odim\_parameter, 31 2973 \item odim\_up, 31 2974 \item oldbasis, 17 2975 \item oldborderbasis, 17 2976 \item oldring, 17 2977 2978 \indexspace 2979 2980 \item pfaffian, 21, 41 2981 \item preimage, 7, 32, 41 2982 \item primarydecomposition, 7, 41 2983 \item printterms, 16 2984 \item proj\_monomial\_curve, 33, 41 2985 \item proj\_points, 7, 35, 41 2986 \item proj\_points1!*, 35 2987 2988 \indexspace 2989 2990 \item radical, 32, 41 2991 \item random\_linear\_form, 21, 41 2992 \item ratpreimage, 33, 41 2993 \item red, 7 2994 \item red\_better, 22 2995 \item red\_extract, 23 2996 \item red\_Interreduce, 23 2997 \item red\_prepare, 23 2998 \item red\_redpol, 23 2999 \item red\_Straight, 22 3000 \item red\_TailRed, 22 3001 \item red\_TailRedDriver, 22 3002 \item red\_TopInterreduce, 23 3003 \item red\_TopRed, 22 3004 \item red\_TopRedBE, 22 3005 \item red\_total, 15 3006 \item red\_TotalRed, 22 3007 \item Resolve, 7, 30, 42 3008 \item reverse lexicographic, 8, 9 3009 \item ring, 13 3010 \item ring\_2a, 17 3011 \item ring\_define, 17 3012 \item ring\_degrees, 17 3013 \item ring\_ecart, 17 3014 \item ring\_from\_a, 17 3015 \item ring\_isnoetherian, 17 3016 \item ring\_lp, 18 3017 \item ring\_names, 17 3018 \item ring\_rlp, 18 3019 \item ring\_sum, 18 3020 \item ring\_tag, 17 3021 \item rules, 16 3022 3023 \indexspace 3024 3025 \item savemat, 42 3026 \item setcaliprintterms, 16 3027 \item setcalitrace, 8, 15 3028 \item setdegrees, 12, 16 3029 \item setgbasis, 8, 42 3030 \item setideal, 13, 14 3031 \item setkorder, 18 3032 \item setmodule, 13, 14 3033 \item setmonset, 16, 25 3034 \item setring, 7, 9, 11, 14, 16, 18 3035 \item setrules, 13, 14, 16, 17, 19 3036 \item sieve, 42 3037 \item singular\_locus, 21, 42 3038 \item stable quotient, 27 3039 \item sublist, 17 3040 \item submodulep, 27, 42 3041 \item switch 3042 \subitem bcsimp, 17 3043 \subitem hardzerotest, 13 3044 \subitem lexefgb, 16, 27 3045 \subitem Noetherian, 10, 18 3046 \item sym, 7, 34, 42 3047 \item symbolic\_power, 34, 42 3048 \item syzygies, 24, 42 3049 \item syzygies1, 24 3050 3051 \indexspace 3052 3053 \item tangentcone, 42 3054 \item term, 19 3055 \item trace, 16 3056 \item tracing, 8 3057 \item triang, 7 3058 \item triangular systems, 7, 26 3059 3060 \indexspace 3061 3062 \item unmixedradical, 32, 42 3063 3064 \indexspace 3065 3066 \item varlessp, 17 3067 \item varnames, 17 3068 \item varopt, 34, 43 3069 3070 \indexspace 3071 3072 \item WeightedHilbertSeries, 8, 29, 30, 43 3073 3074 \indexspace 3075 3076 \item zeroprimarydecomposition, 31, 32, 43 3077 \item zeroprimes, 31, 43 3078 \item zeroradical, 31, 43 3079 \item zerosolve, 15, 27, 43 3080 \item zerosolve1, 15, 27, 43 3081 \item zerosolve2, 27, 43 3082 3083\end{theindex} 3084 3085\pagebreak 3086 3087\begin{thebibliography}{xxx} 3088\bibitem{BS} D. Bayer, M. Stillman: Computation of Hilbert 3089functions. {\it J. Symb. Comp. \bf 14} (1992), 31 - 50. 3090\bibitem{BKW} T. Becker, H. Kredel, V. Weispfenning: \gr bases. A 3091computational approach to commutative algebra. Grad. Texts in Math. 3092141, Springer, New York 1993. 3093\bibitem{BCRT} A. M. Bigatti, P. Conti, L. Robbiano, C. Traverso: A 3094``divide and conquer'' algorithm for Hilbert-Poincare series, 3095multiplicity and dimension of monomial ideals. In: Proc. AAECC-10, 3096LNCS 673 (1993), 76 - 88. 3097\bibitem{BGK} W. Boege, R. Gebauer, H. Kredel: Some examples for 3098solving systems of algebraic equations by calculating \gr bases. {\it 3099J. Symb. Comp. \bf 2} (1986), 83 - 98. 3100\bibitem{B1} B. Buchberger: \gr bases: An algorithmic method in 3101polynomial ideal theory. In: Recent trends in multidimensional 3102system theory (N.~K.~Bose ed), Reidel, Dortrecht 1985, 184 - 232. 3103\bibitem{B2} B. Buchberger: Applications of \gr bases in non-linear 3104computational geometry. LNCS 296 (1988), 52 - 80. 3105\bibitem{CLO} D. Cox, J. Little, D. O'Shea: Ideals, varieties, and 3106algorithms. Undergraduate Texts in Math., Springer, New York 1992. 3107\bibitem{E} D. Eisenbud: Commutative algebra with a view toward 3108algebraic geometry. Springer, 1995. 3109\bibitem{FGLM} Faugere, Gianni, Lazard, Mora: Efficient computations 3110of zerodimensional \gr bases by change of ordering. {\it 3111J. Symb. Comp. \bf 16} (1993), 329 - 344. 3112\bibitem{GTZ} P. Gianni, B. Trager, G. Zacharias: \gr bases and 3113primary decomposition of polynomial ideals. {\it J. Symb. Comp. \bf 31146} (1988), 149 - 167. 3115\bibitem{GMNRT} A. Giovini, T. Mora, G. Niesi, L. Robbiano, C. 3116Traverso: "One sugar cube, please" or Selection strategies in the 3117Buchberger algorithm. In: Proceedings of the ISSAC'91, ACM Press 31181991, 49 - 54. 3119\bibitem{rois} H.-G. Gr\"abe: Two remarks on independent sets. 3120{\it J. Alg. Comb. \bf 2} (1993), 137 - 145. 3121\bibitem{tcah} H.-G. Gr\"abe: The tangent cone algorithm and 3122homogenization. {\it J. Pure Applied Alg.\bf 97} (1994), 303 - 312. 3123 3124\bibitem{ala} H.-G. Gr\"abe: Algorithms in local algebra. To appear 3125 3126\bibitem{fgb} H.-G. Gr\"abe: On factorized \gr bases. Report Nr. 6 3127(1994), Inst. f. Informatik, Univ. Leipzig. 3128 3129To appear in: Proc. ``Computer Algebra in Science and Engineering'', 3130Bielefeld 1994. 3131 3132\bibitem{efgb} H.-G. Gr\"abe: Triangular systems and factorized \gr 3133bases. Report Nr. 7 (1995), Inst. f. Informatik, Univ. Leipzig. 3134 3135\bibitem{primary} H.-G. Gr\"abe: Factorized \gr bases and primary 3136decomposition. To appear. 3137 3138\bibitem{Kr} H. Kredel: Primary ideal decomposition. In: Proc. 3139EUROCAL'87, Lecture Notes in Comp. Sci. 378 (1986), 270 - 281. 3140\bibitem{KW} H. Kredel, V. Weispfenning: Computing dimension and 3141independent sets for polynomial ideals. {\it J. Symb. Comp. \bf 6} 3142(1988), 231 - 247. 3143\bibitem{MMM} M. Marinari, H.-M. M\"oller, T. Mora: \gr bases of 3144ideals given by dual bases. In: Proc. ISSAC'91, ACM Press 1991, 55 - 314563. 3146\bibitem{Mishra} B. Mishra: Algorithmic Algebra. Springer, New York 31471993. 3148\bibitem{MM} H.-M. M\"oller, F. Mora: New constructive methods in 3149classical ideal theory. {\it J. Alg. \bf 100} (1986), 138 -178. 3150\bibitem{Moeller} H.-M. M\"oller: On decomposing systems of polynomial 3151equations with finitely many solutions. {\em J. AAECC \bf 4} (1993), 3152217 - 230. 3153\bibitem{MR88} T. Mora, L. Robbiano: The Gr\"obner fan of an ideal. 3154{\it J. Symb. Comp. \bf 6} (1988), 183 - 208. 3155\bibitem{Mo88} T. Mora: Seven variations on standard bases. 3156Preprint, Univ. Genova, 1988. 3157\bibitem{MPT} T. Mora, G. Pfister, C. Traverso: An introduction to 3158the tangent cone algorithm. In: {\em Issues in non-linear geometry and 3159robotics, C.M. Hoffman ed.}, JAI Press. 3160\bibitem{Ro} L. Robbiano: Computer algebra and commutative algebra. 3161LNCS 357 (1989), 31 - 44. 3162\bibitem{Ru} E. W. Rutman: \gr bases and primary decomposition of 3163modules. {\it J. Symb. Comp. \bf 14} (1992), 483 - 503. 3164 3165\end{thebibliography} 3166 3167\end{document} 3168 3169