001/* 002 * $Id: RGroebnerBasePseudoSeq.java 4116 2012-08-19 13:26:25Z kredel $ 003 */ 004 005package edu.jas.gbufd; 006 007 008import java.util.ArrayList; 009import java.util.Collections; 010import java.util.List; 011import java.util.Map; 012import java.util.TreeMap; 013 014import org.apache.log4j.Logger; 015 016import edu.jas.gb.Pair; 017import edu.jas.poly.ExpVector; 018import edu.jas.poly.GenPolynomial; 019import edu.jas.structure.RegularRingElem; 020import edu.jas.structure.RingFactory; 021import edu.jas.ufd.GCDFactory; 022import 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 032public 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 } 280 logger.info("minGB not boolean closed " + a); 281 G.add(b); // do not reduce 282 } 283 /* stratify: collect polynomials with equal leading terms */ 284 ExpVector e, f; 285 F = new ArrayList<GenPolynomial<C>>(G.size()); 286 List<GenPolynomial<C>> ff; 287 ff = new ArrayList<GenPolynomial<C>>(G); 288 for (int i = 0; i < ff.size(); i++) { 289 a = ff.get(i); 290 if (a == null || a.isZERO()) { 291 continue; 292 } 293 e = a.leadingExpVector(); 294 for (int j = i + 1; j < ff.size(); j++) { 295 b = ff.get(j); 296 if (b == null || b.isZERO()) { 297 continue; 298 } 299 f = b.leadingExpVector(); 300 if (e.equals(f)) { 301 // System.out.println("minGB e == f: " + a + ", " + b); 302 a = a.sum(b); 303 ff.set(j, null); 304 } 305 } 306 F.add(a); 307 } 308 //if (true || isGB(F)) { 309 G = F; 310 //} else { 311 // logger.info("minGB not stratified " + F); 312 //} 313 logger.info("minGB end with #G = " + G.size()); 314 return G; 315 } 316 317 318 /* 319 * Minimal ordered Groebner basis. 320 * @param Gp a Groebner base. 321 * @return a reduced Groebner base of Gp. 322 * @todo use primitivePart 323 */ 324 List<GenPolynomial<C>> minimalGBtesting(List<GenPolynomial<C>> Gp) { 325 if (Gp == null || Gp.size() <= 1) { 326 return Gp; 327 } 328 // remove zero polynomials 329 List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>(Gp.size()); 330 for (GenPolynomial<C> a : Gp) { 331 if (a != null && !a.isZERO()) { // always true in GB() 332 // already positive a = a.abs(); 333 G.add(a); 334 } 335 } 336 //if (G.size() <= 1) { 337 // wg monic do not return G; 338 //} 339 // remove top reducible polynomials 340 GenPolynomial<C> a, b; 341 List<GenPolynomial<C>> F; 342 List<GenPolynomial<C>> bcH; 343 F = new ArrayList<GenPolynomial<C>>(G.size()); 344 while (G.size() > 0) { 345 a = G.remove(0); 346 b = a; 347 if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) { 348 // drop polynomial 349 if (logger.isInfoEnabled()) { 350 List<GenPolynomial<C>> ff; 351 ff = new ArrayList<GenPolynomial<C>>(G); 352 ff.addAll(F); 353 a = red.normalform(ff, a); 354 if (!a.isZERO()) { 355 System.out.println("minGB nf(a) != 0 " + a); 356 bcH = red.reducedBooleanClosure(G, a); 357 if (bcH.size() > 1) { // never happend so far 358 System.out.println("minGB not bc: bcH size = " + bcH.size()); 359 F.add(b); // do not replace, stay with b 360 } else { 361 // System.out.println("minGB add bc(a): a = " + a + ", 362 // bc(a) = " + bcH.get(0)); 363 F.add(b); // do not replace, stay with b 364 // F.addAll( bcH ); 365 } 366 } else { 367 if (!isGB(ff)) { 368 System.out.println("minGB not dropped " + b); 369 F.add(b); 370 } else { 371 System.out.println("minGB dropped " + b); 372 } 373 } 374 } 375 } else { // not top reducible, keep polynomial 376 F.add(a); 377 } 378 } 379 G = F; 380 //if (G.size() <= 1) { 381 // wg monic return G; 382 //} 383 Collections.reverse(G); // important for lex GB 384 // reduce remaining polynomials 385 int len = G.size(); 386 int el = 0; 387 // System.out.println("minGB reducing " + len); 388 while (el < len) { 389 el++; 390 a = G.remove(0); 391 b = a; 392 // System.out.println("minGB doing " + el + ", a = " + a); 393 a = red.normalform(G, a); 394 // not bc: 395 a = engine.basePrimitivePart(a); // not a.monic() since no field 396 if (red.isBooleanClosed(a)) { 397 List<GenPolynomial<C>> ff; 398 ff = new ArrayList<GenPolynomial<C>>(G); 399 ff.add(a); 400 if (isGB(ff)) { 401 System.out.println("minGB reduced " + b + " to " + a); 402 G.add(a); 403 } else { 404 System.out.println("minGB not reduced " + b + " to " + a); 405 G.add(b); 406 } 407 continue; 408 } 409 System.out.println("minGB not bc: a = " + a + "\n BC(a) = " + red.booleanClosure(a) 410 + ", BR(a) = " + red.booleanRemainder(a)); 411 bcH = red.reducedBooleanClosure(G, a); 412 if (bcH.size() > 1) { 413 System.out.println("minGB not bc: bcH size = " + bcH.size()); 414 G.add(b); // do not reduce 415 } else { 416 // G.addAll( bcH ); 417 G.add(b); // do not reduce 418 for (GenPolynomial<C> h : bcH) { 419 h = engine.basePrimitivePart(h); 420 h = h.abs(); // monic() not ok, since no field 421 // G.add( h ); 422 } 423 } 424 } 425 // make abs if possible 426 F = new ArrayList<GenPolynomial<C>>(G.size()); 427 for (GenPolynomial<C> p : G) { 428 a = p.abs(); 429 F.add(a); 430 } 431 G = F; 432 //if (false) { 433 // return G; 434 //} 435 // stratify: collect polynomials with equal leading terms 436 ExpVector e, f; 437 F = new ArrayList<GenPolynomial<C>>(G.size()); 438 for (int i = 0; i < G.size(); i++) { 439 a = G.get(i); 440 if (a == null || a.isZERO()) { 441 continue; 442 } 443 e = a.leadingExpVector(); 444 for (int j = i + 1; j < G.size(); j++) { 445 b = G.get(j); 446 if (b == null || b.isZERO()) { 447 continue; 448 } 449 f = b.leadingExpVector(); 450 if (e.equals(f)) { 451 // System.out.println("minGB e == f: " + a + ", " + b); 452 a = a.sum(b); 453 G.set(j, null); 454 } 455 } 456 F.add(a); 457 } 458 G = F; 459 460 // info on boolean algebra element blocks 461 Map<C, List<GenPolynomial<C>>> bd = new TreeMap<C, List<GenPolynomial<C>>>(); 462 for (GenPolynomial<C> p : G) { 463 C cf = p.leadingBaseCoefficient(); 464 cf = cf.idempotent(); 465 List<GenPolynomial<C>> block = bd.get(cf); 466 if (block == null) { 467 block = new ArrayList<GenPolynomial<C>>(); 468 } 469 block.add(p); 470 bd.put(cf, block); 471 } 472 System.out.println("\nminGB bd:"); 473 for (Map.Entry<C, List<GenPolynomial<C>>> me : bd.entrySet()) { 474 System.out.println("\nkey = " + me.getKey() + ":"); 475 System.out.println("val = " + me.getValue()); 476 } 477 System.out.println(); 478 // 479 return G; 480 } 481 482}