\begin{lisp:documentation}{*colored$-$poly$-$debug*}{VARIABLE}{nil }
If true debugging output is on.
\end{lisp:documentation}

\begin{lisp:documentation}{debug$-$cgb}{MACRO}{{\sf \&rest} args }
{\ } % NO DOCUMENTATION FOR DEBUG-CGB
\end{lisp:documentation}

\begin{lisp:documentation}{make$-$colored$-$poly}{FUNCTION}{poly k {\sf \&key} (key \#'identity) (main$-$order \#'lex$>$) (parameter$-$order \#'lex$>$) {\sf \&aux} l }
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.
\end{lisp:documentation}

\begin{lisp:documentation}{make$-$colored$-$poly$-$list}{FUNCTION}{plist {\sf \&rest} rest }
Translate a list of polynomials PLIST into a list of colored
polynomials by calling MAKE$-$COLORED$-$POLY. Returns the resulting
list. 
\end{lisp:documentation}

\begin{lisp:documentation}{color$-$poly$-$list}{FUNCTION}{flist {\sf \&optional} (cond (list nil nil)) }
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
\end{lisp:documentation}

\begin{lisp:documentation}{color$-$poly}{FUNCTION}{f {\sf \&optional} (cond (list nil nil)) }
Add color to a single polynomial F, according to condition COND.
See the documentation of COLOR$-$POLY$-$LIST.
\end{lisp:documentation}

\begin{lisp:documentation}{colored$-$poly$-$to$-$poly}{FUNCTION}{cpoly }
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.
\end{lisp:documentation}

\begin{lisp:documentation}{colored$-$poly$-$print}{FUNCTION}{poly vars {\sf \&key} (stream t) (beg t) (print$-$green$-$part nil) (mark$-$coefficients nil) }
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.
\end{lisp:documentation}

\begin{lisp:documentation}{colored$-$poly$-$print$-$list}{FUNCTION}{poly$-$list vars {\sf \&key} (stream t) (beg t) (print$-$green$-$part nil) (mark$-$coefficients nil) }
Pring a list of colored polynomials via a call to
COLORED$-$POLY$-$PRINT.
\end{lisp:documentation}

\begin{lisp:documentation}{determine}{FUNCTION}{f {\sf \&optional} (cond (list nil nil)) (order \#'lex$>$) (ring *coefficient$-$ring*) }
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.
\end{lisp:documentation}

\begin{lisp:documentation}{determine$-$1}{FUNCTION}{cond p end gp order ring }
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.
\end{lisp:documentation}

\begin{lisp:documentation}{determine$-$white$-$term}{FUNCTION}{cond term restp end gp order ring }
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
\end{lisp:documentation}

\begin{lisp:documentation}{cond$-$system$-$print}{FUNCTION}{system vars params {\sf \&key} (suppress$-$value t) (print$-$green$-$part nil) (mark$-$coefficients nil) {\sf \&aux} (label 0) }
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. 
\end{lisp:documentation}

\begin{lisp:documentation}{cond$-$print}{FUNCTION}{cond params }
Pretty$-$print a condition COND, using symbol list PARAMS as
parameter names. 
\end{lisp:documentation}

\begin{lisp:documentation}{add$-$pairs}{FUNCTION}{gs pred }
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.
\end{lisp:documentation}

\begin{lisp:documentation}{cond$-$part}{FUNCTION}{p }
Find the part of a colored polynomial P starting with the first
 non$-$green term.
\end{lisp:documentation}

\begin{lisp:documentation}{cond$-$hm}{FUNCTION}{p }
Return the conditional head monomial of a colored polynomial P.
\end{lisp:documentation}

\begin{lisp:documentation}{delete$-$green$-$polys}{FUNCTION}{gamma }
Delete totally green polynomials from in a grobner system GAMMA.
\end{lisp:documentation}

\begin{lisp:documentation}{grobner$-$system}{FUNCTION}{f {\sf \&key} (cover (list '(nil nil))) (main$-$order \#'lex$>$) (parameter$-$order \#'lex$>$) (reduce t) (green$-$reduce t) (top$-$reduction$-$only
                                                                                                                                                                                     nil) (ring
                                                                                                                                                                                           *coefficient$-$ring*) {\sf \&aux} (cover
                                                                                                                                                                                                                              (saturate$-$cover
                                                                                                                                                                                                                               cover
                                                                                                                                                                                                                               parameter$-$order
                                                                                                                                                                                                                               ring)) (gamma
                                                                                                                                                                                                                                       (delete$-$green$-$polys
                                                                                                                                                                                                                                        (mapcan
                                                                                                                                                                                                                                         \#'(lambda (cond) (determine f cond parameter$-$order ring))
                                                                                                                                                                                                                                         cover))) }
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. 
\end{lisp:documentation}

\begin{lisp:documentation}{reorder$-$pairs}{FUNCTION}{b bnew g pred {\sf \&optional} (sort$-$first nil) }
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. 
\end{lisp:documentation}

\begin{lisp:documentation}{colored$-$criterion$-$1}{FUNCTION}{i j f }
Buchberger criterion 1 for colored polynomials.
\end{lisp:documentation}

\begin{lisp:documentation}{colored$-$criterion$-$2}{FUNCTION}{i j f b s }
Buchberger criterion 2 for colored polynomials.
\end{lisp:documentation}

\begin{lisp:documentation}{cond$-$normal$-$form}{FUNCTION}{f fl main$-$order parameter$-$order top$-$reduction$-$only ring }
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.
\end{lisp:documentation}

\begin{lisp:documentation}{cond$-$spoly}{FUNCTION}{f g main$-$order parameter$-$order ring }
Returns the conditional S$-$polynomial of two colored polynomials F
and G. Both polynomials are assumed to be determined.
\end{lisp:documentation}

\begin{lisp:documentation}{cond$-$lm}{FUNCTION}{f }
Returns the conditional leading monomial of a colored polynomial F,
which is assumed to be determined.
\end{lisp:documentation}

\begin{lisp:documentation}{cond$-$lc}{FUNCTION}{f }
Returns the conditional leading coefficient of a colored polynomial
F, which is assumed to be determined.
\end{lisp:documentation}

\begin{lisp:documentation}{colored$-$term$-$times$-$poly}{FUNCTION}{term f order ring }
Returns the product of a colored term TERM and a colored polynomial
F. 
\end{lisp:documentation}

\begin{lisp:documentation}{colored$-$scalar$-$times$-$poly}{FUNCTION}{c f ring }
Returns the product of an element of the coefficient ring C a colored
polynomial F. 
\end{lisp:documentation}

\begin{lisp:documentation}{colored$-$term*}{FUNCTION}{term1 term2 order ring }
Returns the product of two colored terms TERM1 and TERM2.
\end{lisp:documentation}

\begin{lisp:documentation}{color*}{FUNCTION}{c1 c2 }
Returns a product of two colores. Rules:
:red * :red yields :red
any * :green yields :green
otherwise the result is :white.
\end{lisp:documentation}

\begin{lisp:documentation}{color+}{FUNCTION}{c1 c2 }
Returns a sum of colors. Rules:
:green + :green yields :green,
:red + :green yields :red
any other result is :white.
\end{lisp:documentation}

\begin{lisp:documentation}{color$-$}{FUNCTION}{c1 c2 }
Identical to COLOR+.
\end{lisp:documentation}

\begin{lisp:documentation}{colored$-$poly+}{FUNCTION}{p q main$-$order parameter$-$order ring }
Returns the sum of colored polynomials P and Q.
\end{lisp:documentation}

\begin{lisp:documentation}{colored$-$poly$-$}{FUNCTION}{p q main$-$order parameter$-$order ring }
Returns the difference of colored polynomials P and Q.
\end{lisp:documentation}

\begin{lisp:documentation}{colored$-$term$-$uminus}{FUNCTION}{term ring }
Returns the negation of a colored term TERM.
\end{lisp:documentation}

\begin{lisp:documentation}{colored$-$minus$-$poly}{FUNCTION}{p ring }
Returns the negation of a colored polynomial P.
\end{lisp:documentation}

\begin{lisp:documentation}{string$-$grobner$-$system}{FUNCTION}{f vars params {\sf \&key} (cover (list (list "[]" "[]"))) (main$-$order \#'lex$>$) (parameter$-$order \#'lex$>$) (ring
                                                                                                                                                                                  *coefficient$-$ring*) (suppress$-$value
                                                                                                                                                                                                         t) (suppress$-$printing
                                                                                                                                                                                                             nil) (mark$-$coefficients
                                                                                                                                                                                                                   nil) (reduce
                                                                                                                                                                                                                         t) (green$-$reduce
                                                                                                                                                                                                                             t) {\sf \&aux} (f
                                                                                                                                                                                                                                             (parse$-$to$-$colored$-$poly$-$list
                                                                                                                                                                                                                                              f
                                                                                                                                                                                                                                              vars
                                                                                                                                                                                                                                              params
                                                                                                                                                                                                                                              main$-$order
                                                                                                                                                                                                                                              parameter$-$order)) (cover
                                                                                                                                                                                                                                                                   (string$-$cover
                                                                                                                                                                                                                                                                    cover
                                                                                                                                                                                                                                                                    params
                                                                                                                                                                                                                                                                    parameter$-$order)) }
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 [] 
\end{lisp:documentation}

\begin{lisp:documentation}{string$-$cond}{FUNCTION}{cond params {\sf \&optional} (order \#'lex$>$) }
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.
\end{lisp:documentation}

\begin{lisp:documentation}{string$-$cover}{FUNCTION}{cover params {\sf \&optional} (order \#'lex$>$) }
Returns the internal representation of COVER, given in the form of
a list of conditions. See STRING$-$COND for description of a
condition. 
\end{lisp:documentation}

\begin{lisp:documentation}{saturate$-$cover}{FUNCTION}{cover order ring }
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.
\end{lisp:documentation}

\begin{lisp:documentation}{saturate$-$cond}{FUNCTION}{cond order ring }
Saturate a single condition COND. An auxillary function of
SATURATE$-$COVER. 
\end{lisp:documentation}

\begin{lisp:documentation}{string$-$determine}{FUNCTION}{f vars params {\sf \&key} (cond '([] [])) (main$-$order \#'lex$>$) (parameter$-$order \#'lex$>$) (suppress$-$value t) (suppress$-$printing
                                                                                                                                                                                nil) (mark$-$coefficients
                                                                                                                                                                                      nil) (ring
                                                                                                                                                                                            *coefficient$-$ring*) {\sf \&aux} (f
                                                                                                                                                                                                                               (parse$-$to$-$colored$-$poly$-$list
                                                                                                                                                                                                                                f
                                                                                                                                                                                                                                vars
                                                                                                                                                                                                                                params
                                                                                                                                                                                                                                main$-$order
                                                                                                                                                                                                                                parameter$-$order)) (cond
                                                                                                                                                                                                                                                     (string$-$cond
                                                                                                                                                                                                                                                      cond
                                                                                                                                                                                                                                                      params
                                                                                                                                                                                                                                                      parameter$-$order)) }
A string interface to DETERMINE. See the documentation of
STRING$-$GROBNER$-$SYSTEM. 
\end{lisp:documentation}

\begin{lisp:documentation}{tidy$-$grobner$-$system}{FUNCTION}{gs main$-$order parameter$-$order reduce green$-$reduce ring }
Apply TIDY$-$PAIR to every pair of a Grobner system.
\end{lisp:documentation}

\begin{lisp:documentation}{tidy$-$pair}{FUNCTION}{pair main$-$order parameter$-$order reduce green$-$reduce ring {\sf \&aux} gs }
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. 
\end{lisp:documentation}

\begin{lisp:documentation}{tidy$-$cond}{FUNCTION}{cond order ring }
Currently saturates condition COND and does RED$-$REDUCTION on the
red list. 
\end{lisp:documentation}

\begin{lisp:documentation}{colored$-$reduction}{FUNCTION}{cond p main$-$order parameter$-$order ring {\sf \&aux} (open (list (list cond nil p))) closed }
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.
\end{lisp:documentation}

\begin{lisp:documentation}{green$-$reduce$-$colored$-$poly}{FUNCTION}{cond f parameter$-$order ring }
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.
\end{lisp:documentation}

\begin{lisp:documentation}{green$-$reduce$-$colored$-$list}{FUNCTION}{cond fl parameter$-$order ring }
Apply GREEN$-$REDUCE$-$COLORED$-$POLY to a list of polynomials FL.
\end{lisp:documentation}

\begin{lisp:documentation}{cond$-$system$-$green$-$reduce}{FUNCTION}{gs parameter$-$order ring }
Apply GREEN$-$REDUCE$-$COLORED$-$LIST to every pair of
a grobner system GS.
\end{lisp:documentation}

\begin{lisp:documentation}{parse$-$to$-$colored$-$poly$-$list}{FUNCTION}{f vars params main$-$order parameter$-$order {\sf \&aux} (k (length vars)) (vars$-$params (append vars params)) }
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.
\end{lisp:documentation}

\begin{lisp:documentation}{red$-$reduction}{FUNCTION}{p pred ring {\sf \&aux} (p (remove$-$if \#'poly$-$constant$-$p p)) }
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).
\end{lisp:documentation}

