[1] | 1 | \begin{lisp:documentation}{*grobner$-$debug*}{VARIABLE}{nil }
|
---|
| 2 | If T, produce debugging and tracing output.
|
---|
| 3 | \end{lisp:documentation}
|
---|
| 4 |
|
---|
| 5 | \begin{lisp:documentation}{*buchberger$-$merge$-$pairs*}{VARIABLE}{'buchberger$-$merge$-$pairs$-$smallest$-$lcm }
|
---|
| 6 | A variable holding the predicate used to sort critical pairs
|
---|
| 7 | in the order of decreasing priority for the Buchberger algorithm.
|
---|
| 8 | \end{lisp:documentation}
|
---|
| 9 |
|
---|
| 10 | \begin{lisp:documentation}{*gebauer$-$moeller$-$merge$-$pairs*}{VARIABLE}{'gebauer$-$moeller$-$merge$-$pairs$-$use$-$mock$-$spoly }
|
---|
| 11 | A variable holding the predicate used to sort critical pairs
|
---|
| 12 | in the order of decreasing priority for the Gebauer$-$Moeller
|
---|
| 13 | algorithm
|
---|
| 14 | \end{lisp:documentation}
|
---|
| 15 |
|
---|
| 16 | \begin{lisp:documentation}{*grobner$-$function*}{VARIABLE}{'buchberger }
|
---|
| 17 | The name of the function used to calculate Grobner basis
|
---|
| 18 | \end{lisp:documentation}
|
---|
| 19 |
|
---|
| 20 | \begin{lisp:documentation}{select$-$grobner$-$algorithm}{FUNCTION}{algorithm }
|
---|
| 21 | Select one of the several implementations of the Grobner basis
|
---|
| 22 | algorithm.
|
---|
| 23 | \end{lisp:documentation}
|
---|
| 24 |
|
---|
| 25 | \begin{lisp:documentation}{grobner}{FUNCTION}{f {\sf \&optional} (pred \#'lex$>$) (start 0) (top$-$reduction$-$only nil) (ring *coefficient$-$ring*) }
|
---|
| 26 | Return Grobner basis of an ideal generated by polynomial list F.
|
---|
| 27 | Assume that the monomials of each polynomial are ordered according to
|
---|
| 28 | the admissible monomial order PRED. The result will be a list of
|
---|
| 29 | polynomials ordered as well according to PRED. The polynomials from 0
|
---|
| 30 | to START$-$1 in the list F are assumed to be a Grobner basis, and
|
---|
| 31 | thus certain critical pairs do not have to be calculated. If
|
---|
| 32 | TOP$-$REDUCTION$-$ONLY is not NIL then only top reductions will be
|
---|
| 33 | performed, instead of full division, and thus the returned Grobner
|
---|
| 34 | basis will have its polynomials only top$-$reduced with respect to
|
---|
| 35 | the preceding polynomials. RING should be set to the RING structure
|
---|
| 36 | (see COEFFICIENT$-$RING package) corresponding to the coefficients of
|
---|
| 37 | the polynomials in the list F. This function is currently just an
|
---|
| 38 | interface to several algorithms which fine Grobner bases. Use
|
---|
| 39 | SELECT$-$GROBNER$-$ALGORITHM in order to change the algorithm.
|
---|
| 40 | \end{lisp:documentation}
|
---|
| 41 |
|
---|
| 42 | \begin{lisp:documentation}{debug$-$cgb}{MACRO}{{\sf \&rest} args }
|
---|
| 43 | This macro is used in printing debugging and tracing messages
|
---|
| 44 | and its arguments are analogous to the FORMAT function, except
|
---|
| 45 | that the stream argument is omitted. By default, the output is
|
---|
| 46 | sent to *trace$-$output*, which can be set to produce output
|
---|
| 47 | in a file.
|
---|
| 48 | \end{lisp:documentation}
|
---|
| 49 |
|
---|
| 50 | \begin{lisp:documentation}{spoly}{FUNCTION}{f g pred ring }
|
---|
| 51 | Return the S$-$polynomial of F and G, which should
|
---|
| 52 | be two polynomials with terms ordered by PRED and
|
---|
| 53 | coefficients in a ring whose operations are the slots
|
---|
| 54 | of the RING structure.
|
---|
| 55 | \end{lisp:documentation}
|
---|
| 56 |
|
---|
| 57 | \begin{lisp:documentation}{grobner$-$primitive$-$part}{FUNCTION}{p ring }
|
---|
| 58 | Divide polynomial P with integer coefficients by gcd of its
|
---|
| 59 | coefficients and return the result. Use the RING structure from the
|
---|
| 60 | COEFFICIENT$-$RING package to perform the operations on the
|
---|
| 61 | coefficients.
|
---|
| 62 | \end{lisp:documentation}
|
---|
| 63 |
|
---|
| 64 | \begin{lisp:documentation}{grobner$-$content}{FUNCTION}{p ring }
|
---|
| 65 | Greatest common divisor of the coefficients of the polynomial P. Use
|
---|
| 66 | the RING structure to compute the greatest common divisor.
|
---|
| 67 | \end{lisp:documentation}
|
---|
| 68 |
|
---|
| 69 | \begin{lisp:documentation}{normal$-$form}{FUNCTION}{f fl pred top$-$reduction$-$only ring }
|
---|
| 70 | Calculate the normal form of the polynomial F with respect to
|
---|
| 71 | the polynomial list FL. Destructive to F; thus, copy$-$tree should be
|
---|
| 72 | used where F needs to be preserved. It returns multiple values.
|
---|
| 73 | The first value is the polynomial R which is reduced (or
|
---|
| 74 | top$-$reduced if TOP$-$REDUCTION$-$ONLY is not NIL). The second value
|
---|
| 75 | is an integer which is the number of reductions actually performed.
|
---|
| 76 | The third value is the coefficient by which F needs to be multiplied
|
---|
| 77 | in order to be able to perform the division without actually having
|
---|
| 78 | to divide in the coefficient ring (a form of pseudo$-$division is
|
---|
| 79 | used). All operations on the coefficients are performed using the
|
---|
| 80 | RING structure from the COEFFICIENT$-$RING package.
|
---|
| 81 | \end{lisp:documentation}
|
---|
| 82 |
|
---|
| 83 | \begin{lisp:documentation}{buchberger}{FUNCTION}{f pred start top$-$reduction$-$only ring {\sf \&aux} (s (1$-$ (length f))) b m }
|
---|
| 84 | An implementation of the Buchberger algorithm. Return Grobner
|
---|
| 85 | basis of the ideal generated by the polynomial list F.
|
---|
| 86 | The terms of each polynomial are ordered by the admissible
|
---|
| 87 | monomial order PRED. Polynomials 0 to START$-$1 are assumed to
|
---|
| 88 | be a Grobner basis already, so that certain critical pairs
|
---|
| 89 | will not be examined. If TOP$-$REDUCTION$-$ONLY set, top reduction
|
---|
| 90 | will be preformed. The RING structure is used to perform operations
|
---|
| 91 | on coefficents (see COEFFICIENT$-$RING package).
|
---|
| 92 | \end{lisp:documentation}
|
---|
| 93 |
|
---|
| 94 | \begin{lisp:documentation}{grobner$-$op}{FUNCTION}{c1 c2 m a b pred ring {\sf \&aux} n a1 a2 }
|
---|
| 95 | Perform a calculation equivalent to
|
---|
| 96 | (POLY$-$ (SCALAR$-$TIMES$-$POLY C2 A)
|
---|
| 97 | (SCALAR$-$TIMES$-$POLY C1 (MONOM$-$TIMES$-$POLY M B))
|
---|
| 98 | PRED)
|
---|
| 99 | but more efficiently; it destructively modifies A and stores the
|
---|
| 100 | result in it; A is returned.
|
---|
| 101 | \end{lisp:documentation}
|
---|
| 102 |
|
---|
| 103 | \begin{lisp:documentation}{buchberger$-$sort$-$pairs}{FUNCTION}{b g pred ring }
|
---|
| 104 | Sort critical pairs B by the function which is
|
---|
| 105 | the value of the vairable *buchberger$-$merge$-$pairs*.
|
---|
| 106 | G is the list of polynomials which the elemnts
|
---|
| 107 | of B point into. PRED is the admissible monomial order.
|
---|
| 108 | The RING structure holds operations on the coefficients
|
---|
| 109 | as described in the COEFFICIENT$-$RING package.
|
---|
| 110 | \end{lisp:documentation}
|
---|
| 111 |
|
---|
| 112 | \begin{lisp:documentation}{mock$-$spoly}{FUNCTION}{f g pred }
|
---|
| 113 | Returns an upper$-$bound on the leading
|
---|
| 114 | monomial of the S$-$polynomial of F and G, which are two polynomials
|
---|
| 115 | sorted by the admissible monomial order PRED.
|
---|
| 116 | \end{lisp:documentation}
|
---|
| 117 |
|
---|
| 118 | \begin{lisp:documentation}{buchberger$-$merge$-$pairs$-$use$-$mock$-$spoly}{FUNCTION}{b c g pred ring }
|
---|
| 119 | Merges lists of critical pairs B and C into one list.
|
---|
| 120 | The pairs are assumed to be ordered according to the
|
---|
| 121 | increasing value of MOCK$-$SPOLY, as determined by the admissible
|
---|
| 122 | monomial order PRED. G is the list of polynomials which the pairs
|
---|
| 123 | of integers in B and C point into, and RING is the ring structure
|
---|
| 124 | defined in the COEFFICIENT$-$RING package.
|
---|
| 125 | \end{lisp:documentation}
|
---|
| 126 |
|
---|
| 127 | \begin{lisp:documentation}{buchberger$-$merge$-$pairs$-$smallest$-$lcm}{FUNCTION}{b c g pred ring }
|
---|
| 128 | Merges lists of critical pairs B and C into a single ordered
|
---|
| 129 | list. Implements a strategy of ordering pairs according to the
|
---|
| 130 | smallest lcm of the leading monomials of the two polynomials $-$ so
|
---|
| 131 | called normal strategy.
|
---|
| 132 | \end{lisp:documentation}
|
---|
| 133 |
|
---|
| 134 | \begin{lisp:documentation}{buchberger$-$merge$-$pairs$-$use$-$smallest$-$degree}{FUNCTION}{b c g pred ring }
|
---|
| 135 | Mergest lists B and C of critical pairs. This strategy is based on
|
---|
| 136 | ordering the pairs according to the smallest degree of the lcm of
|
---|
| 137 | the leading monomials of the two polynomials.
|
---|
| 138 | \end{lisp:documentation}
|
---|
| 139 |
|
---|
| 140 | \begin{lisp:documentation}{buchberger$-$merge$-$pairs$-$use$-$smallest$-$length}{FUNCTION}{b c g pred ring }
|
---|
| 141 | Mergest lists B and C of critical pairs. This strategy is based on
|
---|
| 142 | ordering the pairs according to the smallest total length of the
|
---|
| 143 | two polynomials, where length is the number of terms.
|
---|
| 144 | \end{lisp:documentation}
|
---|
| 145 |
|
---|
| 146 | \begin{lisp:documentation}{buchberger$-$merge$-$pairs$-$use$-$smallest$-$coefficient$-$length}{FUNCTION}{b c g pred ring }
|
---|
| 147 | Mergest lists B and C of critical pairs. This strategy is based on
|
---|
| 148 | ordering the pairs according to the smallest combined length of the
|
---|
| 149 | coefficients of the two polynomials.
|
---|
| 150 | \end{lisp:documentation}
|
---|
| 151 |
|
---|
| 152 | \begin{lisp:documentation}{buchberger$-$set$-$pair$-$heuristic}{FUNCTION}{method {\sf \&aux} (strategy$-$fn
|
---|
| 153 | (ecase method (:minimal$-$mock$-$spoly \#'buchberger$-$merge$-$pairs$-$use$-$mock$-$spoly)
|
---|
| 154 | (:minimal$-$lcm \#'buchberger$-$merge$-$pairs$-$smallest$-$lcm)
|
---|
| 155 | (:minimal$-$total$-$degree \#'buchberger$-$merge$-$pairs$-$use$-$smallest$-$degree)
|
---|
| 156 | (:minimal$-$length \#'buchberger$-$merge$-$pairs$-$use$-$smallest$-$length)
|
---|
| 157 | (:minimal$-$coefficient$-$length \#'buchberger$-$merge$-$pairs$-$use$-$smallest$-$coefficient$-$length))) }
|
---|
| 158 | Simply sets the variable *buchberger$-$merge$-$pairs* to the
|
---|
| 159 | heuristic function STRATEGY$-$FN implementing one of several
|
---|
| 160 | strategies introduces before of selecting the most promising. METHOD
|
---|
| 161 | should be one of the listed keywords.
|
---|
| 162 | \end{lisp:documentation}
|
---|
| 163 |
|
---|
| 164 | \begin{lisp:documentation}{criterion$-$1}{FUNCTION}{pair g {\sf \&aux} (i (first pair)) (j (second pair)) }
|
---|
| 165 | Returns T if the leading monomials of the two polynomials
|
---|
| 166 | in G pointed to by the integers in PAIR have disjoint (relatively
|
---|
| 167 | prime) monomials. This test is known as the first Buchberger
|
---|
| 168 | criterion.
|
---|
| 169 | \end{lisp:documentation}
|
---|
| 170 |
|
---|
| 171 | \begin{lisp:documentation}{criterion$-$2}{FUNCTION}{pair g m {\sf \&aux} (i (first pair)) (j (second pair)) }
|
---|
| 172 | Returns T if the leading monomial of some element P of G divides
|
---|
| 173 | the LCM of the leading monomials of the two polynomials in the
|
---|
| 174 | polynomial list G, pointed to by the two integers in PAIR, and P
|
---|
| 175 | paired with each of the polynomials pointed to by the the PAIR has
|
---|
| 176 | already been treated, as indicated by the hash table M, which stores
|
---|
| 177 | value T for every treated pair so far.
|
---|
| 178 | \end{lisp:documentation}
|
---|
| 179 |
|
---|
| 180 | \begin{lisp:documentation}{normalize$-$poly}{FUNCTION}{p ring }
|
---|
| 181 | Divide a polynomial by its leading coefficient. It assumes
|
---|
| 182 | that the division is possible, which may not always be the
|
---|
| 183 | case in rings which are not fields. The exact division operator
|
---|
| 184 | is assumed to be provided by the RING structure of the
|
---|
| 185 | COEFFICIENT$-$RING package.
|
---|
| 186 | \end{lisp:documentation}
|
---|
| 187 |
|
---|
| 188 | \begin{lisp:documentation}{normalize$-$basis}{FUNCTION}{plist ring }
|
---|
| 189 | Divide every polynomial in a list PLIST by its leading coefficient.
|
---|
| 190 | Use RING structure to perform the division of the coefficients.
|
---|
| 191 | \end{lisp:documentation}
|
---|
| 192 |
|
---|
| 193 | \begin{lisp:documentation}{reduction}{FUNCTION}{p pred ring }
|
---|
| 194 | Reduce a list of polynomials P, so that non of the terms in any of
|
---|
| 195 | the polynomials is divisible by a leading monomial of another
|
---|
| 196 | polynomial. Return the reduced list.
|
---|
| 197 | \end{lisp:documentation}
|
---|
| 198 |
|
---|
| 199 | \begin{lisp:documentation}{reduced$-$grobner}{FUNCTION}{f {\sf \&optional} (pred \#'lex$>$) (start 0) (top$-$reduction$-$only nil) (ring *coefficient$-$ring*) }
|
---|
| 200 | Return the reduced Grobner basis of the ideal generated by a
|
---|
| 201 | polynomial list F. This combines calls to two functions: GROBNER and
|
---|
| 202 | REDUCTION. The parameters have the same meaning as in GROBNER or
|
---|
| 203 | BUCHBERGER.
|
---|
| 204 | \end{lisp:documentation}
|
---|
| 205 |
|
---|
| 206 | \begin{lisp:documentation}{monom$-$depends$-$p}{FUNCTION}{m k }
|
---|
| 207 | Return T if the monomial M depends on variable number K.
|
---|
| 208 | \end{lisp:documentation}
|
---|
| 209 |
|
---|
| 210 | \begin{lisp:documentation}{term$-$depends$-$p}{FUNCTION}{term k }
|
---|
| 211 | Return T if the term TERM depends on variable number K.
|
---|
| 212 | \end{lisp:documentation}
|
---|
| 213 |
|
---|
| 214 | \begin{lisp:documentation}{poly$-$depends$-$p}{FUNCTION}{p k }
|
---|
| 215 | Return T if the term polynomial P depends on variable number K.
|
---|
| 216 | \end{lisp:documentation}
|
---|
| 217 |
|
---|
| 218 | \begin{lisp:documentation}{ring$-$intersection}{FUNCTION}{plist k {\sf \&key} (key \#'identity) }
|
---|
| 219 | This function assumes that polynomial list PLIST is a Grobner basis
|
---|
| 220 | and it calculates the intersection with the ring R[x[k+1],...,x[n]],
|
---|
| 221 | i.e. it discards polynomials which depend on variables x[0], x[1],
|
---|
| 222 | ..., x[k].
|
---|
| 223 | \end{lisp:documentation}
|
---|
| 224 |
|
---|
| 225 | \begin{lisp:documentation}{elimination$-$ideal}{FUNCTION}{flist k {\sf \&key} (primary$-$order \#'lex$>$) (secondary$-$order \#'lex$>$) (start 0) (order
|
---|
| 226 | (elimination$-$order k :primary$-$order primary$-$order
|
---|
| 227 | :secondary$-$order secondary$-$order)) (top$-$reduction$-$only
|
---|
| 228 | nil) (ring
|
---|
| 229 | *coefficient$-$ring*) }
|
---|
| 230 | Returns the K$-$th elimination ideal of the ideal generated by
|
---|
| 231 | polynomial list FLIST. Thus, a Grobner basis of the ideal generated
|
---|
| 232 | by FLIST is calculated and polynomials depending on variables 0$-$K
|
---|
| 233 | are discarded. The monomial order in the calculation is an
|
---|
| 234 | elimination order formed by combining two orders: PRIMARY$-$ORDER
|
---|
| 235 | used on variables 0$-$K and SECONDARY$-$ORDER used on variables
|
---|
| 236 | starting from variable K+1. Thus, if both orders are set to the
|
---|
| 237 | lexicographic order \#'LEX$>$ then the resulting order is simply
|
---|
| 238 | equivalent to \#'LEX$>$. But one could use arbitrary two orders in
|
---|
| 239 | this function, for instance, two copies of \#'GREVLEX$>$ (see ORDER
|
---|
| 240 | package). When doing so, the caller must ensure that the same order
|
---|
| 241 | has been used to sort the terms of the polynomials FLIST.
|
---|
| 242 | \end{lisp:documentation}
|
---|
| 243 |
|
---|
| 244 | \begin{lisp:documentation}{ideal$-$intersection}{FUNCTION}{f g pred top$-$reduction$-$only ring }
|
---|
| 245 | Return the Grobner basis of the intersection of the ideals
|
---|
| 246 | generated by the polynomial lists F and G. PRED is an admissible
|
---|
| 247 | monomial order with respect to which the terms of F and G have been
|
---|
| 248 | sorted. This order is going to be used in the Grobner basis
|
---|
| 249 | calculation. If TOP$-$REDUCTION$-$ONLY is not NIL, internally the
|
---|
| 250 | Grobner basis algorithm will perform top reduction only. The RING
|
---|
| 251 | parameter, as usual, should be set to a structure defined in the
|
---|
| 252 | package COEFFICIENT$-$RING, and it will be used to perform all
|
---|
| 253 | operations on coefficients.
|
---|
| 254 | \end{lisp:documentation}
|
---|
| 255 |
|
---|
| 256 | \begin{lisp:documentation}{poly$-$contract}{FUNCTION}{f {\sf \&optional} (k 1) }
|
---|
| 257 | Return a polynomial obtained from polynomial F by dropping the
|
---|
| 258 | first K variables, if F does not depend on them. Note that this
|
---|
| 259 | operation makes the polynomial incompatible for certain arithmetical
|
---|
| 260 | operations with the original polynomial F. Calling this function on a
|
---|
| 261 | polynomial F which does depend on variables 0$-$K will result in
|
---|
| 262 | error.
|
---|
| 263 | \end{lisp:documentation}
|
---|
| 264 |
|
---|
| 265 | \begin{lisp:documentation}{poly$-$lcm}{FUNCTION}{f g {\sf \&optional} (pred \#'lex$>$) (ring *coefficient$-$ring*) }
|
---|
| 266 | Return LCM (least common multiple) of two polynomials F and G.
|
---|
| 267 | The polynomials must be ordered according to monomial order PRED
|
---|
| 268 | and their coefficients must be compatible with the RING structure
|
---|
| 269 | defined in the COEFFICIENT$-$RING package.
|
---|
| 270 | \end{lisp:documentation}
|
---|
| 271 |
|
---|
| 272 | \begin{lisp:documentation}{grobner$-$gcd}{FUNCTION}{f g {\sf \&optional} (pred \#'lex$>$) (ring *coefficient$-$ring*) }
|
---|
| 273 | Return GCD (greatest common divisor) of two polynomials F and G.
|
---|
| 274 | The polynomials must be ordered according to monomial order PRED
|
---|
| 275 | and their coefficients must be compatible with the RING structure
|
---|
| 276 | defined in the COEFFICIENT$-$RING package.
|
---|
| 277 | \end{lisp:documentation}
|
---|
| 278 |
|
---|
| 279 | \begin{lisp:documentation}{grobner$-$equal}{FUNCTION}{g1 g2 {\sf \&optional} (pred \#'lex$>$) (ring *coefficient$-$ring*) }
|
---|
| 280 | Returns T if two lists of polynomials G1 and G2, assumed to be
|
---|
| 281 | Grobner bases, generate the same ideal, and NIL otherwise.
|
---|
| 282 | \end{lisp:documentation}
|
---|
| 283 |
|
---|
| 284 | \begin{lisp:documentation}{grobner$-$subsetp}{FUNCTION}{g1 g2 {\sf \&optional} (pred \#'lex$>$) (ring *coefficient$-$ring*) }
|
---|
| 285 | Returns T if a list of polynomials G1 generates
|
---|
| 286 | an ideal contained in the ideal generated by a polynomial list G2,
|
---|
| 287 | both G1 and G2 assumed to be Grobner bases. Returns NIL otherwise.
|
---|
| 288 | \end{lisp:documentation}
|
---|
| 289 |
|
---|
| 290 | \begin{lisp:documentation}{grobner$-$member}{FUNCTION}{p g {\sf \&optional} (pred \#'lex$>$) (ring *coefficient$-$ring*) }
|
---|
| 291 | Returns T if a polynomial P belongs to the ideal generated by the
|
---|
| 292 | polynomial list G, which is assumed to be a Grobner basis. Returns
|
---|
| 293 | NIL otherwise.
|
---|
| 294 | \end{lisp:documentation}
|
---|
| 295 |
|
---|
| 296 | \begin{lisp:documentation}{ideal$-$equal}{FUNCTION}{f1 f2 pred top$-$reduction$-$only ring }
|
---|
| 297 | Returns T if two ideals generated by polynomial lists F1 and F2 are
|
---|
| 298 | identical. Returns NIL otherwise.
|
---|
| 299 | \end{lisp:documentation}
|
---|
| 300 |
|
---|
| 301 | \begin{lisp:documentation}{ideal$-$subsetp}{FUNCTION}{f1 f2 {\sf \&optional} (pred \#'lex$>$) (ring *coefficient$-$ring*) }
|
---|
| 302 | Returns T if the ideal spanned by the polynomial list F1 is contained
|
---|
| 303 | in the ideal spanned by the polynomial list F2. Returns NIL
|
---|
| 304 | otherwise.
|
---|
| 305 | \end{lisp:documentation}
|
---|
| 306 |
|
---|
| 307 | \begin{lisp:documentation}{ideal$-$member}{FUNCTION}{p plist pred top$-$reduction$-$only ring }
|
---|
| 308 | Returns T if the polynomial P belongs to the ideal spanned by the
|
---|
| 309 | polynomial list PLIST, and NIL otherwise.
|
---|
| 310 | \end{lisp:documentation}
|
---|
| 311 |
|
---|
| 312 | \begin{lisp:documentation}{ideal$-$saturation$-$1}{FUNCTION}{f p pred start top$-$reduction$-$only ring {\sf \&aux} (pred (elimination$-$order$-$1 pred)) }
|
---|
| 313 | Returns the reduced Grobner basis of the saturation of the ideal
|
---|
| 314 | generated by a polynomial list F in the ideal generated by a single
|
---|
| 315 | polynomial P. The saturation ideal is defined as the set of
|
---|
| 316 | polynomials H such for some natural number n (* (EXPT P N) H) is in
|
---|
| 317 | the ideal F. Geometrically, over an algebraically closed field, this
|
---|
| 318 | is the set of polynomials in the ideal generated by F which do not
|
---|
| 319 | identically vanish on the variety of P.
|
---|
| 320 | \end{lisp:documentation}
|
---|
| 321 |
|
---|
| 322 | \begin{lisp:documentation}{add$-$variables}{FUNCTION}{plist n }
|
---|
| 323 | Add N new variables, adn the first N variables, to every polynomial
|
---|
| 324 | in polynomial list PLIST. The resulting polynomial will not depend on
|
---|
| 325 | these N variables.
|
---|
| 326 | \end{lisp:documentation}
|
---|
| 327 |
|
---|
| 328 | \begin{lisp:documentation}{extend$-$polynomials}{FUNCTION}{plist {\sf \&aux} (k (length plist)) }
|
---|
| 329 | Returns polynomial list \{U1*P1', U2*P2', ... , UK*PK'\}
|
---|
| 330 | where Ui are new variables and PLIST=\{P1, P2, ... , PK\} is a
|
---|
| 331 | polynomial list. PI' is obtained from PI by adding new variables U1,
|
---|
| 332 | U2, ..., UN UK as the first K variables. Thus, the resulting list is
|
---|
| 333 | consists of polynomials whose terms are ordered by the lexicographic
|
---|
| 334 | order on variables UI, with ties resolved by the monomial order which
|
---|
| 335 | was used to order the terms of the polynomials in PLIST. We note that
|
---|
| 336 | the monomial order does not explicitly participate in this
|
---|
| 337 | calculation, and neither do the variable names.
|
---|
| 338 | \end{lisp:documentation}
|
---|
| 339 |
|
---|
| 340 | \begin{lisp:documentation}{saturation$-$extension}{FUNCTION}{f plist ring {\sf \&aux} (k (length plist)) (d (+ k (length (caaar plist)))) }
|
---|
| 341 | Returns F' union \{U1*P1$-$1,U2*P2$-$1,...,UK*PK$-$1\} where Ui are
|
---|
| 342 | new variables and F' is a polynomial list obtained from F by adding
|
---|
| 343 | variables U1, U2, ..., Uk as the first K variables to each polynomial
|
---|
| 344 | in F. Thus, the resulting list is consists of polynomials whose terms
|
---|
| 345 | are ordered by the lexicographic order on variables Ui, with ties
|
---|
| 346 | resolved by the monomial order which was used to order the terms of
|
---|
| 347 | the polynomials in F. We note that the monomial order does not
|
---|
| 348 | explicitly participate in this calculation, and neither do the
|
---|
| 349 | variable names.
|
---|
| 350 | \end{lisp:documentation}
|
---|
| 351 |
|
---|
| 352 | \begin{lisp:documentation}{polysaturation$-$extension}{FUNCTION}{f plist ring {\sf \&aux} (k (length plist)) (d (+ k (length (caaar plist)))) }
|
---|
| 353 | Returns F' union \{U1*P1+U2*P2+UK*PK$-$1\} where Ui are new variables
|
---|
| 354 | and F' is a polynomial list obtained from F by adding variables U1,
|
---|
| 355 | U2, ..., Uk as the first K variables to each polynomial in F. Thus,
|
---|
| 356 | the resulting list is consists of polynomials whose terms are ordered
|
---|
| 357 | by the lexicographic order on variables Ui, with ties resolved by the
|
---|
| 358 | monomial order which was used to order the terms of the polynomials
|
---|
| 359 | in F. We note that the monomial order does not explicitly participate
|
---|
| 360 | in this calculation, and neither do the variable names.
|
---|
| 361 | \end{lisp:documentation}
|
---|
| 362 |
|
---|
| 363 | \begin{lisp:documentation}{saturation$-$extension$-$1}{FUNCTION}{f p ring }
|
---|
| 364 | Return the list F' union \{U*P$-$1\} where U is a new variable,
|
---|
| 365 | where F' is obtained from the polynomial list F by adding U as the
|
---|
| 366 | first variable. The variable U will be added as the first variable,
|
---|
| 367 | so that it can be easily eliminated.
|
---|
| 368 | \end{lisp:documentation}
|
---|
| 369 |
|
---|
| 370 | \begin{lisp:documentation}{ideal$-$polysaturation$-$1}{FUNCTION}{f plist pred start top$-$reduction$-$only ring }
|
---|
| 371 | Returns the reduced Grobner basis of the ideal obtained by a
|
---|
| 372 | sequence of successive saturations in the polynomials
|
---|
| 373 | of the polynomial list PLIST of the ideal generated by the
|
---|
| 374 | polynomial list F.
|
---|
| 375 | \end{lisp:documentation}
|
---|
| 376 |
|
---|
| 377 | \begin{lisp:documentation}{ideal$-$saturation}{FUNCTION}{f g pred start top$-$reduction$-$only ring {\sf \&aux} (k (length g)) (pred (elimination$-$order k :primary$-$order \#'lex$>$ :secondary$-$order pred)) }
|
---|
| 378 | Returns the reduced Grobner basis of the saturation of the ideal
|
---|
| 379 | generated by a polynomial list F in the ideal generated a polynomial
|
---|
| 380 | list G The saturation ideal is defined as the set of polynomials H
|
---|
| 381 | such for some natural number n and some P in the ideal generated by G
|
---|
| 382 | the polynomial P**N * H is in the ideal spanned by F. Geometrically,
|
---|
| 383 | over an algebraically closed field, this is the set of polynomials in
|
---|
| 384 | the ideal generated by F which do not identically vanish on the
|
---|
| 385 | variety of G.
|
---|
| 386 | \end{lisp:documentation}
|
---|
| 387 |
|
---|
| 388 | \begin{lisp:documentation}{ideal$-$polysaturation}{FUNCTION}{f ideal$-$list pred start top$-$reduction$-$only ring }
|
---|
| 389 | Returns the reduced Grobner basis of the ideal obtained by a
|
---|
| 390 | successive applications of IDEAL$-$SATURATIONS to F and
|
---|
| 391 | lists of polynomials in the list IDEAL$-$LIST.
|
---|
| 392 | \end{lisp:documentation}
|
---|
| 393 |
|
---|
| 394 | \begin{lisp:documentation}{buchberger$-$criterion}{FUNCTION}{g pred ring }
|
---|
| 395 | Returns T if G is a Grobner basis, by using the Buchberger
|
---|
| 396 | criterion: for every two polynomials h1 and h2 in G the
|
---|
| 397 | S$-$polynomial S(h1,h2) reduces to 0 modulo G.
|
---|
| 398 | \end{lisp:documentation}
|
---|
| 399 |
|
---|
| 400 | \begin{lisp:documentation}{grobner$-$test}{FUNCTION}{g f pred ring }
|
---|
| 401 | Test whether G is a Grobner basis and F is contained in G. Return T
|
---|
| 402 | upon success and NIL otherwise.
|
---|
| 403 | \end{lisp:documentation}
|
---|
| 404 |
|
---|
| 405 | \begin{lisp:documentation}{minimization}{FUNCTION}{p pred }
|
---|
| 406 | Returns a sublist of the polynomial list P spanning the same
|
---|
| 407 | monomial ideal as P but minimal, i.e. no leading monomial
|
---|
| 408 | of a polynomial in the sublist divides the leading monomial
|
---|
| 409 | of another polynomial.
|
---|
| 410 | \end{lisp:documentation}
|
---|
| 411 |
|
---|
| 412 | \begin{lisp:documentation}{add$-$minimized}{FUNCTION}{f gred pred }
|
---|
| 413 | Adds a polynomial f to GRED, reduced Grobner basis, preserving the
|
---|
| 414 | property described in the documentation for MINIMIZATION.
|
---|
| 415 | \end{lisp:documentation}
|
---|
| 416 |
|
---|
| 417 | \begin{lisp:documentation}{colon$-$ideal}{FUNCTION}{f g pred top$-$reduction$-$only ring }
|
---|
| 418 | Returns the reduced Grobner basis of the colon ideal Id(F):Id(G),
|
---|
| 419 | where F and G are two lists of polynomials. The colon ideal I:J is
|
---|
| 420 | defined as the set of polynomials H such that there is a polynomial W
|
---|
| 421 | in J for which W*H belongs to I.
|
---|
| 422 | \end{lisp:documentation}
|
---|
| 423 |
|
---|
| 424 | \begin{lisp:documentation}{colon$-$ideal$-$1}{FUNCTION}{f g pred top$-$reduction$-$only ring }
|
---|
| 425 | Returns the reduced Grobner basis of the colon ideal Id(F):Id(\{G\}),
|
---|
| 426 | where F is a list of polynomials and G is a polynomial.
|
---|
| 427 | \end{lisp:documentation}
|
---|
| 428 |
|
---|
| 429 | \begin{lisp:documentation}{pseudo$-$divide}{FUNCTION}{f fl pred ring }
|
---|
| 430 | Pseudo$-$divide a polynomial F by the list of polynomials FL. Return
|
---|
| 431 | multiple values. The first value is a list of quotients A.
|
---|
| 432 | The second value is the remainder R. The third value is an integer
|
---|
| 433 | count of the number of reductions performed. Finally, the fourth
|
---|
| 434 | argument is a scalar coefficient C, such that C*F can be divided by
|
---|
| 435 | FL within the ring of coefficients, which is not necessarily a field.
|
---|
| 436 | The resulting objects satisfy the equation:
|
---|
| 437 | C*F= sum A[i]*FL[i] + R
|
---|
| 438 | \end{lisp:documentation}
|
---|
| 439 |
|
---|
| 440 | \begin{lisp:documentation}{gebauer$-$moeller}{FUNCTION}{f pred start top$-$reduction$-$only ring {\sf \&aux} b g f1 }
|
---|
| 441 | Compute Grobner basis by using the algorithm of Gebauer and Moeller.
|
---|
| 442 | This algorithm is described as BUCHBERGERNEW2 in the book by
|
---|
| 443 | Becker$-$Weispfenning entitled ``Grobner Bases''
|
---|
| 444 | \end{lisp:documentation}
|
---|
| 445 |
|
---|
| 446 | \begin{lisp:documentation}{update}{FUNCTION}{g b h pred ring {\sf \&aux} c d e b$-$new g$-$new pair }
|
---|
| 447 | An implementation of the auxillary UPDATE algorithm used by the
|
---|
| 448 | Gebauer$-$Moeller algorithm. G is a list of polynomials, B is a list
|
---|
| 449 | of critical pairs and H is a new polynomial which possibly will be
|
---|
| 450 | added to G. The naming conventions used are very close to the one
|
---|
| 451 | used in the book of Becker$-$Weispfenning.
|
---|
| 452 | \end{lisp:documentation}
|
---|
| 453 |
|
---|
| 454 | \begin{lisp:documentation}{gebauer$-$moeller$-$merge$-$pairs$-$use$-$mock$-$spoly}{FUNCTION}{b c pred ring }
|
---|
| 455 | The merging strategy used by the Gebauer$-$Moeller algorithm, based
|
---|
| 456 | on MOCK$-$SPOLY; see the documentation of
|
---|
| 457 | BUCHBERGER$-$MERGE$-$PAIRS$-$USE$-$MOCK$-$SPOLY.
|
---|
| 458 | \end{lisp:documentation}
|
---|
| 459 |
|
---|
| 460 | \begin{lisp:documentation}{gebauer$-$moeller$-$merge$-$pairs$-$smallest$-$lcm}{FUNCTION}{b c pred ring }
|
---|
| 461 | The merging strategy based on the smallest$-$lcm (normal strategy);
|
---|
| 462 | see the documentation of BUCHBERGER$-$MERGE$-$PAIRS$-$SMALLEST$-$LCM.
|
---|
| 463 | \end{lisp:documentation}
|
---|
| 464 |
|
---|
| 465 | \begin{lisp:documentation}{gebauer$-$moeller$-$merge$-$pairs$-$use$-$smallest$-$degree}{FUNCTION}{b c pred ring }
|
---|
| 466 | The merging strategy based on the smallest$-$lcm (normal strategy);
|
---|
| 467 | see the documentation of
|
---|
| 468 | BUCHBERGER$-$MERGE$-$PAIRS$-$USE$-$SMALLEST$-$DEGREE.
|
---|
| 469 | \end{lisp:documentation}
|
---|
| 470 |
|
---|
| 471 | \begin{lisp:documentation}{gebauer$-$moeller$-$merge$-$pairs$-$use$-$smallest$-$length}{FUNCTION}{b c pred ring }
|
---|
| 472 | {\ } % NO DOCUMENTATION FOR GEBAUER-MOELLER-MERGE-PAIRS-USE-SMALLEST-LENGTH
|
---|
| 473 | \end{lisp:documentation}
|
---|
| 474 |
|
---|
| 475 | \begin{lisp:documentation}{gebauer$-$moeller$-$merge$-$pairs$-$use$-$smallest$-$coefficient$-$length}{FUNCTION}{b c pred ring }
|
---|
| 476 | The merging strategy based on the smallest$-$lcm (normal strategy);
|
---|
| 477 | see the documentation of
|
---|
| 478 | BUCHBERGER$-$MERGE$-$PAIRS$-$USE$-$SMALLEST$-$COEFFICIENT$-$LENGTH.
|
---|
| 479 | \end{lisp:documentation}
|
---|
| 480 |
|
---|
| 481 | \begin{lisp:documentation}{gebauer$-$moeller$-$set$-$pair$-$heuristic}{FUNCTION}{method {\sf \&aux} (strategy$-$fn
|
---|
| 482 | (ecase method (:minimal$-$mock$-$spoly \#'gebauer$-$moeller$-$merge$-$pairs$-$use$-$mock$-$spoly)
|
---|
| 483 | (:minimal$-$lcm \#'gebauer$-$moeller$-$merge$-$pairs$-$smallest$-$lcm)
|
---|
| 484 | (:minimal$-$total$-$degree \#'gebauer$-$moeller$-$merge$-$pairs$-$use$-$smallest$-$degree)
|
---|
| 485 | (:minimal$-$length \#'gebauer$-$moeller$-$merge$-$pairs$-$use$-$smallest$-$length)
|
---|
| 486 | (:minimal$-$coefficient$-$length
|
---|
| 487 | \#'gebauer$-$moeller$-$merge$-$pairs$-$use$-$smallest$-$coefficient$-$length))) }
|
---|
| 488 | {\ } % NO DOCUMENTATION FOR GEBAUER-MOELLER-SET-PAIR-HEURISTIC
|
---|
| 489 | \end{lisp:documentation}
|
---|
| 490 |
|
---|
| 491 | \begin{lisp:documentation}{spoly$-$sugar}{FUNCTION}{f$-$with$-$sugar g$-$with$-$sugar ring }
|
---|
| 492 | Calculate the ``sugar'' of the S$-$polynomial of two polynomials with
|
---|
| 493 | sugar. A polynomial with sugar is simply a pair (P . SUGAR) where
|
---|
| 494 | SUGAR is an integer constant defined according to the following
|
---|
| 495 | algorighm: the sugar of sum or difference of two polynomials with
|
---|
| 496 | sugar is the MAX of the sugars of those two polynomials. The sugar of
|
---|
| 497 | a product of a term and a polynomial is the sum of the degree of the
|
---|
| 498 | term and the sugar of the polynomial. The idea is to accumulate
|
---|
| 499 | sugar as we perform the arithmetic operations, and that polynomials
|
---|
| 500 | with small (little) sugar should be given priority in the
|
---|
| 501 | calculations. Thus, the ``sugar strategy'' of the critical pair
|
---|
| 502 | selection is to select a pair with the smallest value of sugar of the
|
---|
| 503 | resulting S$-$polynomial.
|
---|
| 504 | \end{lisp:documentation}
|
---|
| 505 |
|
---|
| 506 | \begin{lisp:documentation}{spoly$-$with$-$sugar}{FUNCTION}{f$-$with$-$sugar g$-$with$-$sugar pred ring }
|
---|
| 507 | The S$-$polynomials of two polynomials with SUGAR strategy.
|
---|
| 508 | \end{lisp:documentation}
|
---|
| 509 |
|
---|
| 510 | \begin{lisp:documentation}{normal$-$form$-$with$-$sugar}{FUNCTION}{f fl pred top$-$reduction$-$only ring }
|
---|
| 511 | Normal form of the polynomial with sugar F with respect to
|
---|
| 512 | a list of polynomials with sugar FL. Assumes that FL is not empty.
|
---|
| 513 | Parameters PRED, TOP$-$REDUCTION$-$ONLY and RING have the same
|
---|
| 514 | meaning as in NORMAL$-$FORM. The parameter SUGAR$-$LIMIT should be
|
---|
| 515 | set to a positive integer. If the sugar limit of the partial
|
---|
| 516 | remainder exceeds SUGAR$-$LIMIT then the calculation is stopped and
|
---|
| 517 | the partial remainder is returned, although it is not fully reduced
|
---|
| 518 | with respect to FL.
|
---|
| 519 | \end{lisp:documentation}
|
---|
| 520 |
|
---|
| 521 | \begin{lisp:documentation}{buchberger$-$with$-$sugar}{FUNCTION}{f$-$no$-$sugar pred start top$-$reduction$-$only ring {\sf \&aux} (s (1$-$ (length f$-$no$-$sugar))) b m f }
|
---|
| 522 | Returns a Grobner basis of an ideal generated by a list of ordinary
|
---|
| 523 | polynomials F$-$NO$-$SUGAR. Adds initial sugar to the polynomials and
|
---|
| 524 | performs the Buchberger algorithm with ``sugar strategy''. It returns
|
---|
| 525 | an ordinary list of polynomials with no sugar. One of the most
|
---|
| 526 | effective algorithms for Grobner basis calculation.
|
---|
| 527 | \end{lisp:documentation}
|
---|
| 528 |
|
---|
| 529 | \begin{lisp:documentation}{buchberger$-$with$-$sugar$-$merge$-$pairs}{FUNCTION}{b c g m pred ring }
|
---|
| 530 | Merges lists of critical pairs. It orders pairs according to
|
---|
| 531 | increasing sugar, with ties broken by smaller MOCK$-$SPOLY value of
|
---|
| 532 | the two polynomials. In this function B must already be sorted.
|
---|
| 533 | \end{lisp:documentation}
|
---|
| 534 |
|
---|
| 535 | \begin{lisp:documentation}{buchberger$-$with$-$sugar$-$sort$-$pairs}{FUNCTION}{c g m pred ring }
|
---|
| 536 | Sorts critical pairs C according to sugar strategy.
|
---|
| 537 | \end{lisp:documentation}
|
---|
| 538 |
|
---|
| 539 | \begin{lisp:documentation}{criterion$-$1$-$with$-$sugar}{FUNCTION}{pair g {\sf \&aux} (i (first pair)) (j (second pair)) }
|
---|
| 540 | An implementation of Buchberger's first criterion for polynomials
|
---|
| 541 | with sugar. See the documentation of BUCHBERGER$-$CRITERION$-$1.
|
---|
| 542 | \end{lisp:documentation}
|
---|
| 543 |
|
---|
| 544 | \begin{lisp:documentation}{criterion$-$2$-$with$-$sugar}{FUNCTION}{pair g m {\sf \&aux} (i (first pair)) (j (second pair)) }
|
---|
| 545 | An implementation of Buchberger's first criterion for polynomials
|
---|
| 546 | with sugar. See the documentation of BUCHBERGER$-$CRITERION$-$2.
|
---|
| 547 | \end{lisp:documentation}
|
---|
| 548 |
|
---|
| 549 | \begin{lisp:documentation}{gebauer$-$moeller$-$with$-$sugar}{FUNCTION}{f pred start top$-$reduction$-$only ring {\sf \&aux} b g f1 }
|
---|
| 550 | Compute Grobner basis by using the algorithm of Gebauer and Moeller.
|
---|
| 551 | This algorithm is described as BUCHBERGERNEW2 in the book by
|
---|
| 552 | Becker$-$Weispfenning entitled ``Grobner Bases''
|
---|
| 553 | \end{lisp:documentation}
|
---|
| 554 |
|
---|
| 555 | \begin{lisp:documentation}{update$-$with$-$sugar}{FUNCTION}{g b h pred ring {\sf \&aux} c d e b$-$new g$-$new pair }
|
---|
| 556 | An implementation of the auxillary UPDATE algorithm used by the
|
---|
| 557 | Gebauer$-$Moeller algorithm. G is a list of polynomials, B is a list
|
---|
| 558 | of critical pairs and H is a new polynomial which possibly will be
|
---|
| 559 | added to G. The naming conventions used are very close to the one
|
---|
| 560 | used in the book of Becker$-$Weispfenning. Operates on polynomials
|
---|
| 561 | with sugar.
|
---|
| 562 | \end{lisp:documentation}
|
---|
| 563 |
|
---|
| 564 | \begin{lisp:documentation}{gebauer$-$moeller$-$with$-$sugar$-$merge$-$pairs}{FUNCTION}{b c pred ring }
|
---|
| 565 | Merges lists of critical pairs. It orders pairs according to
|
---|
| 566 | increasing sugar, with ties broken by smaller lcm of head monomials
|
---|
| 567 | In this function B must already be sorted. Operates on polynomials
|
---|
| 568 | with sugar.
|
---|
| 569 | \end{lisp:documentation}
|
---|
| 570 |
|
---|
| 571 | \begin{lisp:documentation}{grobner$-$primitive$-$part$-$with$-$sugar}{FUNCTION}{h ring }
|
---|
| 572 | {\ } % NO DOCUMENTATION FOR GROBNER-PRIMITIVE-PART-WITH-SUGAR
|
---|
| 573 | \end{lisp:documentation}
|
---|
| 574 |
|
---|