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