\section{Background} The Gr\"{o}bner programme {\bf bergman} was originally made with one purpose: to give up flexibility in order (hopefully) to gain efficiency. To-day, a limited couple of choices are incorporated, but only where this could be done without clashing with the efficiency. This version is written in Standard Lisp, with some extensions (mainly from PSL). As far as possible, the extensions are provided in several versions, one of which is based entirely on Standard Lisp, as it is defined in the Salt Lake City Standard Lisp report. (The main non-standard items are: COND's are used with more than two items per "COND pair", and algforminput uses the psl scanner.) The extension handling is done in slext.sl. {\bf Bergman} may also be compiled under (PSL based) Reduce. Such variants start an ordinary Reduce (in symbolic mode). You may then either work with LISP commands as in any {\bf bergman} , or pass to algebraic mode, and whenever you wish submit a list of polynomials to {\bf bergman}, receiving a list of the reduced Gr\"{o}bner basis for the corresponding ideal. You should note that you still have to set up the {\bf bergman} "modes" separately in the ordinary way. (E.g., Reduce has an inbuilt possibility to set characteristic. However, this works completely separate from {\bf bergman}s "coefficient mode", where you also may set a positive characteristic.) Like some higher level algebraic manipulation languages, objects like monomials and polynomials are internally represented as LISP objects, and algebraic operations are represented by procedures containing much more CAR and CDR than PLUS or TIMES. However, regarded as an algebraic manipulation attempt it is indeed very poor, and also not very structured. Instead, the object representations are simple, occupy (comparatively) small space, and the algebraic manipulation procedures make few function calls. (In general, but not consistently, if a slight variation of a routine is needed, a separate very similar procedure is written, instead of procedures calling the same subprocedures with different parameters.) Thus, if the compiler is efficient, the compiled functions ought to be fast. Another loss of flexibility is given by the fixed context for the ideals. The only permitted coefficient rings $K$ are the prime fields, (i. e. $ Q$, the field of rationals, and $Z/(p)$, the Galois field with a prime number $p$ of elements). However, only integer coefficients are actually allowed as input. (If you run {\bf bergman}--under--Reduce, there is also a possibility to use Reduce Standard Forms as coefficients, however. See the manual!) The ideal considered must be given by homogeneous generators (in a finite set of transcendental variables over$ K$); and for many purposes each variable must have weight 1. Only homogeneous polynomials might be reduced with respect to the resulting Gr\"{o}bner basis. Only the total--degree -- reverse--lexicographical and the total--degree -- lexicographical orderings are supported in the commutative variant, and only the total--degree -- lexicographical ordering is supported in the non--commutative one. In the non--commutative version, the problem that then in general the algorithm does not terminate is ignored. However, the user may demand degreewise output, and thus may employ the programme in order to get a partial Gr\"{o}bner basis. On the other hand, the arbitrary large integer precision arithmetic of Standard Lisp is assumed and employed. The prerequisits were in the first hand chosen so as to suite one specific problem, namely the cyclic n-root calculations. (Cf. the references at the end of this document.) The scope has been expanded somewhat, mainly in response to concrete problems of our colleagues and as a result of information and discussions within the POSSO project. The programme utilise the homogeneity in order to make (relatively) efficient tests for being able to discard certain potential S-polynomials. In version 0.9*, there is (in the commutative case) an alternative to the Buchberger algorithm, the `staggered linear basis with substance' (s.a.w.s.) algorithm. In the non-commutative case, an algorithm for calculating the beginning of the Hilbert series is available. \section{Organisation of the programme source files} There is a certain amout of modularisation of BERGMAN. The programme is divided into 'units', each of which corresponds to one or several separate files. In these it is noted which procedures and special variables are ''imported'' from other units, and which ''exported'', i. e., used in other units. This does NOT constitute ''modules'' in the C sense, since almost all procedures are defined and equally available everywhere in the final programme. In order to disencourage the use of lower level procedures or variables in ordinary applications, these use mixed upper and lower case letters (which makes them harder to access directly when the flag RAISE is on, as it generally is). There are some exceptions in upper cases; these are listed as ''available'' (if not exported), documented, and intended for general use. As a matter of fact, the code to a high extent is written AS IF it were truly modularised. Thus there are in general only some specified procedures from one module used in the others, and these and their action are documented in the file protocol.txt. Very often such procedures are defined in different versions. In fact, ''to change mode'' in bergman mainly means ''to replace one set of function definitions with another''. Each unit is referred to in comments by its ''bare name'' 'foo'. The corresponding source file has the bare name suffixed by .sl; compiled versions, et cetera, will of course have other extensions. Thus, the source files of the monomial manipulation unit 'monom' and 'ncmonom' are named monom.sl and ncmonom.sl, respectively; in both, versions of the ''exported'' monomial manipulation procedures are defined, in commutative and non-commutative variants, respectively. There are also some ''header'' files, with macros and with some general lisp procedures; and ''file handler'' files, used to compile the source files and to add some top level interface procedures. These files probably are more sensitive to changes of system than the 'ordinary' source files; you may wish to or have to rewrite some of them. Please then keep the old files for reference! \section{Overview of the (main) units and source files} %as per 1996-08: %hseries.sl reduct.sl pad polynom.sl \begin{center} "FILE HANDLER" FILES: \end{center} \begin{tabular}{ll} compan.sl & Performs the compiling of sourse files for Anick reslolution \\ & Anick reslolution and Betti numbers computation\\ compile.sl & Compiling all main units \\ bmtop.sl & Loads main compiled units and creats BERGMAN \\ topproc.sl & Contains the top-of-the-top level functions. \\ \end{tabular} \begin{center} "HEADER" MACRO FILES: \end{center} \begin{tabular}{ll} macros &General macro file (used in all compilation)\\ accmacr &Macro files used when compiling SAWS unit(s)\\ subsmacr &\\ midmacr &\\ \end{tabular} \begin{center} "LISP EXTENSIONS": \end{center} \begin{tabular}{ll} slext &Defining procedures not in the Standard Lisp document.\\ &(Uses macros.sl. May be used in the compilation of all\\ &other files.)\\ & At present, there are surely several omissions in this\\ &file.\\ alg2lsp &psl Maple- and Reduce-like input parcer procedures.\\ \end{tabular} \begin{center} CENTRAL UNITS: \end{center} \begin{tabular}{ll} Strategic:main &Main functions; S-pair constructions.\\ strategy &Graph component algorithm for eliminating redundant\\ &S-polynomial caculations.\\ \end{tabular} \begin{center} INTERFACE: \end{center} \begin{tabular}{ll} inout & Input and output routines.\\ alg2lsp &\\ \end{tabular} \begin{center} MONOMIAL: \end{center} \begin{tabular}{ll} monom &Monomial handling (including PUREMON manipulations).\\ ncmonom &Non-commutative monomials handling (including PUREMON\\ &manipulations).\\ reclaim &Garbage collection routines. (Could be dependent on\\ &EVERYTHING else, including on the machine.)\\ 'reductions' &Normal form calculations, and other polynomial handling.\\ &Contains some general routines, and some specific for the\\ &char 0 case.\\ \end{tabular} \begin{center} COEFFICIENTS: \end{center} \begin{tabular}{ll} coeff &Coefficient arithmetic handling. Contains mainly means\\ &to use for changing or modifying the coefficient\\ &arithmetics; e. g., by calling on a modulus changer\\ &auxiliary.\\ char0 &Default ( = characteristic 0) coefficient manipulation\\ &procedures.\\ \end{tabular} \begin{center} SPECIAL PURPOSE AUXILIARY UNITS\\ (hopefully loaded automathically when needed): \end{center} \begin{tabular}{ll} odd &Modulus changer auxiliary, compiled and (re)loaded when a\\ &characteristic > 2 (without 'look-up logarithms') is set.\\ logodd &Modulus changer auxiliary, compiled and (re)loaded when a\\ &characteristic > 2 is set, while the 'look-up logarithms'\\ &is active.\\ char2 &Modulus changer auxiliary, loaded when the characteristic\\ &is set to 2.\\ pbseries &Loaded when the double Poincare-Betti series or the Hilbert\\ &series of the associated non-commutative monomially related\\ &algebra is demanded.\\ checkstg, &These files are compiled into the file stg.b, which should\\ accproc, &be loaded automatically (from stagsubstance.sl) when any\\ subsproc, &SAWS (Staggering Algorithm With Substance) procedure\\ & is called.\\ stg,&\\ monomstg,&\\ bind,&\\ write,&\\ ideal&\\ \end{tabular} \begin{center} SOME OTHER THINGS: \end{center} \begin{tabular}{ll} auxil &Extras, not necessary for ordinary usage.\\ debug &Debugging facilities (only for development usage). Not\\ &compiled (as standard).\\ homog &Procedures enabling non-homogeneous input and output; under\\ &development. Not compiled (as standard).\\ \end{tabular} These units do not include any user interface (or e.g. Reduce interface) worthy of mention. Interfaces should be built, picking the 'AVAILABLE' routines you wish from the units. Right now, ''initgr'' and ''initncgr'' provide some sorts of (bad) partial interfaces; also viz. the *prep files. \section{Basic structures and naming conventions} The polynomials are saved as lists of monomials--with--coefficients (COEFFMONOMIALs or ''terms''). An (augmented) monomial consists of three parts. ... is represented by the appropriate exponents of ALL the variables (appearing in the monomial, or not). There is also a rather important part of the monomial, the POINTER; this tells about the Gr\"{o}bner reduction status of the monomial. The MONOMIALs with pointers but without coefficients) are represented uniquely, so that equal monomials have EQ representations. This is done by means of an analogue of the OBLIST structure, called the MONLIST. The POINTER is augmented by a kind of property list for the monomial. In a polynomial, only non-zero coefficient monomials are represented, and they all MUST be of the same total degree. They are sorted by decreasing order (REVLEX or LEX), whence the leading monomial (LeadMon) always comes first. However, normally a polynomial is "augmented" by having NIL or a priority number even 'firster'. Lists of polynomials are either just that, or - in the case of lists of Gr\"{o}bner basis elements (Gbe's) - lists of their LeadMons. (The pointer value of a Gbe LeadMon is precisely that Gbe, whence this causes no loss of information.) In both cases, the polynomials are sorted by DEG-REVLEX or DEG-LEX ordering with respect to their LeadMons. Objects with the same total-degree sometimes are collected on a sublist, which begins with this degree. (This is referred to as ''degree separation''.) The following is a not quite formal description of basic structures. Note that there is not present a formal grammar presented, but a description of LISP objects. In particular, the apparent circulus virtuosis POINTER$->$ AUGMENTED POLYNOMIAL$->$ COEFFMONOMIAL$->$ MONOMIAL$->$ POINTER is a real one; thus the structures are not always printable (and in creating them RPLACA/RPLACD must be used). list(A) signifies a LISP list of at least one object (of type) A. dp(A,B) signifies a LISP dotted pair of A and B, (A . B). NIL, T are the LISP reserved atoms NIL, T. % <> \vspace*{0.3cm} \begin{tabular}{lcl} MONOMIAL & ::=& dp(POINTER,PUREMON)\\ (n.c. MONOMIAL & ::=& dp(dp(POINTER,PROPLIST),\\ & &PUREMON) )\\ POINTER & ::=& NIL | T | \\ & &AUGMENTED POLYNOMIAL | \\ & & list(dp(MONOMIAL,MONOMIAL))\\ COEFFMONOMIAL & ::= &dp(COEFFICIENT,MONOMIAL)\\ COEFFICIENT & ::=& non-zero NUMBER\\ NUMBER & ::=& integer of any size\\ POLYNOMIAL & ::=& list(COEFFMONOMIAL)\\ AUGMENTED POLYNOMIAL& ::=& dp(PRIORITY,POLYNOMIAL)\\ PRIORITY & ::=& NIL | T | NUMBER\\ \end{tabular} \vspace*{0.3cm} (\ldots, \ldots, \ldots) denotes a structure. The items may be on the forms identifier or identifier1:identifier2 . In the second case, identifyer1 signifies the type of the constituend, while identifier2 is the name with which it is denoted in this explanation. (It is of no significance in the source files, since these things are not really implemented as structures.) \ldots | \ldots \ \ldots signifies alternatives, as in C unions. $*$ denotes ''note below''. \begin{tabular}{lcl} NUMBER & ::=& integer of any size\\ POSITIVE & ::=& positive integer of any size\\ NON-NEGATIVE & ::=& 0 | POSITIVE\\ InterfaceMonomial & ::=& list(NON-NEGATIVE) *\\ InterfaceCoefficient& ::= &NUMBER\\ InterfaceTerm & ::=& dp(InterfaceCoefficient,InterfaceMonomial)\\ InterfacePolynomial & ::=& list(InterfaceTerm)\\ Monomial & ::= &{PureMonomial, MonomialPointer, PropertyList}\\ MonomialPointer & ::=& NIL | T | Redor | \\ && list(dp(Monomial,Monomial))\\ RedandTerm & ::=& {RedandCoefficient,Monomial}\\ RedorTerm & ::=& {RedorCoefficient,Monomial}\\ Term & ::=& RedandTerm | RedorTerm\\ PureRedand & ::=& NIL |{RedandTerm: Head, PureRedand: Tail}\\ PureRedor & ::=& NIL | {RedorTerm: Head, PureRedor: Tail}\\ Redand & ::= &{ReductionPriority, PureRedand: PurePart} *\\ Redor & ::=& {ReductionPriority, PureRedor: PurePart} *\\ ReductionPriority & ::= &NIL | NUMBER\\ \end{tabular} NOTES: An InterfaceMonomial in the commutative case is a list of (non-negative) exponents, with a length = the (fixed) number of variables. They are assumed to be (and stay) of inum sizes. In the non-commutative case, it is a list of (strictly) positive integers, the variable indices, also assumed to be and remain of inum size. The PureParts of Redands and Redors may become NIL within a procedure, but the only procedure who may return a Redand with a NIL PurePart is mkAPol() $<<$CHANGE THE NAME TO MkRedand$>>.$ No procedure may return a Redor with NIL PurePart. A 'PUREMON' is regarded as an atom, except in the 'monomials' and 'reclaim' units. Right now, it is implemented as a reverse order LISP list of exponents (including zeroes). (The PROPLIST is organised as an ordinary lisp property list. It is available for the user by means of the PUTM, GETM and PUTGETM procedures.) The different data structure types correspond to certain lower case argument names and certain Capitalised Procedure Constituends, as listed below. Thus, if a procedure has one NUMBER argument (which may well be a COEFFICIENT or a PRIORITY), then this always is called numb. If it has two NUMBER arguments, they are called numb1 and numb2. In addition, in most of the cases the procedure name will contain an N. One list/dotted pair of numbers argument is called lnumb/dpnumb. Different arguments or procedure name constituends are enumerated in the PNM or 'revlex' order polynomial(s), number(s), monomial(s). \begin{tabular}{lcl} Data type & Constituend & Argument\\ & & \\ PUREMON & Mon & inxs\\ MONOMIAL & Mon & mon\\ COEFFMONOMIAL & Mon & cfmon\\ NUMBER & N & numb\\ POLYNOMIAL & Pol & pol\\ AUGMENTED POLYNOMIAL & Pol & augpol\\ \end{tabular} Further conventions: Mult, Quot stands for operations with both/all arguments specified in the procedure name. Sometimes an operation is performed only on a part of a polynomial (PolPart). A position in the list representing the polynomial where (part of) a procedure is to stop or start, as an argument is called place or returnstart. c stands for "current". Gr\"{o}bner basis may be abbreviated e.g. gbasis or gb. Most of these and other abbreviations are probably fairly self- explanatory. \section{Global structures and programme outline } The most important global structures are: \begin{itemize} \item InPols, the input polynomials (the original ideal basis); \item cInPols, ditto of current degree; \item SPairs, the pairs of LeadMons to investigate; \item cSPairs, ditto of current degree; \item GBasis, the Gr\"{o}bner basis; and \item cGBasis, the new Gr\"{o}bner basis elements (of current degree). \end{itemize} They are described below. "Current degree" here stands for "The value of the global variable cDeg". InPols is organised as a list of (zero or more) degree-lists, where each degree-list has a degree NUMBER as its car, and a positive number of AUGMENTED POLYNOMIALs (ordered increasingly w.r.t their LeadMons) as the rest of its elements. (Of course the polynomials in one degree--list all have that total--degree.) The degree--lists are ordered by increasing degree. In the beginning of an ordinary application of the main procedure, GROEBNERKERNEL (found in 'ner'), InPols contains all input poly- nomials. As the work progresses, more and more of these are removed from InPols and processed; thus, in the end InPols is empty. At a given time, InPols contains the input polynomials of higher total- degree than the current degree, while the unprocessed ones of the current degree are listed on cInPols. SPairs is a list of degree--lists, each of which has a degree as its car and MONOMIALs (of that total--degree) as the rest of its elements. Each such MONOMIAL is the lcm of at least one pair of LeadMons, which has not (yet) been discarded as yielding a non-trivial S--polynomial, a critical pair. Critical pairs are represented by dotted pairs of LeadMons (represented as MONOMIALs). The POINTER of the monomial is a list of critical pairs. The monomials in a degree--list are ordered increasingly; and SPairs is ordered by increasing degree. In the beginning of an ordinary GROEBNERKERNEL application, SPairs is empty. In the run of the procedure, newly found critical pairs are inserted in it (as elements of POINTERs of MONOMIALs in adequate positions), while the SPair elements of the current degree are moved to cSPairs and (in due time) processed and removed. Thus, in the end SPair once more is empty. GBasis and cGBasis are lists. Their cars are NIL; the rest of the elements are LeadMons (represented as MONOMIALs) of Gr\"{o}bner basis elements, ordered increasingly by the appropriate ordering. GBasis contains the gbe's of lower than current total--degree; these are in their final form (if the flag IMMEDIATEFULLREDUCTION is on). cGBasis contains the new--found gbe's of the current degree. They may very well change, due to reduction modulo gbe's found later but with lower ordered LeadMons. However, their LeadMons cannot change! (The fact that the main structures are GLOBAL variables makes it possible to use the main functions for slightly different purposes. E. g., in order only to perform a reduction of a polynomial P modulo a known Groebner basis B, just do\\ (RPLACD GBasis B')\\ (ReducePol P)\\ where B' is B represented in the above described way. Such variants may be found in 'auxiliaries'.) The main procedure GROEBNERKERNEL roughly works as follows: \begin{verbatim} While InPols or SPairs is non-empty do begin cDeg:= the lowest existing degree in InPols and/or SPairs ( = min(caar(InPols),caar(SPairs)), if both exist); Move the cDeg component(s) of InPols and/or SPairs to cInPols and/or cSPairs, discarding their cars (i.e., degrees); While cInPols or cSPairs is non-empty do begin If cSPairs is empty, or if car(cInPols) exists, and its LeadMon is strictly of lower order than car(cSPairs), then process car(cInPols), and remove it from cInPols, else begin SP2r:=SPolInputs(car(cSPairs)); For (a.b) in SP2r do process the S-polynomial POINTER(a)-POINTER(b); end; end; For mon in cdr(cGBasis) do PRIORITY(POINTER(mon)):=length(POINTER(mon)); If CUSTSHOW is ON then call DEGREENDDISPLAY, else if SAVEDEGREE is ON then call DEGREEOUTPUT; Consider new LeadMon-pairs among the new gbe's; Call MonReclaim; end; \end{verbatim} Here to process the augmented polynomial pol signifies: \begin{verbatim} begin NGroeb := ReducePol(pol) (i. e., the normal form of pol); If NGroeb <> 0 then (we indeed have a new gbe, whence:) begin POINTER(LeadMon(NGroeb)) := NGroeb; NGroeb := LeadMon(NGroeb); Consider new LeadMon-pairs formed by NGroeb and the old gbe's; Insert NGroeb on its proper place in cdr(cGBasis); If IMMEDIATEFULLREDUCTION is ON, then reduce other new gbe's w. r. t. NGroeb; end; end; \end{verbatim} The process SPolInputs (defined in 'compalg' or in 'noncomm') takes a MONOMIAL mon as its argument, which must have a list of critical pairs as its POINTER. It produces (more or less smartly) a final list of pairs of LeadMons of gbe's, from which S--polynomials will be calculated. (As a side effect, POINTER(mon) is changed.) At the end of the main loop of GROEBNERKERNEL, some more or less optional procedures may be called. DEGREEOUTPUT (defined in 'inout') prints the current degree gbe's, in a form decided by various global or fluid variables, e. g. OutVars, GBasOutChan, and ALGOUTMODE. In order to get its output on the file foo, perform\\ (DEGREEOUTPREPARE "foo")\\ before the GROEBNERKERNEL. (No argument = type on the standard output.) Also perform (ENDDEGREEOUTPUT) or (GROEBNERFINISH) after GROEBNERKERNEL. The form of the output may be governed by assigning ALGOUTMODE different values. (Right now, allowed values are LISP, MACAULAY, PBOUT, and ALG. The latter stands for a "general" (Maple or Reduce type) algebraic form.) On the other hand, DEGREENDDISPLAY is NOT DEFINED. Our experience seems to indicate that users often want to customise output. You may do this by defining DEGREENDDISPLAY as any EXPR with no argument, and by turning ON the flag CUSTSHOW. In this way you may also e. g. interrupt the calculations at a certain degree. Finally, MonReclaim is defined in the 'reclaim' unit. Since Gr\"{o}bner basis calculation often tend to be very space-consuming, effective reclaims may be of considerable value.