source: CGBLisp/doc/grobner.txt@ 1

;;; *GROBNER-DEBUG* (nil)                                            [VARIABLE]
;;;    If T, produce debugging and tracing output.
;;;
;;; *BUCHBERGER-MERGE-PAIRS* ('buchberger-merge-pairs-smallest-lcm)  [VARIABLE]
;;;    A variable holding the predicate used to sort critical pairs
;;;    in the order of decreasing priority for the Buchberger algorithm.
;;;
;;; *GEBAUER-MOELLER-MERGE-PAIRS* ('gebauer-moeller-merge-pairs-use-mock-spoly)  [VARIABLE]
;;;    A variable holding the predicate used to sort critical pairs
;;;    in the order of decreasing priority for the Gebauer-Moeller algorithm
;;;
;;; *GROBNER-FUNCTION* ('buchberger)                                 [VARIABLE]
;;;    The name of the function used to calculate Grobner basis
;;;
;;; SELECT-GROBNER-ALGORITHM (algorithm)                             [FUNCTION]
;;;    Select one of the several implementations of the Grobner basis
;;;    algorithm.
;;;
;;; GROBNER (f &optional (pred #'lex>) (start 0)                     [FUNCTION]
;;;          (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.
;;;
;;; DEBUG-CGB (&rest args)                                              [MACRO]
;;;    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.
;;;
;;; SPOLY (f g pred ring)                                            [FUNCTION]
;;;    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.
;;;
;;; GROBNER-PRIMITIVE-PART (p ring)                                  [FUNCTION]
;;;    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.
;;;
;;; GROBNER-CONTENT (p ring)                                         [FUNCTION]
;;;    Greatest common divisor of the coefficients of the polynomial P. Use
;;;    the RING structure to compute the greatest common divisor.
;;;
;;; NORMAL-FORM (f fl pred top-reduction-only ring)                  [FUNCTION]
;;;    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.
;;;
;;; BUCHBERGER (f pred start top-reduction-only ring                 [FUNCTION]
;;;             &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).
;;;
;;; GROBNER-OP (c1 c2 m a b pred ring &aux n a1 a2)                  [FUNCTION]
;;;    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.
;;;
;;; BUCHBERGER-SORT-PAIRS (b g pred ring)                            [FUNCTION]
;;;    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.
;;;
;;; MOCK-SPOLY (f g pred)                                            [FUNCTION]
;;;    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.
;;;
;;; BUCHBERGER-MERGE-PAIRS-USE-MOCK-SPOLY (b c g pred ring)          [FUNCTION]
;;;    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.
;;;
;;; BUCHBERGER-MERGE-PAIRS-SMALLEST-LCM (b c g pred ring)            [FUNCTION]
;;;    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.
;;;
;;; BUCHBERGER-MERGE-PAIRS-USE-SMALLEST-DEGREE (b c g pred ring)     [FUNCTION]
;;;    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.
;;;
;;; BUCHBERGER-MERGE-PAIRS-USE-SMALLEST-LENGTH (b c g pred ring)     [FUNCTION]
;;;    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.
;;;
;;; BUCHBERGER-MERGE-PAIRS-USE-SMALLEST-COEFFICIENT-LENGTH (b c g    [FUNCTION]
;;;                                                         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.
;;;
;;; BUCHBERGER-SET-PAIR-HEURISTIC (method                            [FUNCTION]
;;;                                &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.
;;;
;;; CRITERION-1 (pair g &aux (i (first pair)) (j (second pair)))     [FUNCTION]
;;;    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. 
;;;
;;; CRITERION-2 (pair g m &aux (i (first pair)) (j (second pair)))   [FUNCTION]
;;;    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.
;;;
;;; NORMALIZE-POLY (p ring)                                          [FUNCTION]
;;;    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.
;;;
;;; NORMALIZE-BASIS (plist ring)                                     [FUNCTION]
;;;    Divide every polynomial in a list PLIST by its leading coefficient.
;;;    Use RING structure to perform the division of the coefficients.
;;;
;;; REDUCTION (p pred ring)                                          [FUNCTION]
;;;    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.
;;;
;;; REDUCED-GROBNER (f &optional (pred #'lex>) (start 0)             [FUNCTION]
;;;                  (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. 
;;;
;;; MONOM-DEPENDS-P (m k)                                            [FUNCTION]
;;;    Return T if the monomial M depends on variable number K.
;;;
;;; TERM-DEPENDS-P (term k)                                          [FUNCTION]
;;;    Return T if the term TERM depends on variable number K.
;;;
;;; POLY-DEPENDS-P (p k)                                             [FUNCTION]
;;;    Return T if the term polynomial P depends on variable number K.
;;;
;;; RING-INTERSECTION (plist k &key (key #'identity))                [FUNCTION]
;;;    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]. 
;;;
;;; ELIMINATION-IDEAL (flist k &key (primary-order #'lex>)           [FUNCTION]
;;;                    (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. 
;;;
;;; IDEAL-INTERSECTION (f g pred top-reduction-only ring)            [FUNCTION]
;;;    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.
;;;
;;; POLY-CONTRACT (f &optional (k 1))                                [FUNCTION]
;;;    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.
;;;
;;; POLY-LCM (f g &optional (pred #'lex>)                            [FUNCTION]
;;;           (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.
;;;
;;; GROBNER-GCD (f g &optional (pred #'lex>)                         [FUNCTION]
;;;              (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.
;;;
;;; GROBNER-EQUAL (g1 g2 &optional (pred #'lex>)                     [FUNCTION]
;;;                (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.
;;;
;;; GROBNER-SUBSETP (g1 g2 &optional (pred #'lex>)                   [FUNCTION]
;;;                  (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.
;;;
;;; GROBNER-MEMBER (p g &optional (pred #'lex>)                      [FUNCTION]
;;;                 (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. 
;;;
;;; IDEAL-EQUAL (f1 f2 pred top-reduction-only ring)                 [FUNCTION]
;;;    Returns T if two ideals generated by polynomial lists F1 and F2 are
;;;    identical. Returns NIL otherwise.
;;;
;;; IDEAL-SUBSETP (f1 f2 &optional (pred #'lex>)                     [FUNCTION]
;;;                (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. 
;;;
;;; IDEAL-MEMBER (p plist pred top-reduction-only ring)              [FUNCTION]
;;;    Returns T if the polynomial P belongs to the ideal spanned by the
;;;    polynomial list PLIST, and NIL otherwise.
;;;
;;; IDEAL-SATURATION-1 (f p pred start top-reduction-only ring       [FUNCTION]
;;;                     &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.
;;;
;;; ADD-VARIABLES (plist n)                                          [FUNCTION]
;;;    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. 
;;;
;;; EXTEND-POLYNOMIALS (plist &aux (k (length plist)))               [FUNCTION]
;;;    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.
;;;
;;; SATURATION-EXTENSION (f plist ring &aux (k (length plist)) (d    [FUNCTION]
;;;                       (+ 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. 
;;;
;;; POLYSATURATION-EXTENSION (f plist ring &aux (k (length plist))   [FUNCTION]
;;;                           (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. 
;;;
;;; SATURATION-EXTENSION-1 (f p ring)                                [FUNCTION]
;;;    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.
;;;
;;; IDEAL-POLYSATURATION-1 (f plist pred start top-reduction-only    [FUNCTION]
;;;                         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.
;;;
;;; IDEAL-SATURATION (f g pred start top-reduction-only ring         [FUNCTION]
;;;                   &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.
;;;
;;; IDEAL-POLYSATURATION (f ideal-list pred start                    [FUNCTION]
;;;                       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.
;;;
;;; BUCHBERGER-CRITERION (g pred ring)                               [FUNCTION]
;;;    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.
;;;
;;; GROBNER-TEST (g f pred ring)                                     [FUNCTION]
;;;    Test whether G is a Grobner basis and F is contained in G. Return T
;;;    upon success and NIL otherwise.
;;;
;;; MINIMIZATION (p pred)                                            [FUNCTION]
;;;    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.
;;;
;;; ADD-MINIMIZED (f gred pred)                                      [FUNCTION]
;;;    Adds a polynomial f to GRED, reduced Grobner basis, preserving the
;;;    property described in the documentation for MINIMIZATION.
;;;
;;; COLON-IDEAL (f g pred top-reduction-only ring)                   [FUNCTION]
;;;    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.
;;;
;;; COLON-IDEAL-1 (f g pred top-reduction-only ring)                 [FUNCTION]
;;;    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.
;;;
;;; PSEUDO-DIVIDE (f fl pred ring)                                   [FUNCTION]
;;;    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
;;;
;;; GEBAUER-MOELLER (f pred start top-reduction-only ring &aux b g   [FUNCTION]
;;;                  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''
;;;
;;; UPDATE (g b h pred ring &aux c d e b-new g-new pair)             [FUNCTION]
;;;    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.
;;;
;;; GEBAUER-MOELLER-MERGE-PAIRS-USE-MOCK-SPOLY (b c pred ring)       [FUNCTION]
;;;    The merging strategy used by the Gebauer-Moeller algorithm, based
;;;    on MOCK-SPOLY; see the documentation of
;;;    BUCHBERGER-MERGE-PAIRS-USE-MOCK-SPOLY.
;;;
;;; GEBAUER-MOELLER-MERGE-PAIRS-SMALLEST-LCM (b c pred ring)         [FUNCTION]
;;;    The merging strategy based on the smallest-lcm (normal strategy); see
;;;    the documentation of BUCHBERGER-MERGE-PAIRS-SMALLEST-LCM.
;;;
;;; GEBAUER-MOELLER-MERGE-PAIRS-USE-SMALLEST-DEGREE (b c pred ring)  [FUNCTION]
;;;    The merging strategy based on the smallest-lcm (normal strategy); see
;;;    the documentation of BUCHBERGER-MERGE-PAIRS-USE-SMALLEST-DEGREE.
;;;
;;; GEBAUER-MOELLER-MERGE-PAIRS-USE-SMALLEST-LENGTH (b c pred ring)  [FUNCTION]
;;;
;;; GEBAUER-MOELLER-MERGE-PAIRS-USE-SMALLEST-COEFFICIENT-LENGTH (b   [FUNCTION]
;;;                                                              c
;;;                                                              pred ring)
;;;    The merging strategy based on the smallest-lcm (normal strategy); see
;;;    the documentation of
;;;    BUCHBERGER-MERGE-PAIRS-USE-SMALLEST-COEFFICIENT-LENGTH. 
;;;
;;; GEBAUER-MOELLER-SET-PAIR-HEURISTIC (method                       [FUNCTION]
;;;                                     &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))))
;;;
;;; SPOLY-SUGAR (f-with-sugar g-with-sugar ring)                     [FUNCTION]
;;;    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.
;;;
;;; SPOLY-WITH-SUGAR (f-with-sugar g-with-sugar pred ring)           [FUNCTION]
;;;    The S-polynomials of two polynomials with SUGAR strategy.
;;;
;;; NORMAL-FORM-WITH-SUGAR (f fl pred top-reduction-only ring)       [FUNCTION]
;;;    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. 
;;;
;;; BUCHBERGER-WITH-SUGAR (f-no-sugar pred start top-reduction-only  [FUNCTION]
;;;                        ring &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.
;;;
;;; BUCHBERGER-WITH-SUGAR-MERGE-PAIRS (b c g m pred ring)            [FUNCTION]
;;;    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.
;;;
;;; BUCHBERGER-WITH-SUGAR-SORT-PAIRS (c g m pred ring)               [FUNCTION]
;;;    Sorts critical pairs C according to sugar strategy.
;;;
;;; CRITERION-1-WITH-SUGAR (pair g &aux (i (first pair)) (j          [FUNCTION]
;;;                         (second pair)))
;;;    An implementation of Buchberger's first criterion for polynomials 
;;;    with sugar. See the documentation of BUCHBERGER-CRITERION-1.
;;;
;;; CRITERION-2-WITH-SUGAR (pair g m &aux (i (first pair)) (j        [FUNCTION]
;;;                         (second pair)))
;;;    An implementation of Buchberger's first criterion for polynomials 
;;;    with sugar. See the documentation of BUCHBERGER-CRITERION-2.
;;;
;;; GEBAUER-MOELLER-WITH-SUGAR (f pred start top-reduction-only      [FUNCTION]
;;;                             ring &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''
;;;
;;; UPDATE-WITH-SUGAR (g b h pred ring &aux c d e b-new g-new pair)  [FUNCTION]
;;;    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.
;;;
;;; GEBAUER-MOELLER-WITH-SUGAR-MERGE-PAIRS (b c pred ring)           [FUNCTION]
;;;    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. 
;;;
;;; GROBNER-PRIMITIVE-PART-WITH-SUGAR (h ring)                       [FUNCTION]
;;;