source: CGBLisp/doc/colored-poly.txt@ 1

;;; *COLORED-POLY-DEBUG* (nil)                                       [VARIABLE]
;;;    If true debugging output is on.
;;;
;;; DEBUG-CGB (&rest args)                                              [MACRO]
;;;
;;; MAKE-COLORED-POLY (poly k &key (key #'identity)                  [FUNCTION]
;;;                    (main-order #'lex>) (parameter-order #'lex>)
;;;                    &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.
;;;
;;; MAKE-COLORED-POLY-LIST (plist &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 (flist &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 (f &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 (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 (poly vars &key (stream t) (beg t)            [FUNCTION]
;;;                     (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.
;;;
;;; COLORED-POLY-PRINT-LIST (poly-list vars &key (stream t) (beg t)  [FUNCTION]
;;;                          (print-green-part nil)
;;;                          (mark-coefficients nil))
;;;    Pring a list of colored polynomials via a call to
;;;    COLORED-POLY-PRINT.
;;;
;;; DETERMINE (f &optional (cond (list nil nil)) (order #'lex>)      [FUNCTION]
;;;            (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.
;;;
;;; DETERMINE-1 (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 (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 (system vars params &key (suppress-value t)    [FUNCTION]
;;;                    (print-green-part nil)
;;;                    (mark-coefficients nil) &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. 
;;;
;;; COND-PRINT (cond params)                                         [FUNCTION]
;;;    Pretty-print a condition COND, using symbol list PARAMS as parameter
;;;    names. 
;;;
;;; ADD-PAIRS (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 (p)                                                    [FUNCTION]
;;;    Find the part of a colored polynomial P starting with the first
;;;     non-green term.
;;;
;;; COND-HM (p)                                                      [FUNCTION]
;;;    Return the conditional head monomial of a colored polynomial P.
;;;
;;; DELETE-GREEN-POLYS (gamma)                                       [FUNCTION]
;;;    Delete totally green polynomials from in a grobner system GAMMA.
;;;
;;; GROBNER-SYSTEM (f &key (cover (list '(nil nil))) (main-order     [FUNCTION]
;;;                 #'lex>)
;;;                 (parameter-order #'lex>) (reduce t)
;;;                 (green-reduce t) (top-reduction-only nil)
;;;                 (ring *coefficient-ring*)
;;;                 &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.
;;;
;;; REORDER-PAIRS (b bnew g pred &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 (i j f)                                      [FUNCTION]
;;;    Buchberger criterion 1 for colored polynomials.
;;;
;;; COLORED-CRITERION-2 (i j f b s)                                  [FUNCTION]
;;;    Buchberger criterion 2 for colored polynomials.
;;;
;;; COND-NORMAL-FORM (f fl main-order parameter-order                [FUNCTION]
;;;                   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.
;;;
;;; COND-SPOLY (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 (f)                                                      [FUNCTION]
;;;    Returns the conditional leading monomial of a colored polynomial F,
;;;    which is assumed to be determined.
;;;
;;; COND-LC (f)                                                      [FUNCTION]
;;;    Returns the conditional leading coefficient of a colored polynomial
;;;    F, which is assumed to be determined.
;;;
;;; COLORED-TERM-TIMES-POLY (term f order ring)                      [FUNCTION]
;;;    Returns the product of a colored term TERM and a colored polynomial
;;;    F. 
;;;
;;; COLORED-SCALAR-TIMES-POLY (c f ring)                             [FUNCTION]
;;;    Returns the product of an element of the coefficient ring C a colored
;;;    polynomial F. 
;;;
;;; COLORED-TERM* (term1 term2 order ring)                           [FUNCTION]
;;;    Returns the product of two colored terms TERM1 and TERM2.
;;;
;;; COLOR* (c1 c2)                                                   [FUNCTION]
;;;    Returns a product of two colores. Rules:
;;;    :red * :red yields :red
;;;    any * :green yields :green
;;;    otherwise the result is :white.
;;;
;;; COLOR+ (c1 c2)                                                   [FUNCTION]
;;;    Returns a sum of colors. Rules:
;;;    :green + :green yields :green,
;;;    :red + :green yields :red
;;;    any other result is :white.
;;;
;;; COLOR- (c1 c2)                                                   [FUNCTION]
;;;    Identical to COLOR+.
;;;
;;; COLORED-POLY+ (p q main-order parameter-order ring)              [FUNCTION]
;;;    Returns the sum of colored polynomials P and Q.
;;;
;;; COLORED-POLY- (p q main-order parameter-order ring)              [FUNCTION]
;;;    Returns the difference of colored polynomials P and Q.
;;;
;;; COLORED-TERM-UMINUS (term ring)                                  [FUNCTION]
;;;    Returns the negation of a colored term TERM.
;;;
;;; COLORED-MINUS-POLY (p ring)                                      [FUNCTION]
;;;    Returns the negation of a colored polynomial P.
;;;
;;; STRING-GROBNER-SYSTEM (f vars params                             [FUNCTION]
;;;                        &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)
;;;                        &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 [] 
;;;
;;; STRING-COND (cond params &optional (order #'lex>))               [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 (cover params &optional (order #'lex>))             [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 (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 (cond order ring)                                  [FUNCTION]
;;;    Saturate a single condition COND. An auxillary function of
;;;    SATURATE-COVER. 
;;;
;;; STRING-DETERMINE (f vars params &key (cond (quote ("[]" "[]")))  [FUNCTION]
;;;                   (main-order #'lex>) (parameter-order #'lex>)
;;;                   (suppress-value t) (suppress-printing nil)
;;;                   (mark-coefficients nil)
;;;                   (ring *coefficient-ring*)
;;;                   &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. 
;;;
;;; TIDY-GROBNER-SYSTEM (gs main-order parameter-order reduce        [FUNCTION]
;;;                      green-reduce ring)
;;;    Apply TIDY-PAIR to every pair of a Grobner system.
;;;
;;; TIDY-PAIR (pair main-order parameter-order reduce green-reduce   [FUNCTION]
;;;            ring &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. 
;;;
;;; TIDY-COND (cond order ring)                                      [FUNCTION]
;;;    Currently saturates condition COND and does RED-REDUCTION on the red
;;;    list. 
;;;
;;; COLORED-REDUCTION (cond p main-order parameter-order ring        [FUNCTION]
;;;                    &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.
;;;
;;; GREEN-REDUCE-COLORED-POLY (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 (cond fl parameter-order ring)         [FUNCTION]
;;;    Apply GREEN-REDUCE-COLORED-POLY to a list of polynomials FL.
;;;
;;; COND-SYSTEM-GREEN-REDUCE (gs parameter-order ring)               [FUNCTION]
;;;    Apply GREEN-REDUCE-COLORED-LIST to every pair of
;;;    a grobner system GS.
;;;
;;; PARSE-TO-COLORED-POLY-LIST (f vars params main-order             [FUNCTION]
;;;                             parameter-order
;;;                             &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.
;;;
;;; RED-REDUCTION (p pred ring                                       [FUNCTION]
;;;                &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).
;;;