source: CGBLisp/latex-doc/grobner.tex@ 1

\begin{lisp:documentation}{*grobner$-$debug*}{VARIABLE}{nil }
If T, produce debugging and tracing output.
\end{lisp:documentation}

\begin{lisp:documentation}{*buchberger$-$merge$-$pairs*}{VARIABLE}{'buchberger$-$merge$-$pairs$-$smallest$-$lcm }
A variable holding the predicate used to sort critical pairs
in the order of decreasing priority for the Buchberger algorithm.
\end{lisp:documentation}

\begin{lisp:documentation}{*gebauer$-$moeller$-$merge$-$pairs*}{VARIABLE}{'gebauer$-$moeller$-$merge$-$pairs$-$use$-$mock$-$spoly }
A variable holding the predicate used to sort critical pairs
in the order of decreasing priority for the Gebauer$-$Moeller
algorithm 
\end{lisp:documentation}

\begin{lisp:documentation}{*grobner$-$function*}{VARIABLE}{'buchberger }
The name of the function used to calculate Grobner basis
\end{lisp:documentation}

\begin{lisp:documentation}{select$-$grobner$-$algorithm}{FUNCTION}{algorithm }
Select one of the several implementations of the Grobner basis
algorithm.
\end{lisp:documentation}

\begin{lisp:documentation}{grobner}{FUNCTION}{f {\sf \&optional} (pred \#'lex$>$) (start 0) (top$-$reduction$-$only nil) (ring *coefficient$-$ring*) }
Return Grobner basis of an ideal generated by polynomial list F.
Assume that the monomials of each polynomial are ordered according to
the admissible monomial order PRED. The result will be a list of
polynomials ordered as well according to PRED. The polynomials from 0
to START$-$1 in the list F are assumed to be a Grobner basis, and
thus certain critical pairs do not have to be calculated. If
TOP$-$REDUCTION$-$ONLY is not NIL then only top reductions will be
performed, instead of full division, and thus the returned Grobner
basis will have its polynomials only top$-$reduced with respect to
the preceding polynomials. RING should be set to the RING structure
(see COEFFICIENT$-$RING package) corresponding to the coefficients of
the polynomials in the list F. This function is currently just an
interface to several algorithms which fine Grobner bases. Use
SELECT$-$GROBNER$-$ALGORITHM in order to change the algorithm.
\end{lisp:documentation}

\begin{lisp:documentation}{debug$-$cgb}{MACRO}{{\sf \&rest} args }
This macro is used in printing debugging and tracing messages
and its arguments are analogous to the FORMAT function, except
that the stream argument is omitted. By default, the output is
sent to *trace$-$output*, which can be set to produce output 
in a file.
\end{lisp:documentation}

\begin{lisp:documentation}{spoly}{FUNCTION}{f g pred ring }
Return the S$-$polynomial of F and G, which should
be two polynomials with terms ordered by PRED and
coefficients in a ring whose operations are the slots
of the RING structure.
\end{lisp:documentation}

\begin{lisp:documentation}{grobner$-$primitive$-$part}{FUNCTION}{p ring }
Divide polynomial P with integer coefficients by gcd of its
coefficients and return the result. Use the RING structure from the
COEFFICIENT$-$RING package to perform the operations on the
coefficients.
\end{lisp:documentation}

\begin{lisp:documentation}{grobner$-$content}{FUNCTION}{p ring }
Greatest common divisor of the coefficients of the polynomial P. Use
the RING structure to compute the greatest common divisor.
\end{lisp:documentation}

\begin{lisp:documentation}{normal$-$form}{FUNCTION}{f fl pred top$-$reduction$-$only ring }
Calculate the normal form of the polynomial F with respect to
the polynomial list FL. Destructive to F; thus, copy$-$tree should be
used where F needs to be preserved. It returns multiple values.
The first value is the polynomial R which is reduced (or
top$-$reduced if TOP$-$REDUCTION$-$ONLY is not NIL). The second value
is an integer which is the number of reductions actually performed.
The third value is the coefficient by which F needs to be multiplied
in order to be able to perform the division without actually having
to divide in the coefficient ring (a form of pseudo$-$division is
used). All operations on the coefficients are performed using the
RING structure from the COEFFICIENT$-$RING package.
\end{lisp:documentation}

\begin{lisp:documentation}{buchberger}{FUNCTION}{f pred start top$-$reduction$-$only ring {\sf \&aux} (s (1$-$ (length f))) b m }
An implementation of the Buchberger algorithm. Return Grobner
basis of the ideal generated by the polynomial list F.
The terms of each polynomial are ordered by the admissible
monomial order PRED. Polynomials 0 to START$-$1 are assumed to
be a Grobner basis already, so that certain critical pairs
will not be examined. If TOP$-$REDUCTION$-$ONLY set, top reduction
will be preformed. The RING structure is used to perform operations
on coefficents (see COEFFICIENT$-$RING package).
\end{lisp:documentation}

\begin{lisp:documentation}{grobner$-$op}{FUNCTION}{c1 c2 m a b pred ring {\sf \&aux} n a1 a2 }
Perform a calculation equivalent to
(POLY$-$ (SCALAR$-$TIMES$-$POLY C2 A)
         (SCALAR$-$TIMES$-$POLY C1 (MONOM$-$TIMES$-$POLY M B))
         PRED)
but more efficiently; it destructively modifies A and stores the 
result in it; A is returned.
\end{lisp:documentation}

\begin{lisp:documentation}{buchberger$-$sort$-$pairs}{FUNCTION}{b g pred ring }
Sort critical pairs B by the function which is
the value of the vairable *buchberger$-$merge$-$pairs*.
G is the list of polynomials which the elemnts
of B point into. PRED is the admissible monomial order.
The RING structure holds operations on the coefficients
as described in the COEFFICIENT$-$RING package.
\end{lisp:documentation}

\begin{lisp:documentation}{mock$-$spoly}{FUNCTION}{f g pred }
Returns an upper$-$bound on the leading
monomial of the S$-$polynomial of F and G, which are two polynomials
sorted by the admissible monomial order PRED.
\end{lisp:documentation}

\begin{lisp:documentation}{buchberger$-$merge$-$pairs$-$use$-$mock$-$spoly}{FUNCTION}{b c g pred ring }
Merges lists of critical pairs B and C into one list. 
The pairs are assumed to be ordered according to the
increasing value of MOCK$-$SPOLY, as determined by the admissible
monomial order PRED. G is the list of polynomials which the pairs
of integers in B and C point into, and RING is the ring structure
defined in the COEFFICIENT$-$RING package.
\end{lisp:documentation}

\begin{lisp:documentation}{buchberger$-$merge$-$pairs$-$smallest$-$lcm}{FUNCTION}{b c g pred ring }
Merges lists of critical pairs B and C into a single ordered
list. Implements a strategy of ordering pairs according to the
smallest lcm of the leading monomials of the two polynomials $-$ so
called normal strategy.
\end{lisp:documentation}

\begin{lisp:documentation}{buchberger$-$merge$-$pairs$-$use$-$smallest$-$degree}{FUNCTION}{b c g pred ring }
Mergest lists B and C of critical pairs. This strategy is based on
ordering the pairs according to the smallest degree of the lcm of
the leading monomials of the two polynomials.
\end{lisp:documentation}

\begin{lisp:documentation}{buchberger$-$merge$-$pairs$-$use$-$smallest$-$length}{FUNCTION}{b c g pred ring }
Mergest lists B and C of critical pairs. This strategy is based on
ordering the pairs according to the smallest total length of the 
two polynomials, where length is the number of terms.
\end{lisp:documentation}

\begin{lisp:documentation}{buchberger$-$merge$-$pairs$-$use$-$smallest$-$coefficient$-$length}{FUNCTION}{b c g pred ring }
Mergest lists B and C of critical pairs. This strategy is based on
ordering the pairs according to the smallest combined length of the 
coefficients of the two polynomials.
\end{lisp:documentation}

\begin{lisp:documentation}{buchberger$-$set$-$pair$-$heuristic}{FUNCTION}{method {\sf \&aux} (strategy$-$fn
                                                                                              (ecase method (:minimal$-$mock$-$spoly \#'buchberger$-$merge$-$pairs$-$use$-$mock$-$spoly)
                                                                                               (:minimal$-$lcm \#'buchberger$-$merge$-$pairs$-$smallest$-$lcm)
                                                                                               (:minimal$-$total$-$degree \#'buchberger$-$merge$-$pairs$-$use$-$smallest$-$degree)
                                                                                               (:minimal$-$length \#'buchberger$-$merge$-$pairs$-$use$-$smallest$-$length)
                                                                                               (:minimal$-$coefficient$-$length \#'buchberger$-$merge$-$pairs$-$use$-$smallest$-$coefficient$-$length))) }
Simply sets the variable *buchberger$-$merge$-$pairs* to the
heuristic function STRATEGY$-$FN implementing one of several
strategies introduces before of selecting the most promising. METHOD
should be one of the listed keywords.
\end{lisp:documentation}

\begin{lisp:documentation}{criterion$-$1}{FUNCTION}{pair g {\sf \&aux} (i (first pair)) (j (second pair)) }
Returns T if the leading monomials of the two polynomials
in G pointed to by the integers in PAIR have disjoint (relatively
prime) monomials. This test is known as the first Buchberger
criterion. 
\end{lisp:documentation}

\begin{lisp:documentation}{criterion$-$2}{FUNCTION}{pair g m {\sf \&aux} (i (first pair)) (j (second pair)) }
Returns T if the leading monomial of some element P of G divides
the LCM of the leading monomials of the two polynomials in the
polynomial list G, pointed to by the two integers in PAIR, and P
paired with each of the polynomials pointed to by the the PAIR has
already been treated, as indicated by the hash table M, which stores
value T for every treated pair so far.
\end{lisp:documentation}

\begin{lisp:documentation}{normalize$-$poly}{FUNCTION}{p ring }
Divide a polynomial by its leading coefficient. It assumes
that the division is possible, which may not always be the
case in rings which are not fields. The exact division operator
is assumed to be provided by the RING structure of the
COEFFICIENT$-$RING package.
\end{lisp:documentation}

\begin{lisp:documentation}{normalize$-$basis}{FUNCTION}{plist ring }
Divide every polynomial in a list PLIST by its leading coefficient.
Use RING structure to perform the division of the coefficients.
\end{lisp:documentation}

\begin{lisp:documentation}{reduction}{FUNCTION}{p pred ring }
Reduce a list of polynomials P, so that non of the terms in any of
the polynomials is divisible by a leading monomial of another
polynomial. Return the reduced list.
\end{lisp:documentation}

\begin{lisp:documentation}{reduced$-$grobner}{FUNCTION}{f {\sf \&optional} (pred \#'lex$>$) (start 0) (top$-$reduction$-$only nil) (ring *coefficient$-$ring*) }
Return the reduced Grobner basis of the ideal generated by a
polynomial list F. This combines calls to two functions: GROBNER and
REDUCTION. The parameters have the same meaning as in GROBNER or
BUCHBERGER. 
\end{lisp:documentation}

\begin{lisp:documentation}{monom$-$depends$-$p}{FUNCTION}{m k }
Return T if the monomial M depends on variable number K.
\end{lisp:documentation}

\begin{lisp:documentation}{term$-$depends$-$p}{FUNCTION}{term k }
Return T if the term TERM depends on variable number K.
\end{lisp:documentation}

\begin{lisp:documentation}{poly$-$depends$-$p}{FUNCTION}{p k }
Return T if the term polynomial P depends on variable number K.
\end{lisp:documentation}

\begin{lisp:documentation}{ring$-$intersection}{FUNCTION}{plist k {\sf \&key} (key \#'identity) }
This function assumes that polynomial list PLIST is a Grobner basis
and it calculates the intersection with the ring R[x[k+1],...,x[n]],
i.e. it discards polynomials which depend on variables x[0], x[1],
..., x[k]. 
\end{lisp:documentation}

\begin{lisp:documentation}{elimination$-$ideal}{FUNCTION}{flist k {\sf \&key} (primary$-$order \#'lex$>$) (secondary$-$order \#'lex$>$) (start 0) (order
                                                                                                                                                   (elimination$-$order k :primary$-$order primary$-$order
                                                                                                                                                    :secondary$-$order secondary$-$order)) (top$-$reduction$-$only
                                                                                                                                                                                            nil) (ring
                                                                                                                                                                                                  *coefficient$-$ring*) }
Returns the K$-$th elimination ideal of the ideal generated by
polynomial list FLIST. Thus, a Grobner basis of the ideal generated
by FLIST is calculated and polynomials depending on variables 0$-$K
are discarded. The monomial order in the calculation is an
elimination order formed by combining two orders: PRIMARY$-$ORDER
used on variables 0$-$K and SECONDARY$-$ORDER used on variables
starting from variable K+1. Thus, if both orders are set to the
lexicographic order \#'LEX$>$ then the resulting order is simply
equivalent to \#'LEX$>$. But one could use arbitrary two orders in
this function, for instance, two copies of \#'GREVLEX$>$ (see ORDER
package). When doing so, the caller must ensure that the same order
has been used to sort the terms of the polynomials FLIST. 
\end{lisp:documentation}

\begin{lisp:documentation}{ideal$-$intersection}{FUNCTION}{f g pred top$-$reduction$-$only ring }
Return the Grobner basis of the intersection of the ideals
generated by the polynomial lists F and G. PRED is an admissible
monomial order with respect to which the terms of F and G have been
sorted. This order is going to be used in the Grobner basis
calculation. If TOP$-$REDUCTION$-$ONLY is not NIL, internally the
Grobner basis algorithm will perform top reduction only.  The RING
parameter, as usual, should be set to a structure defined in the
package COEFFICIENT$-$RING, and it will be used to perform all
operations on coefficients.
\end{lisp:documentation}

\begin{lisp:documentation}{poly$-$contract}{FUNCTION}{f {\sf \&optional} (k 1) }
Return a polynomial obtained from polynomial F by dropping the
first K variables, if F does not depend on them.  Note that this
operation makes the polynomial incompatible for certain arithmetical
operations with the original polynomial F. Calling this function on a
polynomial F which does depend on variables 0$-$K will result in
error. 
\end{lisp:documentation}

\begin{lisp:documentation}{poly$-$lcm}{FUNCTION}{f g {\sf \&optional} (pred \#'lex$>$) (ring *coefficient$-$ring*) }
Return LCM (least common multiple) of two polynomials F and G.
The polynomials must be ordered according to monomial order PRED
and their coefficients must be compatible with the RING structure
defined in the COEFFICIENT$-$RING package.
\end{lisp:documentation}

\begin{lisp:documentation}{grobner$-$gcd}{FUNCTION}{f g {\sf \&optional} (pred \#'lex$>$) (ring *coefficient$-$ring*) }
Return GCD (greatest common divisor) of two polynomials F and G.
The polynomials must be ordered according to monomial order PRED
and their coefficients must be compatible with the RING structure
defined in the COEFFICIENT$-$RING package.
\end{lisp:documentation}

\begin{lisp:documentation}{grobner$-$equal}{FUNCTION}{g1 g2 {\sf \&optional} (pred \#'lex$>$) (ring *coefficient$-$ring*) }
Returns T if two lists of polynomials G1 and G2, assumed to be
Grobner bases, generate  the same ideal, and NIL otherwise.
\end{lisp:documentation}

\begin{lisp:documentation}{grobner$-$subsetp}{FUNCTION}{g1 g2 {\sf \&optional} (pred \#'lex$>$) (ring *coefficient$-$ring*) }
Returns T if a list of polynomials G1 generates
an ideal contained in the ideal generated by a polynomial list G2,
both G1 and G2 assumed to be Grobner bases. Returns NIL otherwise.
\end{lisp:documentation}

\begin{lisp:documentation}{grobner$-$member}{FUNCTION}{p g {\sf \&optional} (pred \#'lex$>$) (ring *coefficient$-$ring*) }
Returns T if a polynomial P belongs to the ideal generated by the
polynomial list G, which is assumed to be a Grobner basis. Returns
NIL otherwise. 
\end{lisp:documentation}

\begin{lisp:documentation}{ideal$-$equal}{FUNCTION}{f1 f2 pred top$-$reduction$-$only ring }
Returns T if two ideals generated by polynomial lists F1 and F2 are
identical. Returns NIL otherwise.
\end{lisp:documentation}

\begin{lisp:documentation}{ideal$-$subsetp}{FUNCTION}{f1 f2 {\sf \&optional} (pred \#'lex$>$) (ring *coefficient$-$ring*) }
Returns T if the ideal spanned by the polynomial list F1 is contained
in the ideal spanned by the polynomial list F2. Returns NIL
otherwise. 
\end{lisp:documentation}

\begin{lisp:documentation}{ideal$-$member}{FUNCTION}{p plist pred top$-$reduction$-$only ring }
Returns T if the polynomial P belongs to the ideal spanned by the
polynomial list PLIST, and NIL otherwise.
\end{lisp:documentation}

\begin{lisp:documentation}{ideal$-$saturation$-$1}{FUNCTION}{f p pred start top$-$reduction$-$only ring {\sf \&aux} (pred (elimination$-$order$-$1 pred)) }
Returns the reduced Grobner basis of the saturation of the ideal
generated by a polynomial list F in the ideal generated by a single
polynomial P. The saturation ideal is defined as the set of
polynomials H such for some natural number n (* (EXPT P N) H) is in
the ideal F. Geometrically, over an algebraically closed field, this
is the set of polynomials in the ideal generated by F which do not
identically vanish on the variety of P.
\end{lisp:documentation}

\begin{lisp:documentation}{add$-$variables}{FUNCTION}{plist n }
Add N new variables, adn the first N variables, to every polynomial
in polynomial list PLIST. The resulting polynomial will not depend on
these N variables. 
\end{lisp:documentation}

\begin{lisp:documentation}{extend$-$polynomials}{FUNCTION}{plist {\sf \&aux} (k (length plist)) }
Returns polynomial list \{U1*P1', U2*P2', ... , UK*PK'\}
where Ui are new variables and PLIST=\{P1, P2, ... , PK\} is a
polynomial list. PI' is obtained from PI by adding new variables U1,
U2, ..., UN UK as the first K variables. Thus, the resulting list is
consists of polynomials whose terms are ordered by the lexicographic
order on variables UI, with ties resolved by the monomial order which
was used to order the terms of the polynomials in PLIST. We note that
the monomial order does not explicitly participate in this
calculation, and neither do the variable names.
\end{lisp:documentation}

\begin{lisp:documentation}{saturation$-$extension}{FUNCTION}{f plist ring {\sf \&aux} (k (length plist)) (d (+ k (length (caaar plist)))) }
Returns F' union \{U1*P1$-$1,U2*P2$-$1,...,UK*PK$-$1\} where Ui are
new variables and F' is a polynomial list  obtained from F by adding
variables U1, U2, ..., Uk as the first K variables to each polynomial
in F. Thus, the resulting list is consists of polynomials whose terms
are ordered by the lexicographic order on variables Ui, with ties
resolved by the monomial order which was used to order the terms of
the polynomials in F. We note that the monomial order does not
explicitly participate in this calculation, and neither do the
variable names. 
\end{lisp:documentation}

\begin{lisp:documentation}{polysaturation$-$extension}{FUNCTION}{f plist ring {\sf \&aux} (k (length plist)) (d (+ k (length (caaar plist)))) }
Returns F' union \{U1*P1+U2*P2+UK*PK$-$1\} where Ui are new variables
and F' is a polynomial list  obtained from F by adding variables U1,
U2, ..., Uk as the first K variables to each polynomial in F. Thus,
the resulting list is consists of polynomials whose terms are ordered
by the lexicographic order on variables Ui, with ties resolved by the
monomial order which was used to order the terms of the polynomials
in F. We note that the monomial order does not explicitly participate
in this calculation, and neither do the variable names. 
\end{lisp:documentation}

\begin{lisp:documentation}{saturation$-$extension$-$1}{FUNCTION}{f p ring }
Return the list F' union \{U*P$-$1\} where U is a new variable,
where F' is obtained from the polynomial list F by adding U as the
first variable. The variable U will be added as the first variable,
so that it can be easily eliminated.
\end{lisp:documentation}

\begin{lisp:documentation}{ideal$-$polysaturation$-$1}{FUNCTION}{f plist pred start top$-$reduction$-$only ring }
Returns the reduced Grobner basis of the ideal obtained by a
sequence of successive saturations in the polynomials
of the polynomial list PLIST of the ideal generated by the
polynomial list F.
\end{lisp:documentation}

\begin{lisp:documentation}{ideal$-$saturation}{FUNCTION}{f g pred start top$-$reduction$-$only ring {\sf \&aux} (k (length g)) (pred (elimination$-$order k :primary$-$order \#'lex$>$ :secondary$-$order pred)) }
Returns the reduced Grobner basis of the saturation of the ideal
generated by a polynomial list F in the ideal generated a polynomial
list G The saturation ideal is defined as the set of polynomials H
such for some natural number n and some P in the ideal generated by G
the polynomial P**N * H is in the ideal spanned by F.  Geometrically,
over an algebraically closed field, this is the set of polynomials in
the ideal generated by F which do not identically vanish on the
variety of G.
\end{lisp:documentation}

\begin{lisp:documentation}{ideal$-$polysaturation}{FUNCTION}{f ideal$-$list pred start top$-$reduction$-$only ring }
Returns the reduced Grobner basis of the ideal obtained by a
successive applications of IDEAL$-$SATURATIONS to F and
lists of polynomials in the list IDEAL$-$LIST.
\end{lisp:documentation}

\begin{lisp:documentation}{buchberger$-$criterion}{FUNCTION}{g pred ring }
Returns T if G is a Grobner basis, by using the Buchberger
criterion: for every two polynomials h1 and h2 in G the
S$-$polynomial S(h1,h2) reduces to 0 modulo G.
\end{lisp:documentation}

\begin{lisp:documentation}{grobner$-$test}{FUNCTION}{g f pred ring }
Test whether G is a Grobner basis and F is contained in G. Return T
upon success and NIL otherwise.
\end{lisp:documentation}

\begin{lisp:documentation}{minimization}{FUNCTION}{p pred }
Returns a sublist of the polynomial list P spanning the same
monomial ideal as P but minimal, i.e. no leading monomial
of a polynomial in the sublist divides the leading monomial
of another polynomial.
\end{lisp:documentation}

\begin{lisp:documentation}{add$-$minimized}{FUNCTION}{f gred pred }
Adds a polynomial f to GRED, reduced Grobner basis, preserving the
property described in the documentation for MINIMIZATION.
\end{lisp:documentation}

\begin{lisp:documentation}{colon$-$ideal}{FUNCTION}{f g pred top$-$reduction$-$only ring }
Returns the reduced Grobner basis of the colon ideal Id(F):Id(G),
where F and G are two lists of polynomials. The colon ideal I:J is
defined as the set of polynomials H such that there is a polynomial W
in J for which W*H belongs to I.
\end{lisp:documentation}

\begin{lisp:documentation}{colon$-$ideal$-$1}{FUNCTION}{f g pred top$-$reduction$-$only ring }
Returns the reduced Grobner basis of the colon ideal Id(F):Id(\{G\}),
where F is a list of polynomials and G is a polynomial.
\end{lisp:documentation}

\begin{lisp:documentation}{pseudo$-$divide}{FUNCTION}{f fl pred ring }
Pseudo$-$divide a polynomial F by the list of polynomials FL. Return
multiple values. The first value is a list of quotients A.
The second value is the remainder R. The third value is an integer
count of the number of reductions performed. Finally, the fourth
argument is a scalar coefficient C, such that C*F can be divided by
FL within the ring of coefficients, which is not necessarily a field.
The resulting objects satisfy the equation:
 C*F= sum A[i]*FL[i] + R
\end{lisp:documentation}

\begin{lisp:documentation}{gebauer$-$moeller}{FUNCTION}{f pred start top$-$reduction$-$only ring {\sf \&aux} b g f1 }
Compute Grobner basis by using the algorithm of Gebauer and Moeller.
This algorithm is described as BUCHBERGERNEW2 in the book by
Becker$-$Weispfenning entitled ``Grobner Bases''
\end{lisp:documentation}

\begin{lisp:documentation}{update}{FUNCTION}{g b h pred ring {\sf \&aux} c d e b$-$new g$-$new pair }
An implementation of the auxillary UPDATE algorithm used by the
Gebauer$-$Moeller algorithm. G is a list of polynomials, B is a list
of critical pairs and H is a new polynomial which possibly will be
added to G. The naming conventions used are very close to the one
used in the book of Becker$-$Weispfenning.
\end{lisp:documentation}

\begin{lisp:documentation}{gebauer$-$moeller$-$merge$-$pairs$-$use$-$mock$-$spoly}{FUNCTION}{b c pred ring }
The merging strategy used by the Gebauer$-$Moeller algorithm, based
on MOCK$-$SPOLY; see the documentation of
BUCHBERGER$-$MERGE$-$PAIRS$-$USE$-$MOCK$-$SPOLY.
\end{lisp:documentation}

\begin{lisp:documentation}{gebauer$-$moeller$-$merge$-$pairs$-$smallest$-$lcm}{FUNCTION}{b c pred ring }
The merging strategy based on the smallest$-$lcm (normal strategy);
see the documentation of BUCHBERGER$-$MERGE$-$PAIRS$-$SMALLEST$-$LCM.
\end{lisp:documentation}

\begin{lisp:documentation}{gebauer$-$moeller$-$merge$-$pairs$-$use$-$smallest$-$degree}{FUNCTION}{b c pred ring }
The merging strategy based on the smallest$-$lcm (normal strategy);
see the documentation of
BUCHBERGER$-$MERGE$-$PAIRS$-$USE$-$SMALLEST$-$DEGREE. 
\end{lisp:documentation}

\begin{lisp:documentation}{gebauer$-$moeller$-$merge$-$pairs$-$use$-$smallest$-$length}{FUNCTION}{b c pred ring }
{\ } % NO DOCUMENTATION FOR GEBAUER-MOELLER-MERGE-PAIRS-USE-SMALLEST-LENGTH
\end{lisp:documentation}

\begin{lisp:documentation}{gebauer$-$moeller$-$merge$-$pairs$-$use$-$smallest$-$coefficient$-$length}{FUNCTION}{b c pred ring }
The merging strategy based on the smallest$-$lcm (normal strategy);
see the documentation of
BUCHBERGER$-$MERGE$-$PAIRS$-$USE$-$SMALLEST$-$COEFFICIENT$-$LENGTH. 
\end{lisp:documentation}

\begin{lisp:documentation}{gebauer$-$moeller$-$set$-$pair$-$heuristic}{FUNCTION}{method {\sf \&aux} (strategy$-$fn
                                                                                                     (ecase method (:minimal$-$mock$-$spoly \#'gebauer$-$moeller$-$merge$-$pairs$-$use$-$mock$-$spoly)
                                                                                                      (:minimal$-$lcm \#'gebauer$-$moeller$-$merge$-$pairs$-$smallest$-$lcm)
                                                                                                      (:minimal$-$total$-$degree \#'gebauer$-$moeller$-$merge$-$pairs$-$use$-$smallest$-$degree)
                                                                                                      (:minimal$-$length \#'gebauer$-$moeller$-$merge$-$pairs$-$use$-$smallest$-$length)
                                                                                                      (:minimal$-$coefficient$-$length
                                                                                                       \#'gebauer$-$moeller$-$merge$-$pairs$-$use$-$smallest$-$coefficient$-$length))) }
{\ } % NO DOCUMENTATION FOR GEBAUER-MOELLER-SET-PAIR-HEURISTIC
\end{lisp:documentation}

\begin{lisp:documentation}{spoly$-$sugar}{FUNCTION}{f$-$with$-$sugar g$-$with$-$sugar ring }
Calculate the ``sugar'' of the S$-$polynomial of two polynomials with
sugar. A polynomial with sugar is simply a pair (P . SUGAR) where
SUGAR is an integer constant defined according to the following
algorighm: the sugar of sum or difference of two polynomials with
sugar is the MAX of the sugars of those two polynomials. The sugar of
a product of a term and a polynomial is the sum of the degree of the
term and the sugar of the polynomial.  The idea is to accumulate
sugar as we perform the arithmetic operations, and that polynomials
with small (little) sugar should be given priority in the
calculations. Thus, the ``sugar strategy'' of the critical pair
selection is to select a pair with the smallest value of sugar of the
resulting S$-$polynomial.
\end{lisp:documentation}

\begin{lisp:documentation}{spoly$-$with$-$sugar}{FUNCTION}{f$-$with$-$sugar g$-$with$-$sugar pred ring }
The S$-$polynomials of two polynomials with SUGAR strategy.
\end{lisp:documentation}

\begin{lisp:documentation}{normal$-$form$-$with$-$sugar}{FUNCTION}{f fl pred top$-$reduction$-$only ring }
Normal form of the polynomial with sugar F with respect to
a list of polynomials with sugar FL. Assumes that FL is not empty.
Parameters PRED, TOP$-$REDUCTION$-$ONLY and RING have the same
meaning as in NORMAL$-$FORM. The parameter SUGAR$-$LIMIT should be
set to a positive integer. If the sugar limit of the partial
remainder exceeds SUGAR$-$LIMIT then the calculation is stopped and
the partial remainder is returned, although it is not fully reduced
with respect to FL. 
\end{lisp:documentation}

\begin{lisp:documentation}{buchberger$-$with$-$sugar}{FUNCTION}{f$-$no$-$sugar pred start top$-$reduction$-$only ring {\sf \&aux} (s (1$-$ (length f$-$no$-$sugar))) b m f }
Returns a Grobner basis of an ideal generated by a list of ordinary
polynomials F$-$NO$-$SUGAR. Adds initial sugar to the polynomials and
performs the Buchberger algorithm with ``sugar strategy''. It returns
an ordinary list of polynomials with no sugar. One of the most
effective algorithms for Grobner basis calculation.
\end{lisp:documentation}

\begin{lisp:documentation}{buchberger$-$with$-$sugar$-$merge$-$pairs}{FUNCTION}{b c g m pred ring }
Merges lists of critical pairs. It orders pairs according to
increasing sugar, with ties broken by smaller MOCK$-$SPOLY value of
the two polynomials. In this function B must already be sorted.
\end{lisp:documentation}

\begin{lisp:documentation}{buchberger$-$with$-$sugar$-$sort$-$pairs}{FUNCTION}{c g m pred ring }
Sorts critical pairs C according to sugar strategy.
\end{lisp:documentation}

\begin{lisp:documentation}{criterion$-$1$-$with$-$sugar}{FUNCTION}{pair g {\sf \&aux} (i (first pair)) (j (second pair)) }
An implementation of Buchberger's first criterion for polynomials 
with sugar. See the documentation of BUCHBERGER$-$CRITERION$-$1.
\end{lisp:documentation}

\begin{lisp:documentation}{criterion$-$2$-$with$-$sugar}{FUNCTION}{pair g m {\sf \&aux} (i (first pair)) (j (second pair)) }
An implementation of Buchberger's first criterion for polynomials 
with sugar. See the documentation of BUCHBERGER$-$CRITERION$-$2.
\end{lisp:documentation}

\begin{lisp:documentation}{gebauer$-$moeller$-$with$-$sugar}{FUNCTION}{f pred start top$-$reduction$-$only ring {\sf \&aux} b g f1 }
Compute Grobner basis by using the algorithm of Gebauer and Moeller.
This algorithm is described as BUCHBERGERNEW2 in the book by
Becker$-$Weispfenning entitled ``Grobner Bases''
\end{lisp:documentation}

\begin{lisp:documentation}{update$-$with$-$sugar}{FUNCTION}{g b h pred ring {\sf \&aux} c d e b$-$new g$-$new pair }
An implementation of the auxillary UPDATE algorithm used by the
Gebauer$-$Moeller algorithm. G is a list of polynomials, B is a list
of critical pairs and H is a new polynomial which possibly will be
added to G. The naming conventions used are very close to the one
used in the book of Becker$-$Weispfenning. Operates on polynomials
with sugar. 
\end{lisp:documentation}

\begin{lisp:documentation}{gebauer$-$moeller$-$with$-$sugar$-$merge$-$pairs}{FUNCTION}{b c pred ring }
Merges lists of critical pairs. It orders pairs according to
increasing sugar, with ties broken by smaller lcm of head monomials
In this function B must already be sorted. Operates on polynomials
with sugar. 
\end{lisp:documentation}

\begin{lisp:documentation}{grobner$-$primitive$-$part$-$with$-$sugar}{FUNCTION}{h ring }
{\ } % NO DOCUMENTATION FOR GROBNER-PRIMITIVE-PART-WITH-SUGAR
\end{lisp:documentation}