001 /*
002 * $Id: RGroebnerBasePseudoSeq.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.Map;
011 import java.util.TreeMap;
012 import java.util.Collections;
013
014 import org.apache.log4j.Logger;
015
016 import edu.jas.gb.Pair;
017 import edu.jas.poly.ExpVector;
018 import edu.jas.poly.GenPolynomial;
019 import edu.jas.structure.RegularRingElem;
020 import edu.jas.structure.RingFactory;
021 import edu.jas.ufd.GCDFactory;
022 import edu.jas.ufd.GreatestCommonDivisorAbstract;
023
024
025 /**
026 * Regular ring Groebner Base with pseudo reduction sequential algorithm.
027 * Implements R-Groebner bases and GB test.
028 * @param <C> coefficient type
029 * @author Heinz Kredel
030 */
031
032 public class RGroebnerBasePseudoSeq<C extends RegularRingElem<C>> extends RGroebnerBaseSeq<C> {
033
034
035 private static final Logger logger = Logger.getLogger(RGroebnerBasePseudoSeq.class);
036
037
038 private final boolean debug = logger.isDebugEnabled();
039
040
041 /**
042 * Greatest common divisor engine for coefficient content and primitive
043 * parts.
044 */
045 protected final GreatestCommonDivisorAbstract<C> engine;
046
047
048 /**
049 * Pseudo reduction engine.
050 */
051 protected final RPseudoReduction<C> red;
052
053
054 /**
055 * Coefficient ring factory.
056 */
057 protected final RingFactory<C> cofac;
058
059
060 /**
061 * Constructor.
062 * @param rf coefficient ring factory.
063 */
064 public RGroebnerBasePseudoSeq(RingFactory<C> rf) {
065 this(new RPseudoReductionSeq<C>(), rf);
066 }
067
068
069 /**
070 * Constructor.
071 * @param red R-pseudo-Reduction engine
072 * @param rf coefficient ring factory.
073 */
074 public RGroebnerBasePseudoSeq(RPseudoReduction<C> red, RingFactory<C> rf) {
075 super(red);
076 this.red = red;
077 cofac = rf;
078 engine = GCDFactory.<C> getImplementation(rf);
079 // not used: engine =
080 // (GreatestCommonDivisorAbstract<C>)GCDFactory.<C>getProxy( rf );
081 }
082
083
084 /**
085 * R-Groebner base using pairlist class.
086 * @param modv module variable number.
087 * @param F polynomial list.
088 * @return GB(F) a R-Groebner base of F.
089 */
090 @Override
091 public List<GenPolynomial<C>> GB(int modv, List<GenPolynomial<C>> F) {
092 if (F == null) {
093 return F;
094 }
095 /* boolean closure */
096 List<GenPolynomial<C>> bcF = red.reducedBooleanClosure(F);
097 logger.info("#bcF-#F = " + (bcF.size() - F.size()));
098 F = bcF;
099 /* normalize input */
100 List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>();
101 OrderedRPairlist<C> pairlist = null;
102 for (GenPolynomial<C> p : F) {
103 if (!p.isZERO()) {
104 p = engine.basePrimitivePart(p); // not monic, no field
105 p = p.abs();
106 if (p.isConstant() && p.leadingBaseCoefficient().isFull()) {
107 G.clear();
108 G.add(p);
109 return G; // since boolean closed and no threads are activated
110 }
111 G.add(p); // G.add( 0, p ); //reverse list
112 if (pairlist == null) {
113 pairlist = new OrderedRPairlist<C>(modv, p.ring);
114 }
115 // putOne not required
116 pairlist.put(p);
117 }
118 }
119 if (G.size() <= 1) {
120 return G; // since boolean closed and no threads are activated
121 }
122 /* loop on critical pairs */
123 Pair<C> pair;
124 GenPolynomial<C> pi;
125 GenPolynomial<C> pj;
126 GenPolynomial<C> S;
127 // GenPolynomial<C> D;
128 GenPolynomial<C> H;
129 List<GenPolynomial<C>> bcH;
130 while (pairlist.hasNext()) {
131 pair = pairlist.removeNext();
132 // System.out.println("pair = " + pair);
133 if (pair == null)
134 continue;
135
136 pi = pair.pi;
137 pj = pair.pj;
138 if (logger.isDebugEnabled()) {
139 logger.info("pi = " + pi);
140 logger.info("pj = " + pj);
141 }
142 if (!red.moduleCriterion(modv, pi, pj)) {
143 continue;
144 }
145
146 // S-polynomial -----------------------
147 // Criterion3(), Criterion4() not applicable
148 S = red.SPolynomial(pi, pj);
149 if (S.isZERO()) {
150 pair.setZero();
151 continue;
152 }
153 if (logger.isDebugEnabled()) {
154 logger.debug("ht(S) = " + S.leadingExpVector());
155 }
156
157 H = red.normalform(G, S);
158 if (H.isZERO()) {
159 pair.setZero();
160 continue;
161 }
162 if (logger.isDebugEnabled()) {
163 logger.debug("ht(H) = " + H.leadingExpVector());
164 }
165 H = engine.basePrimitivePart(H);
166 H = H.abs(); // not monic, no field
167 if (H.isConstant() && H.leadingBaseCoefficient().isFull()) {
168 // mostly useless
169 G.clear();
170 G.add(H);
171 return G; // not boolean closed ok, no threads are activated
172 }
173 if (logger.isDebugEnabled()) {
174 logger.debug("H = " + H);
175 }
176 if (!H.isZERO()) {
177 // logger.info("Sred = " + H);
178 // len = G.size();
179 bcH = red.reducedBooleanClosure(G, H);
180 // logger.info("#bcH = " + bcH.size());
181 // G.addAll( bcH );
182 for (GenPolynomial<C> h : bcH) {
183 h = engine.basePrimitivePart(h);
184 h = h.abs(); // monic() not ok, since no field
185 logger.info("bc(Sred) = " + h);
186 G.add(h);
187 pairlist.put(h);
188 }
189 if (debug) {
190 if (!pair.getUseCriterion3() || !pair.getUseCriterion4()) {
191 logger.info("H != 0 but: " + pair);
192 }
193 }
194 }
195 }
196 logger.debug("#sequential list = " + G.size());
197 G = minimalGB(G);
198 // G = red.irreducibleSet(G); // not correct since not boolean closed
199 logger.info("" + pairlist);
200 return G;
201 }
202
203
204 /**
205 * Minimal ordered Groebner basis.
206 * @param Gp a Groebner base.
207 * @return a reduced Groebner base of Gp.
208 */
209 @Override
210 public List<GenPolynomial<C>> minimalGB(List<GenPolynomial<C>> Gp) {
211 if (Gp == null || Gp.size() <= 1) {
212 return Gp;
213 }
214 // remove zero polynomials
215 List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>(Gp.size());
216 for (GenPolynomial<C> a : Gp) {
217 if (a != null && !a.isZERO()) { // always true in GB()
218 a = a.abs(); // already positive in GB
219 G.add(a);
220 }
221 }
222 // remove top reducible polynomials
223 logger.info("minGB start with " + G.size());
224 GenPolynomial<C> a, b;
225 List<GenPolynomial<C>> F;
226 F = new ArrayList<GenPolynomial<C>>(G.size());
227 while (G.size() > 0) {
228 a = G.remove(0);
229 b = a;
230 if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) {
231 // try to drop polynomial
232 List<GenPolynomial<C>> ff;
233 ff = new ArrayList<GenPolynomial<C>>(G);
234 ff.addAll(F);
235 a = red.normalform(ff, a);
236 if (a.isZERO()) {
237 if (false && !isGB(ff)) { // is really required, but why?
238 logger.info("minGB not dropped " + b);
239 F.add(b);
240 } else {
241 if (debug) {
242 logger.debug("minGB dropped " + b);
243 }
244 }
245 } else { // happens
246 logger.info("minGB not zero " + a);
247 F.add(a);
248 }
249 } else { // not top reducible, keep polynomial
250 F.add(a);
251 }
252 }
253 G = F;
254 Collections.reverse(G); // important for lex GB
255 // reduce remaining polynomials
256 int len = G.size();
257 int el = 0;
258 while (el < len) {
259 el++;
260 a = G.remove(0);
261 b = a;
262 a = red.normalform(G, a);
263 a = engine.basePrimitivePart(a); // not a.monic() since no field
264 a = a.abs();
265 if (red.isBooleanClosed(a)) {
266 List<GenPolynomial<C>> ff;
267 ff = new ArrayList<GenPolynomial<C>>(G);
268 ff.add(a);
269 if (true || isGB(ff)) {
270 if (debug) {
271 logger.debug("minGB reduced " + b + " to " + a);
272 }
273 G.add(a);
274 } else {
275 logger.info("minGB not reduced " + b + " to " + a);
276 G.add(b);
277 }
278 continue;
279 } else {
280 logger.info("minGB not boolean closed " + a);
281 G.add(b); // do not reduce
282 }
283 }
284 /* stratify: collect polynomials with equal leading terms */
285 ExpVector e, f;
286 F = new ArrayList<GenPolynomial<C>>(G.size());
287 List<GenPolynomial<C>> ff;
288 ff = new ArrayList<GenPolynomial<C>>(G);
289 for (int i = 0; i < ff.size(); i++) {
290 a = ff.get(i);
291 if (a == null || a.isZERO()) {
292 continue;
293 }
294 e = a.leadingExpVector();
295 for (int j = i + 1; j < ff.size(); j++) {
296 b = ff.get(j);
297 if (b == null || b.isZERO()) {
298 continue;
299 }
300 f = b.leadingExpVector();
301 if (e.equals(f)) {
302 // System.out.println("minGB e == f: " + a + ", " + b);
303 a = a.sum(b);
304 ff.set(j, null);
305 }
306 }
307 F.add(a);
308 }
309 if (true || isGB(F)) {
310 G = F;
311 } else {
312 logger.info("minGB not stratified " + F);
313 }
314 logger.info("minGB end with " + G.size());
315 return G;
316 }
317
318
319 /*
320 * Minimal ordered Groebner basis.
321 * @param Gp a Groebner base.
322 * @return a reduced Groebner base of Gp.
323 * @todo use primitivePart
324 */
325 List<GenPolynomial<C>> minimalGBtesting(List<GenPolynomial<C>> Gp) {
326 if (Gp == null || Gp.size() <= 1) {
327 return Gp;
328 }
329 // remove zero polynomials
330 List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>(Gp.size());
331 for (GenPolynomial<C> a : Gp) {
332 if (a != null && !a.isZERO()) { // always true in GB()
333 // already positive a = a.abs();
334 G.add(a);
335 }
336 }
337 if (G.size() <= 1) {
338 // wg monic do not return G;
339 }
340 // remove top reducible polynomials
341 GenPolynomial<C> a, b;
342 List<GenPolynomial<C>> F;
343 List<GenPolynomial<C>> bcH;
344 F = new ArrayList<GenPolynomial<C>>(G.size());
345 while (G.size() > 0) {
346 a = G.remove(0);
347 b = a;
348 if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) {
349 // drop polynomial
350 if (true || debug) {
351 List<GenPolynomial<C>> ff;
352 ff = new ArrayList<GenPolynomial<C>>(G);
353 ff.addAll(F);
354 a = red.normalform(ff, a);
355 if (!a.isZERO()) {
356 System.out.println("minGB nf(a) != 0 " + a);
357 bcH = red.reducedBooleanClosure(G, a);
358 if (bcH.size() > 1) { // never happend so far
359 System.out.println("minGB not bc: bcH size = " + bcH.size());
360 F.add(b); // do not replace, stay with b
361 } else {
362 // System.out.println("minGB add bc(a): a = " + a + ",
363 // bc(a) = " + bcH.get(0));
364 F.add(b); // do not replace, stay with b
365 // F.addAll( bcH );
366 }
367 } else {
368 if (!isGB(ff)) {
369 System.out.println("minGB not dropped " + b);
370 F.add(b);
371 } else {
372 System.out.println("minGB dropped " + b);
373 }
374 }
375 }
376 } else { // not top reducible, keep polynomial
377 F.add(a);
378 }
379 }
380 G = F;
381 if (G.size() <= 1) {
382 // wg monic return G;
383 }
384 Collections.reverse(G); // important for lex GB
385 // reduce remaining polynomials
386 int len = G.size();
387 int el = 0;
388 // System.out.println("minGB reducing " + len);
389 while (el < len) {
390 el++;
391 a = G.remove(0);
392 b = a;
393 // System.out.println("minGB doing " + el + ", a = " + a);
394 a = red.normalform(G, a);
395 // not bc:
396 a = engine.basePrimitivePart(a); // not a.monic() since no field
397 if (red.isBooleanClosed(a)) {
398 List<GenPolynomial<C>> ff;
399 ff = new ArrayList<GenPolynomial<C>>(G);
400 ff.add(a);
401 if (isGB(ff)) {
402 System.out.println("minGB reduced " + b + " to " + a);
403 G.add(a);
404 } else {
405 System.out.println("minGB not reduced " + b + " to " + a);
406 G.add(b);
407 }
408 continue;
409 }
410 System.out.println("minGB not bc: a = " + a + "\n BC(a) = " + red.booleanClosure(a)
411 + ", BR(a) = " + red.booleanRemainder(a));
412 bcH = red.reducedBooleanClosure(G, a);
413 if (bcH.size() > 1) {
414 System.out.println("minGB not bc: bcH size = " + bcH.size());
415 G.add(b); // do not reduce
416 } else {
417 // G.addAll( bcH );
418 G.add(b); // do not reduce
419 for (GenPolynomial<C> h : bcH) {
420 h = engine.basePrimitivePart(h);
421 h = h.abs(); // monic() not ok, since no field
422 // G.add( h );
423 }
424 }
425 }
426 // make abs if possible
427 F = new ArrayList<GenPolynomial<C>>(G.size());
428 for (GenPolynomial<C> p : G) {
429 a = p.abs();
430 F.add(a);
431 }
432 G = F;
433
434 if (false) {
435 return G;
436 }
437
438 // stratify: collect polynomials with equal leading terms
439 ExpVector e, f;
440 F = new ArrayList<GenPolynomial<C>>(G.size());
441 for (int i = 0; i < G.size(); i++) {
442 a = G.get(i);
443 if (a == null || a.isZERO()) {
444 continue;
445 }
446 e = a.leadingExpVector();
447 for (int j = i + 1; j < G.size(); j++) {
448 b = G.get(j);
449 if (b == null || b.isZERO()) {
450 continue;
451 }
452 f = b.leadingExpVector();
453 if (e.equals(f)) {
454 // System.out.println("minGB e == f: " + a + ", " + b);
455 a = a.sum(b);
456 G.set(j, null);
457 }
458 }
459 F.add(a);
460 }
461 G = F;
462
463 // info on boolean algebra element blocks
464 Map<C, List<GenPolynomial<C>>> bd = new TreeMap<C, List<GenPolynomial<C>>>();
465 for (GenPolynomial<C> p : G) {
466 C cf = p.leadingBaseCoefficient();
467 cf = cf.idempotent();
468 List<GenPolynomial<C>> block = bd.get(cf);
469 if (block == null) {
470 block = new ArrayList<GenPolynomial<C>>();
471 }
472 block.add(p);
473 bd.put(cf, block);
474 }
475 System.out.println("\nminGB bd:");
476 for (C k : bd.keySet()) {
477 System.out.println("\nkey = " + k + ":");
478 System.out.println("val = " + bd.get(k));
479 }
480 System.out.println();
481 //
482 return G;
483 }
484
485 }