[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
|
---|
[3310] | 103 | (if exponent-supplied-p
|
---|
[3308] | 104 | (when (slot-boundp self 'exponents)
|
---|
[3310] | 105 | (warn "Ignoring argument EXPONENT."))
|
---|
[3308] | 106 | (cond
|
---|
| 107 | ((slot-boundp self 'dimension)
|
---|
| 108 | (let ((dim (slot-value self 'dimension)))
|
---|
| 109 | (setf (slot-value self 'exponents)
|
---|
| 110 | (make-array (list dim) :initial-element (if exponent-supplied-p exponent 0)
|
---|
[3309] | 111 | :element-type 'exponent))))
|
---|
| 112 | (t
|
---|
| 113 | (error "Slot DIMENSION is unbound, but must be known if EXPONENT is supplied.")))))
|
---|
[3293] | 114 |
|
---|
[2850] | 115 | (defmethod r-equalp ((m1 monom) (m2 monom))
|
---|
[2778] | 116 | "Returns T iff monomials M1 and M2 have identical
|
---|
| 117 | EXPONENTS."
|
---|
[2779] | 118 | (equalp (monom-exponents m1) (monom-exponents m2)))
|
---|
[2547] | 119 |
|
---|
[2398] | 120 | (defmethod r-coeff ((m monom))
|
---|
| 121 | "A MONOM can be treated as a special case of TERM,
|
---|
| 122 | where the coefficient is 1."
|
---|
| 123 | 1)
|
---|
[2397] | 124 |
|
---|
[2143] | 125 | (defmethod r-elt ((m monom) index)
|
---|
[48] | 126 | "Return the power in the monomial M of variable number INDEX."
|
---|
[2023] | 127 | (with-slots (exponents)
|
---|
| 128 | m
|
---|
[2154] | 129 | (elt exponents index)))
|
---|
[48] | 130 |
|
---|
[2160] | 131 | (defmethod (setf r-elt) (new-value (m monom) index)
|
---|
[2023] | 132 | "Return the power in the monomial M of variable number INDEX."
|
---|
| 133 | (with-slots (exponents)
|
---|
| 134 | m
|
---|
[2154] | 135 | (setf (elt exponents index) new-value)))
|
---|
[2023] | 136 |
|
---|
[2779] | 137 | (defmethod r-total-degree ((m monom) &optional (start 0) (end (monom-dimension m)))
|
---|
[48] | 138 | "Return the todal degree of a monomoal M. Optinally, a range
|
---|
| 139 | of variables may be specified with arguments START and END."
|
---|
[2023] | 140 | (declare (type fixnum start end))
|
---|
| 141 | (with-slots (exponents)
|
---|
| 142 | m
|
---|
[2154] | 143 | (reduce #'+ exponents :start start :end end)))
|
---|
[48] | 144 |
|
---|
[2064] | 145 |
|
---|
[2779] | 146 | (defmethod r-sugar ((m monom) &aux (start 0) (end (monom-dimension m)))
|
---|
[48] | 147 | "Return the sugar of a monomial M. Optinally, a range
|
---|
| 148 | of variables may be specified with arguments START and END."
|
---|
[2032] | 149 | (declare (type fixnum start end))
|
---|
[2155] | 150 | (r-total-degree m start end))
|
---|
[48] | 151 |
|
---|
[2478] | 152 | (defmethod multiply-by ((self monom) (other monom))
|
---|
[2807] | 153 | (with-slots ((exponents1 exponents) (dimension1 dimension))
|
---|
[2478] | 154 | self
|
---|
[2811] | 155 | (with-slots ((exponents2 exponents) (dimension2 dimension))
|
---|
[2478] | 156 | other
|
---|
[2811] | 157 | (unless (= dimension1 dimension2)
|
---|
[2813] | 158 | (error "Incompatible dimensions: ~A and ~A.~%" dimension1 dimension2))
|
---|
[2811] | 159 | (map-into exponents1 #'+ exponents1 exponents2)))
|
---|
[2480] | 160 | self)
|
---|
[2069] | 161 |
|
---|
[2818] | 162 | (defmethod divide-by ((self monom) (other monom))
|
---|
| 163 | (with-slots ((exponents1 exponents) (dimension1 dimension))
|
---|
| 164 | self
|
---|
| 165 | (with-slots ((exponents2 exponents) (dimension2 dimension))
|
---|
| 166 | other
|
---|
| 167 | (unless (= dimension1 dimension2)
|
---|
| 168 | (error "Incompatible dimensions: ~A and ~A.~%" dimension1 dimension2))
|
---|
| 169 | (map-into exponents1 #'- exponents1 exponents2)))
|
---|
| 170 | self)
|
---|
| 171 |
|
---|
[3004] | 172 | (defmethod copy-instance :around ((object monom) &rest initargs &key &allow-other-keys)
|
---|
[3018] | 173 | "An :AROUNT method for COPY-INSTANCE. The primary method is a shallow copy,
|
---|
| 174 | while for monomials we typically need a fresh copy of the
|
---|
| 175 | exponents."
|
---|
[3004] | 176 | (declare (ignore object initargs))
|
---|
[3002] | 177 | (let ((copy (call-next-method)))
|
---|
[3003] | 178 | (setf (monom-exponents copy) (copy-seq (monom-exponents copy)))
|
---|
[3002] | 179 | copy))
|
---|
[2950] | 180 |
|
---|
[2816] | 181 | (defmethod r* ((m1 monom) (m2 monom))
|
---|
| 182 | "Non-destructively multiply monomial M1 by M2."
|
---|
[3032] | 183 | (multiply-by (copy-instance m1) (copy-instance m2)))
|
---|
[2816] | 184 |
|
---|
[2144] | 185 | (defmethod r/ ((m1 monom) (m2 monom))
|
---|
[2819] | 186 | "Non-destructively divide monomial M1 by monomial M2."
|
---|
[3032] | 187 | (divide-by (copy-instance m1) (copy-instance m2)))
|
---|
[48] | 188 |
|
---|
[2144] | 189 | (defmethod r-divides-p ((m1 monom) (m2 monom))
|
---|
[48] | 190 | "Returns T if monomial M1 divides monomial M2, NIL otherwise."
|
---|
[2039] | 191 | (with-slots ((exponents1 exponents))
|
---|
| 192 | m1
|
---|
| 193 | (with-slots ((exponents2 exponents))
|
---|
| 194 | m2
|
---|
| 195 | (every #'<= exponents1 exponents2))))
|
---|
[48] | 196 |
|
---|
[2075] | 197 |
|
---|
[2144] | 198 | (defmethod r-divides-lcm-p ((m1 monom) (m2 monom) (m3 monom))
|
---|
[2055] | 199 | "Returns T if monomial M1 divides LCM(M2,M3), NIL otherwise."
|
---|
[875] | 200 | (every #'(lambda (x y z) (<= x (max y z)))
|
---|
[869] | 201 | m1 m2 m3))
|
---|
[48] | 202 |
|
---|
[2049] | 203 |
|
---|
[2144] | 204 | (defmethod r-lcm-divides-lcm-p ((m1 monom) (m2 monom) (m3 monom) (m4 monom))
|
---|
[48] | 205 | "Returns T if monomial MONOM-LCM(M1,M2) divides MONOM-LCM(M3,M4), NIL otherwise."
|
---|
[1890] | 206 | (declare (type monom m1 m2 m3 m4))
|
---|
[869] | 207 | (every #'(lambda (x y z w) (<= (max x y) (max z w)))
|
---|
| 208 | m1 m2 m3 m4))
|
---|
| 209 |
|
---|
[2144] | 210 | (defmethod r-lcm-equal-lcm-p (m1 m2 m3 m4)
|
---|
[2075] | 211 | "Returns T if monomial LCM(M1,M2) equals LCM(M3,M4), NIL otherwise."
|
---|
[2171] | 212 | (with-slots ((exponents1 exponents))
|
---|
[2076] | 213 | m1
|
---|
[2171] | 214 | (with-slots ((exponents2 exponents))
|
---|
[2076] | 215 | m2
|
---|
[2171] | 216 | (with-slots ((exponents3 exponents))
|
---|
[2076] | 217 | m3
|
---|
[2171] | 218 | (with-slots ((exponents4 exponents))
|
---|
[2076] | 219 | m4
|
---|
[2077] | 220 | (every
|
---|
| 221 | #'(lambda (x y z w) (= (max x y) (max z w)))
|
---|
| 222 | exponents1 exponents2 exponents3 exponents4))))))
|
---|
[48] | 223 |
|
---|
[2144] | 224 | (defmethod r-divisible-by-p ((m1 monom) (m2 monom))
|
---|
[48] | 225 | "Returns T if monomial M1 is divisible by monomial M2, NIL otherwise."
|
---|
[2171] | 226 | (with-slots ((exponents1 exponents))
|
---|
[2144] | 227 | m1
|
---|
[2171] | 228 | (with-slots ((exponents2 exponents))
|
---|
[2144] | 229 | m2
|
---|
| 230 | (every #'>= exponents1 exponents2))))
|
---|
[2078] | 231 |
|
---|
[2146] | 232 | (defmethod r-rel-prime-p ((m1 monom) (m2 monom))
|
---|
[48] | 233 | "Returns T if two monomials M1 and M2 are relatively prime (disjoint)."
|
---|
[2171] | 234 | (with-slots ((exponents1 exponents))
|
---|
[2078] | 235 | m1
|
---|
[2171] | 236 | (with-slots ((exponents2 exponents))
|
---|
[2078] | 237 | m2
|
---|
[2154] | 238 | (every #'(lambda (x y) (zerop (min x y))) exponents1 exponents2))))
|
---|
[48] | 239 |
|
---|
[2076] | 240 |
|
---|
[2146] | 241 | (defmethod r-lcm ((m1 monom) (m2 monom))
|
---|
[48] | 242 | "Returns least common multiple of monomials M1 and M2."
|
---|
[2319] | 243 | (with-slots ((exponents1 exponents) (dimension1 dimension))
|
---|
[2082] | 244 | m1
|
---|
[2171] | 245 | (with-slots ((exponents2 exponents))
|
---|
[2082] | 246 | m2
|
---|
| 247 | (let* ((exponents (copy-seq exponents1))
|
---|
[2319] | 248 | (dimension dimension1))
|
---|
[2082] | 249 | (map-into exponents #'max exponents1 exponents2)
|
---|
[2200] | 250 | (make-instance 'monom :dimension dimension :exponents exponents)))))
|
---|
[48] | 251 |
|
---|
[2080] | 252 |
|
---|
[2146] | 253 | (defmethod r-gcd ((m1 monom) (m2 monom))
|
---|
[48] | 254 | "Returns greatest common divisor of monomials M1 and M2."
|
---|
[2320] | 255 | (with-slots ((exponents1 exponents) (dimension1 dimension))
|
---|
[2082] | 256 | m1
|
---|
[2171] | 257 | (with-slots ((exponents2 exponents))
|
---|
[2082] | 258 | m2
|
---|
| 259 | (let* ((exponents (copy-seq exponents1))
|
---|
[2320] | 260 | (dimension dimension1))
|
---|
[2082] | 261 | (map-into exponents #'min exponents1 exponents2)
|
---|
[2197] | 262 | (make-instance 'monom :dimension dimension :exponents exponents)))))
|
---|
[48] | 263 |
|
---|
[2146] | 264 | (defmethod r-depends-p ((m monom) k)
|
---|
[48] | 265 | "Return T if the monomial M depends on variable number K."
|
---|
[2083] | 266 | (declare (type fixnum k))
|
---|
| 267 | (with-slots (exponents)
|
---|
| 268 | m
|
---|
[2154] | 269 | (plusp (elt exponents k))))
|
---|
[48] | 270 |
|
---|
[3020] | 271 | (defmethod left-tensor-product-by ((self monom) (other monom))
|
---|
[2321] | 272 | (with-slots ((exponents1 exponents) (dimension1 dimension))
|
---|
[3020] | 273 | self
|
---|
[2321] | 274 | (with-slots ((exponents2 exponents) (dimension2 dimension))
|
---|
[3020] | 275 | other
|
---|
| 276 | (setf dimension1 (+ dimension1 dimension2)
|
---|
[3036] | 277 | exponents1 (concatenate 'vector exponents2 exponents1))))
|
---|
| 278 | self)
|
---|
[48] | 279 |
|
---|
[3026] | 280 | (defmethod right-tensor-product-by ((self monom) (other monom))
|
---|
| 281 | (with-slots ((exponents1 exponents) (dimension1 dimension))
|
---|
| 282 | self
|
---|
| 283 | (with-slots ((exponents2 exponents) (dimension2 dimension))
|
---|
| 284 | other
|
---|
| 285 | (setf dimension1 (+ dimension1 dimension2)
|
---|
[3036] | 286 | exponents1 (concatenate 'vector exponents1 exponents2))))
|
---|
| 287 | self)
|
---|
[3026] | 288 |
|
---|
[3039] | 289 | (defmethod left-contract ((self monom) k)
|
---|
[1638] | 290 | "Drop the first K variables in monomial M."
|
---|
[2085] | 291 | (declare (fixnum k))
|
---|
[2196] | 292 | (with-slots (dimension exponents)
|
---|
[3040] | 293 | self
|
---|
[2197] | 294 | (setf dimension (- dimension k)
|
---|
[3039] | 295 | exponents (subseq exponents k)))
|
---|
| 296 | self)
|
---|
[886] | 297 |
|
---|
| 298 | (defun make-monom-variable (nvars pos &optional (power 1)
|
---|
[2218] | 299 | &aux (m (make-instance 'monom :dimension nvars)))
|
---|
[886] | 300 | "Construct a monomial in the polynomial ring
|
---|
| 301 | RING[X[0],X[1],X[2],...X[NVARS-1]] over the (unspecified) ring RING
|
---|
| 302 | which represents a single variable. It assumes number of variables
|
---|
| 303 | NVARS and the variable is at position POS. Optionally, the variable
|
---|
| 304 | may appear raised to power POWER. "
|
---|
[1924] | 305 | (declare (type fixnum nvars pos power) (type monom m))
|
---|
[2089] | 306 | (with-slots (exponents)
|
---|
| 307 | m
|
---|
[2154] | 308 | (setf (elt exponents pos) power)
|
---|
[2089] | 309 | m))
|
---|
[1151] | 310 |
|
---|
[2150] | 311 | (defmethod r->list ((m monom))
|
---|
[1152] | 312 | "A human-readable representation of a monomial M as a list of exponents."
|
---|
[2779] | 313 | (coerce (monom-exponents m) 'list))
|
---|
[2780] | 314 |
|
---|
[2783] | 315 | (defmethod r-dimension ((self monom))
|
---|
| 316 | (monom-dimension self))
|
---|
| 317 |
|
---|
[2780] | 318 | (defmethod r-exponents ((self monom))
|
---|
| 319 | (monom-exponents self))
|
---|