source: branches/f4grobner/polynomial.lisp@ 3089

;;; -*-  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 "POLYNOMIAL"
  (:use :cl :utils :ring :monom :order :term #| :infix |# )
  (:export "POLY"
           "POLY-TERMLIST"
           "POLY-TERM-ORDER"
           "CHANGE-TERM-ORDER"
           "SATURATION-EXTENSION")
  (:documentation "Implements polynomials"))

(in-package :polynomial)

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

(defclass poly ()
  ((termlist :initarg :termlist :accessor poly-termlist
             :documentation "List of terms.")
   (order :initarg :order :accessor poly-term-order
          :documentation "Monomial/term order."))
  (:default-initargs :termlist nil :order #'lex>)
  (:documentation "A polynomial with a list of terms TERMLIST, ordered
according to term order ORDER, which defaults to LEX>."))

(defmethod print-object ((self poly) stream)
  (format stream "#<POLY TERMLIST=~A ORDER=~A>" 
          (poly-termlist self)
          (poly-term-order self)))

(defgeneric change-term-order (self other)
  (:documentation "Change term order of SELF to the term order of OTHER.")
  (:method ((self poly) (other poly))
    (unless (eq (poly-term-order self) (poly-term-order other))
      (setf (poly-termlist self) (sort (poly-termlist self) (poly-term-order other))
            (poly-term-order self) (poly-term-order other)))
    self))

(defmethod r-equalp ((self poly) (other poly))
  "POLY instances are R-EQUALP if they have the same
order and if all terms are R-EQUALP."
  (and (every #'r-equalp (poly-termlist self) (poly-termlist other))
       (eq (poly-term-order self) (poly-term-order other))))

(defmethod insert-item ((self poly) (item term))
  (push item (poly-termlist self))
  self)

(defmethod append-item ((self poly) (item term))
  (setf (cdr (last (poly-termlist self))) (list item))
  self)

;; Leading term
(defgeneric leading-term (object)
  (:method ((self poly)) 
    (car (poly-termlist self)))
  (:documentation "The leading term of a polynomial, or NIL for zero polynomial."))

;; Second term
(defgeneric second-leading-term (object) 
  (:method ((self poly))
    (cadar (poly-termlist self)))
  (:documentation "The second leading term of a polynomial, or NIL for a polynomial with at most one term."))

;; Leading coefficient
(defgeneric leading-coefficient (object)
  (:method ((self poly))
    (r-coeff (leading-term self)))
  (:documentation "The leading coefficient of a polynomial. It signals error for a zero polynomial."))

;; Second coefficient
(defgeneric second-leading-coefficient (object)
  (:method ((self poly)) 
    (r-coeff (second-leading-term self)))
  (:documentation "The second leading coefficient of a polynomial. It
  signals error for a polynomial with at most one term."))

;; Testing for a zero polynomial
(defmethod r-zerop ((self poly))
  (null (poly-termlist self)))

;; The number of terms
(defmethod r-length ((self poly))
  (length (poly-termlist self)))

(defmethod multiply-by ((self poly) (other monom))
  (mapc #'(lambda (term) (multiply-by term other))
        (poly-termlist self))
  self)

(defmethod multiply-by ((self poly) (other scalar))
  (mapc #'(lambda (term) (multiply-by term other))
        (poly-termlist self))
  self)


(defmacro fast-add/subtract (p q order-fn add/subtract-fn uminus-fn)
  "Return an expression which will efficiently adds/subtracts two
polynomials, P and Q.  The addition/subtraction of coefficients is
performed by calling ADD/SUBTRACT-METHOD-NAME.  If UMINUS-METHOD-NAME
is supplied, it is used to negate the coefficients of Q which do not
have a corresponding coefficient in P. The code implements an
efficient algorithm to add two polynomials represented as sorted lists
of terms. The code destroys both arguments, reusing the terms to build
the result."
  `(macrolet ((lc (x) `(r-coeff (car ,x))))
     (do ((p ,p)
          (q ,q)
          r)
         ((or (endp p) (endp q))
          ;; NOTE: R contains the result in reverse order. Can it
          ;; be more efficient to produce the terms in correct order?
          (unless (endp q) 
            ;; Upon subtraction, we must change the sign of
            ;; all coefficients in q
            ,@(when uminus-fn
                    `((mapc #'(lambda (x) (setf x (funcall ,uminus-fn x))) q)))
            (setf r (nreconc r q)))
          r)
       (multiple-value-bind 
             (greater-p equal-p)
           (funcall ,order-fn (car p) (car q))
         (cond
           (greater-p
            (rotatef (cdr p) r p)
            )
           (equal-p
            (let ((s (funcall ,add/subtract-fn (lc p) (lc q))))
              (cond 
                ((r-zerop s)
                 (setf p (cdr p))
                 )
                (t 
                 (setf (lc p) s)
                 (rotatef (cdr p) r p))))
            (setf q (cdr q))
            )
           (t 
            ;;Negate the term of Q if UMINUS provided, signallig
            ;;that we are doing subtraction
            ,(when uminus-fn
                   `(setf (lc q) (funcall ,uminus-fn (lc q))))
            (rotatef (cdr q) r q)))))))


(defmacro def-add/subtract-method (add/subtract-method-name
                                   uminus-method-name
                                   &optional
                                     (doc-string nil doc-string-supplied-p))
  "This macro avoids code duplication for two similar operations: ADD-TO and SUBTRACT-FROM."
  `(defmethod ,add/subtract-method-name ((self poly) (other poly))
     ,@(when doc-string-supplied-p `(,doc-string))
     ;; Ensure orders are compatible
     (change-term-order other self)
     (setf (poly-termlist self) (fast-add/subtract 
                                 (poly-termlist self) (poly-termlist other)
                                 (poly-term-order self)
                                 #',add/subtract-method-name
                                 ,(when uminus-method-name `(function ,uminus-method-name))))
     self))

(eval-when (:compile-toplevel :load-toplevel :execute)

  (def-add/subtract-method add-to nil
    "Adds to polynomial SELF another polynomial OTHER.
This operation destructively modifies both polynomials.
The result is stored in SELF. This implementation does
no consing, entirely reusing the sells of SELF and OTHER.")

  (def-add/subtract-method subtract-from unary-minus
    "Subtracts from polynomial SELF another polynomial OTHER.
This operation destructively modifies both polynomials.
The result is stored in SELF. This implementation does
no consing, entirely reusing the sells of SELF and OTHER.")

  )



(defmethod unary-minus ((self poly))
  "Destructively modifies the coefficients of the polynomial SELF,
by changing their sign."
  (mapc #'unary-minus (poly-termlist self))
  self)

(defun add-termlists (p q order-fn)
  "Destructively adds two termlists P and Q ordered according to ORDER-FN."
  (fast-add/subtract p q order-fn #'add-to nil))

(defmacro multiply-term-by-termlist-dropping-zeros (term termlist 
                                                    &optional (reverse-arg-order-P nil))
  "Multiplies term TERM by a list of term, TERMLIST.
Takes into accound divisors of zero in the ring, by
deleting zero terms. Optionally, if REVERSE-ARG-ORDER-P
is T, change the order of arguments; this may be important
if we extend the package to non-commutative rings."
  `(mapcan #'(lambda (other-term) 
               (let ((prod (r*
                            ,@(cond 
                               (reverse-arg-order-p
                                `(other-term ,term))
                               (t 
                                `(,term other-term))))))
                 (cond 
                   ((r-zerop prod) nil)
                   (t (list prod)))))
           ,termlist))

(defun multiply-termlists (p q order-fn)
  (cond 
    ((or (endp p) (endp q))         
     ;;p or q is 0 (represented by NIL)
     nil)       
    ;; If p= p0+p1 and q=q0+q1 then p*q=p0*q0+p0*q1+p1*q
    ((endp (cdr p))
     (multiply-term-by-termlist-dropping-zeros (car p) q))
    ((endp (cdr q))
     (multiply-term-by-termlist-dropping-zeros (car q) p t))
    (t
     (cons (r* (car p) (car q))
           (add-termlists 
            (multiply-term-by-termlist-dropping-zeros (car p) (cdr q))
            (multiply-termlists (cdr p) q order-fn)
            order-fn)))))

(defmethod multiply-by ((self poly) (other poly))
  (change-term-order other self)
  (setf (poly-termlist self) (multiply-termlists (poly-termlist self)
                                                 (poly-termlist other)
                                                 (poly-term-order self)))
  self)

(defmethod r* ((poly1 poly) (poly2 poly))
  "Non-destructively multiply POLY1 by POLY2."
  (multiply-by (copy-instance POLY1) (copy-instance POLY2)))

(defmethod left-tensor-product-by ((self poly) (other term))
  (setf (poly-termlist self) 
        (mapcan #'(lambda (term) 
                    (let ((prod (left-tensor-product-by term other)))
                      (cond 
                        ((r-zerop prod) nil)
                        (t (list prod)))))
                (poly-termlist self)))
  self)

(defmethod right-tensor-product-by ((self poly) (other term))
  (setf (poly-termlist self) 
        (mapcan #'(lambda (term) 
                    (let ((prod (right-tensor-product-by term other)))
                      (cond 
                        ((r-zerop prod) nil)
                        (t (list prod)))))
                (poly-termlist self)))
  self)

(defmethod left-tensor-product-by ((self poly) (other monom))
  (setf (poly-termlist self) 
        (mapcan #'(lambda (term) 
                    (let ((prod (left-tensor-product-by term other)))
                      (cond 
                        ((r-zerop prod) nil)
                        (t (list prod)))))
                (poly-termlist self)))
  self)

(defmethod right-tensor-product-by ((self poly) (other monom))
  (setf (poly-termlist self) 
        (mapcan #'(lambda (term) 
                    (let ((prod (right-tensor-product-by term other)))
                      (cond 
                        ((r-zerop prod) nil)
                        (t (list prod)))))
                (poly-termlist self)))
  self)


(defun standard-extension (plist &aux (k (length plist)) (i 0))
  "Calculate [U1*P1,U2*P2,...,UK*PK], where PLIST=[P1,P2,...,PK]
is a list of polynomials. Destructively modifies PLIST elements."
  (mapc #'(lambda (poly)
            (left-tensor-product-by 
             poly 
             (prog1 
                 (make-monom-variable k i) 
               (incf i))))
        plist))

(defmethod poly-dimension ((poly poly))
  (cond ((r-zerop poly) -1)
        (t (monom-dimension (leading-term poly)))))

(defun standard-extension-1 (plist 
                             &aux 
                               (k (length plist))
                               (plist (poly-standard-extension plist))
                               (nvars (poly-dimension (car plist))))
  "Calculate [U1*P1-1,U2*P2-1,...,UK*PK-1], where PLIST=[P1,P2,...,PK].
Firstly, new K variables U1, U2, ..., UK, are inserted into each
polynomial.  Subsequently, P1, P2, ..., PK are destructively modified
tantamount to replacing PI with UI*PI-1."
  ;; Implementation note: we use STANDARD-EXTENSION and then subtract
  ;; 1 from each polynomial; since UI*PI has no constant term,
  ;; we just need to append the constant term at the end
  ;; of each termlist.
  (flet ((subtract-1 (p) 
           (append-item p (make-instance 'term :coeff -1 :dimension (+ k nvars)))))
    (setf plist (mapc #'subtract-1 plist)))
  plist)


(defun standard-sum (F plist 
                                 &aux 
                                   (k (length plist))
                                   (d (+ k (monom-dimension (poly-lt (car plist)))))
                                   ;; Add k variables to f
                                   (f (poly-list-add-variables f k))
                                   ;; Set PLIST to [U1*P1,U2*P2,...,UK*PK]
                                   (plist (apply #'nconc (poly-standard-extension plist))))
  "Calculate the polynomial U1*P1+U2*P2+...+UK*PK-1, where PLIST=[P1,P2,...,PK].
Firstly, new K variables, U1, U2, ..., UK, are inserted into each
polynomial.  Subsequently, P1, P2, ..., PK are destructively modified
tantamount to replacing PI with UI*PI, and the resulting polynomials
are added.  It should be noted that the term order is not modified,
which is equivalent to using a lexicographic order on the first K
variables."
  (setf (cdr (last (poly-termlist plist)))
        ;; Add -1 as the last term
        (list (make-term :monom (make-monom :dimension d)
                         :coeff (funcall (ring-uminus ring) (funcall (ring-unit ring))))))
  (append f (list plist)))

#|


(defun saturation-extension-1 (ring f p) 
  "Calculate [F, U*P-1]. It destructively modifies F."
  (declare (type ring ring))
  (polysaturation-extension ring f (list p)))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Evaluation of polynomial (prefix) expressions
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defun coerce-coeff (ring expr vars)
  "Coerce an element of the coefficient ring to a constant polynomial."
  ;; Modular arithmetic handler by rat
  (declare (type ring ring))
  (make-poly-from-termlist (list (make-term :monom (make-monom :dimension (length vars))
                                            :coeff (funcall (ring-parse ring) expr)))
                           0))

(defun poly-eval (expr vars 
                  &optional 
                    (ring +ring-of-integers+) 
                    (order #'lex>)
                    (list-marker :[)
                  &aux 
                    (ring-and-order (make-ring-and-order :ring ring :order order)))
  "Evaluate Lisp form EXPR to a polynomial or a list of polynomials in
variables VARS. Return the resulting polynomial or list of
polynomials.  Standard arithmetical operators in form EXPR are
replaced with their analogues in the ring of polynomials, and the
resulting expression is evaluated, resulting in a polynomial or a list
of polynomials in internal form. A similar operation in another computer
algebra system could be called 'expand' or so."
  (declare (type ring ring))
  (labels ((p-eval (arg) (poly-eval arg vars ring order))
           (p-eval-scalar (arg) (poly-eval-scalar arg))
           (p-eval-list (args) (mapcar #'p-eval args))
           (p-add (x y) (poly-add ring-and-order x y)))
    (cond
      ((null expr) (error "Empty expression"))
      ((eql expr 0) (make-poly-zero))
      ((member expr vars :test #'equalp)
       (let ((pos (position expr vars :test #'equalp)))
         (make-poly-variable ring (length vars) pos)))
      ((atom expr)
       (coerce-coeff ring expr vars))
      ((eq (car expr) list-marker)
       (cons list-marker (p-eval-list (cdr expr))))
      (t
       (case (car expr)
         (+ (reduce #'p-add (p-eval-list (cdr expr))))
         (- (case (length expr)
              (1 (make-poly-zero))
              (2 (poly-uminus ring (p-eval (cadr expr))))
              (3 (poly-sub ring-and-order (p-eval (cadr expr)) (p-eval (caddr expr))))
              (otherwise (poly-sub ring-and-order (p-eval (cadr expr))
                                   (reduce #'p-add (p-eval-list (cddr expr)))))))
         (*
          (if (endp (cddr expr))                ;unary
              (p-eval (cdr expr))
              (reduce #'(lambda (p q) (poly-mul ring-and-order p q)) (p-eval-list (cdr expr)))))
         (/ 
          ;; A polynomial can be divided by a scalar
          (cond 
            ((endp (cddr expr))
             ;; A special case (/ ?), the inverse
             (coerce-coeff ring (apply (ring-div ring) (cdr expr)) vars))
            (t
             (let ((num (p-eval (cadr expr)))
                   (denom-inverse (apply (ring-div ring)
                                         (cons (funcall (ring-unit ring)) 
                                               (mapcar #'p-eval-scalar (cddr expr))))))
               (scalar-times-poly ring denom-inverse num)))))
         (expt
          (cond
            ((member (cadr expr) vars :test #'equalp)
             ;;Special handling of (expt var pow)
             (let ((pos (position (cadr expr) vars :test #'equalp)))
               (make-poly-variable ring (length vars) pos (caddr expr))))
            ((not (and (integerp (caddr expr)) (plusp (caddr expr))))
             ;; Negative power means division in coefficient ring
             ;; Non-integer power means non-polynomial coefficient
             (coerce-coeff ring expr vars))
            (t (poly-expt ring-and-order (p-eval (cadr expr)) (caddr expr)))))
         (otherwise
          (coerce-coeff ring expr vars)))))))

(defun poly-eval-scalar (expr 
                         &optional
                           (ring +ring-of-integers+)
                         &aux 
                           (order #'lex>))
  "Evaluate a scalar expression EXPR in ring RING."
  (declare (type ring ring))
  (poly-lc (poly-eval expr nil ring order)))

(defun spoly (ring-and-order f g
              &aux
                (ring (ro-ring ring-and-order)))
  "It yields the S-polynomial of polynomials F and G."
  (declare (type ring-and-order ring-and-order) (type poly f g))
  (let* ((lcm (monom-lcm (poly-lm f) (poly-lm g)))
         (mf (monom-div lcm (poly-lm f)))
         (mg (monom-div lcm (poly-lm g))))
    (declare (type monom mf mg))
    (multiple-value-bind (c cf cg)
        (funcall (ring-ezgcd ring) (poly-lc f) (poly-lc g))
      (declare (ignore c))
      (poly-sub 
       ring-and-order
       (scalar-times-poly ring cg (monom-times-poly mf f))
       (scalar-times-poly ring cf (monom-times-poly mg g))))))


(defun poly-primitive-part (ring p)
  "Divide polynomial P with integer coefficients by gcd of its
coefficients and return the result."
  (declare (type ring ring) (type poly p))
  (if (poly-zerop p)
      (values p 1)
      (let ((c (poly-content ring p)))
        (values (make-poly-from-termlist 
                 (mapcar
                  #'(lambda (x)
                      (make-term :monom (term-monom x)
                                 :coeff (funcall (ring-div ring) (term-coeff x) c)))
                  (poly-termlist p))
                 (poly-sugar p))
                c))))

(defun poly-content (ring p)
  "Greatest common divisor of the coefficients of the polynomial P. Use the RING structure
to compute the greatest common divisor."
  (declare (type ring ring) (type poly p))
  (reduce (ring-gcd ring) (mapcar #'term-coeff (rest (poly-termlist p))) :initial-value (poly-lc p)))

(defun read-infix-form (&key (stream t))
  "Parser of infix expressions with integer/rational coefficients
The parser will recognize two kinds of polynomial expressions:

- polynomials in fully expanded forms with coefficients
  written in front of symbolic expressions; constants can be optionally
  enclosed in (); for example, the infix form
        X^2-Y^2+(-4/3)*U^2*W^3-5
  parses to
        (+ (- (EXPT X 2) (EXPT Y 2)) (* (- (/ 4 3)) (EXPT U 2) (EXPT W 3)) (- 5))

- lists of polynomials; for example
        [X-Y, X^2+3*Z]          
  parses to
          (:[ (- X Y) (+ (EXPT X 2) (* 3 Z)))
  where the first symbol [ marks a list of polynomials.

-other infix expressions, for example
        [(X-Y)*(X+Y)/Z,(X+1)^2]
parses to:
        (:[ (/ (* (- X Y) (+ X Y)) Z) (EXPT (+ X 1) 2))
Currently this function is implemented using M. Kantrowitz's INFIX package."
  (read-from-string
   (concatenate 'string
                "#I(" 
                (with-output-to-string (s)
                  (loop
                     (multiple-value-bind (line eof)
                         (read-line stream t)
                       (format s "~A" line)
                       (when eof (return)))))
                ")")))

(defun read-poly (vars &key
                         (stream t) 
                         (ring +ring-of-integers+) 
                         (order #'lex>))
  "Reads an expression in prefix form from a stream STREAM.
The expression read from the strem should represent a polynomial or a
list of polynomials in variables VARS, over the ring RING.  The
polynomial or list of polynomials is returned, with terms in each
polynomial ordered according to monomial order ORDER."
  (poly-eval (read-infix-form :stream stream) vars ring order))

(defun string->poly (str vars 
                     &optional
                       (ring +ring-of-integers+) 
                       (order #'lex>))
  "Converts a string STR to a polynomial in variables VARS."
  (with-input-from-string (s str)
    (read-poly vars :stream s :ring ring :order order)))

(defun poly->alist (p)
  "Convert a polynomial P to an association list. Thus, the format of the
returned value is  ((MONOM[0] . COEFF[0]) (MONOM[1] . COEFF[1]) ...), where
MONOM[I] is a list of exponents in the monomial and COEFF[I] is the
corresponding coefficient in the ring."
  (cond
    ((poly-p p)
     (mapcar #'term->cons (poly-termlist p)))
    ((and (consp p) (eq (car p) :[))
     (cons :[ (mapcar #'poly->alist (cdr p))))))

(defun string->alist (str vars
                      &optional
                        (ring +ring-of-integers+) 
                        (order #'lex>))
  "Convert a string STR representing a polynomial or polynomial list to
an association list (... (MONOM . COEFF) ...)."
  (poly->alist (string->poly str vars ring order)))

(defun poly-equal-no-sugar-p (p q)
  "Compare polynomials for equality, ignoring sugar."
  (declare (type poly p q))
  (equalp (poly-termlist p) (poly-termlist q)))

(defun poly-set-equal-no-sugar-p (p q)
  "Compare polynomial sets P and Q for equality, ignoring sugar."
  (null (set-exclusive-or  p q :test #'poly-equal-no-sugar-p )))

(defun poly-list-equal-no-sugar-p (p q)
  "Compare polynomial lists P and Q for equality, ignoring sugar."
  (every #'poly-equal-no-sugar-p p q))
|#