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 :ring)
|
---|
24 | (:export "MONOM"
|
---|
25 | "EXPONENT"
|
---|
26 | "MONOM-DIMENSION"
|
---|
27 | "MONOM-EXPONENTS"
|
---|
28 | "MAKE-MONOM-VARIABLE")
|
---|
29 | (:documentation
|
---|
30 | "This package implements basic operations on monomials.
|
---|
31 | DATA STRUCTURES: Conceptually, monomials can be represented as lists:
|
---|
32 |
|
---|
33 | monom: (n1 n2 ... nk) where ni are non-negative integers
|
---|
34 |
|
---|
35 | However, lists may be implemented as other sequence types, so the
|
---|
36 | flexibility to change the representation should be maintained in the
|
---|
37 | code to use general operations on sequences whenever possible. The
|
---|
38 | optimization for the actual representation should be left to
|
---|
39 | declarations and the compiler.
|
---|
40 |
|
---|
41 | EXAMPLES: Suppose that variables are x and y. Then
|
---|
42 |
|
---|
43 | Monom x*y^2 ---> (1 2) "))
|
---|
44 |
|
---|
45 | (in-package :monom)
|
---|
46 |
|
---|
47 | (proclaim '(optimize (speed 3) (space 0) (safety 0) (debug 0)))
|
---|
48 |
|
---|
49 | (deftype exponent ()
|
---|
50 | "Type of exponent in a monomial."
|
---|
51 | 'fixnum)
|
---|
52 |
|
---|
53 | (defclass monom ()
|
---|
54 | ((dimension :initarg :dimension :accessor monom-dimension
|
---|
55 | :documentation "The number of variables.")
|
---|
56 | (exponents :initarg :exponents :accessor monom-exponents
|
---|
57 | :documentation "The powers of the variables."))
|
---|
58 | ;; default-initargs are not needed, they are handled by SHARED-INITIALIZE
|
---|
59 | ;;(:default-initargs :dimension 'foo :exponents 'bar :exponent 'baz)
|
---|
60 | (:documentation
|
---|
61 | "Implements a monomial, i.e. a product of powers
|
---|
62 | of variables, like X*Y^2."))
|
---|
63 |
|
---|
64 | (defmethod print-object ((self monom) stream)
|
---|
65 | (print-unreadable-object (self stream :type t :identity t)
|
---|
66 | (with-accessors ((dimension monom-dimension) (exponents monom-exponents))
|
---|
67 | self
|
---|
68 | (format stream "DIMENSION=~A EXPONENTS=~A"
|
---|
69 | dimension exponents))))
|
---|
70 |
|
---|
71 | ;; SHARED-INITIALIZE allows instance initialization in a style similar to MAKE-ARRAY, e.g.
|
---|
72 | ;;
|
---|
73 | ;; (MAKE-INSTANCE :EXPONENTS '(1 2 3)) --> #<MONOM DIMENSION=3 EXPONENTS=#(1 2 3)>
|
---|
74 | ;; (MAKE-INSTANCE :DIMENSION 3) --> #<MONOM DIMENSION=3 EXPONENTS=#(0 0 0)>
|
---|
75 | ;; (MAKE-INSTANCE :DIMENSION 3 :EXPONENT 7) --> #<MONOM DIMENSION=3 EXPONENTS=#(7 7 7)>
|
---|
76 | ;;
|
---|
77 | (defmethod initialize-instance :after ((self monom) slot-names
|
---|
78 | &key
|
---|
79 | (dimension 0 dimension-supplied-p)
|
---|
80 | (exponents nil exponents-supplied-p)
|
---|
81 | (exponent 0 exponent-supplied-p)
|
---|
82 | &allow-other-keys
|
---|
83 | )
|
---|
84 | (when (and dimension-supplied-p (slot-accessible-p 'dimension))
|
---|
85 | (setf (slot-value self 'dimension) dimension))
|
---|
86 |
|
---|
87 | (when (and exponents-supplied-p (slot-accessible-p 'exponents))
|
---|
88 | (let ((dim (length exponents)))
|
---|
89 | (when (and dimension-supplied-p (/= dimension dim))
|
---|
90 | (error "EXPONENTS must have length DIMENSION"))
|
---|
91 | (setf (slot-value self 'dimension) dim
|
---|
92 | (slot-value self 'exponents) (make-array dim :initial-contents exponents))
|
---|
93 | (setf (slot-value self 'dimension) (length exponents))))
|
---|
94 |
|
---|
95 | ;; when all exponents are to be identical
|
---|
96 | (when (and exponent-supplied-p (slot-accessible-p 'exponents))
|
---|
97 | (unless (slot-boundp self 'dimension)
|
---|
98 | (error "Slot DIMENSION is unbound, but must be known if EXPONENT is supplied."))
|
---|
99 | (let ((dim (slot-value self 'dimension)))
|
---|
100 | (setf (slot-value self 'exponents)
|
---|
101 | (make-array (list dim) :initial-element exponent
|
---|
102 | :element-type 'exponent))))))
|
---|
103 |
|
---|
104 | (defmethod r-equalp ((m1 monom) (m2 monom))
|
---|
105 | "Returns T iff monomials M1 and M2 have identical
|
---|
106 | EXPONENTS."
|
---|
107 | (equalp (monom-exponents m1) (monom-exponents m2)))
|
---|
108 |
|
---|
109 | (defmethod r-coeff ((m monom))
|
---|
110 | "A MONOM can be treated as a special case of TERM,
|
---|
111 | where the coefficient is 1."
|
---|
112 | 1)
|
---|
113 |
|
---|
114 | (defmethod r-elt ((m monom) index)
|
---|
115 | "Return the power in the monomial M of variable number INDEX."
|
---|
116 | (with-slots (exponents)
|
---|
117 | m
|
---|
118 | (elt exponents index)))
|
---|
119 |
|
---|
120 | (defmethod (setf r-elt) (new-value (m monom) index)
|
---|
121 | "Return the power in the monomial M of variable number INDEX."
|
---|
122 | (with-slots (exponents)
|
---|
123 | m
|
---|
124 | (setf (elt exponents index) new-value)))
|
---|
125 |
|
---|
126 | (defmethod r-total-degree ((m monom) &optional (start 0) (end (monom-dimension m)))
|
---|
127 | "Return the todal degree of a monomoal M. Optinally, a range
|
---|
128 | of variables may be specified with arguments START and END."
|
---|
129 | (declare (type fixnum start end))
|
---|
130 | (with-slots (exponents)
|
---|
131 | m
|
---|
132 | (reduce #'+ exponents :start start :end end)))
|
---|
133 |
|
---|
134 |
|
---|
135 | (defmethod r-sugar ((m monom) &aux (start 0) (end (monom-dimension m)))
|
---|
136 | "Return the sugar of a monomial M. Optinally, a range
|
---|
137 | of variables may be specified with arguments START and END."
|
---|
138 | (declare (type fixnum start end))
|
---|
139 | (r-total-degree m start end))
|
---|
140 |
|
---|
141 | (defmethod multiply-by ((self monom) (other monom))
|
---|
142 | (with-slots ((exponents1 exponents) (dimension1 dimension))
|
---|
143 | self
|
---|
144 | (with-slots ((exponents2 exponents) (dimension2 dimension))
|
---|
145 | other
|
---|
146 | (unless (= dimension1 dimension2)
|
---|
147 | (error "Incompatible dimensions: ~A and ~A.~%" dimension1 dimension2))
|
---|
148 | (map-into exponents1 #'+ exponents1 exponents2)))
|
---|
149 | self)
|
---|
150 |
|
---|
151 | (defmethod divide-by ((self monom) (other monom))
|
---|
152 | (with-slots ((exponents1 exponents) (dimension1 dimension))
|
---|
153 | self
|
---|
154 | (with-slots ((exponents2 exponents) (dimension2 dimension))
|
---|
155 | other
|
---|
156 | (unless (= dimension1 dimension2)
|
---|
157 | (error "Incompatible dimensions: ~A and ~A.~%" dimension1 dimension2))
|
---|
158 | (map-into exponents1 #'- exponents1 exponents2)))
|
---|
159 | self)
|
---|
160 |
|
---|
161 | (defmethod copy-instance :around ((object monom) &rest initargs &key &allow-other-keys)
|
---|
162 | "An :AROUNT method for COPY-INSTANCE. The primary method is a shallow copy,
|
---|
163 | while for monomials we typically need a fresh copy of the
|
---|
164 | exponents."
|
---|
165 | (declare (ignore object initargs))
|
---|
166 | (let ((copy (call-next-method)))
|
---|
167 | (setf (monom-exponents copy) (copy-seq (monom-exponents copy)))
|
---|
168 | copy))
|
---|
169 |
|
---|
170 | (defmethod r* ((m1 monom) (m2 monom))
|
---|
171 | "Non-destructively multiply monomial M1 by M2."
|
---|
172 | (multiply-by (copy-instance m1) (copy-instance m2)))
|
---|
173 |
|
---|
174 | (defmethod r/ ((m1 monom) (m2 monom))
|
---|
175 | "Non-destructively divide monomial M1 by monomial M2."
|
---|
176 | (divide-by (copy-instance m1) (copy-instance m2)))
|
---|
177 |
|
---|
178 | (defmethod r-divides-p ((m1 monom) (m2 monom))
|
---|
179 | "Returns T if monomial M1 divides monomial M2, NIL otherwise."
|
---|
180 | (with-slots ((exponents1 exponents))
|
---|
181 | m1
|
---|
182 | (with-slots ((exponents2 exponents))
|
---|
183 | m2
|
---|
184 | (every #'<= exponents1 exponents2))))
|
---|
185 |
|
---|
186 |
|
---|
187 | (defmethod r-divides-lcm-p ((m1 monom) (m2 monom) (m3 monom))
|
---|
188 | "Returns T if monomial M1 divides LCM(M2,M3), NIL otherwise."
|
---|
189 | (every #'(lambda (x y z) (<= x (max y z)))
|
---|
190 | m1 m2 m3))
|
---|
191 |
|
---|
192 |
|
---|
193 | (defmethod r-lcm-divides-lcm-p ((m1 monom) (m2 monom) (m3 monom) (m4 monom))
|
---|
194 | "Returns T if monomial MONOM-LCM(M1,M2) divides MONOM-LCM(M3,M4), NIL otherwise."
|
---|
195 | (declare (type monom m1 m2 m3 m4))
|
---|
196 | (every #'(lambda (x y z w) (<= (max x y) (max z w)))
|
---|
197 | m1 m2 m3 m4))
|
---|
198 |
|
---|
199 | (defmethod r-lcm-equal-lcm-p (m1 m2 m3 m4)
|
---|
200 | "Returns T if monomial LCM(M1,M2) equals LCM(M3,M4), NIL otherwise."
|
---|
201 | (with-slots ((exponents1 exponents))
|
---|
202 | m1
|
---|
203 | (with-slots ((exponents2 exponents))
|
---|
204 | m2
|
---|
205 | (with-slots ((exponents3 exponents))
|
---|
206 | m3
|
---|
207 | (with-slots ((exponents4 exponents))
|
---|
208 | m4
|
---|
209 | (every
|
---|
210 | #'(lambda (x y z w) (= (max x y) (max z w)))
|
---|
211 | exponents1 exponents2 exponents3 exponents4))))))
|
---|
212 |
|
---|
213 | (defmethod r-divisible-by-p ((m1 monom) (m2 monom))
|
---|
214 | "Returns T if monomial M1 is divisible by monomial M2, NIL otherwise."
|
---|
215 | (with-slots ((exponents1 exponents))
|
---|
216 | m1
|
---|
217 | (with-slots ((exponents2 exponents))
|
---|
218 | m2
|
---|
219 | (every #'>= exponents1 exponents2))))
|
---|
220 |
|
---|
221 | (defmethod r-rel-prime-p ((m1 monom) (m2 monom))
|
---|
222 | "Returns T if two monomials M1 and M2 are relatively prime (disjoint)."
|
---|
223 | (with-slots ((exponents1 exponents))
|
---|
224 | m1
|
---|
225 | (with-slots ((exponents2 exponents))
|
---|
226 | m2
|
---|
227 | (every #'(lambda (x y) (zerop (min x y))) exponents1 exponents2))))
|
---|
228 |
|
---|
229 |
|
---|
230 | (defmethod r-lcm ((m1 monom) (m2 monom))
|
---|
231 | "Returns least common multiple of monomials M1 and M2."
|
---|
232 | (with-slots ((exponents1 exponents) (dimension1 dimension))
|
---|
233 | m1
|
---|
234 | (with-slots ((exponents2 exponents))
|
---|
235 | m2
|
---|
236 | (let* ((exponents (copy-seq exponents1))
|
---|
237 | (dimension dimension1))
|
---|
238 | (map-into exponents #'max exponents1 exponents2)
|
---|
239 | (make-instance 'monom :dimension dimension :exponents exponents)))))
|
---|
240 |
|
---|
241 |
|
---|
242 | (defmethod r-gcd ((m1 monom) (m2 monom))
|
---|
243 | "Returns greatest common divisor of monomials M1 and M2."
|
---|
244 | (with-slots ((exponents1 exponents) (dimension1 dimension))
|
---|
245 | m1
|
---|
246 | (with-slots ((exponents2 exponents))
|
---|
247 | m2
|
---|
248 | (let* ((exponents (copy-seq exponents1))
|
---|
249 | (dimension dimension1))
|
---|
250 | (map-into exponents #'min exponents1 exponents2)
|
---|
251 | (make-instance 'monom :dimension dimension :exponents exponents)))))
|
---|
252 |
|
---|
253 | (defmethod r-depends-p ((m monom) k)
|
---|
254 | "Return T if the monomial M depends on variable number K."
|
---|
255 | (declare (type fixnum k))
|
---|
256 | (with-slots (exponents)
|
---|
257 | m
|
---|
258 | (plusp (elt exponents k))))
|
---|
259 |
|
---|
260 | (defmethod left-tensor-product-by ((self monom) (other monom))
|
---|
261 | (with-slots ((exponents1 exponents) (dimension1 dimension))
|
---|
262 | self
|
---|
263 | (with-slots ((exponents2 exponents) (dimension2 dimension))
|
---|
264 | other
|
---|
265 | (setf dimension1 (+ dimension1 dimension2)
|
---|
266 | exponents1 (concatenate 'vector exponents2 exponents1))))
|
---|
267 | self)
|
---|
268 |
|
---|
269 | (defmethod right-tensor-product-by ((self monom) (other monom))
|
---|
270 | (with-slots ((exponents1 exponents) (dimension1 dimension))
|
---|
271 | self
|
---|
272 | (with-slots ((exponents2 exponents) (dimension2 dimension))
|
---|
273 | other
|
---|
274 | (setf dimension1 (+ dimension1 dimension2)
|
---|
275 | exponents1 (concatenate 'vector exponents1 exponents2))))
|
---|
276 | self)
|
---|
277 |
|
---|
278 | (defmethod left-contract ((self monom) k)
|
---|
279 | "Drop the first K variables in monomial M."
|
---|
280 | (declare (fixnum k))
|
---|
281 | (with-slots (dimension exponents)
|
---|
282 | self
|
---|
283 | (setf dimension (- dimension k)
|
---|
284 | exponents (subseq exponents k)))
|
---|
285 | self)
|
---|
286 |
|
---|
287 | (defun make-monom-variable (nvars pos &optional (power 1)
|
---|
288 | &aux (m (make-instance 'monom :dimension nvars)))
|
---|
289 | "Construct a monomial in the polynomial ring
|
---|
290 | RING[X[0],X[1],X[2],...X[NVARS-1]] over the (unspecified) ring RING
|
---|
291 | which represents a single variable. It assumes number of variables
|
---|
292 | NVARS and the variable is at position POS. Optionally, the variable
|
---|
293 | may appear raised to power POWER. "
|
---|
294 | (declare (type fixnum nvars pos power) (type monom m))
|
---|
295 | (with-slots (exponents)
|
---|
296 | m
|
---|
297 | (setf (elt exponents pos) power)
|
---|
298 | m))
|
---|
299 |
|
---|
300 | (defmethod r->list ((m monom))
|
---|
301 | "A human-readable representation of a monomial M as a list of exponents."
|
---|
302 | (coerce (monom-exponents m) 'list))
|
---|
303 |
|
---|
304 | (defmethod r-dimension ((self monom))
|
---|
305 | (monom-dimension self))
|
---|
306 |
|
---|
307 | (defmethod r-exponents ((self monom))
|
---|
308 | (monom-exponents self))
|
---|