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 | ;;;
|
---|