Debian Codegraph @

doc/bergman1.0.man/inside.tex

raw
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