1 | ;;; -*- Mode: Lisp -*-
|
---|
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 | (defpackage "BUCHBERGER"
|
---|
23 | (:use :cl :grobner-debug
|
---|
24 | :ring :polynomial :order :division
|
---|
25 | :criterion :pair-queue :priority-queue
|
---|
26 | )
|
---|
27 | (:export "BUCHBERGER" "PARALLEL-BUCHBERGER"))
|
---|
28 |
|
---|
29 | (in-package :buchberger)
|
---|
30 |
|
---|
31 | ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
|
---|
32 | ;;
|
---|
33 | ;; Buchberger Algorithm Implementation
|
---|
34 | ;;
|
---|
35 | ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
|
---|
36 |
|
---|
37 | (defun buchberger (ring f start &optional (top-reduction-only $poly_top_reduction_only))
|
---|
38 | "An implementation of the Buchberger algorithm. Return Grobner basis
|
---|
39 | of the ideal generated by the polynomial list F. Polynomials 0 to
|
---|
40 | START-1 are assumed to be a Grobner basis already, so that certain
|
---|
41 | critical pairs will not be examined. If TOP-REDUCTION-ONLY set, top
|
---|
42 | reduction will be preformed. This function assumes that all polynomials
|
---|
43 | in F are non-zero."
|
---|
44 | (declare (type fixnum start))
|
---|
45 | (when (endp f) (return-from buchberger f)) ;cut startup costs
|
---|
46 | (debug-cgb "~&GROBNER BASIS - BUCHBERGER ALGORITHM")
|
---|
47 | (when (plusp start) (debug-cgb "~&INCREMENTAL:~d done" start))
|
---|
48 | #+grobner-check (when (plusp start)
|
---|
49 | (grobner-test ring (subseq f 0 start) (subseq f 0 start)))
|
---|
50 | ;;Initialize critical pairs
|
---|
51 | (let ((b (pair-queue-initialize (make-pair-queue)
|
---|
52 | f start))
|
---|
53 | (b-done (make-hash-table :test #'equal)))
|
---|
54 | (declare (type priority-queue b) (type hash-table b-done))
|
---|
55 | (dotimes (i (1- start))
|
---|
56 | (do ((j (1+ i) (1+ j))) ((>= j start))
|
---|
57 | (setf (gethash (list (elt f i) (elt f j)) b-done) t)))
|
---|
58 | (do ()
|
---|
59 | ((pair-queue-empty-p b)
|
---|
60 | #+grobner-check(grobner-test ring f f)
|
---|
61 | (debug-cgb "~&GROBNER END")
|
---|
62 | f)
|
---|
63 | (let ((pair (pair-queue-remove b)))
|
---|
64 | (declare (type pair pair))
|
---|
65 | (cond
|
---|
66 | ((criterion-1 pair) nil)
|
---|
67 | ((criterion-2 pair b-done f) nil)
|
---|
68 | (t
|
---|
69 | (let ((sp (normal-form ring (spoly ring (pair-first pair)
|
---|
70 | (pair-second pair))
|
---|
71 | f top-reduction-only)))
|
---|
72 | (declare (type poly sp))
|
---|
73 | (cond
|
---|
74 | ((poly-zerop sp)
|
---|
75 | nil)
|
---|
76 | (t
|
---|
77 | (setf sp (poly-primitive-part ring sp)
|
---|
78 | f (nconc f (list sp)))
|
---|
79 | ;; Add new critical pairs
|
---|
80 | (dolist (h f)
|
---|
81 | (pair-queue-insert b (make-pair h sp)))
|
---|
82 | (debug-cgb "~&Sugar: ~d Polynomials: ~d; Pairs left: ~d; Pairs done: ~d;"
|
---|
83 | (pair-sugar pair) (length f) (pair-queue-size b)
|
---|
84 | (hash-table-count b-done)))))))
|
---|
85 | (setf (gethash (list (pair-first pair) (pair-second pair)) b-done)
|
---|
86 | t)))))
|
---|
87 |
|
---|
88 | (defun parallel-buchberger (ring f start &optional (top-reduction-only $poly_top_reduction_only))
|
---|
89 | "An implementation of the Buchberger algorithm. Return Grobner basis
|
---|
90 | of the ideal generated by the polynomial list F. Polynomials 0 to
|
---|
91 | START-1 are assumed to be a Grobner basis already, so that certain
|
---|
92 | critical pairs will not be examined. If TOP-REDUCTION-ONLY set, top
|
---|
93 | reduction will be preformed."
|
---|
94 | (declare (ignore top-reduction-only)
|
---|
95 | (type fixnum start))
|
---|
96 | (when (endp f) (return-from parallel-buchberger f)) ;cut startup costs
|
---|
97 | (debug-cgb "~&GROBNER BASIS - PARALLEL-BUCHBERGER ALGORITHM")
|
---|
98 | (when (plusp start) (debug-cgb "~&INCREMENTAL:~d done" start))
|
---|
99 | #+grobner-check (when (plusp start)
|
---|
100 | (grobner-test ring (subseq f 0 start) (subseq f 0 start)))
|
---|
101 | ;;Initialize critical pairs
|
---|
102 | (let ((b (pair-queue-initialize (make-pair-queue) f start))
|
---|
103 | (b-done (make-hash-table :test #'equal)))
|
---|
104 | (declare (type priority-queue b)
|
---|
105 | (type hash-table b-done))
|
---|
106 | (dotimes (i (1- start))
|
---|
107 | (do ((j (1+ i) (1+ j))) ((>= j start))
|
---|
108 | (declare (type fixnum j))
|
---|
109 | (setf (gethash (list (elt f i) (elt f j)) b-done) t)))
|
---|
110 | (do ()
|
---|
111 | ((pair-queue-empty-p b)
|
---|
112 | #+grobner-check(grobner-test ring f f)
|
---|
113 | (debug-cgb "~&GROBNER END")
|
---|
114 | f)
|
---|
115 | (let ((pair (pair-queue-remove b)))
|
---|
116 | (when (null (pair-division-data pair))
|
---|
117 | (setf (pair-division-data pair) (list (spoly ring
|
---|
118 | (pair-first pair)
|
---|
119 | (pair-second pair))
|
---|
120 | (make-poly-zero)
|
---|
121 | (funcall (ring-unit ring))
|
---|
122 | 0)))
|
---|
123 | (cond
|
---|
124 | ((criterion-1 pair) nil)
|
---|
125 | ((criterion-2 pair b-done f) nil)
|
---|
126 | (t
|
---|
127 | (let* ((dd (pair-division-data pair))
|
---|
128 | (p (first dd))
|
---|
129 | (sp (second dd))
|
---|
130 | (c (third dd))
|
---|
131 | (division-count (fourth dd)))
|
---|
132 | (cond
|
---|
133 | ((poly-zerop p) ;normal form completed
|
---|
134 | (debug-cgb "~&~3T~d reduction~:p" division-count)
|
---|
135 | (cond
|
---|
136 | ((poly-zerop sp)
|
---|
137 | (debug-cgb " ---> 0")
|
---|
138 | nil)
|
---|
139 | (t
|
---|
140 | (setf sp (poly-nreverse sp)
|
---|
141 | sp (poly-primitive-part ring sp)
|
---|
142 | f (nconc f (list sp)))
|
---|
143 | ;; Add new critical pairs
|
---|
144 | (dolist (h f)
|
---|
145 | (pair-queue-insert b (make-pair h sp)))
|
---|
146 | (debug-cgb "~&Sugar: ~d Polynomials: ~d; Pairs left: ~d; Pairs done: ~d;"
|
---|
147 | (pair-sugar pair) (length f) (pair-queue-size b)
|
---|
148 | (hash-table-count b-done))))
|
---|
149 | (setf (gethash (list (pair-first pair) (pair-second pair))
|
---|
150 | b-done) t))
|
---|
151 | (t ;normal form not complete
|
---|
152 | (do ()
|
---|
153 | ((cond
|
---|
154 | ((> (poly-sugar sp) (pair-sugar pair))
|
---|
155 | (debug-cgb "(~a)?" (poly-sugar sp))
|
---|
156 | t)
|
---|
157 | ((poly-zerop p)
|
---|
158 | (debug-cgb ".")
|
---|
159 | t)
|
---|
160 | (t nil))
|
---|
161 | (setf (first dd) p
|
---|
162 | (second dd) sp
|
---|
163 | (third dd) c
|
---|
164 | (fourth dd) division-count
|
---|
165 | (pair-sugar pair) (poly-sugar sp))
|
---|
166 | (pair-queue-insert b pair))
|
---|
167 | (multiple-value-setq (p sp c division-count)
|
---|
168 | (normal-form-step ring f p sp c division-count))))))))))))
|
---|