| 1 |
|
| 2 |
|
| 3 |
|
| 4 |
\section{Background} |
| 5 |
|
| 6 |
The Gr\"{o}bner programme {\bf bergman} was originally made with one purpose: |
| 7 |
to give up flexibility in order (hopefully) to gain efficiency. |
| 8 |
To-day, a limited couple of choices are incorporated, but only where |
| 9 |
this could be done without clashing with the efficiency. This version |
| 10 |
is written in Standard Lisp, with some extensions (mainly from PSL). |
| 11 |
As far as possible, the extensions are provided in several versions, |
| 12 |
one of which is based entirely on Standard Lisp, as it is defined |
| 13 |
in the Salt Lake City Standard Lisp report. (The main non-standard |
| 14 |
items are: COND's are used with more than two items per "COND pair", |
| 15 |
and algforminput uses the psl scanner.) The extension handling |
| 16 |
is done in slext.sl. |
| 17 |
|
| 18 |
{\bf Bergman} may also be compiled under (PSL based) Reduce. Such variants |
| 19 |
start an ordinary Reduce (in symbolic mode). You may then either |
| 20 |
work with LISP commands as in any {\bf bergman} , or pass to algebraic |
| 21 |
mode, and whenever you wish submit a list of polynomials to |
| 22 |
{\bf bergman}, receiving a list of the reduced Gr\"{o}bner basis for the |
| 23 |
corresponding ideal. You should note that you still have to set up |
| 24 |
the {\bf bergman} "modes" separately in the ordinary way. (E.g., Reduce |
| 25 |
has an inbuilt possibility to set characteristic. However, this |
| 26 |
works completely separate from {\bf bergman}s "coefficient mode", where |
| 27 |
you also may set a positive characteristic.) |
| 28 |
|
| 29 |
Like some higher level algebraic manipulation languages, objects like |
| 30 |
monomials and polynomials are internally represented as LISP objects, |
| 31 |
and algebraic operations are represented by procedures containing much |
| 32 |
more CAR and CDR than PLUS or TIMES. However, regarded as an algebraic |
| 33 |
manipulation attempt it is indeed very poor, and also not very |
| 34 |
structured. Instead, the object representations are simple, occupy |
| 35 |
(comparatively) small space, and the algebraic manipulation procedures |
| 36 |
make few function calls. (In general, but not consistently, if a slight |
| 37 |
variation of a routine is needed, a separate very similar procedure is |
| 38 |
written, instead of procedures calling the same subprocedures with |
| 39 |
different parameters.) Thus, if the compiler is efficient, the compiled |
| 40 |
functions ought to be fast. |
| 41 |
|
| 42 |
Another loss of flexibility is given by the fixed context for the |
| 43 |
ideals. The only permitted coefficient rings $K$ are the prime fields, |
| 44 |
(i. e. $ Q$, the field of rationals, and $Z/(p)$, the Galois field with |
| 45 |
a prime number $p$ of elements). However, only integer coefficients are |
| 46 |
actually allowed as input. (If you run {\bf bergman}--under--Reduce, there is |
| 47 |
also a possibility to use Reduce Standard Forms as coefficients, |
| 48 |
however. See the manual!) The ideal considered must be given by |
| 49 |
homogeneous generators (in a finite set of transcendental variables |
| 50 |
over$ K$); and for many purposes each variable must have weight 1. Only |
| 51 |
homogeneous polynomials might be reduced with respect to the resulting |
| 52 |
Gr\"{o}bner basis. Only the total--degree -- reverse--lexicographical and |
| 53 |
the total--degree -- lexicographical orderings are supported in the |
| 54 |
commutative variant, and only the total--degree -- lexicographical |
| 55 |
ordering is supported in the non--commutative one. |
| 56 |
|
| 57 |
In the non--commutative version, the problem that then in general the |
| 58 |
algorithm does not terminate is ignored. However, the user may demand |
| 59 |
degreewise output, and thus may employ the programme in order to get a |
| 60 |
partial Gr\"{o}bner basis. |
| 61 |
|
| 62 |
On the other hand, the arbitrary large integer precision arithmetic of |
| 63 |
Standard Lisp is assumed and employed. |
| 64 |
|
| 65 |
The prerequisits were in the first hand chosen so as to suite one |
| 66 |
specific problem, namely the cyclic n-root calculations. (Cf. the |
| 67 |
references at the end of this document.) The scope has been expanded |
| 68 |
somewhat, mainly in response to concrete problems of our colleagues and |
| 69 |
as a result of information and discussions within the POSSO project. |
| 70 |
|
| 71 |
The programme utilise the homogeneity in order to make (relatively) |
| 72 |
efficient tests for being able to discard certain potential |
| 73 |
S-polynomials. |
| 74 |
|
| 75 |
In version 0.9*, there is (in the commutative case) an alternative to |
| 76 |
the Buchberger algorithm, the `staggered linear basis with substance' |
| 77 |
(s.a.w.s.) algorithm. In the non-commutative case, an algorithm for |
| 78 |
calculating the beginning of the Hilbert series is available. |
| 79 |
|
| 80 |
|
| 81 |
\section{Organisation of the programme source files} |
| 82 |
|
| 83 |
There is a certain amout of modularisation of BERGMAN. The programme is |
| 84 |
divided into 'units', each of which corresponds to one or several |
| 85 |
separate files. In these it is noted which procedures and special |
| 86 |
variables are ''imported'' from other units, and which ''exported'', i. e., |
| 87 |
used in other units. This does NOT constitute ''modules'' in the C sense, |
| 88 |
since almost all procedures are defined and equally available everywhere |
| 89 |
in the final programme. In order to disencourage the use of lower level |
| 90 |
procedures or variables in ordinary applications, these use mixed upper |
| 91 |
and lower case letters (which makes them harder to access directly when |
| 92 |
the flag RAISE is on, as it generally is). There are some exceptions in |
| 93 |
upper cases; these are listed as ''available'' (if not exported), |
| 94 |
documented, and intended for general use. |
| 95 |
|
| 96 |
As a matter of fact, the code to a high extent is written AS IF it |
| 97 |
were truly modularised. Thus there are in general only some specified |
| 98 |
procedures from one module used in the others, and these and their |
| 99 |
action are documented in the file protocol.txt. Very often such |
| 100 |
procedures are defined in different versions. In fact, ''to change mode'' |
| 101 |
in bergman mainly means ''to replace one set of function definitions |
| 102 |
with another''. |
| 103 |
|
| 104 |
Each unit is referred to in comments by its ''bare name'' 'foo'. The |
| 105 |
corresponding source file has the bare name suffixed by .sl; compiled |
| 106 |
versions, et cetera, will of course have other extensions. Thus, the |
| 107 |
source files of the monomial manipulation unit 'monom' and 'ncmonom' |
| 108 |
are named monom.sl and ncmonom.sl, respectively; in both, versions of |
| 109 |
the ''exported'' monomial manipulation procedures are defined, in |
| 110 |
commutative and non-commutative variants, respectively. |
| 111 |
|
| 112 |
There are also some ''header'' files, with macros and with some general |
| 113 |
lisp procedures; and ''file handler'' files, used to compile the source |
| 114 |
files and to add some top level interface procedures. These files |
| 115 |
probably are more sensitive to changes of system than the 'ordinary' |
| 116 |
source files; you may wish to or have to rewrite some of them. Please |
| 117 |
then keep the old files for reference! |
| 118 |
|
| 119 |
|
| 120 |
|
| 121 |
\section{Overview of the (main) units and source files} |
| 122 |
%as per 1996-08: |
| 123 |
|
| 124 |
%hseries.sl reduct.sl pad polynom.sl |
| 125 |
\begin{center} |
| 126 |
|
| 127 |
"FILE HANDLER" FILES: |
| 128 |
\end{center} |
| 129 |
|
| 130 |
\begin{tabular}{ll} |
| 131 |
compan.sl & Performs the compiling of sourse files for Anick reslolution \\ |
| 132 |
& Anick reslolution and Betti numbers computation\\ |
| 133 |
compile.sl & Compiling all main units \\ |
| 134 |
bmtop.sl & Loads main compiled units and creats BERGMAN \\ |
| 135 |
topproc.sl & Contains the top-of-the-top level functions. \\ |
| 136 |
|
| 137 |
\end{tabular} |
| 138 |
|
| 139 |
\begin{center} |
| 140 |
|
| 141 |
"HEADER" MACRO FILES: |
| 142 |
\end{center} |
| 143 |
|
| 144 |
\begin{tabular}{ll} |
| 145 |
macros &General macro file (used in all compilation)\\ |
| 146 |
accmacr &Macro files used when compiling SAWS unit(s)\\ |
| 147 |
subsmacr &\\ |
| 148 |
midmacr &\\ |
| 149 |
\end{tabular} |
| 150 |
|
| 151 |
\begin{center} |
| 152 |
"LISP EXTENSIONS": |
| 153 |
\end{center} |
| 154 |
|
| 155 |
\begin{tabular}{ll} |
| 156 |
slext &Defining procedures not in the Standard Lisp document.\\ |
| 157 |
&(Uses macros.sl. May be used in the compilation of all\\ |
| 158 |
&other files.)\\ |
| 159 |
& At present, there are surely several omissions in this\\ |
| 160 |
&file.\\ |
| 161 |
alg2lsp &psl Maple- and Reduce-like input parcer procedures.\\ |
| 162 |
\end{tabular} |
| 163 |
|
| 164 |
\begin{center} |
| 165 |
CENTRAL UNITS: |
| 166 |
\end{center} |
| 167 |
|
| 168 |
\begin{tabular}{ll} |
| 169 |
Strategic:main &Main functions; S-pair constructions.\\ |
| 170 |
strategy &Graph component algorithm for eliminating redundant\\ |
| 171 |
&S-polynomial caculations.\\ |
| 172 |
\end{tabular} |
| 173 |
|
| 174 |
|
| 175 |
\begin{center} |
| 176 |
INTERFACE: |
| 177 |
\end{center} |
| 178 |
|
| 179 |
\begin{tabular}{ll} |
| 180 |
inout & Input and output routines.\\ |
| 181 |
alg2lsp &\\ |
| 182 |
\end{tabular} |
| 183 |
|
| 184 |
\begin{center} |
| 185 |
MONOMIAL: |
| 186 |
\end{center} |
| 187 |
|
| 188 |
\begin{tabular}{ll} |
| 189 |
monom &Monomial handling (including PUREMON manipulations).\\ |
| 190 |
ncmonom &Non-commutative monomials handling (including PUREMON\\ |
| 191 |
&manipulations).\\ |
| 192 |
reclaim &Garbage collection routines. (Could be dependent on\\ |
| 193 |
&EVERYTHING else, including on the machine.)\\ |
| 194 |
'reductions' &Normal form calculations, and other polynomial handling.\\ |
| 195 |
&Contains some general routines, and some specific for the\\ |
| 196 |
&char 0 case.\\ |
| 197 |
\end{tabular} |
| 198 |
|
| 199 |
|
| 200 |
\begin{center} |
| 201 |
COEFFICIENTS: |
| 202 |
\end{center} |
| 203 |
|
| 204 |
\begin{tabular}{ll} |
| 205 |
coeff &Coefficient arithmetic handling. Contains mainly means\\ |
| 206 |
&to use for changing or modifying the coefficient\\ |
| 207 |
&arithmetics; e. g., by calling on a modulus changer\\ |
| 208 |
&auxiliary.\\ |
| 209 |
char0 &Default ( = characteristic 0) coefficient manipulation\\ |
| 210 |
&procedures.\\ |
| 211 |
\end{tabular} |
| 212 |
\begin{center} |
| 213 |
SPECIAL PURPOSE AUXILIARY UNITS\\ |
| 214 |
(hopefully loaded automathically |
| 215 |
when needed): |
| 216 |
\end{center} |
| 217 |
|
| 218 |
\begin{tabular}{ll} |
| 219 |
odd &Modulus changer auxiliary, compiled and (re)loaded when a\\ |
| 220 |
&characteristic > 2 (without 'look-up logarithms') is set.\\ |
| 221 |
|
| 222 |
logodd &Modulus changer auxiliary, compiled and (re)loaded when a\\ |
| 223 |
&characteristic > 2 is set, while the 'look-up logarithms'\\ |
| 224 |
&is active.\\ |
| 225 |
char2 &Modulus changer auxiliary, loaded when the characteristic\\ |
| 226 |
&is set to 2.\\ |
| 227 |
|
| 228 |
pbseries &Loaded when the double Poincare-Betti series or the Hilbert\\ |
| 229 |
&series of the associated non-commutative monomially related\\ |
| 230 |
&algebra is demanded.\\ |
| 231 |
|
| 232 |
checkstg, &These files are compiled into the file stg.b, which should\\ |
| 233 |
accproc, &be loaded automatically (from stagsubstance.sl) when any\\ |
| 234 |
subsproc, &SAWS (Staggering Algorithm With Substance) procedure\\ |
| 235 |
& is called.\\ |
| 236 |
stg,&\\ |
| 237 |
monomstg,&\\ |
| 238 |
bind,&\\ |
| 239 |
write,&\\ |
| 240 |
ideal&\\ |
| 241 |
\end{tabular} |
| 242 |
|
| 243 |
\begin{center} |
| 244 |
SOME OTHER THINGS: |
| 245 |
\end{center} |
| 246 |
|
| 247 |
\begin{tabular}{ll} |
| 248 |
auxil &Extras, not necessary for ordinary usage.\\ |
| 249 |
|
| 250 |
debug &Debugging facilities (only for development usage). Not\\ |
| 251 |
&compiled (as standard).\\ |
| 252 |
|
| 253 |
homog &Procedures enabling non-homogeneous input and output; under\\ |
| 254 |
&development. Not compiled (as standard).\\ |
| 255 |
\end{tabular} |
| 256 |
|
| 257 |
These units do not include any user interface (or e.g. Reduce interface) |
| 258 |
worthy of mention. Interfaces should be built, picking the 'AVAILABLE' |
| 259 |
routines you wish from the units. Right now, ''initgr'' and ''initncgr'' |
| 260 |
provide some sorts of (bad) partial interfaces; also viz. the *prep |
| 261 |
files. |
| 262 |
|
| 263 |
|
| 264 |
\section{Basic structures and naming conventions} |
| 265 |
|
| 266 |
The polynomials are saved as lists of monomials--with--coefficients |
| 267 |
(COEFFMONOMIALs or ''terms''). An (augmented) monomial consists of three |
| 268 |
parts. ... is represented by the |
| 269 |
appropriate exponents of ALL the variables (appearing in the monomial, |
| 270 |
or not). There is also a rather important part of the monomial, the |
| 271 |
POINTER; |
| 272 |
this tells |
| 273 |
about the Gr\"{o}bner reduction status of the monomial. The MONOMIALs |
| 274 |
with pointers but without coefficients) are represented uniquely, so that |
| 275 |
equal monomials have EQ representations. This is done by means of an |
| 276 |
analogue of the OBLIST structure, called the MONLIST. |
| 277 |
|
| 278 |
The POINTER is augmented by a kind of property list for the monomial. |
| 279 |
|
| 280 |
In a polynomial, only non-zero coefficient monomials are represented, |
| 281 |
and they all MUST be of the same total degree. They are sorted by |
| 282 |
decreasing order (REVLEX or LEX), whence the leading |
| 283 |
monomial (LeadMon) always comes first. However, normally a polynomial |
| 284 |
is "augmented" by having NIL or a priority number even 'firster'. |
| 285 |
|
| 286 |
Lists of polynomials are either just that, or - in the case of lists of |
| 287 |
Gr\"{o}bner basis elements (Gbe's) - lists of their LeadMons. (The pointer |
| 288 |
value of a Gbe LeadMon is precisely that Gbe, whence this causes no loss |
| 289 |
of information.) In both cases, the polynomials are sorted by DEG-REVLEX |
| 290 |
or DEG-LEX ordering with respect to their LeadMons. |
| 291 |
|
| 292 |
Objects with the same total-degree sometimes are collected on a sublist, |
| 293 |
which begins with this degree. (This is referred to as ''degree separation''.) |
| 294 |
|
| 295 |
The following is a not quite formal description of basic structures. Note |
| 296 |
that there is not present a formal grammar presented, but a |
| 297 |
description of LISP objects. |
| 298 |
In particular, the apparent circulus virtuosis POINTER$->$ |
| 299 |
AUGMENTED POLYNOMIAL$->$ COEFFMONOMIAL$->$ |
| 300 |
MONOMIAL$->$ POINTER is a real one; thus the |
| 301 |
structures are not always printable (and in creating them RPLACA/RPLACD |
| 302 |
must be used). |
| 303 |
|
| 304 |
list(A) signifies a LISP list of at least one object (of type) A. |
| 305 |
|
| 306 |
dp(A,B) signifies a LISP dotted pair of A and B, (A . B). |
| 307 |
|
| 308 |
NIL, T are the LISP reserved atoms NIL, T. |
| 309 |
|
| 310 |
% <<EXPLAIN TREES>> |
| 311 |
\vspace*{0.3cm} |
| 312 |
\begin{tabular}{lcl} |
| 313 |
|
| 314 |
MONOMIAL & ::=& dp(POINTER,PUREMON)\\ |
| 315 |
(n.c. MONOMIAL & ::=& dp(dp(POINTER,PROPLIST),\\ |
| 316 |
& &PUREMON) )\\ |
| 317 |
POINTER & ::=& NIL | T | \\ |
| 318 |
& &AUGMENTED POLYNOMIAL | \\ |
| 319 |
& & list(dp(MONOMIAL,MONOMIAL))\\ |
| 320 |
COEFFMONOMIAL & ::= &dp(COEFFICIENT,MONOMIAL)\\ |
| 321 |
COEFFICIENT & ::=& non-zero NUMBER\\ |
| 322 |
NUMBER & ::=& integer of any size\\ |
| 323 |
POLYNOMIAL & ::=& list(COEFFMONOMIAL)\\ |
| 324 |
AUGMENTED POLYNOMIAL& ::=& dp(PRIORITY,POLYNOMIAL)\\ |
| 325 |
PRIORITY & ::=& NIL | T | NUMBER\\ |
| 326 |
\end{tabular} |
| 327 |
\vspace*{0.3cm} |
| 328 |
(\ldots, \ldots, \ldots) denotes a structure. The items may be on the forms |
| 329 |
identifier or identifier1:identifier2 . In the second case, identifyer1 |
| 330 |
signifies the type of the constituend, while identifier2 is the name |
| 331 |
with which it is denoted in this explanation. (It is of no significance |
| 332 |
in the source files, since these things are not really implemented as |
| 333 |
structures.) |
| 334 |
|
| 335 |
\ldots | \ldots \ \ldots signifies alternatives, as in C unions. |
| 336 |
|
| 337 |
$*$ denotes ''note below''. |
| 338 |
|
| 339 |
\begin{tabular}{lcl} |
| 340 |
NUMBER & ::=& integer of any size\\ |
| 341 |
POSITIVE & ::=& positive integer of any size\\ |
| 342 |
NON-NEGATIVE & ::=& 0 | POSITIVE\\ |
| 343 |
|
| 344 |
InterfaceMonomial & ::=& list(NON-NEGATIVE) *\\ |
| 345 |
InterfaceCoefficient& ::= &NUMBER\\ |
| 346 |
InterfaceTerm & ::=& dp(InterfaceCoefficient,InterfaceMonomial)\\ |
| 347 |
InterfacePolynomial & ::=& list(InterfaceTerm)\\ |
| 348 |
|
| 349 |
Monomial & ::= &{PureMonomial, MonomialPointer, PropertyList}\\ |
| 350 |
MonomialPointer & ::=& NIL | T | Redor | \\ |
| 351 |
&& list(dp(Monomial,Monomial))\\ |
| 352 |
RedandTerm & ::=& {RedandCoefficient,Monomial}\\ |
| 353 |
RedorTerm & ::=& {RedorCoefficient,Monomial}\\ |
| 354 |
Term & ::=& RedandTerm | RedorTerm\\ |
| 355 |
PureRedand & ::=& NIL |{RedandTerm: Head, PureRedand: Tail}\\ |
| 356 |
PureRedor & ::=& NIL | {RedorTerm: Head, PureRedor: Tail}\\ |
| 357 |
Redand & ::= &{ReductionPriority, PureRedand: PurePart} *\\ |
| 358 |
Redor & ::=& {ReductionPriority, PureRedor: PurePart} *\\ |
| 359 |
ReductionPriority & ::= &NIL | NUMBER\\ |
| 360 |
\end{tabular} |
| 361 |
|
| 362 |
NOTES: An InterfaceMonomial in the commutative case is a list of |
| 363 |
(non-negative) exponents, with a length = the (fixed) number of |
| 364 |
variables. They are assumed to be (and stay) of inum sizes. In the |
| 365 |
non-commutative case, it is a list of (strictly) positive integers, |
| 366 |
the variable indices, also assumed to be and remain of inum size. |
| 367 |
The PureParts of Redands and Redors may become NIL within a |
| 368 |
procedure, but the only procedure who may return a Redand with a |
| 369 |
NIL PurePart is mkAPol() $<<$CHANGE THE NAME TO MkRedand$>>.$ No procedure |
| 370 |
may return a Redor with NIL PurePart. |
| 371 |
|
| 372 |
A 'PUREMON' is regarded as an atom, except in the 'monomials' and |
| 373 |
'reclaim' units. Right now, it is implemented as a reverse order LISP list |
| 374 |
of exponents (including zeroes). |
| 375 |
|
| 376 |
(The PROPLIST is organised as an ordinary lisp property list. It is |
| 377 |
available for the user by means of the PUTM, GETM and PUTGETM procedures.) |
| 378 |
|
| 379 |
The different data structure types correspond to certain lower case |
| 380 |
argument names and certain Capitalised Procedure Constituends, as listed |
| 381 |
below. Thus, if a procedure has one NUMBER argument (which may well be |
| 382 |
a COEFFICIENT or a PRIORITY), then this always is called numb. If it has |
| 383 |
two NUMBER arguments, they are called numb1 and numb2. In addition, in |
| 384 |
most of the cases the procedure name will contain an N. One list/dotted |
| 385 |
pair of numbers argument is called lnumb/dpnumb. |
| 386 |
|
| 387 |
Different arguments or procedure name constituends are enumerated in the |
| 388 |
PNM or 'revlex' order polynomial(s), number(s), monomial(s). |
| 389 |
|
| 390 |
\begin{tabular}{lcl} |
| 391 |
Data type & Constituend & Argument\\ |
| 392 |
& & \\ |
| 393 |
PUREMON & Mon & inxs\\ |
| 394 |
MONOMIAL & Mon & mon\\ |
| 395 |
COEFFMONOMIAL & Mon & cfmon\\ |
| 396 |
NUMBER & N & numb\\ |
| 397 |
POLYNOMIAL & Pol & pol\\ |
| 398 |
AUGMENTED POLYNOMIAL & Pol & augpol\\ |
| 399 |
\end{tabular} |
| 400 |
|
| 401 |
Further conventions: Mult, Quot stands for operations with both/all |
| 402 |
arguments specified in the procedure name. Sometimes an operation is |
| 403 |
performed only on a part of a polynomial (PolPart). A position in the |
| 404 |
list representing the polynomial where (part of) a procedure is to |
| 405 |
stop or start, as an argument is called place or returnstart. |
| 406 |
c stands for "current". Gr\"{o}bner basis may be abbreviated e.g. gbasis |
| 407 |
or gb. Most of these and other abbreviations are probably fairly self- |
| 408 |
explanatory. |
| 409 |
|
| 410 |
|
| 411 |
\section{Global structures and programme outline } |
| 412 |
|
| 413 |
The most important global structures are: |
| 414 |
\begin{itemize} |
| 415 |
\item InPols, the input polynomials (the original ideal basis); |
| 416 |
\item cInPols, ditto of current degree; |
| 417 |
\item SPairs, the pairs of LeadMons to investigate; |
| 418 |
\item cSPairs, ditto of current degree; |
| 419 |
\item GBasis, the Gr\"{o}bner basis; and |
| 420 |
\item cGBasis, the new Gr\"{o}bner basis elements (of current degree). |
| 421 |
\end{itemize} |
| 422 |
|
| 423 |
They are described below. "Current degree" here stands for "The value |
| 424 |
of the global variable cDeg". |
| 425 |
|
| 426 |
InPols is organised as a list of (zero or more) degree-lists, where |
| 427 |
each degree-list has a degree NUMBER as its car, and a positive |
| 428 |
number of AUGMENTED POLYNOMIALs (ordered increasingly w.r.t their |
| 429 |
LeadMons) as the rest of its elements. (Of course the polynomials in |
| 430 |
one degree--list all have that total--degree.) The degree--lists are |
| 431 |
ordered by increasing degree. |
| 432 |
|
| 433 |
In the beginning of an ordinary application of the main procedure, |
| 434 |
GROEBNERKERNEL (found in 'ner'), InPols contains all input poly- |
| 435 |
nomials. As the work progresses, more and more of these are removed |
| 436 |
from InPols and processed; thus, in the end InPols is empty. At a |
| 437 |
given time, InPols contains the input polynomials of higher total- |
| 438 |
degree than the current degree, while the unprocessed ones of the |
| 439 |
current degree are listed on cInPols. |
| 440 |
|
| 441 |
SPairs is a list of degree--lists, each of which has a degree as its |
| 442 |
car and MONOMIALs (of that total--degree) as the rest of its elements. |
| 443 |
Each such MONOMIAL is the lcm of at least one pair of LeadMons, which |
| 444 |
has not (yet) been discarded as yielding a non-trivial S--polynomial, |
| 445 |
a critical pair. Critical pairs are represented by dotted pairs of |
| 446 |
LeadMons (represented as MONOMIALs). The POINTER of the monomial |
| 447 |
is a list of critical pairs. The monomials in a degree--list are |
| 448 |
ordered increasingly; and SPairs is ordered by increasing degree. |
| 449 |
|
| 450 |
In the beginning of an ordinary GROEBNERKERNEL application, SPairs |
| 451 |
is empty. In the run of the procedure, newly found critical pairs |
| 452 |
are inserted in it (as elements of POINTERs of MONOMIALs in adequate |
| 453 |
positions), while the SPair elements of the current degree are moved |
| 454 |
to cSPairs and (in due time) processed and removed. Thus, in the end |
| 455 |
SPair once more is empty. |
| 456 |
|
| 457 |
GBasis and cGBasis are lists. Their cars are NIL; the rest of the |
| 458 |
elements are LeadMons (represented as MONOMIALs) of Gr\"{o}bner basis |
| 459 |
elements, ordered increasingly by the appropriate ordering. GBasis |
| 460 |
contains the gbe's of lower than current total--degree; these are |
| 461 |
in their final form (if the flag IMMEDIATEFULLREDUCTION is on). |
| 462 |
cGBasis contains the new--found gbe's of the current degree. They |
| 463 |
may very well change, due to reduction modulo gbe's found later |
| 464 |
but with lower ordered LeadMons. However, their LeadMons cannot |
| 465 |
change! |
| 466 |
|
| 467 |
(The fact that the main structures are GLOBAL variables makes it |
| 468 |
possible to use the main functions for slightly different purposes. |
| 469 |
E. g., in order only to perform a reduction of a polynomial P modulo |
| 470 |
a known Groebner basis B, just do\\ |
| 471 |
(RPLACD GBasis B')\\ |
| 472 |
(ReducePol P)\\ |
| 473 |
where B' is B represented in the above described way. Such variants |
| 474 |
may be found in 'auxiliaries'.) |
| 475 |
|
| 476 |
The main procedure GROEBNERKERNEL roughly works as follows: |
| 477 |
|
| 478 |
\begin{verbatim} |
| 479 |
While InPols or SPairs is non-empty do |
| 480 |
begin |
| 481 |
cDeg:= the lowest existing degree in InPols and/or SPairs |
| 482 |
( = min(caar(InPols),caar(SPairs)), if both exist); |
| 483 |
Move the cDeg component(s) of InPols and/or SPairs to cInPols |
| 484 |
and/or cSPairs, discarding their cars (i.e., degrees); |
| 485 |
While cInPols or cSPairs is non-empty do |
| 486 |
begin |
| 487 |
If cSPairs is empty, or if car(cInPols) exists, and its LeadMon |
| 488 |
is strictly of lower order than car(cSPairs), |
| 489 |
then process car(cInPols), and remove it from cInPols, |
| 490 |
else |
| 491 |
begin |
| 492 |
SP2r:=SPolInputs(car(cSPairs)); |
| 493 |
For (a.b) in SP2r do |
| 494 |
process the S-polynomial POINTER(a)-POINTER(b); |
| 495 |
end; |
| 496 |
end; |
| 497 |
For mon in cdr(cGBasis) do PRIORITY(POINTER(mon)):=length(POINTER(mon)); |
| 498 |
If CUSTSHOW is ON then call DEGREENDDISPLAY, |
| 499 |
else if SAVEDEGREE is ON then call DEGREEOUTPUT; |
| 500 |
Consider new LeadMon-pairs among the new gbe's; |
| 501 |
Call MonReclaim; |
| 502 |
end; |
| 503 |
\end{verbatim} |
| 504 |
|
| 505 |
Here to process the augmented polynomial pol signifies: |
| 506 |
|
| 507 |
\begin{verbatim} |
| 508 |
|
| 509 |
begin |
| 510 |
NGroeb := ReducePol(pol) (i. e., the normal form of pol); |
| 511 |
If NGroeb <> 0 then (we indeed have a new gbe, whence:) |
| 512 |
begin |
| 513 |
POINTER(LeadMon(NGroeb)) := NGroeb; |
| 514 |
NGroeb := LeadMon(NGroeb); |
| 515 |
Consider new LeadMon-pairs formed by NGroeb and the old gbe's; |
| 516 |
Insert NGroeb on its proper place in cdr(cGBasis); |
| 517 |
If IMMEDIATEFULLREDUCTION is ON, |
| 518 |
then reduce other new gbe's w. r. t. NGroeb; |
| 519 |
end; |
| 520 |
end; |
| 521 |
\end{verbatim} |
| 522 |
|
| 523 |
The process SPolInputs (defined in 'compalg' or in 'noncomm') takes |
| 524 |
a MONOMIAL mon as its argument, which must have a list of critical |
| 525 |
pairs as its POINTER. It produces (more or less smartly) a final list |
| 526 |
of pairs of LeadMons of gbe's, from which S--polynomials will be |
| 527 |
calculated. (As a side effect, POINTER(mon) is changed.) |
| 528 |
|
| 529 |
At the end of the main loop of GROEBNERKERNEL, some more or less |
| 530 |
optional procedures may be called. DEGREEOUTPUT (defined in 'inout') |
| 531 |
prints the current degree gbe's, in a form decided by various global |
| 532 |
or fluid variables, e. g. OutVars, GBasOutChan, and ALGOUTMODE. |
| 533 |
In order to get its output on the file foo, perform\\ |
| 534 |
(DEGREEOUTPREPARE "foo")\\ |
| 535 |
before the GROEBNERKERNEL. (No argument = type on the standard output.) |
| 536 |
Also perform (ENDDEGREEOUTPUT) or (GROEBNERFINISH) after |
| 537 |
GROEBNERKERNEL. |
| 538 |
The form of the output may be governed by assigning ALGOUTMODE |
| 539 |
different values. (Right now, allowed values are LISP, MACAULAY, PBOUT, |
| 540 |
and ALG. The latter stands for a "general" (Maple or Reduce type) |
| 541 |
algebraic form.) |
| 542 |
|
| 543 |
On the other hand, DEGREENDDISPLAY is NOT DEFINED. Our |
| 544 |
experience seems to indicate that users often want to customise |
| 545 |
output. |
| 546 |
You may do this by defining DEGREENDDISPLAY as any EXPR with |
| 547 |
no argument, and by turning ON the flag CUSTSHOW. In this way you |
| 548 |
may also e. g. interrupt the calculations at a certain degree. |
| 549 |
|
| 550 |
Finally, MonReclaim is defined in the 'reclaim' unit. Since Gr\"{o}bner |
| 551 |
basis calculation often tend to be very space-consuming, effective |
| 552 |
reclaims may be of considerable value. |
| 553 |
|