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/division.lisp@ 231

Last change on this file since 231 was 192, checked in by Marek Rychlik, 9 years ago
File size: 7.2 KB
Line 
1;;; -*- Mode: Lisp; Package: Maxima; Syntax: Common-Lisp; Base: 10 -*-
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
22(in-package :ngrobner)
23
24;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
25;;
26;; An implementation of the division algorithm
27;;
28;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
29
30(defun grobner-op (ring c1 c2 m f g)
31 "Returns C2*F-C1*M*G, where F and G are polynomials M is a monomial.
32Assume that the leading terms will cancel."
33 #+grobner-check(funcall (ring-zerop ring)
34 (funcall (ring-sub ring)
35 (funcall (ring-mul ring) c2 (poly-lc f))
36 (funcall (ring-mul ring) c1 (poly-lc g))))
37 #+grobner-check(monom-equal-p (poly-lm f) (monom-mul m (poly-lm g)))
38 ;; Note that we can drop the leading terms of f ang g
39 (poly-sub ring
40 (scalar-times-poly-1 ring c2 f)
41 (scalar-times-poly-1 ring c1 (monom-times-poly m g))))
42
43(defun poly-pseudo-divide (ring f fl)
44 "Pseudo-divide a polynomial F by the list of polynomials FL. Return
45multiple values. The first value is a list of quotients A. The second
46value is the remainder R. The third argument is a scalar coefficient
47C, such that C*F can be divided by FL within the ring of coefficients,
48which is not necessarily a field. Finally, the fourth value is an
49integer count of the number of reductions performed. The resulting
50objects satisfy the equation: C*F= sum A[i]*FL[i] + R."
51 (declare (type poly f) (list fl))
52 (do ((r (make-poly-zero))
53 (c (funcall (ring-unit ring)))
54 (a (make-list (length fl) :initial-element (make-poly-zero)))
55 (division-count 0)
56 (p f))
57 ((poly-zerop p)
58 (debug-cgb "~&~3T~d reduction~:p" division-count)
59 (when (poly-zerop r) (debug-cgb " ---> 0"))
60 (values (mapcar #'poly-nreverse a) (poly-nreverse r) c division-count))
61 (declare (fixnum division-count))
62 (do ((fl fl (rest fl)) ;scan list of divisors
63 (b a (rest b)))
64 ((cond
65 ((endp fl) ;no division occurred
66 (push (poly-lt p) (poly-termlist r)) ;move lt(p) to remainder
67 (setf (poly-sugar r) (max (poly-sugar r) (term-sugar (poly-lt p))))
68 (pop (poly-termlist p)) ;remove lt(p) from p
69 t)
70 ((monom-divides-p (poly-lm (car fl)) (poly-lm p)) ;division occurred
71 (incf division-count)
72 (multiple-value-bind (gcd c1 c2)
73 (funcall (ring-ezgcd ring) (poly-lc (car fl)) (poly-lc p))
74 (declare (ignore gcd))
75 (let ((m (monom-div (poly-lm p) (poly-lm (car fl)))))
76 ;; Multiply the equation c*f=sum ai*fi+r+p by c1.
77 (mapl #'(lambda (x)
78 (setf (car x) (scalar-times-poly ring c1 (car x))))
79 a)
80 (setf r (scalar-times-poly ring c1 r)
81 c (funcall (ring-mul ring) c c1)
82 p (grobner-op ring c2 c1 m p (car fl)))
83 (push (make-term m c2) (poly-termlist (car b))))
84 t)))))))
85
86(defun poly-exact-divide (ring f g)
87 "Divide a polynomial F by another polynomial G. Assume that exact division
88with no remainder is possible. Returns the quotient."
89 (declare (type poly f g))
90 (multiple-value-bind (quot rem coeff division-count)
91 (poly-pseudo-divide ring f (list g))
92 (declare (ignore division-count coeff)
93 (list quot)
94 (type poly rem)
95 (type fixnum division-count))
96 (unless (poly-zerop rem) (error "Exact division failed."))
97 (car quot)))
98
99
100
101;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
102;;
103;; An implementation of the normal form
104;;
105;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
106
107(defun normal-form-step (ring fl p r c division-count
108 &aux (g (find (poly-lm p) fl
109 :test #'monom-divisible-by-p
110 :key #'poly-lm)))
111 (cond
112 (g ;division possible
113 (incf division-count)
114 (multiple-value-bind (gcd cg cp)
115 (funcall (ring-ezgcd ring) (poly-lc g) (poly-lc p))
116 (declare (ignore gcd))
117 (let ((m (monom-div (poly-lm p) (poly-lm g))))
118 ;; Multiply the equation c*f=sum ai*fi+r+p by cg.
119 (setf r (scalar-times-poly ring cg r)
120 c (funcall (ring-mul ring) c cg)
121 ;; p := cg*p-cp*m*g
122 p (grobner-op ring cp cg m p g))))
123 (debug-cgb "/"))
124 (t ;no division possible
125 (push (poly-lt p) (poly-termlist r)) ;move lt(p) to remainder
126 (setf (poly-sugar r) (max (poly-sugar r) (term-sugar (poly-lt p))))
127 (pop (poly-termlist p)) ;remove lt(p) from p
128 (debug-cgb "+")))
129 (values p r c division-count))
130
131;; Merge it sometime with poly-pseudo-divide
132(defun normal-form (ring f fl &optional (top-reduction-only $poly_top_reduction_only))
133 ;; Loop invariant: c*f0=sum ai*fi+r+f, where f0 is the initial value of f
134 #+grobner-check(when (null fl) (warn "normal-form: empty divisor list."))
135 (do ((r (make-poly-zero))
136 (c (funcall (ring-unit ring)))
137 (division-count 0))
138 ((or (poly-zerop f)
139 ;;(endp fl)
140 (and top-reduction-only (not (poly-zerop r))))
141 (progn
142 (debug-cgb "~&~3T~d reduction~:p" division-count)
143 (when (poly-zerop r)
144 (debug-cgb " ---> 0")))
145 (setf (poly-termlist f) (nreconc (poly-termlist r) (poly-termlist f)))
146 (values f c division-count))
147 (declare (fixnum division-count)
148 (type poly r))
149 (multiple-value-setq (f r c division-count)
150 (normal-form-step ring fl f r c division-count))))
151
152(defun buchberger-criterion (ring g)
153 "Returns T if G is a Grobner basis, by using the Buchberger
154criterion: for every two polynomials h1 and h2 in G the S-polynomial
155S(h1,h2) reduces to 0 modulo G."
156 (every
157 #'poly-zerop
158 (makelist (normal-form ring (spoly ring (elt g i) (elt g j)) g nil)
159 (i 0 (- (length g) 2))
160 (j (1+ i) (1- (length g))))))
161
162
163(defun poly-normalize (ring p &aux (c (poly-lc p)))
164 "Divide a polynomial by its leading coefficient. It assumes
165that the division is possible, which may not always be the
166case in rings which are not fields. The exact division operator
167is assumed to be provided by the RING structure of the
168COEFFICIENT-RING package."
169 (mapc #'(lambda (term)
170 (setf (term-coeff term) (funcall (ring-div ring) (term-coeff term) c)))
171 (poly-termlist p))
172 p)
173
174(defun poly-normalize-list (ring plist)
175 "Divide every polynomial in a list PLIST by its leading coefficient. "
176 (mapcar #'(lambda (x) (poly-normalize ring x)) plist))
Note: See TracBrowser for help on using the repository browser.