close Warning: Can't synchronize with repository "(default)" (The repository directory has changed, you should resynchronize the repository with: trac-admin $ENV repository resync '(default)'). Look in the Trac log for more information.

source: branches/f4grobner/monom.lisp@ 3553

Last change on this file since 3553 was 3553, checked in by Marek Rychlik, 9 years ago

* empty log message *

File size: 19.7 KB
Line 
1;;; -*- Mode: Lisp -*-
2;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
3;;;
4;;; Copyright (C) 1999, 2002, 2009, 2015 Marek Rychlik <rychlik@u.arizona.edu>
5;;;
6;;; This program is free software; you can redistribute it and/or modify
7;;; it under the terms of the GNU General Public License as published by
8;;; the Free Software Foundation; either version 2 of the License, or
9;;; (at your option) any later version.
10;;;
11;;; This program is distributed in the hope that it will be useful,
12;;; but WITHOUT ANY WARRANTY; without even the implied warranty of
13;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14;;; GNU General Public License for more details.
15;;;
16;;; You should have received a copy of the GNU General Public License
17;;; along with this program; if not, write to the Free Software
18;;; Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
19;;;
20;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
21
22(defpackage "MONOM"
23 (:use :cl :copy)
24 (:export "MONOM"
25 "EXPONENT"
26 "MONOM-DIMENSION"
27 "MONOM-EXPONENTS"
28 "MONOM-EQUALP"
29 "MONOM-ELT"
30 "MONOM-TOTAL-DEGREE"
31 "MONOM-SUGAR"
32 "MONOM-MULTIPLY-BY"
33 "MONOM-DIVIDE-BY"
34 "MONOM-COPY-INSTANCE"
35 "MONOM-MULTIPLY-2"
36 "MONOM-MULTIPLY"
37 "MONOM-DIVIDES-P"
38 "MONOM-DIVIDES-LCM-P"
39 "MONOM-LCM-DIVIDES-LCM-P"
40 "MONOM-LCM-EQUAL-LCM-P"
41 "MONOM-DIVISIBLE-BY-P"
42 "MONOM-REL-PRIME-P"
43 "MONOM-LCM"
44 "MONOM-GCD"
45 "MONOM-DEPENDS-P"
46 "MONOM-LEFT-TENSOR-PRODUCT-BY"
47 "MONOM-RIGHT-TENSOR-PRODUCT-BY"
48 "MONOM-LEFT-CONTRACT"
49 "MAKE-MONOM-VARIABLE"
50 "MONOM->LIST"
51 "LEX>"
52 "GRLEX>"
53 "REVLEX>"
54 "GREVLEX>"
55 "INVLEX>"
56 "REVERSE-MONOMIAL-ORDER"
57 "MAKE-ELIMINATION-ORDER-FACTORY")
58 (:documentation
59 "This package implements basic operations on monomials, including
60various monomial orders.
61
62DATA STRUCTURES: Conceptually, monomials can be represented as lists:
63
64 monom: (n1 n2 ... nk) where ni are non-negative integers
65
66However, lists may be implemented as other sequence types, so the
67flexibility to change the representation should be maintained in the
68code to use general operations on sequences whenever possible. The
69optimization for the actual representation should be left to
70declarations and the compiler.
71
72EXAMPLES: Suppose that variables are x and y. Then
73
74 Monom x*y^2 ---> (1 2) "))
75
76(in-package :monom)
77
78(proclaim '(optimize (speed 3) (space 0) (safety 0) (debug 0)))
79
80(deftype exponent ()
81 "Type of exponent in a monomial."
82 'fixnum)
83
84(defclass monom ()
85 ((exponents :initarg :exponents :accessor monom-exponents
86 :documentation "The powers of the variables."))
87 ;; default-initargs are not needed, they are handled by SHARED-INITIALIZE
88 ;;(:default-initargs :dimension 'foo :exponents 'bar :exponent 'baz)
89 (:documentation
90 "Implements a monomial, i.e. a product of powers
91of variables, like X*Y^2."))
92
93(defmethod print-object ((self monom) stream)
94 (print-unreadable-object (self stream :type t :identity t)
95 (with-accessors ((exponents monom-exponents))
96 self
97 (format stream "EXPONENTS=~A"
98 exponents))))
99
100(defmethod initialize-instance :after ((self monom)
101 &key
102 (dimension 0 dimension-supplied-p)
103 (exponents nil exponents-supplied-p)
104 (exponent 0)
105 &allow-other-keys
106 )
107 "The following INITIALIZE-INSTANCE method allows instance initialization
108of a MONOM in a style similar to MAKE-ARRAY, e.g.:
109
110 (MAKE-INSTANCE :EXPONENTS '(1 2 3)) --> #<MONOM EXPONENTS=#(1 2 3)>
111 (MAKE-INSTANCE :DIMENSION 3) --> #<MONOM EXPONENTS=#(0 0 0)>
112 (MAKE-INSTANCE :DIMENSION 3 :EXPONENT 7) --> #<MONOM EXPONENTS=#(7 7 7)>
113
114If both DIMENSION and EXPONENTS are supplied, they must be compatible,
115i.e. the length of EXPONENTS must be equal DIMENSION. If EXPONENTS
116is not supplied, a monom with repeated value EXPONENT is created.
117By default EXPONENT is 0, which results in a constant monomial.
118"
119 (cond
120 (exponents-supplied-p
121 (when (and dimension-supplied-p
122 (/= dimension (length exponents)))
123 (error "EXPONENTS (~A) must have supplied length DIMENSION (~A)"
124 exponents dimension))
125 (let ((dim (length exponents)))
126 (setf (slot-value self 'exponents) (make-array dim :initial-contents exponents))))
127 (dimension-supplied-p
128 ;; when all exponents are to be identical
129 (setf (slot-value self 'exponents) (make-array (list dimension)
130 :initial-element exponent
131 :element-type 'exponent)))
132 (t
133 (error "Initarg DIMENSION or EXPONENTS must be supplied."))))
134
135(defgeneric monom-dimension (m)
136 (:method ((m monom))
137 (length (monom-exponents m))))
138
139(defgeneric universal-equalp (object1 object2)
140 (:documentation "Returns T iff OBJECT1 and OBJECT2 are equal.")
141 (:method ((m1 monom) (m2 monom))
142 "Returns T iff monomials M1 and M2 have identical EXPONENTS."
143 (equalp (monom-exponents m1) (monom-exponents m2))))
144
145(defgeneric monom-elt (m index)
146 (:documentation "Return the power in the monomial M of variable number INDEX."
147 (:method ((m monom) index)
148 "Return the power in the monomial M of variable number INDEX."
149 (with-slots (exponents)
150 m
151 (elt exponents index))))
152
153(defgeneric (setf monom-elt) (new-value m index)
154 (:documentation "Set the power in the monomial M of variable number INDEX.")
155 (:method (new-value (m monom) index)
156 (with-slots (exponents)
157 m
158 (setf (elt exponents index) new-value))))
159
160(defgeneric total-degree (m &optional start end)
161 (:documentation "Return the total degree of a monomoal M. Optinally, a range
162of variables may be specified with arguments START and END.")
163 (:method ((m monom) &optional (start 0) (end (monom-dimension m)))
164 (declare (type fixnum start end))
165 (with-slots (exponents)
166 m
167 (reduce #'+ exponents :start start :end end))))
168
169(defgeneric sugar (m &optional start end)
170 (:documentation "Return the sugar of a monomial M. Optinally, a range
171of variables may be specified with arguments START and END.")
172 (:method ((m monom) &optional (start 0) (end (monom-dimension m)))
173 (declare (type fixnum start end))
174 (total-degree m start end)))
175
176(defgeneric multiply-by (self other)
177 (:documentation "Multiply SELF by OTHER, return SELF.")
178 (:method ((self monom) (other monom))
179 (with-slots ((exponents1 exponents))
180 self
181 (with-slots ((exponents2 exponents))
182 other
183 (unless (= (length exponents1) (length exponents2))
184 (error "Incompatible dimensions"))
185 (map-into exponents1 #'+ exponents1 exponents2)))
186 self))
187
188(defgeneric divide-by (self other)
189 (:documentation "Divide SELF by OTHER, return SELF.")
190 (:method ((self monom) (other monom))
191 (with-slots ((exponents1 exponents))
192 self
193 (with-slots ((exponents2 exponents))
194 other
195 (unless (= (length exponents1) (length exponents2))
196 (error "divide-by: Incompatible dimensions."))
197 (unless (every #'>= exponents1 exponents2)
198 (error "divide-by: Negative power would result."))
199 (map-into exponents1 #'- exponents1 exponents2)))
200 self))
201
202(defmethod copy-instance :around ((object monom) &rest initargs &key &allow-other-keys)
203 "An :AROUND method of COPY-INSTANCE. It replaces
204exponents with a fresh copy of the sequence."
205 (declare (ignore object initargs))
206 (let ((copy (call-next-method)))
207 (setf (monom-exponents copy) (copy-seq (monom-exponents copy)))
208 copy))
209
210(defgeneric multiply-2 (object1 object2)
211 (:documentation "Multiply OBJECT1 by OBJECT2")
212 (:method (object1 object2)
213 (universal-multiply-by (copy-instance object1) (copy-instance object2))))
214
215(defgeneric divide (numerator &rest denominators)
216 (:documentation "Non-destructively divide object NUMERATOR by product of DENOMINATORS.")
217 (:method ((numerator monom) &rest denominators)
218 (divide-by (copy-instance numerator) (reduce #'multiply-2 denominators))))
219
220(defmethod monom-divides-p ((m1 monom) (m2 monom))
221 "Returns T if monomial M1 divides monomial M2, NIL otherwise."
222 (with-slots ((exponents1 exponents))
223 m1
224 (with-slots ((exponents2 exponents))
225 m2
226 (every #'<= exponents1 exponents2))))
227
228
229(defmethod monom-divides-lcm-p ((m1 monom) (m2 monom) (m3 monom))
230 "Returns T if monomial M1 divides LCM(M2,M3), NIL otherwise."
231 (every #'(lambda (x y z) (<= x (max y z)))
232 m1 m2 m3))
233
234(defmethod monom-lcm-divides-lcm-p ((m1 monom) (m2 monom) (m3 monom) (m4 monom))
235 "Returns T if monomial MONOM-LCM(M1,M2) divides MONOM-LCM(M3,M4), NIL otherwise."
236 (declare (type monom m1 m2 m3 m4))
237 (every #'(lambda (x y z w) (<= (max x y) (max z w)))
238 m1 m2 m3 m4))
239
240(defmethod monom-lcm-equal-lcm-p (m1 m2 m3 m4)
241 "Returns T if monomial LCM(M1,M2) equals LCM(M3,M4), NIL otherwise."
242 (with-slots ((exponents1 exponents))
243 m1
244 (with-slots ((exponents2 exponents))
245 m2
246 (with-slots ((exponents3 exponents))
247 m3
248 (with-slots ((exponents4 exponents))
249 m4
250 (every
251 #'(lambda (x y z w) (= (max x y) (max z w)))
252 exponents1 exponents2 exponents3 exponents4))))))
253
254(defmethod monom-divisible-by-p ((m1 monom) (m2 monom))
255 "Returns T if monomial M1 is divisible by monomial M2, NIL otherwise."
256 (with-slots ((exponents1 exponents))
257 m1
258 (with-slots ((exponents2 exponents))
259 m2
260 (every #'>= exponents1 exponents2))))
261
262(defmethod monom-rel-prime-p ((m1 monom) (m2 monom))
263 "Returns T if two monomials M1 and M2 are relatively prime (disjoint)."
264 (with-slots ((exponents1 exponents))
265 m1
266 (with-slots ((exponents2 exponents))
267 m2
268 (every #'(lambda (x y) (zerop (min x y))) exponents1 exponents2))))
269
270
271(defmethod monom-lcm ((m1 monom) (m2 monom))
272 "Returns least common multiple of monomials M1 and M2."
273 (with-slots ((exponents1 exponents))
274 m1
275 (with-slots ((exponents2 exponents))
276 m2
277 (let* ((exponents (copy-seq exponents1)))
278 (map-into exponents #'max exponents1 exponents2)
279 (make-instance 'monom :exponents exponents)))))
280
281
282(defmethod monom-gcd ((m1 monom) (m2 monom))
283 "Returns greatest common divisor of monomials M1 and M2."
284 (with-slots ((exponents1 exponents))
285 m1
286 (with-slots ((exponents2 exponents))
287 m2
288 (let* ((exponents (copy-seq exponents1)))
289 (map-into exponents #'min exponents1 exponents2)
290 (make-instance 'monom :exponents exponents)))))
291
292(defmethod monom-depends-p ((m monom) k)
293 "Return T if the monomial M depends on variable number K."
294 (declare (type fixnum k))
295 (with-slots (exponents)
296 m
297 (plusp (elt exponents k))))
298
299(defmethod monom-left-tensor-product-by ((self monom) (other monom))
300 (with-slots ((exponents1 exponents))
301 self
302 (with-slots ((exponents2 exponents))
303 other
304 (setf exponents1 (concatenate 'vector exponents2 exponents1))))
305 self)
306
307(defmethod monom-right-tensor-product-by ((self monom) (other monom))
308 (with-slots ((exponents1 exponents))
309 self
310 (with-slots ((exponents2 exponents))
311 other
312 (setf exponents1 (concatenate 'vector exponents1 exponents2))))
313 self)
314
315(defmethod monom-left-contract ((self monom) k)
316 "Drop the first K variables in monomial M."
317 (declare (fixnum k))
318 (with-slots (exponents)
319 self
320 (setf exponents (subseq exponents k)))
321 self)
322
323(defun make-monom-variable (nvars pos &optional (power 1)
324 &aux (m (make-instance 'monom :dimension nvars)))
325 "Construct a monomial in the polynomial ring
326RING[X[0],X[1],X[2],...X[NVARS-1]] over the (unspecified) ring RING
327which represents a single variable. It assumes number of variables
328NVARS and the variable is at position POS. Optionally, the variable
329may appear raised to power POWER. "
330 (declare (type fixnum nvars pos power) (type monom m))
331 (with-slots (exponents)
332 m
333 (setf (elt exponents pos) power)
334 m))
335
336(defmethod monom->list ((m monom))
337 "A human-readable representation of a monomial M as a list of exponents."
338 (coerce (monom-exponents m) 'list))
339
340
341;; pure lexicographic
342(defgeneric lex> (p q &optional start end)
343 (:documentation "Return T if P>Q with respect to lexicographic
344order, otherwise NIL. The second returned value is T if P=Q,
345otherwise it is NIL.")
346 (:method ((p monom) (q monom) &optional (start 0) (end (monom-dimension p)))
347 (declare (type fixnum start end))
348 (do ((i start (1+ i)))
349 ((>= i end) (values nil t))
350 (cond
351 ((> (monom-elt p i) (monom-elt q i))
352 (return-from lex> (values t nil)))
353 ((< (monom-elt p i) (monom-elt q i))
354 (return-from lex> (values nil nil)))))))
355
356;; total degree order, ties broken by lexicographic
357(defgeneric grlex> (p q &optional start end)
358 (:documentation "Return T if P>Q with respect to graded
359lexicographic order, otherwise NIL. The second returned value is T if
360P=Q, otherwise it is NIL.")
361 (:method ((p monom) (q monom) &optional (start 0) (end (monom-dimension p)))
362 (declare (type monom p q) (type fixnum start end))
363 (let ((d1 (monom-total-degree p start end))
364 (d2 (monom-total-degree q start end)))
365 (declare (type fixnum d1 d2))
366 (cond
367 ((> d1 d2) (values t nil))
368 ((< d1 d2) (values nil nil))
369 (t
370 (lex> p q start end))))))
371
372;; reverse lexicographic
373(defgeneric revlex> (p q &optional start end)
374 (:documentation "Return T if P>Q with respect to reverse
375lexicographic order, NIL otherwise. The second returned value is T if
376P=Q, otherwise it is NIL. This is not and admissible monomial order
377because some sets do not have a minimal element. This order is useful
378in constructing other orders.")
379 (:method ((p monom) (q monom) &optional (start 0) (end (monom-dimension p)))
380 (declare (type fixnum start end))
381 (do ((i (1- end) (1- i)))
382 ((< i start) (values nil t))
383 (declare (type fixnum i))
384 (cond
385 ((< (monom-elt p i) (monom-elt q i))
386 (return-from revlex> (values t nil)))
387 ((> (monom-elt p i) (monom-elt q i))
388 (return-from revlex> (values nil nil)))))))
389
390
391;; total degree, ties broken by reverse lexicographic
392(defgeneric grevlex> (p q &optional start end)
393 (:documentation "Return T if P>Q with respect to graded reverse
394lexicographic order, NIL otherwise. The second returned value is T if
395P=Q, otherwise it is NIL.")
396 (:method ((p monom) (q monom) &optional (start 0) (end (monom-dimension p)))
397 (declare (type fixnum start end))
398 (let ((d1 (monom-total-degree p start end))
399 (d2 (monom-total-degree q start end)))
400 (declare (type fixnum d1 d2))
401 (cond
402 ((> d1 d2) (values t nil))
403 ((< d1 d2) (values nil nil))
404 (t
405 (revlex> p q start end))))))
406
407(defgeneric invlex> (p q &optional start end)
408 (:documentation "Return T if P>Q with respect to inverse
409lexicographic order, NIL otherwise The second returned value is T if
410P=Q, otherwise it is NIL.")
411 (:method ((p monom) (q monom) &optional (start 0) (end (monom-dimension p)))
412 (declare (type fixnum start end))
413 (do ((i (1- end) (1- i)))
414 ((< i start) (values nil t))
415 (declare (type fixnum i))
416 (cond
417 ((> (monom-elt p i) (monom-elt q i))
418 (return-from invlex> (values t nil)))
419 ((< (monom-elt p i) (monom-elt q i))
420 (return-from invlex> (values nil nil)))))))
421
422(defun reverse-monomial-order (order)
423 "Create the inverse monomial order to the given monomial order ORDER."
424 #'(lambda (p q &optional (start 0) (end (monom-dimension q)))
425 (declare (type monom p q) (type fixnum start end))
426 (funcall order q p start end)))
427
428;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
429;;
430;; Order making functions
431;;
432;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
433
434;; This returns a closure with the same signature
435;; as all orders such as #'LEX>.
436(defun make-elimination-order-factory-1 (&optional (secondary-elimination-order #'lex>))
437 "It constructs an elimination order used for the 1-st elimination ideal,
438i.e. for eliminating the first variable. Thus, the order compares the degrees of the
439first variable in P and Q first, with ties broken by SECONDARY-ELIMINATION-ORDER."
440 #'(lambda (p q &optional (start 0) (end (monom-dimension p)))
441 (declare (type monom p q) (type fixnum start end))
442 (cond
443 ((> (monom-elt p start) (monom-elt q start))
444 (values t nil))
445 ((< (monom-elt p start) (monom-elt q start))
446 (values nil nil))
447 (t
448 (funcall secondary-elimination-order p q (1+ start) end)))))
449
450;; This returns a closure which is called with an integer argument.
451;; The result is *another closure* with the same signature as all
452;; orders such as #'LEX>.
453(defun make-elimination-order-factory (&optional
454 (primary-elimination-order #'lex>)
455 (secondary-elimination-order #'lex>))
456 "Return a function with a single integer argument K. This should be
457the number of initial K variables X[0],X[1],...,X[K-1], which precede
458remaining variables. The call to the closure creates a predicate
459which compares monomials according to the K-th elimination order. The
460monomial orders PRIMARY-ELIMINATION-ORDER and
461SECONDARY-ELIMINATION-ORDER are used to compare the first K and the
462remaining variables, respectively, with ties broken by lexicographical
463order. That is, if PRIMARY-ELIMINATION-ORDER yields (VALUES NIL T),
464which indicates that the first K variables appear with identical
465powers, then the result is that of a call to
466SECONDARY-ELIMINATION-ORDER applied to the remaining variables
467X[K],X[K+1],..."
468 #'(lambda (k)
469 (cond
470 ((<= k 0)
471 (error "K must be at least 1"))
472 ((= k 1)
473 (make-elimination-order-factory-1 secondary-elimination-order))
474 (t
475 #'(lambda (p q &optional (start 0) (end (monom-dimension p)))
476 (declare (type monom p q) (type fixnum start end))
477 (multiple-value-bind (primary equal)
478 (funcall primary-elimination-order p q start k)
479 (if equal
480 (funcall secondary-elimination-order p q k end)
481 (values primary nil))))))))
482
483(defclass term (monom)
484 ((coeff :initarg :coeff :accessor term-coeff))
485 (:default-initargs :coeff nil)
486 (:documentation "Implements a term, i.e. a product of a scalar
487and powers of some variables, such as 5*X^2*Y^3."))
488
489(defmethod print-object ((self term) stream)
490 (print-unreadable-object (self stream :type t :identity t)
491 (with-accessors ((exponents monom-exponents)
492 (coeff term-coeff))
493 self
494 (format stream "EXPONENTS=~A COEFF=~A"
495 exponents coeff))))
496
497(defmethod universal-equalp ((term1 term) (term2 term))
498 "Returns T if TERM1 and TERM2 are equal as MONOM, and coefficients
499are UNIVERSAL-EQUALP."
500 (and (call-next-method)
501 (universal-equalp (term-coeff term1) (term-coeff term2))))
502
503(defmethod update-instance-for-different-class :after ((old monom) (new term) &key)
504 (setf (term-coeff new) 1))
505
506(defmethod term-multiply-by ((self term) (other term))
507 "Destructively multiply terms SELF and OTHER and store the result into SELF.
508It returns SELF."
509 (setf (term-coeff self) (universal-multiply-by (term-coeff self) (scalar-coeff other))))
510
511(defmethod term-left-tensor-product-by ((self term) (other term))
512 (setf (term-coeff self) (universal-multiply-by (term-coeff self) (term-coeff other)))
513 (call-next-method))
514
515(defmethod term-right-tensor-product-by ((self term) (other term))
516 (setf (term-coeff self) (multiply-by (term-coeff self) (term-coeff other)))
517 (call-next-method))
518
519(defmethod monom-divide-by ((self term) (other term))
520 "Destructively divide term SELF by OTHER and store the result into SELF.
521It returns SELF."
522 (setf (term-coeff self) (divide-by (term-coeff self) (term-coeff other)))
523 (call-next-method))
524
525(defmethod monom-unary-minus ((self term))
526 (setf (term-coeff self) (monom-unary-minus (term-coeff self)))
527 self)
528
529(defmethod monom-multiply ((term1 term) (term2 term))
530 "Non-destructively multiply TERM1 by TERM2."
531 (monom-multiply-by (copy-instance term1) (copy-instance term2)))
532
533(defmethod monom-multiply ((term1 number) (term2 monom))
534 "Non-destructively multiply TERM1 by TERM2."
535 (monom-multiply term1 (change-class (copy-instance term2) 'term)))
536
537(defmethod monom-zerop ((self term))
538 (zerop (term-coeff self)))
Note: See TracBrowser for help on using the repository browser.