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/ideal.lisp@ 953

Last change on this file since 953 was 903, checked in by Marek Rychlik, 9 years ago

* empty log message *

File size: 8.8 KB
RevLine 
[73]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
[67]22;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
23;;
24;; Operations in ideal theory
25;;
26;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
27
[502]28(defpackage "IDEAL"
[518]29 (:use :cl :ring :monomial :order :term :polynomial :division :grobner-wrap)
[531]30 (:export "POLY-DEPENDS-P"
31 "RING-INTERSECTION"
32 "ELIMINATION-IDEAL"
33 "COLON-IDEAL"
34 "COLON-IDEAL-1"
35 "IDEAL-INTERSECTION"
36 "POLY-LCM"
37 "GROBNER-EQUAL"
38 "GROBNER-SUBSETP"
39 "GROBNER-MEMBER"
40 "IDEAL-SATURATION-1"
41 "IDEAL-SATURATION"
42 "IDEAL-POLYSATURATION-1"
43 "IDEAL-POLYSATURATION"
44 ))
[502]45
46(in-package :ideal)
47
[67]48;; Does the term depend on variable K?
49(defun term-depends-p (term k)
50 "Return T if the term TERM depends on variable number K."
51 (monom-depends-p (term-monom term) k))
52
53;; Does the polynomial P depend on variable K?
54(defun poly-depends-p (p k)
55 "Return T if the term polynomial P depends on variable number K."
56 (some #'(lambda (term) (term-depends-p term k)) (poly-termlist p)))
57
58(defun ring-intersection (plist k)
59 "This function assumes that polynomial list PLIST is a Grobner basis
60and it calculates the intersection with the ring R[x[k+1],...,x[n]], i.e.
61it discards polynomials which depend on variables x[0], x[1], ..., x[k]."
62 (dotimes (i k plist)
63 (setf plist
64 (remove-if #'(lambda (p)
65 (poly-depends-p p i))
66 plist))))
67
[902]68(defun elimination-ideal (ring-and-order flist k &optional (top-reduction-only $poly_top_reduction_only) (start 0))
69 (ring-intersection (reduced-grobner ring-and-order flist start top-reduction-only) k))
[67]70
71(defun colon-ideal (ring f g &optional (top-reduction-only $poly_top_reduction_only))
72 "Returns the reduced Grobner basis of the colon ideal Id(F):Id(G),
73where F and G are two lists of polynomials. The colon ideal I:J is
74defined as the set of polynomials H such that for all polynomials W in
75J the polynomial W*H belongs to I."
76 (cond
77 ((endp g)
78 ;;Id(G) consists of 0 only so W*0=0 belongs to Id(F)
79 (if (every #'poly-zerop f)
80 (error "First ideal must be non-zero.")
[156]81 (list (make-poly-from-termlist
[67]82 (list (make-term
[821]83 (make-monom (monom-dimension (poly-lm (find-if-not #'poly-zerop f))))
[67]84 (funcall (ring-unit ring))))))))
85 ((endp (cdr g))
86 (colon-ideal-1 ring f (car g) top-reduction-only))
87 (t
88 (ideal-intersection ring
89 (colon-ideal-1 ring f (car g) top-reduction-only)
90 (colon-ideal ring f (rest g) top-reduction-only)
91 top-reduction-only))))
92
93(defun colon-ideal-1 (ring f g &optional (top-reduction-only $poly_top_reduction_only))
94 "Returns the reduced Grobner basis of the colon ideal Id(F):Id({G}), where
95F is a list of polynomials and G is a polynomial."
96 (mapcar #'(lambda (x) (poly-exact-divide ring x g)) (ideal-intersection ring f (list g) top-reduction-only)))
97
98
[902]99(defun ideal-intersection (ring-and-order f g &optional (top-reduction-only $poly_top_reduction_only))
[67]100 (mapcar #'poly-contract
101 (ring-intersection
102 (reduced-grobner
[902]103 ring-and-order
[822]104 (append (mapcar #'(lambda (p) (poly-extend p (make-monom 1 :initial-exponent 1))) f)
[67]105 (mapcar #'(lambda (p)
[902]106 (poly-append (poly-extend (poly-uminus ring-and-order p)
[822]107 (make-monom 1 :initial-exponent 1))
[67]108 (poly-extend p)))
109 g))
110 0
111 top-reduction-only)
112 1)))
113
114(defun poly-lcm (ring f g)
115 "Return LCM (least common multiple) of two polynomials F and G.
116The polynomials must be ordered according to monomial order PRED
117and their coefficients must be compatible with the RING structure
118defined in the COEFFICIENT-RING package."
119 (cond
120 ((poly-zerop f) f)
121 ((poly-zerop g) g)
122 ((and (endp (cdr (poly-termlist f))) (endp (cdr (poly-termlist g))))
123 (let ((m (monom-lcm (poly-lm f) (poly-lm g))))
124 (make-poly-from-termlist (list (make-term m (funcall (ring-lcm ring) (poly-lc f) (poly-lc g)))))))
125 (t
126 (multiple-value-bind (f f-cont)
127 (poly-primitive-part ring f)
128 (multiple-value-bind (g g-cont)
129 (poly-primitive-part ring g)
130 (scalar-times-poly
131 ring
132 (funcall (ring-lcm ring) f-cont g-cont)
133 (poly-primitive-part ring (car (ideal-intersection ring (list f) (list g) nil)))))))))
134
135;; Do two Grobner bases yield the same ideal?
136(defun grobner-equal (ring g1 g2)
137 "Returns T if two lists of polynomials G1 and G2, assumed to be Grobner bases,
138generate the same ideal, and NIL otherwise."
139 (and (grobner-subsetp ring g1 g2) (grobner-subsetp ring g2 g1)))
140
141(defun grobner-subsetp (ring g1 g2)
142 "Returns T if a list of polynomials G1 generates
143an ideal contained in the ideal generated by a polynomial list G2,
144both G1 and G2 assumed to be Grobner bases. Returns NIL otherwise."
145 (every #'(lambda (p) (grobner-member ring p g2)) g1))
146
147(defun grobner-member (ring p g)
148 "Returns T if a polynomial P belongs to the ideal generated by the
149polynomial list G, which is assumed to be a Grobner basis. Returns NIL otherwise."
150 (poly-zerop (normal-form ring p g nil)))
151
152;; Calculate F : p^inf
[902]153(defun ideal-saturation-1 (ring-and-order f p start &optional (top-reduction-only $poly_top_reduction_only))
[67]154 "Returns the reduced Grobner basis of the saturation of the ideal
155generated by a polynomial list F in the ideal generated by a single
156polynomial P. The saturation ideal is defined as the set of
157polynomials H such for some natural number n (* (EXPT P N) H) is in the ideal
158F. Geometrically, over an algebraically closed field, this is the set
159of polynomials in the ideal generated by F which do not identically
160vanish on the variety of P."
161 (mapcar
162 #'poly-contract
163 (ring-intersection
164 (reduced-grobner
[902]165 ring-and-order
166 (saturation-extension-1 ring-and-order f p)
[67]167 start top-reduction-only)
168 1)))
169
170
171
172;; Calculate F : p1^inf : p2^inf : ... : ps^inf
173(defun ideal-polysaturation-1 (ring f plist start &optional (top-reduction-only $poly_top_reduction_only))
174 "Returns the reduced Grobner basis of the ideal obtained by a
175sequence of successive saturations in the polynomials
176of the polynomial list PLIST of the ideal generated by the
177polynomial list F."
178 (cond
179 ((endp plist) (reduced-grobner ring f start top-reduction-only))
180 (t (let ((g (ideal-saturation-1 ring f (car plist) start top-reduction-only)))
181 (ideal-polysaturation-1 ring g (rest plist) (length g) top-reduction-only)))))
182
[903]183(defun ideal-saturation (ring-and-order f g start &optional (top-reduction-only $poly_top_reduction_only)
[67]184 &aux
[903]185 (k (length g)))
[67]186 "Returns the reduced Grobner basis of the saturation of the ideal
187generated by a polynomial list F in the ideal generated a polynomial
188list G. The saturation ideal is defined as the set of polynomials H
189such for some natural number n and some P in the ideal generated by G
190the polynomial P**N * H is in the ideal spanned by F. Geometrically,
191over an algebraically closed field, this is the set of polynomials in
192the ideal generated by F which do not identically vanish on the
193variety of G."
194 (mapcar
195 #'(lambda (q) (poly-contract q k))
196 (ring-intersection
[903]197 (reduced-grobner ring-and-order
198 (polysaturation-extension ring-and-order f g)
[67]199 start
200 top-reduction-only)
201 k)))
202
[903]203(defun ideal-polysaturation (ring-and-order f ideal-list start &optional (top-reduction-only $poly_top_reduction_only))
[67]204 "Returns the reduced Grobner basis of the ideal obtained by a
205successive applications of IDEAL-SATURATION to F and lists of
206polynomials in the list IDEAL-LIST."
207 (cond
208 ((endp ideal-list) f)
[903]209 (t (let ((h (ideal-saturation ring-and-order f (car ideal-list) start top-reduction-only)))
210 (ideal-polysaturation ring-and-order h (rest ideal-list) (length h) top-reduction-only)))))
Note: See TracBrowser for help on using the repository browser.