The Comprehensive Gröbner basis package

*colored$-$poly$-$debug*

$\parbox{\pboxargslen}{\em nil \/}$ [VARIABLE]

If true debugging output is on.

debug$-$cgb

$\parbox{\pboxargslen}{\em {\sf \&rest} args \/}$ [MACRO]

make$-$colored$-$poly

$\parbox{\pboxargslen}{\em poly k {\sf \&key} (key \char93 'identity)... ...er \char93 'lex$\gt$) (parameter$-$order \char93 'lex$\gt$) {\sf \&aux} l \/}$ [FUNCTION]

Colored poly is represented as a list (TERM1 TERM2 ... TERMS) where each term is a triple (MONOM . (POLY . COLOR)) where monoms and polys have common number of variables while color is one of the three: :RED, :GREEN or :WHITE. This function translates an ordinary polynomial into a colored one by dividing variables into K and N$-$K, where N is the total number of variables in the polynomial poly; the function KEY can be called to select variables in arbitrary order.

make$-$colored$-$poly$-$list

$\parbox{\pboxargslen}{\em plist {\sf \&rest} rest \/}$ [FUNCTION]

Translate a list of polynomials PLIST into a list of colored polynomials by calling MAKE$-$COLORED$-$POLY. Returns the resulting list.

color$-$poly$-$list

$\parbox{\pboxargslen}{\em flist {\sf \&optional} (cond (list nil nil)) \/}$ [FUNCTION]

Add colors to an ordinary list of polynomials FLIST, according to a condition COND. A condition is a pair of polynomial lists. Each polynomial in COND is a polynomial in parameters only. The list (FIRST COND) is called the ``green list'' and it consists of polynomials which vanish for the parameters associated with the condition. The list (SECOND COND) is called the ``red list

color$-$poly

$\parbox{\pboxargslen}{\em f {\sf \&optional} (cond (list nil nil)) \/}$ [FUNCTION]

Add color to a single polynomial F, according to condition COND. See the documentation of COLOR$-$POLY$-$LIST.

colored$-$poly$-$to$-$poly

$\parbox{\pboxargslen}{\em cpoly \/}$ [FUNCTION]

For a given colored polynomial CPOLY, removes the colors and it returns the polynomial as an ordinary polynomial with coefficients which are polynomials in parameters.

colored$-$poly$-$print

$\parbox{\pboxargslen}{\em poly vars {\sf \&key} (stream t) (beg t) (print$-$green$-$part nil) (mark$-$coefficients nil) \/}$ [FUNCTION]

Print a colored polynomial POLY. Use variables VARS to represent the variables. Some of the variables are going to be used as parameters, according to the length of the monomials in the main monomial and coefficient part of each term in POLY. The key variable STREAM may be used to redirect the output. If parameter PRINT$-$GREEN$-$PART is set then the coefficients which have color :GREEN will be printed, otherwise they are discarded silently. If MARK$-$COEFFICIENTS is not NIL then every coefficient will be marked according to its color, for instance G(U$-$1) would mean that U$-$1 is in the green list. Returns P.

colored$-$poly$-$print$-$list

$\parbox{\pboxargslen}{\em poly$-$list vars {\sf \&key} (stream t) (beg t) (print$-$green$-$part nil) (mark$-$coefficients nil) \/}$ [FUNCTION]

Pring a list of colored polynomials via a call to COLORED$-$POLY$-$PRINT.

determine

$\parbox{\pboxargslen}{\em f {\sf \&optional} (cond (list nil nil)) (order \char93 'lex$\gt$) (ring *coefficient$-$ring*) \/}$ [FUNCTION]

This function takes a list of colored polynomials F and a condition COND, and it returns a list of pairs (COND' F') such that COND' cover COND and F' is a ``determined'' version of the colored polynomial list F, i.e. every polynomial has its leading coefficient determined. This means that some of the initial coefficients in each polynomial in F' are in the green list of COND, and the first non$-$green coefficient is in the red list of COND. We note that F' differs from F only by different colors: some of the terms marked :WHITE are now marked either :GREEN or :RED. Coloring is done either by explicitly checking membership in red or green list of COND, or implicitly by performing Grobner basis calculations in the polynomial ring over the parameters. The admissible monomial order ORDER is used only in the parameter space. Also, the ring structure RING is used only for calculations on polynomials of the parameters only.

determine$-$1

$\parbox{\pboxargslen}{\em cond p end gp order ring \/}$ [FUNCTION]

Determine a single colored polynomial P according to condition COND. Prepend green part GP to P. Cons the result with END, which should be a list of colored polynomials, and return the resulting list of polynomials. This is an auxillary function of DETERMINE.

determine$-$white$-$term

$\parbox{\pboxargslen}{\em cond term restp end gp order ring \/}$ [FUNCTION]

This is an auxillary function of DETERMINE. In this function the parameter COND is a condition. The parameters TERM, RESTP and GP are three parts of a polynomial being processed, where TERM is colored :WHITE. We test the membership in the red and green list of COND we try to determine whether the term is :RED or :GREEN. This is done by performing ideal membership tests in the polynomial ring. Let C be the coefficient of TERM. Thus, C is a polynomial in parameters. We find whether C is in the green list by performing a plain ideal membership test. However, to test properly whether C is in the red list, one needs a different strategy. In fact, we test whether adding C to the red list would produce a non$-$empty set of parameters in some algebraic extension. The test is whether 1 belongs to the saturation ideal of (FIRST COND) in (CONS C (SECOND COND)). Thus, we use POLY$-$SATURATION. If we are successful in determining the color of TERM, we simply change the color of the term and return the list ((COND P)) where P is obtained by appending GP, (LIST TERM) and RESTP. If we cannot determine whether TERM is :RED or :GREEN, we return the list ((COND' P') (COND'' P

cond$-$system$-$print

$\parbox{\pboxargslen}{\em system vars params {\sf \&key} (suppress$-$... ...rint$-$green$-$part nil) (mark$-$coefficients nil) {\sf \&aux} (label 0) \/}$ [FUNCTION]

A conditional system SYSTEM is a list of pairs (COND PLIST), where COND is a condition (a pair (GREEN$-$LIST RED$-$LIST)) and PLIST is a list of colored polynomials. This function pretty$-$prints this list of pairs. A conditional system is the data structure returned by GROBNER$-$SYSTEM. This function returns SYSTEM, if SUPPRESS$-$VALUE is non$-$NIL and no value otherwise. If MARK$-$COEFFICIENTS is non$-$NIL coefficients will be marked as in G(u$-$1)*x+R(2)*y, which means that u$-$1 is :GREEN and 2 is :RED.

cond$-$print

$\parbox{\pboxargslen}{\em cond params \/}$ [FUNCTION]

Pretty$-$print a condition COND, using symbol list PARAMS as parameter names.

add$-$pairs

$\parbox{\pboxargslen}{\em gs pred \/}$ [FUNCTION]

The parameter GS shoud be a Grobner system, i.e. a set of pairs (CONDITION POLY$-$LIST) This functions adds the third component: the list of initial critical pairs (I J), as in the ordinary Grobner basis algorithm. In addition, it adds the length of of the POLY$-$LIST, less 1, as the fourth component. The resulting list of quadruples is returned.

cond$-$part

$\parbox{\pboxargslen}{\em p \/}$ [FUNCTION]

Find the part of a colored polynomial P starting with the first non$-$green term.

cond$-$hm

$\parbox{\pboxargslen}{\em p \/}$ [FUNCTION]

Return the conditional head monomial of a colored polynomial P.

delete$-$green$-$polys

$\parbox{\pboxargslen}{\em gamma \/}$ [FUNCTION]

Delete totally green polynomials from in a grobner system GAMMA.

grobner$-$system

$\parbox{\pboxargslen}{\em f {\sf \&key} (cover (list '(nil nil))) (ma... ...char93 '(lambda (cond) (determine f cond parameter$-$order ring)) cover))) \/}$ [FUNCTION]

This function returns a grobner system, given a list of colored polynomials F, Other parameters are: A cover COVER, i.e. a list of conditions, i.e. pairs of the form (GREEN$-$LIST RED$-$LIST), where GREEN$-$LIST and RED$-$LIST are to lists of ordinary polynomials in parameters. A monomial order MAIN$-$ORDER used on main variables (not parameters). A monomial order PARAMETER$-$ORDER used in calculations with parameters only. REDUCE, a flag deciding whether COLORED$-$REDUCTION will be performed on the resulting grobner system. GREEN$-$REDUCE, a flag deciding whether the green list of each condition will be reduced in a form of a reduced Grobner basis. TOP$-$REDUCTION$-$ONLY, a flag deciding whether in the internal calculations in the space of parameters top reduction only will be used. RING, a structure as in the package COEFFICIENT$-$RING, used in operations on the coefficients of the polynomials in parameters.

reorder$-$pairs

$\parbox{\pboxargslen}{\em b bnew g pred {\sf \&optional} (sort$-$first nil) \/}$ [FUNCTION]

Reorder pairs according to some heuristic. The heuristic at this time is ad hoc, in the future it should be replaced with sugar strategy and a mechanism for implementing new heuristic strategies, as in the GROBNER package.

colored$-$criterion$-$1

$\parbox{\pboxargslen}{\em i j f \/}$ [FUNCTION]

Buchberger criterion 1 for colored polynomials.

colored$-$criterion$-$2

$\parbox{\pboxargslen}{\em i j f b s \/}$ [FUNCTION]

Buchberger criterion 2 for colored polynomials.

cond$-$normal$-$form

$\parbox{\pboxargslen}{\em f fl main$-$order parameter$-$order top$-$reduction$-$only ring \/}$ [FUNCTION]

Returns the conditional normal form of a colored polynomial F with respect to the list of colored polynomials FL. The list FL is assumed to consist of determined polynomials, i.e. such that the first term which is not marked :GREEN is :RED.

cond$-$spoly

$\parbox{\pboxargslen}{\em f g main$-$order parameter$-$order ring \/}$ [FUNCTION]

Returns the conditional S$-$polynomial of two colored polynomials F and G. Both polynomials are assumed to be determined.

cond$-$lm

$\parbox{\pboxargslen}{\em f \/}$ [FUNCTION]

Returns the conditional leading monomial of a colored polynomial F, which is assumed to be determined.

cond$-$lc

$\parbox{\pboxargslen}{\em f \/}$ [FUNCTION]

Returns the conditional leading coefficient of a colored polynomial F, which is assumed to be determined.

colored$-$term$-$times$-$poly

$\parbox{\pboxargslen}{\em term f order ring \/}$ [FUNCTION]

Returns the product of a colored term TERM and a colored polynomial F.

colored$-$scalar$-$times$-$poly

$\parbox{\pboxargslen}{\em c f ring \/}$ [FUNCTION]

Returns the product of an element of the coefficient ring C a colored polynomial F.

colored$-$term*

$\parbox{\pboxargslen}{\em term1 term2 order ring \/}$ [FUNCTION]

Returns the product of two colored terms TERM1 and TERM2.

color*

$\parbox{\pboxargslen}{\em c1 c2 \/}$ [FUNCTION]

Returns a product of two colores. Rules: :red * :red yields :red any * :green yields :green otherwise the result is :white.

color+

$\parbox{\pboxargslen}{\em c1 c2 \/}$ [FUNCTION]

Returns a sum of colors. Rules: :green + :green yields :green, :red + :green yields :red any other result is :white.

color$-$

$\parbox{\pboxargslen}{\em c1 c2 \/}$ [FUNCTION]

Identical to COLOR+.

colored$-$poly+

$\parbox{\pboxargslen}{\em p q main$-$order parameter$-$order ring \/}$ [FUNCTION]

Returns the sum of colored polynomials P and Q.

colored$-$poly$-$

$\parbox{\pboxargslen}{\em p q main$-$order parameter$-$order ring \/}$ [FUNCTION]

Returns the difference of colored polynomials P and Q.

colored$-$term$-$uminus

$\parbox{\pboxargslen}{\em term ring \/}$ [FUNCTION]

Returns the negation of a colored term TERM.

colored$-$minus$-$poly

$\parbox{\pboxargslen}{\em p ring \/}$ [FUNCTION]

Returns the negation of a colored polynomial P.

string$-$grobner$-$system

$\parbox{\pboxargslen}{\em f vars params {\sf \&key} (cover (list (l... ...meter$-$order)) (cover (string$-$cover cover params parameter$-$order)) \/}$ [FUNCTION]

An interface to GROBNER$-$SYSTEM in which polynomials can be specified in infix notations as strings. Lists of polynomials are comma$-$separated list marked by a matchfix operators []

string$-$cond

$\parbox{\pboxargslen}{\em cond params {\sf \&optional} (order \char93 'lex$\gt$) \/}$ [FUNCTION]

Return the internal representation of a condition COND, specified as pairs of strings (GREEN$-$LIST RED$-$LIST). GREEN$-$LIST and RED$-$LIST in the input are assumed to be strings which parse to two lists of polynomials with respect to variables whose names are in the list of symbols PARAMS. ORDER is the predicate used to sort the terms of the polynomials.

string$-$cover

$\parbox{\pboxargslen}{\em cover params {\sf \&optional} (order \char93 'lex$\gt$) \/}$ [FUNCTION]

Returns the internal representation of COVER, given in the form of a list of conditions. See STRING$-$COND for description of a condition.

saturate$-$cover

$\parbox{\pboxargslen}{\em cover order ring \/}$ [FUNCTION]

Brings every condition of a list of conditions COVER to the form (G R) where G is saturated with respect to R and G is a Grobner basis We could reduce R so that the elements of R are relatively prime, but this is not currently done.

saturate$-$cond

$\parbox{\pboxargslen}{\em cond order ring \/}$ [FUNCTION]

Saturate a single condition COND. An auxillary function of SATURATE$-$COVER.

string$-$determine

$\parbox{\pboxargslen}{\em f vars params {\sf \&key} (cond '([] [])) ... ...arameter$-$order)) (cond (string$-$cond cond params parameter$-$order)) \/}$ [FUNCTION]

A string interface to DETERMINE. See the documentation of STRING$-$GROBNER$-$SYSTEM.

tidy$-$grobner$-$system

$\parbox{\pboxargslen}{\em gs main$-$order parameter$-$order reduce green$-$reduce ring \/}$ [FUNCTION]

Apply TIDY$-$PAIR to every pair of a Grobner system.

tidy$-$pair

$\parbox{\pboxargslen}{\em pair main$-$order parameter$-$order reduce green$-$reduce ring {\sf \&aux} gs \/}$ [FUNCTION]

Make the output of Grobner system more readable by performing certain simplifications on an element of a Grobner system. If REDUCE is non$-$NIL then COLORED$-$reduction will be performed. In addition TIDY$-$COND is called on the condition part of the pair PAIR.

tidy$-$cond

$\parbox{\pboxargslen}{\em cond order ring \/}$ [FUNCTION]

Currently saturates condition COND and does RED$-$REDUCTION on the red list.

colored$-$reduction

$\parbox{\pboxargslen}{\em cond p main$-$order parameter$-$order ring {\sf \&aux} (open (list (list cond nil p))) closed \/}$ [FUNCTION]

Reduce a list of colored polynomials P. The difficulty as compared to the usual Buchberger algorithm is that the polys may have the same leading monomial which may result in cancellations and polynomials which may not be determined. Thus, when we find those, we will have to split the condition by calling determine. Returns a list of pairs (COND' P') where P' is a reduced grobner basis with respect to any parameter choice compatible with condition COND'. Moreover, COND' form a cover of COND.

green$-$reduce$-$colored$-$poly

$\parbox{\pboxargslen}{\em cond f parameter$-$order ring \/}$ [FUNCTION]

It takes a colored polynomial F and it returns a modified polynomial obtained by reducing coefficient of F modulo green list of the condition COND.

green$-$reduce$-$colored$-$list

$\parbox{\pboxargslen}{\em cond fl parameter$-$order ring \/}$ [FUNCTION]

Apply GREEN$-$REDUCE$-$COLORED$-$POLY to a list of polynomials FL.

cond$-$system$-$green$-$reduce

$\parbox{\pboxargslen}{\em gs parameter$-$order ring \/}$ [FUNCTION]

Apply GREEN$-$REDUCE$-$COLORED$-$LIST to every pair of a grobner system GS.

parse$-$to$-$colored$-$poly$-$list

$\parbox{\pboxargslen}{\em f vars params main$-$order parameter$-$order {\sf \&aux} (k (length vars)) (vars$-$params (append vars params)) \/}$ [FUNCTION]

Parse a list of polynomials F, given as a string, with respect to a list of variables VARS, given as a list of symbols, to the internal representation of a colored polynomial. The polynomials will be properly sorted by MAIN$-$ORDER, with the coefficients, which are polynomials in parameters, sorted by PARAMETER$-$ORDER. Both orders must be admissible monomial orders. This form is suitable for parsing polynomials with integer coefficients.

red$-$reduction

$\parbox{\pboxargslen}{\em p pred ring {\sf \&aux} (p (remove$-$if \char93 'poly$-$constant$-$p p)) \/}$ [FUNCTION]

Takes a family of polynomials and produce a list whose prime factors are the same but they are relatively prime Repetitively used the following procedure: it finds two elements f, g of P which are not relatively prime; it replaces f and g with f/GCD(f,g), g/ GCD(f,f) and GCD(f,g).