[1201] | 1 | ;;; -*- Mode: Lisp -*-
|
---|
[81] | 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 |
|
---|
[1610] | 22 | (defpackage "MONOM"
|
---|
[2025] | 23 | (:use :cl :ring)
|
---|
[422] | 24 | (:export "MONOM"
|
---|
[423] | 25 | "EXPONENT"
|
---|
[2781] | 26 | "MONOM-DIMENSION"
|
---|
| 27 | "MONOM-EXPONENTS"
|
---|
[2524] | 28 | "MAKE-MONOM-VARIABLE")
|
---|
| 29 | (:documentation
|
---|
| 30 | "This package implements basic operations on monomials.
|
---|
| 31 | DATA STRUCTURES: Conceptually, monomials can be represented as lists:
|
---|
[81] | 32 |
|
---|
[2524] | 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 |
|
---|
[1610] | 45 | (in-package :monom)
|
---|
[48] | 46 |
|
---|
[1925] | 47 | (proclaim '(optimize (speed 3) (space 0) (safety 0) (debug 0)))
|
---|
[1923] | 48 |
|
---|
[48] | 49 | (deftype exponent ()
|
---|
| 50 | "Type of exponent in a monomial."
|
---|
| 51 | 'fixnum)
|
---|
| 52 |
|
---|
[2022] | 53 | (defclass monom ()
|
---|
[3054] | 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."))
|
---|
[3289] | 58 | ;; default-initargs are not needed, they are handled by SHARED-INITIALIZE
|
---|
| 59 | ;;(:default-initargs :dimension 'foo :exponents 'bar :exponent 'baz)
|
---|
[2779] | 60 | (:documentation
|
---|
| 61 | "Implements a monomial, i.e. a product of powers
|
---|
| 62 | of variables, like X*Y^2."))
|
---|
[880] | 63 |
|
---|
[2245] | 64 | (defmethod print-object ((self monom) stream)
|
---|
[3196] | 65 | (print-unreadable-object (self stream :type t :identity t)
|
---|
[3216] | 66 | (with-accessors ((dimension monom-dimension) (exponents monom-exponents))
|
---|
| 67 | self
|
---|
| 68 | (format stream "DIMENSION=~A EXPONENTS=~A"
|
---|
| 69 | dimension exponents))))
|
---|
[2027] | 70 |
|
---|
[3300] | 71 | ;; The following INITIALIZE-INSTANCE method allows instance
|
---|
| 72 | ;; initialization in a style similar to MAKE-ARRAY, e.g.
|
---|
[3291] | 73 | ;;
|
---|
[3292] | 74 | ;; (MAKE-INSTANCE :EXPONENTS '(1 2 3)) --> #<MONOM DIMENSION=3 EXPONENTS=#(1 2 3)>
|
---|
| 75 | ;; (MAKE-INSTANCE :DIMENSION 3) --> #<MONOM DIMENSION=3 EXPONENTS=#(0 0 0)>
|
---|
[3291] | 76 | ;; (MAKE-INSTANCE :DIMENSION 3 :EXPONENT 7) --> #<MONOM DIMENSION=3 EXPONENTS=#(7 7 7)>
|
---|
| 77 | ;;
|
---|
[3299] | 78 | (defmethod initialize-instance :after ((self monom)
|
---|
[3297] | 79 | &key
|
---|
| 80 | (dimension 0 dimension-supplied-p)
|
---|
| 81 | (exponents nil exponents-supplied-p)
|
---|
| 82 | (exponent 0 exponent-supplied-p)
|
---|
| 83 | &allow-other-keys
|
---|
[2390] | 84 | )
|
---|
[3298] | 85 | (when dimension-supplied-p
|
---|
[3303] | 86 | (when (and (slot-boundp self 'dimension)
|
---|
| 87 | (/= (slot-value self 'dimension) dimension))
|
---|
| 88 | (warn "Changing MONOM DIMENSION from ~A to ~A."
|
---|
| 89 | (slot-value self 'dimension) dimension))
|
---|
[3298] | 90 | (setf (slot-value self 'dimension) dimension))
|
---|
[3293] | 91 |
|
---|
[3298] | 92 | (when exponents-supplied-p
|
---|
| 93 | (let ((dim (length exponents)))
|
---|
[3302] | 94 | (when (and (slot-boundp self 'dimension)
|
---|
| 95 | (/= (slot-value self 'dimension) dim))
|
---|
[3304] | 96 | (warn "Changing slot DIMENSION ~A to match the length of EXPONENTS ~A"
|
---|
| 97 | (slot-value self 'dimension) (length exponents)))
|
---|
[3298] | 98 | (setf (slot-value self 'dimension) dim
|
---|
[3305] | 99 | (slot-value self 'exponents) (make-array dim :initial-contents exponents)
|
---|
| 100 | (slot-value self 'dimension) (length exponents))))
|
---|
[3293] | 101 |
|
---|
[3298] | 102 | ;; when all exponents are to be identical
|
---|
[3299] | 103 | (when exponent-supplied-p
|
---|
[3298] | 104 | (unless (slot-boundp self 'dimension)
|
---|
| 105 | (error "Slot DIMENSION is unbound, but must be known if EXPONENT is supplied."))
|
---|
| 106 | (let ((dim (slot-value self 'dimension)))
|
---|
| 107 | (setf (slot-value self 'exponents)
|
---|
| 108 | (make-array (list dim) :initial-element exponent
|
---|
| 109 | :element-type 'exponent)))))
|
---|
[3293] | 110 |
|
---|
[2850] | 111 | (defmethod r-equalp ((m1 monom) (m2 monom))
|
---|
[2778] | 112 | "Returns T iff monomials M1 and M2 have identical
|
---|
| 113 | EXPONENTS."
|
---|
[2779] | 114 | (equalp (monom-exponents m1) (monom-exponents m2)))
|
---|
[2547] | 115 |
|
---|
[2398] | 116 | (defmethod r-coeff ((m monom))
|
---|
| 117 | "A MONOM can be treated as a special case of TERM,
|
---|
| 118 | where the coefficient is 1."
|
---|
| 119 | 1)
|
---|
[2397] | 120 |
|
---|
[2143] | 121 | (defmethod r-elt ((m monom) index)
|
---|
[48] | 122 | "Return the power in the monomial M of variable number INDEX."
|
---|
[2023] | 123 | (with-slots (exponents)
|
---|
| 124 | m
|
---|
[2154] | 125 | (elt exponents index)))
|
---|
[48] | 126 |
|
---|
[2160] | 127 | (defmethod (setf r-elt) (new-value (m monom) index)
|
---|
[2023] | 128 | "Return the power in the monomial M of variable number INDEX."
|
---|
| 129 | (with-slots (exponents)
|
---|
| 130 | m
|
---|
[2154] | 131 | (setf (elt exponents index) new-value)))
|
---|
[2023] | 132 |
|
---|
[2779] | 133 | (defmethod r-total-degree ((m monom) &optional (start 0) (end (monom-dimension m)))
|
---|
[48] | 134 | "Return the todal degree of a monomoal M. Optinally, a range
|
---|
| 135 | of variables may be specified with arguments START and END."
|
---|
[2023] | 136 | (declare (type fixnum start end))
|
---|
| 137 | (with-slots (exponents)
|
---|
| 138 | m
|
---|
[2154] | 139 | (reduce #'+ exponents :start start :end end)))
|
---|
[48] | 140 |
|
---|
[2064] | 141 |
|
---|
[2779] | 142 | (defmethod r-sugar ((m monom) &aux (start 0) (end (monom-dimension m)))
|
---|
[48] | 143 | "Return the sugar of a monomial M. Optinally, a range
|
---|
| 144 | of variables may be specified with arguments START and END."
|
---|
[2032] | 145 | (declare (type fixnum start end))
|
---|
[2155] | 146 | (r-total-degree m start end))
|
---|
[48] | 147 |
|
---|
[2478] | 148 | (defmethod multiply-by ((self monom) (other monom))
|
---|
[2807] | 149 | (with-slots ((exponents1 exponents) (dimension1 dimension))
|
---|
[2478] | 150 | self
|
---|
[2811] | 151 | (with-slots ((exponents2 exponents) (dimension2 dimension))
|
---|
[2478] | 152 | other
|
---|
[2811] | 153 | (unless (= dimension1 dimension2)
|
---|
[2813] | 154 | (error "Incompatible dimensions: ~A and ~A.~%" dimension1 dimension2))
|
---|
[2811] | 155 | (map-into exponents1 #'+ exponents1 exponents2)))
|
---|
[2480] | 156 | self)
|
---|
[2069] | 157 |
|
---|
[2818] | 158 | (defmethod divide-by ((self monom) (other monom))
|
---|
| 159 | (with-slots ((exponents1 exponents) (dimension1 dimension))
|
---|
| 160 | self
|
---|
| 161 | (with-slots ((exponents2 exponents) (dimension2 dimension))
|
---|
| 162 | other
|
---|
| 163 | (unless (= dimension1 dimension2)
|
---|
| 164 | (error "Incompatible dimensions: ~A and ~A.~%" dimension1 dimension2))
|
---|
| 165 | (map-into exponents1 #'- exponents1 exponents2)))
|
---|
| 166 | self)
|
---|
| 167 |
|
---|
[3004] | 168 | (defmethod copy-instance :around ((object monom) &rest initargs &key &allow-other-keys)
|
---|
[3018] | 169 | "An :AROUNT method for COPY-INSTANCE. The primary method is a shallow copy,
|
---|
| 170 | while for monomials we typically need a fresh copy of the
|
---|
| 171 | exponents."
|
---|
[3004] | 172 | (declare (ignore object initargs))
|
---|
[3002] | 173 | (let ((copy (call-next-method)))
|
---|
[3003] | 174 | (setf (monom-exponents copy) (copy-seq (monom-exponents copy)))
|
---|
[3002] | 175 | copy))
|
---|
[2950] | 176 |
|
---|
[2816] | 177 | (defmethod r* ((m1 monom) (m2 monom))
|
---|
| 178 | "Non-destructively multiply monomial M1 by M2."
|
---|
[3032] | 179 | (multiply-by (copy-instance m1) (copy-instance m2)))
|
---|
[2816] | 180 |
|
---|
[2144] | 181 | (defmethod r/ ((m1 monom) (m2 monom))
|
---|
[2819] | 182 | "Non-destructively divide monomial M1 by monomial M2."
|
---|
[3032] | 183 | (divide-by (copy-instance m1) (copy-instance m2)))
|
---|
[48] | 184 |
|
---|
[2144] | 185 | (defmethod r-divides-p ((m1 monom) (m2 monom))
|
---|
[48] | 186 | "Returns T if monomial M1 divides monomial M2, NIL otherwise."
|
---|
[2039] | 187 | (with-slots ((exponents1 exponents))
|
---|
| 188 | m1
|
---|
| 189 | (with-slots ((exponents2 exponents))
|
---|
| 190 | m2
|
---|
| 191 | (every #'<= exponents1 exponents2))))
|
---|
[48] | 192 |
|
---|
[2075] | 193 |
|
---|
[2144] | 194 | (defmethod r-divides-lcm-p ((m1 monom) (m2 monom) (m3 monom))
|
---|
[2055] | 195 | "Returns T if monomial M1 divides LCM(M2,M3), NIL otherwise."
|
---|
[875] | 196 | (every #'(lambda (x y z) (<= x (max y z)))
|
---|
[869] | 197 | m1 m2 m3))
|
---|
[48] | 198 |
|
---|
[2049] | 199 |
|
---|
[2144] | 200 | (defmethod r-lcm-divides-lcm-p ((m1 monom) (m2 monom) (m3 monom) (m4 monom))
|
---|
[48] | 201 | "Returns T if monomial MONOM-LCM(M1,M2) divides MONOM-LCM(M3,M4), NIL otherwise."
|
---|
[1890] | 202 | (declare (type monom m1 m2 m3 m4))
|
---|
[869] | 203 | (every #'(lambda (x y z w) (<= (max x y) (max z w)))
|
---|
| 204 | m1 m2 m3 m4))
|
---|
| 205 |
|
---|
[2144] | 206 | (defmethod r-lcm-equal-lcm-p (m1 m2 m3 m4)
|
---|
[2075] | 207 | "Returns T if monomial LCM(M1,M2) equals LCM(M3,M4), NIL otherwise."
|
---|
[2171] | 208 | (with-slots ((exponents1 exponents))
|
---|
[2076] | 209 | m1
|
---|
[2171] | 210 | (with-slots ((exponents2 exponents))
|
---|
[2076] | 211 | m2
|
---|
[2171] | 212 | (with-slots ((exponents3 exponents))
|
---|
[2076] | 213 | m3
|
---|
[2171] | 214 | (with-slots ((exponents4 exponents))
|
---|
[2076] | 215 | m4
|
---|
[2077] | 216 | (every
|
---|
| 217 | #'(lambda (x y z w) (= (max x y) (max z w)))
|
---|
| 218 | exponents1 exponents2 exponents3 exponents4))))))
|
---|
[48] | 219 |
|
---|
[2144] | 220 | (defmethod r-divisible-by-p ((m1 monom) (m2 monom))
|
---|
[48] | 221 | "Returns T if monomial M1 is divisible by monomial M2, NIL otherwise."
|
---|
[2171] | 222 | (with-slots ((exponents1 exponents))
|
---|
[2144] | 223 | m1
|
---|
[2171] | 224 | (with-slots ((exponents2 exponents))
|
---|
[2144] | 225 | m2
|
---|
| 226 | (every #'>= exponents1 exponents2))))
|
---|
[2078] | 227 |
|
---|
[2146] | 228 | (defmethod r-rel-prime-p ((m1 monom) (m2 monom))
|
---|
[48] | 229 | "Returns T if two monomials M1 and M2 are relatively prime (disjoint)."
|
---|
[2171] | 230 | (with-slots ((exponents1 exponents))
|
---|
[2078] | 231 | m1
|
---|
[2171] | 232 | (with-slots ((exponents2 exponents))
|
---|
[2078] | 233 | m2
|
---|
[2154] | 234 | (every #'(lambda (x y) (zerop (min x y))) exponents1 exponents2))))
|
---|
[48] | 235 |
|
---|
[2076] | 236 |
|
---|
[2146] | 237 | (defmethod r-lcm ((m1 monom) (m2 monom))
|
---|
[48] | 238 | "Returns least common multiple of monomials M1 and M2."
|
---|
[2319] | 239 | (with-slots ((exponents1 exponents) (dimension1 dimension))
|
---|
[2082] | 240 | m1
|
---|
[2171] | 241 | (with-slots ((exponents2 exponents))
|
---|
[2082] | 242 | m2
|
---|
| 243 | (let* ((exponents (copy-seq exponents1))
|
---|
[2319] | 244 | (dimension dimension1))
|
---|
[2082] | 245 | (map-into exponents #'max exponents1 exponents2)
|
---|
[2200] | 246 | (make-instance 'monom :dimension dimension :exponents exponents)))))
|
---|
[48] | 247 |
|
---|
[2080] | 248 |
|
---|
[2146] | 249 | (defmethod r-gcd ((m1 monom) (m2 monom))
|
---|
[48] | 250 | "Returns greatest common divisor of monomials M1 and M2."
|
---|
[2320] | 251 | (with-slots ((exponents1 exponents) (dimension1 dimension))
|
---|
[2082] | 252 | m1
|
---|
[2171] | 253 | (with-slots ((exponents2 exponents))
|
---|
[2082] | 254 | m2
|
---|
| 255 | (let* ((exponents (copy-seq exponents1))
|
---|
[2320] | 256 | (dimension dimension1))
|
---|
[2082] | 257 | (map-into exponents #'min exponents1 exponents2)
|
---|
[2197] | 258 | (make-instance 'monom :dimension dimension :exponents exponents)))))
|
---|
[48] | 259 |
|
---|
[2146] | 260 | (defmethod r-depends-p ((m monom) k)
|
---|
[48] | 261 | "Return T if the monomial M depends on variable number K."
|
---|
[2083] | 262 | (declare (type fixnum k))
|
---|
| 263 | (with-slots (exponents)
|
---|
| 264 | m
|
---|
[2154] | 265 | (plusp (elt exponents k))))
|
---|
[48] | 266 |
|
---|
[3020] | 267 | (defmethod left-tensor-product-by ((self monom) (other monom))
|
---|
[2321] | 268 | (with-slots ((exponents1 exponents) (dimension1 dimension))
|
---|
[3020] | 269 | self
|
---|
[2321] | 270 | (with-slots ((exponents2 exponents) (dimension2 dimension))
|
---|
[3020] | 271 | other
|
---|
| 272 | (setf dimension1 (+ dimension1 dimension2)
|
---|
[3036] | 273 | exponents1 (concatenate 'vector exponents2 exponents1))))
|
---|
| 274 | self)
|
---|
[48] | 275 |
|
---|
[3026] | 276 | (defmethod right-tensor-product-by ((self monom) (other monom))
|
---|
| 277 | (with-slots ((exponents1 exponents) (dimension1 dimension))
|
---|
| 278 | self
|
---|
| 279 | (with-slots ((exponents2 exponents) (dimension2 dimension))
|
---|
| 280 | other
|
---|
| 281 | (setf dimension1 (+ dimension1 dimension2)
|
---|
[3036] | 282 | exponents1 (concatenate 'vector exponents1 exponents2))))
|
---|
| 283 | self)
|
---|
[3026] | 284 |
|
---|
[3039] | 285 | (defmethod left-contract ((self monom) k)
|
---|
[1638] | 286 | "Drop the first K variables in monomial M."
|
---|
[2085] | 287 | (declare (fixnum k))
|
---|
[2196] | 288 | (with-slots (dimension exponents)
|
---|
[3040] | 289 | self
|
---|
[2197] | 290 | (setf dimension (- dimension k)
|
---|
[3039] | 291 | exponents (subseq exponents k)))
|
---|
| 292 | self)
|
---|
[886] | 293 |
|
---|
| 294 | (defun make-monom-variable (nvars pos &optional (power 1)
|
---|
[2218] | 295 | &aux (m (make-instance 'monom :dimension nvars)))
|
---|
[886] | 296 | "Construct a monomial in the polynomial ring
|
---|
| 297 | RING[X[0],X[1],X[2],...X[NVARS-1]] over the (unspecified) ring RING
|
---|
| 298 | which represents a single variable. It assumes number of variables
|
---|
| 299 | NVARS and the variable is at position POS. Optionally, the variable
|
---|
| 300 | may appear raised to power POWER. "
|
---|
[1924] | 301 | (declare (type fixnum nvars pos power) (type monom m))
|
---|
[2089] | 302 | (with-slots (exponents)
|
---|
| 303 | m
|
---|
[2154] | 304 | (setf (elt exponents pos) power)
|
---|
[2089] | 305 | m))
|
---|
[1151] | 306 |
|
---|
[2150] | 307 | (defmethod r->list ((m monom))
|
---|
[1152] | 308 | "A human-readable representation of a monomial M as a list of exponents."
|
---|
[2779] | 309 | (coerce (monom-exponents m) 'list))
|
---|
[2780] | 310 |
|
---|
[2783] | 311 | (defmethod r-dimension ((self monom))
|
---|
| 312 | (monom-dimension self))
|
---|
| 313 |
|
---|
[2780] | 314 | (defmethod r-exponents ((self monom))
|
---|
| 315 | (monom-exponents self))
|
---|