001 /*
002 * $Id: RGroebnerBaseSeq.java 3626 2011-05-08 09:51:57Z kredel $
003 */
004
005 package edu.jas.gbufd;
006
007
008 import java.util.ArrayList;
009 import java.util.List;
010 import java.util.Collections;
011
012 import org.apache.log4j.Logger;
013
014 import edu.jas.gb.GroebnerBaseAbstract;
015 import edu.jas.gb.Pair;
016 import edu.jas.poly.ExpVector;
017 import edu.jas.poly.GenPolynomial;
018 import edu.jas.structure.RegularRingElem;
019
020
021 /**
022 * Regular ring Groebner Base sequential algorithm. Implements R-Groebner bases
023 * and GB test.
024 * @param <C> coefficient type
025 * @author Heinz Kredel
026 */
027
028 public class RGroebnerBaseSeq<C extends RegularRingElem<C>> extends
029 GroebnerBaseAbstract<C> {
030
031
032 private static final Logger logger = Logger.getLogger(RGroebnerBaseSeq.class);
033
034
035 private final boolean debug = logger.isDebugEnabled();
036
037
038 /**
039 * Reduction engine.
040 */
041 protected RReduction<C> red; // shadow super.red
042
043
044 /**
045 * Constructor.
046 */
047 public RGroebnerBaseSeq() {
048 this(new RReductionSeq<C>());
049 }
050
051
052 /**
053 * Constructor.
054 * @param red R-Reduction engine
055 */
056 public RGroebnerBaseSeq(RReduction<C> red) {
057 super(red);
058 this.red = red;
059 assert super.red == this.red;
060 }
061
062
063 /**
064 * R-Groebner base test.
065 * @param modv module variable number.
066 * @param F polynomial list.
067 * @return true, if F is a R-Groebner base, else false.
068 */
069 @Override
070 public boolean isGB(int modv, List<GenPolynomial<C>> F) {
071 if (F == null) {
072 return true;
073 }
074 if (!red.isBooleanClosed(F)) {
075 if (true || debug) {
076 System.out.println("not boolean closed");
077 }
078 return false;
079 }
080 GenPolynomial<C> pi, pj, s, h;
081 for (int i = 0; i < F.size(); i++) {
082 pi = F.get(i);
083 for (int j = i + 1; j < F.size(); j++) {
084 pj = F.get(j);
085 if (!red.moduleCriterion(modv, pi, pj)) {
086 continue;
087 }
088 // red.criterion4 not applicable
089 s = red.SPolynomial(pi, pj);
090 if (s.isZERO()) {
091 continue;
092 }
093 s = red.normalform(F, s);
094 if (!s.isZERO()) {
095 if (debug) {
096 System.out.println("p" + i + " = " + pi);
097 System.out.println("p" + j + " = " + pj);
098 System.out.println("s-pol = " + red.SPolynomial(pi, pj));
099 System.out.println("s-pol(" + i + "," + j + ") != 0: " + s);
100 //System.out.println("red = " + red.getClass().getName());
101 }
102 return false;
103 }
104 }
105 }
106 return true;
107 }
108
109
110 /**
111 * R-Groebner base using pairlist class.
112 * @param modv module variable number.
113 * @param F polynomial list.
114 * @return GB(F) a R-Groebner base of F.
115 */
116 public List<GenPolynomial<C>> GB(int modv, List<GenPolynomial<C>> F) {
117 /* boolean closure */
118 List<GenPolynomial<C>> bcF = red.reducedBooleanClosure(F);
119 logger.info("#bcF-#F = " + (bcF.size() - F.size()));
120 F = bcF;
121 /* normalize input */
122 List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>();
123 OrderedRPairlist<C> pairlist = null;
124 for (GenPolynomial<C> p : F) {
125 if (!p.isZERO()) {
126 p = p.monic(); //p.abs(); // not monic, monic if boolean closed
127 if (p.isONE()) {
128 G.clear();
129 G.add(p);
130 return G; // since boolean closed and no threads are activated
131 }
132 G.add(p); //G.add( 0, p ); //reverse list
133 if (pairlist == null) {
134 pairlist = new OrderedRPairlist<C>(modv, p.ring);
135 }
136 // putOne not required
137 pairlist.put(p);
138 }
139 }
140 if (G.size() <= 1) {
141 return G; // since boolean closed and no threads are activated
142 }
143 /* loop on critical pairs */
144 Pair<C> pair;
145 GenPolynomial<C> pi;
146 GenPolynomial<C> pj;
147 GenPolynomial<C> S;
148 //GenPolynomial<C> D;
149 GenPolynomial<C> H;
150 List<GenPolynomial<C>> bcH;
151 //int len = G.size();
152 //System.out.println("len = " + len);
153 while (pairlist.hasNext()) {
154 pair = pairlist.removeNext();
155 //System.out.println("pair = " + pair);
156 if (pair == null)
157 continue;
158
159 pi = pair.pi;
160 pj = pair.pj;
161 if (logger.isDebugEnabled()) {
162 logger.debug("pi = " + pi);
163 logger.debug("pj = " + pj);
164 }
165 if (!red.moduleCriterion(modv, pi, pj)) {
166 continue;
167 }
168
169 // S-polynomial -----------------------
170 // Criterion3() Criterion4() not applicable
171 S = red.SPolynomial(pi, pj);
172 if (S.isZERO()) {
173 pair.setZero();
174 continue;
175 }
176 if (logger.isDebugEnabled()) {
177 logger.debug("ht(S) = " + S.leadingExpVector());
178 }
179
180 H = red.normalform(G, S);
181 if (H.isZERO()) {
182 pair.setZero();
183 continue;
184 }
185 //H = H.monic(); // only for boolean closed H
186 if (logger.isDebugEnabled()) {
187 logger.debug("ht(H) = " + H.leadingExpVector());
188 }
189
190 if (H.isONE()) { // mostly useless
191 G.clear();
192 G.add(H);
193 return G; // not boolean closed ok, since no threads are activated
194 }
195 if (logger.isDebugEnabled()) {
196 logger.debug("H = " + H);
197 }
198 if (!H.isZERO()) {
199 logger.info("Sred = " + H);
200 //len = G.size();
201 bcH = red.reducedBooleanClosure(G, H);
202 logger.info("#bcH = " + bcH.size());
203 for (GenPolynomial<C> h : bcH) {
204 h = h.monic(); // monic() ok, since boolean closed
205 G.add(h);
206 pairlist.put(h);
207 }
208 if (debug) {
209 if (!pair.getUseCriterion3() || !pair.getUseCriterion4()) {
210 logger.info("H != 0 but: " + pair);
211 }
212 }
213 }
214 }
215 logger.debug("#sequential list = " + G.size());
216 G = minimalGB(G);
217 //G = red.irreducibleSet(G);
218 logger.info("" + pairlist);
219 return G;
220 }
221
222
223 /**
224 * Minimal ordered Groebner basis.
225 * @param Gp a Groebner base.
226 * @return a reduced Groebner base of Gp.
227 */
228 @Override
229 public List<GenPolynomial<C>> minimalGB(List<GenPolynomial<C>> Gp) {
230 if (Gp == null || Gp.size() <= 1) {
231 return Gp;
232 }
233 // remove zero polynomials
234 List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>(Gp.size());
235 for (GenPolynomial<C> a : Gp) {
236 if (a != null && !a.isZERO()) { // always true in GB()
237 // already positive a = a.abs();
238 G.add(a);
239 }
240 }
241 if (G.size() <= 1) {
242 //wg monic do not return G;
243 }
244 // remove top reducible polynomials
245 GenPolynomial<C> a, b;
246 List<GenPolynomial<C>> F;
247 List<GenPolynomial<C>> bcH;
248 F = new ArrayList<GenPolynomial<C>>(G.size());
249 while (G.size() > 0) {
250 a = G.remove(0);
251 b = a;
252 if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) {
253 // drop polynomial
254 if (true || debug) {
255 List<GenPolynomial<C>> ff;
256 ff = new ArrayList<GenPolynomial<C>>(G);
257 ff.addAll(F);
258 a = red.normalform(ff, a);
259 if (!a.isZERO()) { // happens
260 logger.info("minGB not zero " + a);
261 bcH = red.reducedBooleanClosure(G, a);
262 if (bcH.size() > 1) { // never happend so far
263 System.out.println("minGB not bc: bcH size = " + bcH.size());
264 F.add(b); // do not replace, stay with b
265 } else {
266 //System.out.println("minGB add bc(a): a = " + a + ", bc(a) = " + bcH.get(0));
267 F.addAll(bcH);
268 }
269 } else {
270 //System.out.println("minGB dropped " + b);
271 }
272 }
273 } else {
274 F.add(a);
275 }
276 }
277 G = F;
278 if (G.size() <= 1) {
279 // wg monic return G;
280 }
281 Collections.reverse(G); // important for lex GB
282 // reduce remaining polynomials
283 int len = G.size();
284 int el = 0;
285 while (el < len) {
286 a = G.remove(0);
287 b = a;
288 //System.out.println("doing " + a.length());
289 a = red.normalform(G, a);
290 bcH = red.reducedBooleanClosure(G, a);
291 if (bcH.size() > 1) {
292 System.out.println("minGB not bc: bcH size = " + bcH.size());
293 G.add(b); // do not reduce
294 } else {
295 G.addAll(bcH);
296 }
297 el++;
298 }
299 // make monic if possible
300 F = new ArrayList<GenPolynomial<C>>(G.size());
301 for (GenPolynomial<C> p : G) {
302 a = p.monic().abs();
303 if (p.length() != a.length()) {
304 System.out.println("minGB not bc: #p != #a: a = " + a + ", p = " + p);
305 a = p; // dont make monic for now
306 }
307 F.add(a);
308 }
309 G = F;
310
311 /* stratify: collect polynomials with equal leading terms */
312 ExpVector e, f;
313 F = new ArrayList<GenPolynomial<C>>(G.size());
314 for (int i = 0; i < G.size(); i++) {
315 a = G.get(i);
316 if (a == null || a.isZERO()) {
317 continue;
318 }
319 e = a.leadingExpVector();
320 for (int j = i + 1; j < G.size(); j++) {
321 b = G.get(j);
322 if (b == null || b.isZERO()) {
323 continue;
324 }
325 f = b.leadingExpVector();
326 if (e.equals(f)) {
327 //System.out.println("minGB e == f: " + a + ", " + b);
328 a = a.sum(b);
329 G.set(j, null);
330 }
331 }
332 F.add(a);
333 }
334 G = F;
335
336 /* info on boolean algebra element blocks
337 Map<C,List<GenPolynomial<C>>> bd = new TreeMap<C,List<GenPolynomial<C>>>();
338 for ( GenPolynomial<C> p : G ) {
339 C cf = p.leadingBaseCoefficient();
340 cf = cf.idempotent();
341 List<GenPolynomial<C>> block = bd.get( cf );
342 if ( block == null ) {
343 block = new ArrayList<GenPolynomial<C>>();
344 }
345 block.add( p );
346 bd.put( cf, block );
347 }
348 System.out.println("\nminGB bd:");
349 for( C k: bd.keySet() ) {
350 System.out.println("\nkey = " + k + ":");
351 System.out.println("val = " + bd.get(k));
352 }
353 System.out.println();
354 */
355 return G;
356 }
357
358 }