source: branches/f4grobner/monom.lisp@ 3542

;;; -*-  Mode: Lisp -*- 
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;                                                                              
;;;  Copyright (C) 1999, 2002, 2009, 2015 Marek Rychlik <rychlik@u.arizona.edu>          
;;;                                                                              
;;;  This program is free software; you can redistribute it and/or modify        
;;;  it under the terms of the GNU General Public License as published by        
;;;  the Free Software Foundation; either version 2 of the License, or           
;;;  (at your option) any later version.                                         
;;;                                                                              
;;;  This program is distributed in the hope that it will be useful,             
;;;  but WITHOUT ANY WARRANTY; without even the implied warranty of              
;;;  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the               
;;;  GNU General Public License for more details.                                
;;;                                                                              
;;;  You should have received a copy of the GNU General Public License           
;;;  along with this program; if not, write to the Free Software                 
;;;  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  
;;;                                                                              
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defpackage "MONOM"
  (:use :cl :copy)
  (:export "MONOM"
           "EXPONENT"
           "MONOM-DIMENSION"
           "MONOM-EXPONENTS"
           "MONOM-EQUALP"
           "MONOM-ELT"
           "MONOM-TOTAL-DEGREE"
           "MONOM-SUGAR"
           "MONOM-MULTIPLY-BY"
           "MONOM-DIVIDE-BY"
           "MONOM-COPY-INSTANCE"
           "MONOM-MULTIPLY-2"
           "MONOM-MULTIPLY"
           "MONOM-DIVIDES-P"
           "MONOM-DIVIDES-LCM-P"
           "MONOM-LCM-DIVIDES-LCM-P"
           "MONOM-LCM-EQUAL-LCM-P"
           "MONOM-DIVISIBLE-BY-P"
           "MONOM-REL-PRIME-P"
           "MONOM-LCM"
           "MONOM-GCD"
           "MONOM-DEPENDS-P"
           "MONOM-LEFT-TENSOR-PRODUCT-BY"
           "MONOM-RIGHT-TENSOR-PRODUCT-BY"
           "MONOM-LEFT-CONTRACT"
           "MAKE-MONOM-VARIABLE"
           "MONOM->LIST"
           "LEX>"
           "GRLEX>"
           "REVLEX>"
           "GREVLEX>"
           "INVLEX>"
           "REVERSE-MONOMIAL-ORDER"
           "MAKE-ELIMINATION-ORDER-FACTORY")
  (:documentation
   "This package implements basic operations on monomials, including
various monomial orders.

DATA STRUCTURES: Conceptually, monomials can be represented as lists:

        monom: (n1 n2 ... nk) where ni are non-negative integers

However, lists may be implemented as other sequence types, so the
flexibility to change the representation should be maintained in the
code to use general operations on sequences whenever possible. The
optimization for the actual representation should be left to
declarations and the compiler.

EXAMPLES: Suppose that variables are x and y. Then

        Monom x*y^2 ---> (1 2) "))

(in-package :monom)

(proclaim '(optimize (speed 3) (space 0) (safety 0) (debug 0)))

(deftype exponent ()
  "Type of exponent in a monomial."
  'fixnum)

(defclass monom ()
  ((exponents :initarg :exponents :accessor monom-exponents
              :documentation "The powers of the variables."))
  ;; default-initargs are not needed, they are handled by SHARED-INITIALIZE
  ;;(:default-initargs :dimension 'foo :exponents 'bar :exponent 'baz)
  (:documentation 
   "Implements a monomial, i.e. a product of powers
of variables, like X*Y^2."))

(defmethod print-object ((self monom) stream)
  (print-unreadable-object (self stream :type t :identity t)
    (with-accessors ((exponents monom-exponents))
        self
      (format stream "EXPONENTS=~A"
              exponents))))

(defmethod initialize-instance :after ((self monom)
                                       &key 
                                         (dimension 0 dimension-supplied-p)
                                         (exponents nil exponents-supplied-p)
                                         (exponent  0)
                                       &allow-other-keys
                                       )
  "The following INITIALIZE-INSTANCE method allows instance initialization
of a MONOM in a style similar to MAKE-ARRAY, e.g.:

 (MAKE-INSTANCE :EXPONENTS '(1 2 3))      --> #<MONOM EXPONENTS=#(1 2 3)>
 (MAKE-INSTANCE :DIMENSION 3)             --> #<MONOM EXPONENTS=#(0 0 0)>
 (MAKE-INSTANCE :DIMENSION 3 :EXPONENT 7) --> #<MONOM EXPONENTS=#(7 7 7)>

If both DIMENSION and EXPONENTS are supplied, they must be compatible,
i.e. the length of EXPONENTS must be equal DIMENSION. If EXPONENTS
is not supplied, a monom with repeated value EXPONENT is created.
By default EXPONENT is 0, which results in a constant monomial.
"
  (cond 
    (exponents-supplied-p
     (when (and dimension-supplied-p
                (/= dimension (length exponents)))
       (error "EXPONENTS (~A) must have supplied length DIMENSION (~A)"
              exponents dimension))
     (let ((dim (length exponents)))
       (setf (slot-value self 'exponents) (make-array dim :initial-contents exponents))))
    (dimension-supplied-p
     ;; when all exponents are to be identical
     (setf (slot-value self 'exponents) (make-array (list dimension) 
                                                    :initial-element exponent
                                                    :element-type 'exponent)))
    (t  
     (error "Initarg DIMENSION or EXPONENTS must be supplied."))))

(defgeneric monom-dimension (m)
  (:method ((m monom))
    (length (monom-exponents m))))

(defgeneric universal-equalp (object1 object2)
  (:documentation "Returns T iff OBJECT1 and OBJECT2 are equal.")
  (:method ((m1 monom) (m2 monom))
    "Returns T iff monomials M1 and M2 have identical EXPONENTS."
    (equalp (monom-exponents m1) (monom-exponents m2))))

(defgeneric monom-elt (m index)
  (:documentation 
   "Return the power in the monomial M of variable number INDEX.")
  (:method ((m monom) index)
    (with-slots (exponents)
        m
      (elt exponents index))))

(defgeneric (setf monom-elt) (new-value m index)
  (:documentation "Return the power in the monomial M of variable number INDEX.")
  (:method (new-value (m monom) index)
    (with-slots (exponents)
        m
      (setf (elt exponents index) new-value))))

(defgeneric monom-total-degree (m &optional start end)
  (:documentation "Return the todal degree of a monomoal M. Optinally, a range
of variables may be specified with arguments START and END.")
  (:method ((m monom) &optional (start 0) (end (monom-dimension m)))
    (declare (type fixnum start end))
    (with-slots (exponents)
        m
      (reduce #'+ exponents :start start :end end))))

(defgeneric monom-sugar (m &optional start end)
  (:documentation "Return the sugar of a monomial M. Optinally, a range
of variables may be specified with arguments START and END.")
  (:method ((m monom)  &optional (start 0) (end (monom-dimension m)))
    (declare (type fixnum start end))
    (monom-total-degree m start end)))

(defgeneric monom-multiply-by (self other)
  (:method ((self monom) (other monom))
    (with-slots ((exponents1 exponents))
        self
      (with-slots ((exponents2 exponents))
          other
        (unless (= (length exponents1) (length exponents2))
          (error "Incompatible dimensions"))
        (map-into exponents1 #'+ exponents1 exponents2)))
  self))

(defgeneric monom-divide-by (self other)
  (:method ((self monom) (other monom))
    (with-slots ((exponents1 exponents))
        self
      (with-slots ((exponents2 exponents))
          other
        (unless (= (length exponents1) (length exponents2))
          (error "divide-by: Incompatible dimensions."))
        (unless (every #'>= exponents1 exponents2)
          (error "divide-by: Negative power would result."))
        (map-into exponents1 #'- exponents1 exponents2)))
  self))

(defmethod copy-instance :around ((object monom)  &rest initargs &key &allow-other-keys)
  "An :AROUND method of COPY-INSTANCE. It replaces
exponents with a fresh copy of the sequence."
    (declare (ignore object initargs))
    (let ((copy (call-next-method)))
      (setf (monom-exponents copy) (copy-seq (monom-exponents copy)))
      copy))

(defmethod monom-multiply-2 ((m1 monom) (m2 monom))
  "Non-destructively multiply monomial M1 by M2."
  (monom-multiply-by (copy-instance m1) (copy-instance m2)))

(defmethod monom-multiply ((numerator monom) &rest denominators)
  "Non-destructively divide monomial NUMERATOR by product of DENOMINATORS."
  (monom-divide-by (copy-instance numerator) (reduce #'monom-multiply-2 denominators)))

(defmethod monom-divides-p ((m1 monom) (m2 monom))
  "Returns T if monomial M1 divides monomial M2, NIL otherwise."
  (with-slots ((exponents1 exponents))
      m1
    (with-slots ((exponents2 exponents))
        m2
      (every #'<= exponents1 exponents2))))


(defmethod monom-divides-lcm-p ((m1 monom) (m2 monom) (m3 monom))
  "Returns T if monomial M1 divides LCM(M2,M3), NIL otherwise."
  (every #'(lambda (x y z) (<= x (max y z))) 
         m1 m2 m3))


(defmethod monom-lcm-divides-lcm-p ((m1 monom) (m2 monom) (m3 monom) (m4 monom))
  "Returns T if monomial MONOM-LCM(M1,M2) divides MONOM-LCM(M3,M4), NIL otherwise."
  (declare (type monom m1 m2 m3 m4))
  (every #'(lambda (x y z w) (<= (max x y) (max z w))) 
         m1 m2 m3 m4))
         
(defmethod monom-lcm-equal-lcm-p (m1 m2 m3 m4)
  "Returns T if monomial LCM(M1,M2) equals LCM(M3,M4), NIL otherwise."
  (with-slots ((exponents1 exponents))
      m1
    (with-slots ((exponents2 exponents))
        m2
      (with-slots ((exponents3 exponents))
          m3
        (with-slots ((exponents4 exponents))
            m4
          (every 
           #'(lambda (x y z w) (= (max x y) (max z w)))
           exponents1 exponents2 exponents3 exponents4))))))

(defmethod monom-divisible-by-p ((m1 monom) (m2 monom))
  "Returns T if monomial M1 is divisible by monomial M2, NIL otherwise."
  (with-slots ((exponents1 exponents))
      m1
    (with-slots ((exponents2 exponents))
        m2
      (every #'>= exponents1 exponents2))))

(defmethod monom-rel-prime-p ((m1 monom) (m2 monom))
  "Returns T if two monomials M1 and M2 are relatively prime (disjoint)."
  (with-slots ((exponents1 exponents))
      m1
    (with-slots ((exponents2 exponents))
        m2
      (every #'(lambda (x y) (zerop (min x y))) exponents1 exponents2))))


(defmethod monom-lcm ((m1 monom) (m2 monom)) 
  "Returns least common multiple of monomials M1 and M2."
  (with-slots ((exponents1 exponents))
      m1
    (with-slots ((exponents2 exponents))
        m2
      (let* ((exponents (copy-seq exponents1)))
        (map-into exponents #'max exponents1 exponents2)
        (make-instance 'monom :exponents exponents)))))


(defmethod monom-gcd ((m1 monom) (m2 monom))
  "Returns greatest common divisor of monomials M1 and M2."
  (with-slots ((exponents1 exponents))
      m1
    (with-slots ((exponents2 exponents))
        m2
      (let* ((exponents (copy-seq exponents1)))
        (map-into exponents #'min exponents1 exponents2)
        (make-instance 'monom :exponents exponents)))))

(defmethod monom-depends-p ((m monom) k)
  "Return T if the monomial M depends on variable number K."
  (declare (type fixnum k))
  (with-slots (exponents)
      m
    (plusp (elt exponents k))))

(defmethod monom-left-tensor-product-by ((self monom) (other monom))
  (with-slots ((exponents1 exponents))
      self
    (with-slots ((exponents2 exponents))
        other
      (setf exponents1 (concatenate 'vector exponents2 exponents1))))
  self)

(defmethod monom-right-tensor-product-by ((self monom) (other monom))
  (with-slots ((exponents1 exponents))
      self
    (with-slots ((exponents2 exponents))
        other
      (setf exponents1 (concatenate 'vector exponents1 exponents2))))
  self)

(defmethod monom-left-contract ((self monom) k)
  "Drop the first K variables in monomial M."
  (declare (fixnum k))
  (with-slots (exponents) 
      self
    (setf exponents (subseq exponents k)))
  self)

(defun make-monom-variable (nvars pos &optional (power 1)
                            &aux (m (make-instance 'monom :dimension nvars)))
  "Construct a monomial in the polynomial ring
RING[X[0],X[1],X[2],...X[NVARS-1]] over the (unspecified) ring RING
which represents a single variable. It assumes number of variables
NVARS and the variable is at position POS. Optionally, the variable
may appear raised to power POWER. "
  (declare (type fixnum nvars pos power) (type monom m))
  (with-slots (exponents)
      m
    (setf (elt exponents pos) power)
    m))

(defmethod monom->list ((m monom))
  "A human-readable representation of a monomial M as a list of exponents."  
  (coerce (monom-exponents m) 'list))


;; pure lexicographic
(defgeneric lex> (p q &optional start end)
  (:documentation "Return T if P>Q with respect to lexicographic
order, otherwise NIL.  The second returned value is T if P=Q,
otherwise it is NIL.")
  (:method ((p monom) (q monom) &optional (start 0) (end (monom-dimension  p)))
    (declare (type fixnum start end))
    (do ((i start (1+ i)))
        ((>= i end) (values nil t))
      (cond
        ((> (monom-elt p i) (monom-elt q i))
         (return-from lex> (values t nil)))
        ((< (monom-elt p i) (monom-elt q i))
         (return-from lex> (values nil nil)))))))

;; total degree order, ties broken by lexicographic
(defgeneric grlex> (p q &optional start end)
  (:documentation "Return T if P>Q with respect to graded
lexicographic order, otherwise NIL.  The second returned value is T if
P=Q, otherwise it is NIL.")
  (:method ((p monom) (q monom) &optional (start 0) (end (monom-dimension  p)))
    (declare (type monom p q) (type fixnum start end))
    (let ((d1 (monom-total-degree p start end))
          (d2 (monom-total-degree q start end)))
      (declare (type fixnum d1 d2))
      (cond
        ((> d1 d2) (values t nil))
        ((< d1 d2) (values nil nil))
        (t
         (lex> p q start end))))))

;; reverse lexicographic
(defgeneric revlex> (p q &optional start end)
  (:documentation "Return T if P>Q with respect to reverse
lexicographic order, NIL otherwise.  The second returned value is T if
P=Q, otherwise it is NIL. This is not and admissible monomial order
because some sets do not have a minimal element. This order is useful
in constructing other orders.")
  (:method ((p monom) (q monom) &optional (start 0) (end (monom-dimension  p)))
    (declare (type fixnum start end))
    (do ((i (1- end) (1- i)))
        ((< i start) (values nil t))
      (declare (type fixnum i))
      (cond
        ((< (monom-elt p i) (monom-elt q i))
         (return-from revlex> (values t nil)))
        ((> (monom-elt p i) (monom-elt q i))
         (return-from revlex> (values nil nil)))))))


;; total degree, ties broken by reverse lexicographic
(defgeneric grevlex> (p q &optional start end)
  (:documentation "Return T if P>Q with respect to graded reverse
lexicographic order, NIL otherwise. The second returned value is T if
P=Q, otherwise it is NIL.")
  (:method  ((p monom) (q monom) &optional (start 0) (end (monom-dimension  p)))
    (declare (type fixnum start end))
    (let ((d1 (monom-total-degree p start end))
          (d2 (monom-total-degree q start end)))
      (declare (type fixnum d1 d2))
      (cond
        ((> d1 d2) (values t nil))
        ((< d1 d2) (values nil nil))
        (t
         (revlex> p q start end))))))

(defgeneric invlex> (p q &optional start end)
  (:documentation "Return T if P>Q with respect to inverse
lexicographic order, NIL otherwise The second returned value is T if
P=Q, otherwise it is NIL.")
  (:method ((p monom) (q monom) &optional (start 0) (end (monom-dimension  p)))
    (declare  (type fixnum start end))
    (do ((i (1- end) (1- i)))
        ((< i start) (values nil t))
      (declare (type fixnum i))
      (cond
        ((> (monom-elt p i) (monom-elt q i))
         (return-from invlex> (values t nil)))
        ((< (monom-elt p i) (monom-elt q i))
         (return-from invlex> (values nil nil)))))))

(defun reverse-monomial-order (order)
  "Create the inverse monomial order to the given monomial order ORDER."
  #'(lambda (p q &optional (start 0) (end (monom-dimension q))) 
      (declare (type monom p q) (type fixnum start end))
      (funcall order q p start end)))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Order making functions
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; This returns a closure with the same signature
;; as all orders such as #'LEX>.
(defun make-elimination-order-factory-1 (&optional (secondary-elimination-order #'lex>))
  "It constructs an elimination order used for the 1-st elimination ideal,
i.e. for eliminating the first variable. Thus, the order compares the degrees of the
first variable in P and Q first, with ties broken by SECONDARY-ELIMINATION-ORDER."
  #'(lambda (p q &optional (start 0) (end (monom-dimension p)))
      (declare (type monom p q) (type fixnum start end))
      (cond
        ((> (monom-elt p start) (monom-elt q start))
         (values t nil))
        ((< (monom-elt p start) (monom-elt q start))
         (values nil nil))
        (t 
         (funcall secondary-elimination-order p q (1+ start) end)))))

;; This returns a closure which is called with an integer argument.
;; The result is *another closure* with the same signature as all
;; orders such as #'LEX>.
(defun make-elimination-order-factory (&optional 
                                         (primary-elimination-order #'lex>)
                                         (secondary-elimination-order #'lex>))
  "Return a function with a single integer argument K. This should be
the number of initial K variables X[0],X[1],...,X[K-1], which precede
remaining variables.  The call to the closure creates a predicate
which compares monomials according to the K-th elimination order. The
monomial orders PRIMARY-ELIMINATION-ORDER and
SECONDARY-ELIMINATION-ORDER are used to compare the first K and the
remaining variables, respectively, with ties broken by lexicographical
order. That is, if PRIMARY-ELIMINATION-ORDER yields (VALUES NIL T),
which indicates that the first K variables appear with identical
powers, then the result is that of a call to
SECONDARY-ELIMINATION-ORDER applied to the remaining variables
X[K],X[K+1],..."
  #'(lambda (k) 
      (cond 
        ((<= k 0) 
         (error "K must be at least 1"))
        ((= k 1)
         (make-elimination-order-factory-1 secondary-elimination-order))
        (t
         #'(lambda (p q &optional (start 0) (end (monom-dimension  p)))
             (declare (type monom p q) (type fixnum start end))
             (multiple-value-bind (primary equal)
                 (funcall primary-elimination-order p q start k)
               (if equal
                   (funcall secondary-elimination-order p q k end)
                   (values primary nil))))))))

(defclass term (monom)
  ((coeff :initarg :coeff :accessor term-coeff))
  (:default-initargs :coeff nil)
  (:documentation "Implements a term, i.e. a product of a scalar
and powers of some variables, such as 5*X^2*Y^3."))

(defmethod print-object ((self term) stream)
  (print-unreadable-object (self stream :type t :identity t)
    (with-accessors ((exponents monom-exponents)
                     (coeff term-coeff))
        self
      (format stream "EXPONENTS=~A COEFF=~A"
              exponents coeff))))

(defmethod universal-equalp ((term1 term) (term2 term))
  "Returns T if TERM1 and TERM2 are equal as MONOM, and coefficients
are UNIVERSAL-EQUALP."
  (and (call-next-method)
       (universal-equalp (term-coeff term1) (term-coeff term2))))

(defmethod update-instance-for-different-class :after ((old monom) (new term) &key)
  (setf (term-coeff new) 1))

(defmethod term-multiply-by ((self term) (other term))
  "Destructively multiply terms SELF and OTHER and store the result into SELF.
It returns SELF."
  (setf (term-coeff self) (universal-multiply-by (term-coeff self) (scalar-coeff other))))

(defmethod term-left-tensor-product-by ((self term) (other term))
  (setf (term-coeff self) (universal-multiply-by (term-coeff self) (term-coeff other)))
  (call-next-method))

(defmethod term-right-tensor-product-by ((self term) (other term))
  (setf (term-coeff self) (multiply-by (term-coeff self) (term-coeff other)))
  (call-next-method))

(defmethod monom-divide-by ((self term) (other term))
  "Destructively divide term SELF by OTHER and store the result into SELF.
It returns SELF."
  (setf (term-coeff self) (divide-by (term-coeff self) (term-coeff other)))
  (call-next-method))

(defmethod monom-unary-minus ((self term))
  (setf (term-coeff self) (monom-unary-minus (term-coeff self)))
  self)

(defmethod monom-multiply ((term1 term) (term2 term))
  "Non-destructively multiply TERM1 by TERM2."
  (monom-multiply-by (copy-instance term1) (copy-instance term2)))

(defmethod monom-multiply ((term1 number) (term2 monom))
  "Non-destructively multiply TERM1 by TERM2."
  (monom-multiply term1 (change-class (copy-instance term2) 'term)))

(defmethod monom-zerop ((self term))
  (zerop (term-coeff self)))