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