001/* 002 * $Id: SolvableGroebnerBasePseudoRecSeq.java 5219 2015-04-12 09:59:36Z kredel $ 003 */ 004 005package edu.jas.gbufd; 006 007 008import java.util.ArrayList; 009import java.util.Collections; 010import java.util.List; 011 012import org.apache.log4j.Logger; 013 014import edu.jas.gb.OrderedPairlist; 015import edu.jas.gb.Pair; 016import edu.jas.gb.PairList; 017import edu.jas.gb.SolvableExtendedGB; 018import edu.jas.gb.SolvableGroebnerBaseAbstract; 019import edu.jas.poly.GenPolynomial; 020import edu.jas.poly.GenPolynomialRing; 021import edu.jas.poly.GenSolvablePolynomial; 022import edu.jas.poly.GenSolvablePolynomialRing; 023import edu.jas.poly.QLRSolvablePolynomialRing; 024import edu.jas.poly.PolyUtil; 025import edu.jas.poly.PolynomialList; 026import edu.jas.structure.GcdRingElem; 027import edu.jas.structure.RingFactory; 028import edu.jas.ufd.GCDFactory; 029import edu.jas.ufd.GreatestCommonDivisorAbstract; 030import edu.jas.ufd.GreatestCommonDivisorFake; 031 032 033/** 034 * Solvable Groebner Base with pseudo reduction sequential algorithm. Implements 035 * coefficient fraction free Groebner bases. Coefficients can for example be 036 * (commutative) multivariate polynomials. 037 * @param <C> coefficient type 038 * @author Heinz Kredel 039 * 040 * @see edu.jas.application.GBAlgorithmBuilder 041 * @see edu.jas.gbufd.GBFactory 042 */ 043 044public class SolvableGroebnerBasePseudoRecSeq<C extends GcdRingElem<C>> extends 045 SolvableGroebnerBaseAbstract<GenPolynomial<C>> { 046 047 048 private static final Logger logger = Logger.getLogger(SolvableGroebnerBasePseudoRecSeq.class); 049 050 051 private final boolean debug = logger.isDebugEnabled(); 052 053 054 /** 055 * Greatest common divisor engine for coefficient content and primitive 056 * parts. 057 */ 058 protected final GreatestCommonDivisorAbstract<C> engine; 059 060 061 /** 062 * Pseudo reduction engine. 063 */ 064 protected final SolvablePseudoReduction<C> sredRec; 065 066 067 /** 068 * Pseudo reduction engine. 069 */ 070 protected final SolvablePseudoReduction<GenPolynomial<C>> sred; 071 072 073 /** 074 * Coefficient ring factory. 075 */ 076 //protected final RingFactory<C> cofac; 077 protected final GenPolynomialRing<C> cofac; 078 079 080 /** 081 * Constructor. 082 * @param rf coefficient ring factory. 083 */ 084 public SolvableGroebnerBasePseudoRecSeq(RingFactory<GenPolynomial<C>> rf) { 085 this(rf, new SolvablePseudoReductionSeq<C>()); 086 } 087 088 089 /** 090 * Constructor. 091 * @param rf coefficient ring factory. 092 * @param pl pair selection strategy 093 */ 094 public SolvableGroebnerBasePseudoRecSeq(RingFactory<GenPolynomial<C>> rf, PairList<GenPolynomial<C>> pl) { 095 this(rf, new SolvablePseudoReductionSeq<C>(), pl); 096 } 097 098 099 /** 100 * Constructor. 101 * @param rf coefficient ring factory. 102 * @param red pseudo reduction engine. <b>Note:</b> red must be an instance 103 * of PseudoReductionSeq. 104 */ 105 public SolvableGroebnerBasePseudoRecSeq(RingFactory<GenPolynomial<C>> rf, SolvablePseudoReduction<C> red) { 106 this(rf, red, new OrderedPairlist<GenPolynomial<C>>()); 107 } 108 109 110 /** 111 * Constructor. 112 * @param rf coefficient ring factory. 113 * @param red pseudo reduction engine. <b>Note:</b> red must be an instance 114 * of PseudoReductionSeq. 115 * @param pl pair selection strategy 116 */ 117 @SuppressWarnings({ "cast", "unchecked" }) 118 public SolvableGroebnerBasePseudoRecSeq(RingFactory<GenPolynomial<C>> rf, SolvablePseudoReduction<C> red, 119 PairList<GenPolynomial<C>> pl) { 120 super((SolvablePseudoReduction<GenPolynomial<C>>) (SolvablePseudoReduction) red, pl); 121 this.sred = (SolvablePseudoReduction<GenPolynomial<C>>) (SolvablePseudoReduction) red; 122 sredRec = red; 123 //this.red = sred; 124 cofac = (GenPolynomialRing<C>) rf; 125 if (!cofac.isCommutative()) { 126 logger.warn("right reduction not correct for " + cofac.toScript()); 127 engine = new GreatestCommonDivisorFake<C>(); 128 // TODO check that also coeffTable is empty for recursive solvable poly ring 129 } else { 130 //engine = GCDFactory.<C> getImplementation(cofac.coFac); 131 // 132 engine = GCDFactory.<C> getProxy(cofac.coFac); 133 } 134 } 135 136 137 /** 138 * Left Groebner base using pairlist class. 139 * @param modv module variable number. 140 * @param F polynomial list. 141 * @return GB(F) a Groebner base of F. 142 */ 143 @Override 144 public List<GenSolvablePolynomial<GenPolynomial<C>>> leftGB(int modv, 145 List<GenSolvablePolynomial<GenPolynomial<C>>> F) { 146 List<GenSolvablePolynomial<GenPolynomial<C>>> G = normalizeZerosOnes(F); 147 G = PolynomialList.<GenPolynomial<C>> castToSolvableList(PolyUtil.<C> monicRec(engine 148 .recursivePrimitivePart(PolynomialList.<GenPolynomial<C>> castToList(G)))); 149 if (G.size() <= 1) { 150 return G; 151 } 152 GenSolvablePolynomialRing<GenPolynomial<C>> ring = G.get(0).ring; 153 if (ring.coFac.isField()) { // TODO remove 154 throw new IllegalArgumentException("coefficients from a field"); 155 } 156 PairList<GenPolynomial<C>> pairlist = strategy.create(modv, ring); 157 pairlist.put(PolynomialList.<GenPolynomial<C>> castToList(G)); 158 logger.info("leftGB start " + pairlist); 159 160 Pair<GenPolynomial<C>> pair; 161 GenSolvablePolynomial<GenPolynomial<C>> pi, pj, S, H; 162 while (pairlist.hasNext()) { 163 pair = pairlist.removeNext(); 164 if (pair == null) 165 continue; 166 167 pi = (GenSolvablePolynomial<GenPolynomial<C>>) pair.pi; 168 pj = (GenSolvablePolynomial<GenPolynomial<C>>) pair.pj; 169 if (debug) { 170 logger.debug("pi = " + pi); 171 logger.debug("pj = " + pj); 172 } 173 174 S = sred.leftSPolynomial(pi, pj); 175 if (S.isZERO()) { 176 pair.setZero(); 177 continue; 178 } 179 if (debug) { 180 logger.info("ht(S) = " + S.leadingExpVector()); 181 } 182 183 H = sredRec.leftNormalformRecursive(G, S); 184 if (H.isZERO()) { 185 pair.setZero(); 186 continue; 187 } 188 if (debug) { 189 logger.info("ht(H) = " + H.leadingExpVector() + ", #(H) = " + H.length()); 190 } 191 H = (GenSolvablePolynomial<GenPolynomial<C>>) engine.recursivePrimitivePart(H); 192 H = PolyUtil.<C> monic(H); 193 if (H.isConstant()) { 194 G.clear(); 195 G.add(H); 196 return G; // since no threads are activated 197 } 198 if (debug) { 199 logger.info("lc(pp(H)) = " + H.leadingBaseCoefficient().toScript()); 200 } 201 if (H.length() > 0) { 202 G.add(H); 203 pairlist.put(H); 204 } 205 } 206 logger.debug("#sequential list = " + G.size()); 207 G = leftMinimalGB(G); 208 logger.info("leftGB end " + pairlist); 209 return G; 210 } 211 212 213 /** 214 * Minimal ordered Solvable Groebner basis. 215 * @param Gp a Solvable Groebner base. 216 * @return a reduced Solvable Groebner base of Gp. 217 */ 218 @Override 219 public List<GenSolvablePolynomial<GenPolynomial<C>>> leftMinimalGB( 220 List<GenSolvablePolynomial<GenPolynomial<C>>> Gp) { 221 List<GenSolvablePolynomial<GenPolynomial<C>>> G = normalizeZerosOnes(Gp); 222 if (G.size() <= 1) { 223 return G; 224 } 225 // remove top reducible polynomials 226 GenSolvablePolynomial<GenPolynomial<C>> a; 227 List<GenSolvablePolynomial<GenPolynomial<C>>> F = new ArrayList<GenSolvablePolynomial<GenPolynomial<C>>>( 228 G.size()); 229 while (G.size() > 0) { 230 a = G.remove(0); 231 if (sred.isTopReducible(G, a) || sred.isTopReducible(F, a)) { 232 // drop polynomial 233 if (debug) { 234 System.out.println("dropped " + a); 235 List<GenSolvablePolynomial<GenPolynomial<C>>> ff; 236 ff = new ArrayList<GenSolvablePolynomial<GenPolynomial<C>>>(G); 237 ff.addAll(F); 238 a = sredRec.leftNormalformRecursive(ff, a); 239 if (!a.isZERO()) { 240 System.out.println("error, nf(a) " + a); 241 } 242 } 243 } else { 244 F.add(a); 245 } 246 } 247 G = F; 248 if (G.size() <= 1) { 249 return G; 250 } 251 Collections.reverse(G); // important for lex GB 252 // reduce remaining polynomials 253 int len = G.size(); 254 int i = 0; 255 while (i < len) { 256 a = G.remove(0); 257 //System.out.println("doing " + a.length()); 258 a = sredRec.leftNormalformRecursive(G, a); 259 a = (GenSolvablePolynomial<GenPolynomial<C>>) engine.recursivePrimitivePart(a); //a.monic(); not possible 260 a = PolyUtil.<C> monic(a); 261 G.add(a); // adds as last 262 i++; 263 } 264 return G; 265 } 266 267 268 /** 269 * Twosided Solvable Groebner base using pairlist class. 270 * @param modv number of module variables. 271 * @param Fp solvable polynomial list. 272 * @return tsGB(Fp) a twosided Groebner base of Fp. 273 */ 274 @Override 275 public List<GenSolvablePolynomial<GenPolynomial<C>>> twosidedGB(int modv, 276 List<GenSolvablePolynomial<GenPolynomial<C>>> Fp) { 277 List<GenSolvablePolynomial<GenPolynomial<C>>> G = normalizeZerosOnes(Fp); 278 G = PolynomialList.<GenPolynomial<C>> castToSolvableList(PolyUtil.<C> monicRec(engine 279 .recursivePrimitivePart(PolynomialList.<GenPolynomial<C>> castToList(G)))); 280 if (G.size() < 1) { // two-sided! 281 return G; 282 } 283 //System.out.println("G = " + G); 284 GenSolvablePolynomialRing<GenPolynomial<C>> ring = G.get(0).ring; // assert != null 285 if (ring.coFac.isField()) { // TODO remove 286 throw new IllegalArgumentException("coefficients from a field"); 287 } 288 // add also coefficient generators 289 List<GenSolvablePolynomial<GenPolynomial<C>>> X; 290 X = PolynomialList.castToSolvableList(ring.generators(modv)); 291 logger.info("right multipliers = " + X); 292 List<GenSolvablePolynomial<GenPolynomial<C>>> F = new ArrayList<GenSolvablePolynomial<GenPolynomial<C>>>( 293 G.size() * (1 + X.size())); 294 F.addAll(G); 295 GenSolvablePolynomial<GenPolynomial<C>> p, x, q; 296 for (int i = 0; i < F.size(); i++) { // F changes 297 p = F.get(i); 298 for (int j = 0; j < X.size(); j++) { 299 x = X.get(j); 300 if (x.isONE()) { 301 continue; 302 } 303 q = p.multiply(x); 304 q = sredRec.leftNormalformRecursive(F, q); 305 if (!q.isZERO()) { 306 q = (GenSolvablePolynomial<GenPolynomial<C>>) engine.recursivePrimitivePart(q); 307 q = PolyUtil.<C> monic(q); 308 F.add(q); 309 } 310 } 311 } 312 G = F; 313 //System.out.println("G generated = " + G); 314 PairList<GenPolynomial<C>> pairlist = strategy.create(modv, ring); 315 pairlist.put(PolynomialList.<GenPolynomial<C>> castToList(G)); 316 logger.info("twosidedGB start " + pairlist); 317 318 Pair<GenPolynomial<C>> pair; 319 GenSolvablePolynomial<GenPolynomial<C>> pi, pj, S, H; 320 while (pairlist.hasNext()) { 321 pair = pairlist.removeNext(); 322 if (pair == null) { 323 continue; 324 } 325 326 pi = (GenSolvablePolynomial<GenPolynomial<C>>) pair.pi; 327 pj = (GenSolvablePolynomial<GenPolynomial<C>>) pair.pj; 328 if (debug) { 329 logger.debug("pi = " + pi); 330 logger.debug("pj = " + pj); 331 } 332 333 S = sred.leftSPolynomial(pi, pj); 334 if (S.isZERO()) { 335 pair.setZero(); 336 continue; 337 } 338 if (debug) { 339 logger.info("ht(S) = " + S.leadingExpVector()); 340 } 341 342 H = sredRec.leftNormalformRecursive(G, S); 343 if (H.isZERO()) { 344 pair.setZero(); 345 continue; 346 } 347 if (debug) { 348 logger.info("ht(H) = " + H.leadingExpVector()); 349 } 350 351 H = (GenSolvablePolynomial<GenPolynomial<C>>) engine.recursivePrimitivePart(H); 352 H = PolyUtil.<C> monic(H); 353 if (H.isONE()) { 354 G.clear(); 355 G.add(H); 356 return G; // since no threads are activated 357 } 358 if (debug) { 359 logger.info("lc(pp(H)) = " + H.leadingBaseCoefficient()); 360 } 361 if (H.length() > 0) { 362 G.add(H); 363 pairlist.put(H); 364 for (int j = 0; j < X.size(); j++) { 365 x = X.get(j); 366 if (x.isONE()) { 367 continue; 368 } 369 p = H.multiply(x); 370 p = sredRec.leftNormalformRecursive(G, p); 371 if (!p.isZERO()) { 372 p = (GenSolvablePolynomial<GenPolynomial<C>>) engine.recursivePrimitivePart(p); 373 p = PolyUtil.<C> monic(p); 374 if (p.isONE()) { 375 G.clear(); 376 G.add(p); 377 return G; // since no threads are activated 378 } 379 G.add(p); 380 pairlist.put(p); 381 } 382 } 383 } 384 } 385 logger.debug("#sequential list = " + G.size()); 386 G = leftMinimalGB(G); 387 logger.info("twosidedGB end " + pairlist); 388 return G; 389 } 390 391 392 /** 393 * Left Groebner base test. 394 * @param modv number of module variables. 395 * @param F solvable polynomial list. 396 * @return true, if F is a left Groebner base, else false. 397 */ 398 @Override 399 public boolean isLeftGBsimple(int modv, List<GenSolvablePolynomial<GenPolynomial<C>>> F) { 400 //System.out.println("F to left check = " + F); 401 GenSolvablePolynomial<GenPolynomial<C>> pi, pj, s, h; 402 for (int i = 0; i < F.size(); i++) { 403 pi = F.get(i); 404 for (int j = i + 1; j < F.size(); j++) { 405 pj = F.get(j); 406 if (!red.moduleCriterion(modv, pi, pj)) { 407 continue; 408 } 409 // if ( ! red.criterion4( pi, pj ) ) { continue; } 410 s = sred.leftSPolynomial(pi, pj); 411 if (s.isZERO()) { 412 continue; 413 } 414 h = sredRec.leftNormalformRecursive(F, s); 415 if (!h.isZERO()) { 416 return false; 417 } 418 } 419 } 420 return true; 421 } 422 423 424 /** 425 * Left Groebner base idempotence test. 426 * @param modv module variable number. 427 * @param F solvable polynomial list. 428 * @return true, if F is equal to GB(F), else false. 429 */ 430 @Override 431 public boolean isLeftGBidem(int modv, List<GenSolvablePolynomial<GenPolynomial<C>>> F) { 432 if (F == null || F.isEmpty()) { 433 return true; 434 } 435 GenSolvablePolynomialRing<GenPolynomial<C>> pring = F.get(0).ring; 436 List<GenSolvablePolynomial<GenPolynomial<C>>> G = leftGB(modv, F); 437 PolynomialList<GenPolynomial<C>> Fp = new PolynomialList<GenPolynomial<C>>(pring, F); 438 PolynomialList<GenPolynomial<C>> Gp = new PolynomialList<GenPolynomial<C>>(pring, G); 439 return Fp.compareTo(Gp) == 0; 440 } 441 442 443 /** 444 * Twosided Groebner base test. 445 * @param modv number of module variables. 446 * @param Fp solvable polynomial list. 447 * @return true, if Fp is a two-sided Groebner base, else false. 448 */ 449 @Override 450 public boolean isTwosidedGB(int modv, List<GenSolvablePolynomial<GenPolynomial<C>>> Fp) { 451 //System.out.println("F to twosided check = " + Fp); 452 if (Fp == null || Fp.size() == 0) { // 0 not 1 453 return true; 454 } 455 GenSolvablePolynomialRing<GenPolynomial<C>> ring = Fp.get(0).ring; // assert != null 456 //List<GenSolvablePolynomial<C>> X = generateUnivar( modv, Fp ); 457 List<GenSolvablePolynomial<GenPolynomial<C>>> X, Y; 458 X = PolynomialList.castToSolvableList(ring.generators()); // todo use? modv 459 Y = new ArrayList<GenSolvablePolynomial<GenPolynomial<C>>>(); 460 for (GenSolvablePolynomial<GenPolynomial<C>> x : X) { 461 if (x.isConstant()) { 462 Y.add(x); 463 } 464 } 465 X = Y; 466 X.addAll(ring.univariateList(modv)); 467 logger.info("right multipliers = " + X); 468 List<GenSolvablePolynomial<GenPolynomial<C>>> F = new ArrayList<GenSolvablePolynomial<GenPolynomial<C>>>( 469 Fp.size() * (1 + X.size())); 470 F.addAll(Fp); 471 GenSolvablePolynomial<GenPolynomial<C>> p, x, pi, pj, s, h; 472 for (int i = 0; i < Fp.size(); i++) { 473 p = Fp.get(i); 474 for (int j = 0; j < X.size(); j++) { 475 x = X.get(j); 476 if (x.isONE()) { 477 continue; 478 } 479 p = p.multiply(x); 480 p = sredRec.leftNormalformRecursive(F, p); 481 if (!p.isZERO()) { 482 return false; 483 //F.add(p); 484 } 485 } 486 } 487 //System.out.println("F to check = " + F); 488 for (int i = 0; i < F.size(); i++) { 489 pi = F.get(i); 490 for (int j = i + 1; j < F.size(); j++) { 491 pj = F.get(j); 492 if (!red.moduleCriterion(modv, pi, pj)) { 493 continue; 494 } 495 // if ( ! red.criterion4( pi, pj ) ) { continue; } 496 s = sred.leftSPolynomial(pi, pj); 497 if (s.isZERO()) { 498 continue; 499 } 500 h = sredRec.leftNormalformRecursive(F, s); 501 if (!h.isZERO()) { 502 logger.info("is not TwosidedGB: " + h); 503 return false; 504 } 505 } 506 } 507 return true; 508 } 509 510 511 /** 512 * Solvable Extended Groebner base using critical pair class. 513 * @param modv module variable number. 514 * @param F solvable polynomial list. 515 * @return a container for an extended left Groebner base of F. <b>Note: 516 * </b> not implemented; 517 */ 518 //@SuppressWarnings("unchecked") 519 @Override 520 public SolvableExtendedGB<GenPolynomial<C>> extLeftGB(int modv, 521 List<GenSolvablePolynomial<GenPolynomial<C>>> F) { 522 throw new UnsupportedOperationException(); // TODO 523 } 524 525}