close Warning: Can't synchronize with repository "(default)" (The repository directory has changed, you should resynchronize the repository with: trac-admin $ENV repository resync '(default)'). Look in the Trac log for more information.

source: branches/f4grobner/polynomial.lisp@ 4437

Last change on this file since 4437 was 4436, checked in by Marek Rychlik, 8 years ago

* empty log message *

File size: 24.2 KB
Line 
1;;----------------------------------------------------------------
2;;; -*- Mode: Lisp -*-
3;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
4;;;
5;;; Copyright (C) 1999, 2002, 2009, 2015 Marek Rychlik <rychlik@u.arizona.edu>
6;;;
7;;; This program is free software; you can redistribute it and/or modify
8;;; it under the terms of the GNU General Public License as published by
9;;; the Free Software Foundation; either version 2 of the License, or
10;;; (at your option) any later version.
11;;;
12;;; This program is distributed in the hope that it will be useful,
13;;; but WITHOUT ANY WARRANTY; without even the implied warranty of
14;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15;;; GNU General Public License for more details.
16;;;
17;;; You should have received a copy of the GNU General Public License
18;;; along with this program; if not, write to the Free Software
19;;; Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
20;;;
21;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
22
23(defpackage "POLYNOMIAL"
24 (:use :cl :utils :monom :copy :ring)
25 (:export "POLY"
26 "POLY-DIMENSION"
27 "POLY-TERMLIST"
28 "POLY-TERM-ORDER"
29 "POLY-INSERT-TERM"
30 "SCALAR-MULTIPLY-BY"
31 "SCALAR-DIVIDE-BY"
32 "LEADING-TERM"
33 "LEADING-MONOMIAL"
34 "LEADING-COEFFICIENT"
35 "SECOND-LEADING-TERM"
36 "SECOND-LEADING-MONOMIAL"
37 "SECOND-LEADING-COEFFICIENT"
38 "ADD-TO"
39 "ADD"
40 "SUBTRACT-FROM"
41 "SUBTRACT"
42 "CHANGE-TERM-ORDER"
43 "STANDARD-EXTENSION"
44 "STANDARD-EXTENSION-1"
45 "STANDARD-SUM"
46 "SATURATION-EXTENSION"
47 "ALIST->POLY"
48 "->INFIX"
49 "UNIVERSAL-EZGCD"
50 "S-POLYNOMIAL"
51 "POLY-CONTENT"
52 "POLY-PRIMITIVE-PART"
53 "SATURATION-EXTENSION-1"
54 "MAKE-POLY-VARIABLE"
55 "MAKE-POLY-CONSTANT"
56 "MAKE-ZERO-FOR"
57 "MAKE-UNIT-FOR"
58 "UNIVERSAL-EXPT"
59 "UNIVERSAL-EQUALP"
60 "UNIVERSAL-ZEROP"
61 "POLY-LENGTH"
62 "POLY-REVERSE"
63 "POLY-P"
64 "+LIST-MARKER+"
65 "POLY-EVAL"
66 "*COEFFICIENT-CLASS*")
67 (:documentation "Implements polynomials. A polynomial is essentially
68a mapping of monomials of the same degree to coefficients. The
69momomials are ordered according to a monomial order."))
70
71(in-package :polynomial)
72
73(proclaim '(optimize (speed 3) (space 0) (safety 0) (debug 0)))
74
75(defclass poly (ring)
76 ((dimension :initform nil
77 :initarg :dimension
78 :accessor poly-dimension
79 :documentation "Shared dimension of all terms, the number of variables")
80 (termlist :initform nil :initarg :termlist :accessor poly-termlist
81 :documentation "List of terms.")
82 (order :initform #'lex> :initarg :order :accessor poly-term-order
83 :documentation "Monomial/term order."))
84 (:default-initargs :dimension nil :termlist nil :order #'lex>)
85 (:documentation "A polynomial with a list of terms TERMLIST, ordered
86according to term order ORDER, which defaults to LEX>."))
87
88(defmethod print-object ((self poly) stream)
89 (print-unreadable-object (self stream :type t :identity t)
90 (with-accessors ((dimension poly-dimension)
91 (termlist poly-termlist)
92 (order poly-term-order))
93 self
94 (format stream "DIMENSION=~A TERMLIST=~A ORDER=~A"
95 dimension termlist order))))
96
97(defmethod copy-instance :around ((object poly) &rest initargs &key &allow-other-keys)
98 "Returns a deep copy of the polynomial POLY, by copying the TERMLIST and its terms."
99 (declare (ignore object initargs))
100 (let ((copy (call-next-method)))
101 (with-slots (termlist)
102 copy
103 (setf termlist (mapcar #'copy-instance termlist)))
104 copy))
105
106
107(defgeneric change-term-order (self other)
108 (:documentation "Change term order of SELF to the term order of OTHER.")
109 (:method ((self poly) (other poly))
110 (unless (eq (poly-term-order self) (poly-term-order other))
111 (setf (poly-termlist self) (sort (poly-termlist self) (poly-term-order other))
112 (poly-term-order self) (poly-term-order other)))
113 self))
114
115(defgeneric poly-insert-term (self term)
116 (:documentation "Insert a term TERM into SELF before all other
117terms. Order is not enforced.")
118 (:method ((self poly) (term term))
119 (cond ((null (poly-dimension self))
120 (setf (poly-dimension self) (monom-dimension term)))
121 (t (assert (= (poly-dimension self) (monom-dimension term)))))
122 (push term (poly-termlist self))
123 self))
124
125(defgeneric poly-append-term (self term)
126 (:documentation "Append a term TERM to SELF after all other terms. Order is not enforced.")
127 (:method ((self poly) (term term))
128 (cond ((null (poly-dimension self))
129 (setf (poly-dimension self) (monom-dimension term)))
130 (t (assert (= (poly-dimension self) (monom-dimension term)))))
131 (setf (cdr (last (poly-termlist self))) (list term))
132 self))
133
134(defun alist->poly (alist &aux (poly (make-instance 'poly)))
135 "It reads polynomial from an alist formatted as ( ... (exponents . coeff) ...).
136It can be used to enter simple polynomials by hand, e.g the polynomial
137in two variables, X and Y, given in standard notation as:
138
139 3*X^2*Y^3+2*Y+7
140
141can be entered as
142(ALIST->POLY '(((2 3) . 3) ((0 1) . 2) ((0 0) . 7))).
143
144NOTE: The primary use is for low-level debugging of the package."
145 (dolist (x alist poly)
146 (poly-insert-term poly (make-instance 'term :exponents (car x) :coeff (cdr x)))))
147
148(defmethod update-instance-for-different-class :after ((old term) (new poly) &key)
149 "Converts OLD of class TERM to a NEW of class POLY, by making it into a 1-element TERMLIST."
150 (reinitialize-instance new
151 :dimension (monom-dimension old)
152 :termlist (list old)))
153
154(defmethod update-instance-for-different-class :after ((old monom) (new poly) &key)
155 "Converts OLD of class MONOM to a NEW of class POLY, by making it into a 1-element TERMLIST."
156 (reinitialize-instance new
157 :dimension (monom-dimension old)
158 :termlist (list (change-class old 'term))))
159
160(defmethod universal-equalp ((self poly) (other poly))
161 "Implements equality of polynomials."
162 (and (eql (poly-dimension self) (poly-dimension other))
163 (every #'universal-equalp (poly-termlist self) (poly-termlist other))
164 (eq (poly-term-order self) (poly-term-order other))))
165
166(defgeneric leading-term (object)
167 (:method ((self poly))
168 (car (poly-termlist self)))
169 (:documentation "The leading term of a polynomial, or NIL for zero polynomial."))
170
171(defgeneric second-leading-term (object)
172 (:method ((self poly))
173 (cadar (poly-termlist self)))
174 (:documentation "The second leading term of a polynomial, or NIL for a polynomial with at most one term."))
175
176(defgeneric leading-monomial (object)
177 (:method ((self poly))
178 (change-class (copy-instance (leading-term self)) 'monom))
179 (:documentation "The leading monomial of a polynomial, or NIL for zero polynomial."))
180
181(defgeneric second-leading-monomial (object)
182 (:method ((self poly))
183 (change-class (copy-instance (second-leading-term self)) 'monom))
184 (:documentation "The leading monomial of a polynomial, or NIL for zero polynomial."))
185
186(defgeneric leading-coefficient (object)
187 (:method ((self poly))
188 (term-coeff (leading-term self)))
189 (:documentation "The leading coefficient of a polynomial. It signals error for a zero polynomial."))
190
191(defgeneric second-leading-coefficient (object)
192 (:method ((self poly))
193 (term-coeff (second-leading-term self)))
194 (:documentation "The second leading coefficient of a polynomial. It
195 signals error for a polynomial with at most one term."))
196
197(defmethod universal-zerop ((self poly))
198 "Return T iff SELF is a zero polynomial."
199 (null (poly-termlist self)))
200
201(defgeneric poly-length (self)
202 (:documentation "Return the number of terms.")
203 (:method ((self poly))
204 (length (poly-termlist self))))
205
206(defgeneric scalar-multiply-by (self other)
207 (:documentation "Multiply vector SELF by a scalar OTHER.")
208 (:method ((self poly) other)
209 (mapc #'(lambda (term) (setf (term-coeff term) (multiply-by (term-coeff term) other)))
210 (poly-termlist self))
211 self))
212
213(defgeneric scalar-divide-by (self other)
214 (:documentation "Divide vector SELF by a scalar OTHER.")
215 (:method ((self poly) other)
216 (mapc #'(lambda (term) (setf (term-coeff term) (divide-by (term-coeff term) other)))
217 (poly-termlist self))
218 self))
219
220(defmethod unary-inverse :before ((self poly))
221 "Checks invertibility of a polynomial SELF. To be invertable, the
222polynomial must be an invertible, constant polynomial."
223 (with-slots (termlist)
224 self
225 (assert (and (= (length termlist) 1) (zerop (total-degree (car termlist))))
226 nil
227 "To be invertible, the polynomial must have 1 term of total degree 0.")))
228
229(defmethod unary-inverse ((self poly))
230 "Returns the unary inverse of a polynomial SELF."
231 (with-slots (termlist)
232 self
233 (setf (car termlist) (unary-inverse (car termlist)))
234 self))
235
236(defmethod multiply-by ((self poly) (other monom))
237 "Multiply a polynomial SELF by OTHER."
238 (mapc #'(lambda (term) (multiply-by term other))
239 (poly-termlist self))
240 self)
241
242(defmethod multiply-by ((self poly) (other term))
243 "Multiply a polynomial SELF by OTHER."
244 (mapc #'(lambda (term) (multiply-by term other))
245 (poly-termlist self))
246 self)
247
248#|
249(defmacro fast-add/subtract (p q order-fn add/subtract-fn uminus-fn)
250 "Return an expression which will efficiently adds/subtracts two
251polynomials, P and Q. The addition/subtraction of coefficients is
252performed by calling ADD/SUBTRACT-FN. If UMINUS-FN is supplied, it is
253used to negate the coefficients of Q which do not have a corresponding
254coefficient in P. The code implements an efficient algorithm to add
255two polynomials represented as sorted lists of terms. The code
256destroys both arguments, reusing the terms to build the result."
257 `(macrolet ((lc (x) `(term-coeff (car ,x))))
258 (do ((p ,p)
259 (q ,q)
260 r)
261 ((or (endp p) (endp q))
262 ;; NOTE: R contains the result in reverse order. Can it
263 ;; be more efficient to produce the terms in correct order?
264 (unless (endp q)
265 ;; Upon subtraction, we must change the sign of
266 ;; all coefficients in q
267 ,@(when uminus-fn
268 `((mapc #'(lambda (x) (setf x (funcall ,uminus-fn x))) q)))
269 (setf r (nreconc r q)))
270 (unless (endp p)
271 (setf r (nreconc r p)))
272 r)
273 (multiple-value-bind
274 (greater-p equal-p)
275 (funcall ,order-fn (car p) (car q))
276 (cond
277 (greater-p
278 (rotatef (cdr p) r p)
279 )
280 (equal-p
281 (let ((s (funcall ,add/subtract-fn (lc p) (lc q))))
282 (cond
283 ((universal-zerop s)
284 (setf p (cdr p))
285 )
286 (t
287 (setf (lc p) s)
288 (rotatef (cdr p) r p))))
289 (setf q (cdr q))
290 )
291 (t
292 ;;Negate the term of Q if UMINUS provided, signallig
293 ;;that we are doing subtraction
294 ,(when uminus-fn
295 `(setf (lc q) (funcall ,uminus-fn (lc q))))
296 (rotatef (cdr q) r q))))
297 ;;(format t "P:~A~%" p)
298 ;;(format t "Q:~A~%" q)
299 ;;(format t "R:~A~%" r)
300 )))
301|#
302
303
304
305
306#|
307(defun fast-add (p q order-fn add-fn)
308 "Add two polynomials, P and Q, represented as lists of terms.
309The operation is destructive to both polynomials, as the terms
310of both lists are combined into the result. The operation does not
311create any new instance of TERM."
312 (macrolet ((lc (x) `(term-coeff (car ,x))))
313 (do (r)
314 ((or (endp p) (endp q))
315 ;; NOTE: R contains the result in reverse order. Can it
316 ;; be more efficient to produce the terms in correct order?
317 (unless (endp q)
318 (setf r (nreconc r q)))
319 (unless (endp p)
320 (setf r (nreconc r p)))
321 r)
322 (multiple-value-bind
323 (greater-p equal-p)
324 (funcall order-fn (car p) (car q))
325 (cond
326 (greater-p
327 (rotatef (cdr p) r p)
328 )
329 (equal-p
330 (let ((s (funcall add-fn (lc p) (lc q))))
331 (cond
332 ((universal-zerop s)
333 (setf p (cdr p))
334 )
335 (t
336 (setf (lc p) s)
337 (rotatef (cdr p) r p))))
338 (setf q (cdr q))
339 )
340 (t
341 (rotatef (cdr q) r q)))))))
342|#
343
344;; Getter/setter of leading coefficient
345(defun lc (x) (term-coeff (car x)))
346(defun (setf lc) (new-value x) (setf (term-coeff (car x)) new-value))
347
348(defun fast-add (p q order-fn add-fn)
349 (cond
350 ((endp p) q)
351 ((endp q) p)
352 (t
353 (multiple-value-bind
354 (greater-p equal-p)
355 (funcall order-fn (car p) (car q))
356 (cond
357 (greater-p ; (> (cadr h) (car q))
358 (cons (car p) (fast-add (cdr p) q order-fn add-fn))
359 )
360 (equal-p ; (= (cadr h)) (car q))
361 (let ((s (funcall add-fn (lc p) (lc q))))
362 (cond
363 ((universal-zerop s)
364 (fast-add (cdr p) (cdr q) order-fn add-fn))
365 (t
366 ;; Adjust the lc of p
367 (setf (lc p) s)
368 (cons (car p) (fast-add (cdr p) (cdr q) order-fn add-fn))
369 ))))
370 (t ;(< (cadr h) (car q))
371 (cons (car q) (fast-add p (cdr q) order-fn add-fn))
372 ))))))
373
374
375
376#|
377;; NOTE: The stuff below works, but may not be worth the trouble.
378
379(defmacro def-add/subtract-method (add/subtract-method-name
380 uminus-method-name
381 &optional
382 (doc-string nil doc-string-supplied-p))
383 "This macro avoids code duplication for two similar operations: ADD-TO and SUBTRACT-FROM."
384 `(defmethod ,add/subtract-method-name ((self poly) (other poly))
385 ,@(when doc-string-supplied-p `(,doc-string))
386 ;; Ensure orders are compatible
387 (change-term-order other self)
388 (setf (poly-termlist self) (fast-add/subtract
389 (poly-termlist self) (poly-termlist other)
390 (poly-term-order self)
391 #',add/subtract-method-name
392 ,(when uminus-method-name `(function ,uminus-method-name))))
393 self))
394
395(eval-when (:load-toplevel :execute)
396
397 (def-add/subtract-method add-to nil
398 "Adds to polynomial SELF another polynomial OTHER.
399This operation destructively modifies both polynomials.
400The result is stored in SELF. This implementation does
401no consing, entirely reusing the sells of SELF and OTHER.")
402
403 (def-add/subtract-method subtract-from unary-minus
404 "Subtracts from polynomial SELF another polynomial OTHER.
405This operation destructively modifies both polynomials.
406The result is stored in SELF. This implementation does
407no consing, entirely reusing the sells of SELF and OTHER.")
408 )
409
410|#
411
412(defmethod unary-minus ((self poly))
413 "Destructively modifies the coefficients of the polynomial SELF,
414by changing their sign."
415 (mapc #'unary-minus (poly-termlist self))
416 self)
417
418(defun add-termlists (p q order-fn)
419 "Destructively adds two termlists P and Q ordered according to ORDER-FN."
420 (fast-add p q order-fn #'add-to))
421
422(defun subtract-termlists (p q order-fn)
423 "Destructively subtracts two termlists P and Q ordered according to ORDER-FN."
424 (setf q (mapc #'unary-minus q))
425 (add-termlists p q order-fn))
426
427(defmethod add-to ((self poly) (other poly) &aux (other-copy (copy-instance other)))
428 "Adds to polynomial SELF another polynomial OTHER.
429This operation destructively modifies both polynomials.
430The result is stored in SELF. This implementation does
431no consing, entirely reusing the sells of SELF and OTHER."
432 (change-term-order other-copy self)
433 (setf (poly-termlist self) (add-termlists
434 (poly-termlist self) (poly-termlist other-copy)
435 (poly-term-order self)))
436 self)
437
438
439(defmethod subtract-from ((self poly) (other poly) &aux (other-copy (copy-instance other)))
440 "Subtracts from polynomial SELF another polynomial OTHER.
441This operation destructively modifies both polynomials.
442The result is stored in SELF. This implementation does
443no consing, entirely reusing the sells of SELF and OTHER."
444 (change-term-order other-copy self)
445 (setf (poly-termlist self) (subtract-termlists
446 (poly-termlist self) (poly-termlist other-copy)
447 (poly-term-order self)))
448 self)
449
450
451(defmethod add-to ((self poly) (other term) &aux (other-copy (copy-instance other)))
452 "Adds to a polynomial SELF a term OTHER. The term OTHER is not
453modified."
454 (add-to self (change-class other-copy 'poly)))
455
456(defmethod subtract-from ((self poly) (other term) &aux (other-copy (copy-instance other)))
457 "Subtracts from a polynomial SELF a term OTHER. The term OTHER is not
458modified."
459 (subtract-from self (change-class other-copy 'poly)))
460
461
462(defmacro multiply-term-by-termlist-dropping-zeros (term termlist
463 &optional (reverse-arg-order-P nil))
464 "Multiplies term TERM by a list of term, TERMLIST.
465Takes into accound divisors of zero in the ring, by
466deleting zero terms. Optionally, if REVERSE-ARG-ORDER-P
467is T, change the order of arguments; this may be important
468if we extend the package to non-commutative rings."
469 `(mapcan #'(lambda (other-term)
470 (let ((prod (multiply
471 ,@(cond
472 (reverse-arg-order-p
473 `(other-term ,term))
474 (t
475 `(,term other-term))))))
476 (cond
477 ((universal-zerop prod) nil)
478 (t (list prod)))))
479 ,termlist))
480
481(defun multiply-termlists (p q order-fn)
482 "A version of polynomial multiplication, operating
483directly on termlists."
484 (cond
485 ((or (endp p) (endp q))
486 ;;p or q is 0 (represented by NIL)
487 nil)
488 ;; If p= p0+p1 and q=q0+q1 then p*q=p0*q0+p0*q1+p1*q
489 ((endp (cdr p))
490 (multiply-term-by-termlist-dropping-zeros (car p) q))
491 ((endp (cdr q))
492 (multiply-term-by-termlist-dropping-zeros (car q) p t))
493 (t
494 (cons (multiply (car p) (car q))
495 (add-termlists
496 (multiply-term-by-termlist-dropping-zeros (car p) (cdr q))
497 (multiply-termlists (cdr p) q order-fn)
498 order-fn)))))
499
500(defmethod multiply-by ((self poly) (other poly) &aux (other-copy (copy-instance other)))
501 (change-term-order other-copy self)
502 (setf (poly-termlist self) (multiply-termlists (poly-termlist self)
503 (poly-termlist other-copy)
504 (poly-term-order self)))
505 self)
506
507(defmethod left-tensor-product-by ((self poly) (other monom))
508 (setf (poly-termlist self)
509 (mapcan #'(lambda (term)
510 (let ((prod (left-tensor-product-by term other)))
511 (cond
512 ((universal-zerop prod) nil)
513 (t (list prod)))))
514 (poly-termlist self)))
515 (incf (poly-dimension self) (monom-dimension other))
516 self)
517
518(defmethod right-tensor-product-by ((self poly) (other monom))
519 (setf (poly-termlist self)
520 (mapcan #'(lambda (term)
521 (let ((prod (right-tensor-product-by term other)))
522 (cond
523 ((universal-zerop prod) nil)
524 (t (list prod)))))
525 (poly-termlist self)))
526 (incf (poly-dimension self) (monom-dimension other))
527 self)
528
529
530(defun standard-extension (plist &aux (k (length plist)) (i 0))
531 "Calculate [U1*P1,U2*P2,...,UK*PK], where PLIST=[P1,P2,...,PK]
532is a list of polynomials. Destructively modifies PLIST elements."
533 (mapc #'(lambda (poly)
534 (left-tensor-product-by
535 poly
536 (prog1
537 (make-monom-variable k i)
538 (incf i))))
539 plist))
540
541(defun standard-extension-1 (plist
542 &aux
543 (plist (standard-extension plist))
544 (nvars (poly-dimension (car plist))))
545 "Calculate [U1*P1-1,U2*P2-1,...,UK*PK-1], where PLIST=[P1,P2,...,PK].
546Firstly, new K variables U1, U2, ..., UK, are inserted into each
547polynomial. Subsequently, P1, P2, ..., PK are destructively modified
548tantamount to replacing PI with UI*PI-1. It assumes that all
549polynomials have the same dimension, and only the first polynomial
550is examined to determine this dimension."
551 ;; Implementation note: we use STANDARD-EXTENSION and then subtract
552 ;; 1 from each polynomial; since UI*PI has no constant term,
553 ;; we just need to append the constant term at the end
554 ;; of each termlist.
555 (flet ((subtract-1 (p)
556 (poly-append-term p (make-instance 'term :dimension nvars :coeff -1))))
557 (setf plist (mapc #'subtract-1 plist)))
558 plist)
559
560
561(defun standard-sum (plist
562 &aux
563 (plist (standard-extension plist))
564 (nvars (poly-dimension (car plist))))
565 "Calculate the polynomial U1*P1+U2*P2+...+UK*PK-1, where PLIST=[P1,P2,...,PK].
566Firstly, new K variables, U1, U2, ..., UK, are inserted into each
567polynomial. Subsequently, P1, P2, ..., PK are destructively modified
568tantamount to replacing PI with UI*PI, and the resulting polynomials
569are added. Finally, 1 is subtracted. It should be noted that the term
570order is not modified, which is equivalent to using a lexicographic
571order on the first K variables."
572 (flet ((subtract-1 (p)
573 (poly-append-term p (make-instance 'term :dimension nvars :coeff -1))))
574 (subtract-1
575 (make-instance
576 'poly
577 :termlist (apply #'nconc (mapcar #'poly-termlist plist))))))
578
579(defgeneric s-polynomial (object1 object2)
580 (:documentation "Yields the S-polynomial of OBJECT1 and OBJECT2.")
581 (:method ((f poly) (g poly))
582 (let* ((lcm (universal-lcm (leading-monomial f) (leading-monomial g)))
583 (mf (divide lcm (leading-monomial f)))
584 (mg (divide lcm (leading-monomial g))))
585 (multiple-value-bind (c cf cg)
586 (universal-ezgcd (leading-coefficient f) (leading-coefficient g))
587 (declare (ignore c))
588 (subtract
589 (multiply f (change-class mf 'term :coeff cg))
590 (multiply g (change-class mg 'term :coeff cf)))))))
591
592(defgeneric poly-content (object)
593 (:documentation "Greatest common divisor of the coefficients of the polynomial object OBJECT.")
594 (:method ((self poly))
595 (reduce #'universal-gcd
596 (mapcar #'term-coeff (rest (poly-termlist self)))
597 :initial-value (leading-coefficient self))))
598
599(defun poly-primitive-part (self)
600 "Divide polynomial SELF by gcd of its
601coefficients. Return the resulting polynomial."
602 (scalar-divide-by self (poly-content self)))
603
604(defun poly-insert-variables (self k)
605 (left-tensor-product-by self (make-instance 'monom :dimension k)))
606
607(defun saturation-extension (f plist &aux (k (length plist)))
608 "Calculate [F', U1*P1-1,U2*P2-1,...,UK*PK-1], where
609PLIST=[P1,P2,...,PK] and F' is F with variables U1,U2,...,UK inserted
610as first K variables. It destructively modifies F and PLIST."
611 (nconc (mapc #'(lambda (x) (poly-insert-variables x k)) f)
612 (standard-extension-1 plist)))
613
614(defun polysaturation-extension (f plist &aux (k (length plist)))
615 "Calculate [F', U1*P1+U2*P2+...+UK*PK-1], where PLIST=[P1,P2,...,PK]
616and F' is F with variables U1,U2,...,UK inserted as first K
617variables. It destructively modifies F and PLIST."
618 (nconc (mapc #'(lambda (x) (poly-insert-variables x k)) f)
619 (list (standard-sum plist))))
620
621(defun saturation-extension-1 (f p)
622 "Given family of polynomials F and a polynomial P, calculate [F',
623U*P-1], where F' is F with variable inserted as the first variable. It
624destructively modifies F and P."
625 (polysaturation-extension f (list p)))
626
627(defmethod multiply-by ((self poly) (other ring))
628 (scalar-multiply-by self other))
629
630(defun make-poly-variable (nvars pos &optional (power 1))
631 (change-class (make-monom-variable nvars pos power) 'poly))
632
633(defun make-poly-constant (nvars coeff)
634 (change-class (make-term-constant nvars coeff) 'poly))
635
636(defgeneric universal-expt (x y)
637 (:documentation "Raises X to power Y.")
638 (:method ((x number) (y integer)) (expt x y))
639 (:method ((x t) (y integer))
640 (declare (type fixnum y))
641 (cond
642 ((minusp y) (error "universal-expt: Negative exponent."))
643 ((universal-zerop x) (if (zerop y) 1))
644 (t
645 (do ((k 1 (ash k 1))
646 (q x (multiply q q)) ;keep squaring
647 (p (make-unit-for x) (if (not (zerop (logand k y))) (multiply p q) p)))
648 ((> k y) p)
649 (declare (fixnum k)))))))
650
651(defgeneric poly-p (object)
652 (:documentation "Checks if an object is a polynomial.")
653 (:method ((self poly)) t)
654 (:method ((self t)) nil))
655
656(defmethod ->sexp :before ((self poly) &optional vars)
657 "Ensures that the number of variables in VARS maches the polynomial dimension of the
658polynomial SELF."
659 (with-slots (dimension)
660 self
661 (assert (= (length vars) dimension)
662 nil
663 "Number of variables ~S does not match the dimension ~S"
664 vars dimension)))
665
666(defmethod ->sexp ((self poly) &optional vars)
667 "Converts a polynomial SELF to a sexp."
668 (let ((m (mapcar #'(lambda (trm) (->sexp trm vars))
669 (poly-termlist self))))
670 (cond ((endp m) 0)
671 ((endp (cdr m)) (car m))
672 (t (cons '+ m)))))
673
674(defconstant +list-marker+ :[
675 "A sexp with this head is considered a list of polynomials.")
676
677(defmethod ->sexp ((self cons) &optional vars)
678 (assert (eql (car self) +list-marker+))
679 (cons +list-marker+ (mapcar #'(lambda (p) (->sexp p vars)) (cdr self))))
680
681(defmethod make-zero-for ((self poly))
682 (make-instance 'poly :dimension (poly-dimension self)))
683
684(defmethod make-unit-for ((self poly))
685 (make-poly-constant (poly-dimension self) 1))
686
687(defgeneric poly-reverse (self)
688 (:documentation "Reverse the order of terms in a polynomial SELF.")
689 (:method ((self poly))
690 (with-slots (termlist)
691 self
692 (setf termlist (nreverse termlist)))
693 self))
694
695
696
Note: See TracBrowser for help on using the repository browser.