001/* 002 * $Id: GroebnerBasePseudoParallel.java 5061 2015-01-01 19:45:33Z kredel $ 003 */ 004 005package edu.jas.gbufd; 006 007 008import java.util.ArrayList; 009import java.util.Collections; 010import java.util.List; 011import java.util.ListIterator; 012import java.util.concurrent.Semaphore; 013 014import org.apache.log4j.Logger; 015 016import edu.jas.gb.GroebnerBaseAbstract; 017import edu.jas.gb.OrderedPairlist; 018import edu.jas.gb.Pair; 019import edu.jas.gb.PairList; 020import edu.jas.poly.GenPolynomial; 021import edu.jas.poly.GenPolynomialRing; 022import edu.jas.structure.GcdRingElem; 023import edu.jas.structure.RingFactory; 024import edu.jas.ufd.GCDFactory; 025import edu.jas.ufd.GreatestCommonDivisorAbstract; 026import edu.jas.util.Terminator; 027import edu.jas.util.ThreadPool; 028 029 030/** 031 * Groebner Base with pseudo reduction multi-threaded parallel algorithm. 032 * Implements coefficient fraction free Groebner bases. 033 * Coefficients can for example be integers or (commutative) univariate polynomials. 034 * @param <C> coefficient type 035 * @author Heinz Kredel 036 * 037 * @see edu.jas.application.GBAlgorithmBuilder 038 * @see edu.jas.gbufd.GBFactory 039 */ 040 041public class GroebnerBasePseudoParallel<C extends GcdRingElem<C>> extends GroebnerBaseAbstract<C> { 042 043 044 private static final Logger logger = Logger.getLogger(GroebnerBasePseudoParallel.class); 045 046 047 private final boolean debug = logger.isDebugEnabled(); 048 049 050 /** 051 * Number of threads to use. 052 */ 053 protected final int threads; 054 055 056 /** 057 * Pool of threads to use. 058 */ 059 protected transient final ThreadPool pool; 060 061 062 /** 063 * Greatest common divisor engine for coefficient content and primitive 064 * parts. 065 */ 066 protected final GreatestCommonDivisorAbstract<C> engine; 067 068 069 /** 070 * Pseudo reduction engine. 071 */ 072 protected final PseudoReduction<C> red; 073 074 075 /** 076 * Coefficient ring factory. 077 */ 078 protected final RingFactory<C> cofac; 079 080 081 /** 082 * Constructor. 083 * @param threads number of threads to use. 084 * @param rf coefficient ring factory. 085 */ 086 public GroebnerBasePseudoParallel(int threads, RingFactory<C> rf) { 087 this(threads, rf, new PseudoReductionPar<C>()); 088 } 089 090 091 /** 092 * Constructor. 093 * @param threads number of threads to use. 094 * @param rf coefficient ring factory. <b>Note:</b> red must be an instance 095 * of PseudoReductionPar. 096 * @param red pseudo reduction engine. 097 */ 098 public GroebnerBasePseudoParallel(int threads, RingFactory<C> rf, PseudoReduction<C> red) { 099 this(threads, rf, red, new ThreadPool(threads)); 100 } 101 102 103 /** 104 * Constructor. 105 * @param threads number of threads to use. 106 * @param rf coefficient ring factory. <b>Note:</b> red must be an instance 107 * of PseudoReductionPar. 108 * @param red pseudo reduction engine. 109 * @param pool ThreadPool to use. 110 */ 111 public GroebnerBasePseudoParallel(int threads, RingFactory<C> rf, PseudoReduction<C> red, ThreadPool pool) { 112 this(threads, rf, red, pool, new OrderedPairlist<C>()); 113 } 114 115 116 /** 117 * Constructor. 118 * @param threads number of threads to use. 119 * @param rf coefficient ring factory. <b>Note:</b> red must be an instance 120 * of PseudoReductionPar. 121 * @param pl pair selection strategy 122 */ 123 public GroebnerBasePseudoParallel(int threads, RingFactory<C> rf, PairList<C> pl) { 124 this(threads, rf, new PseudoReductionPar<C>(), new ThreadPool(threads), pl); 125 } 126 127 128 /** 129 * Constructor. 130 * @param threads number of threads to use. 131 * @param rf coefficient ring factory. <b>Note:</b> red must be an instance 132 * of PseudoReductionPar. 133 * @param red pseudo reduction engine. 134 * @param pool ThreadPool to use. 135 * @param pl pair selection strategy 136 */ 137 public GroebnerBasePseudoParallel(int threads, RingFactory<C> rf, PseudoReduction<C> red, 138 ThreadPool pool, PairList<C> pl) { 139 super(red, pl); 140 if (!(red instanceof PseudoReductionPar)) { 141 logger.warn("parallel GB should use parallel aware reduction"); 142 } 143 this.red = red; 144 cofac = rf; 145 if (threads < 1) { 146 threads = 1; 147 } 148 this.threads = threads; 149 engine = GCDFactory.<C> getImplementation(rf); 150 //not used: engine = (GreatestCommonDivisorAbstract<C>)GCDFactory.<C>getProxy( rf ); 151 this.pool = pool; 152 } 153 154 155 /** 156 * Cleanup and terminate ThreadPool. 157 */ 158 @Override 159 public void terminate() { 160 if (pool == null) { 161 return; 162 } 163 pool.terminate(); 164 } 165 166 167 /** 168 * Cancel ThreadPool. 169 */ 170 @Override 171 public int cancel() { 172 if (pool == null) { 173 return 0; 174 } 175 int s = pool.cancel(); 176 return s; 177 } 178 179 180 /** 181 * Groebner base using pairlist class. 182 * @param modv module variable number. 183 * @param F polynomial list. 184 * @return GB(F) a Groebner base of F. 185 */ 186 public List<GenPolynomial<C>> GB(int modv, List<GenPolynomial<C>> F) { 187 List<GenPolynomial<C>> G = normalizeZerosOnes(F); 188 G = engine.basePrimitivePart(G); 189 if ( G.size() <= 1 ) { 190 return G; 191 } 192 GenPolynomialRing<C> ring = G.get(0).ring; 193 if ( ring.coFac.isField() ) { // TODO remove 194 throw new IllegalArgumentException("coefficients from a field"); 195 } 196 PairList<C> pairlist = strategy.create( modv, ring ); 197 pairlist.put(G); 198 199 /* 200 GenPolynomial<C> p; 201 List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>(); 202 PairList<C> pairlist = null; 203 int l = F.size(); 204 ListIterator<GenPolynomial<C>> it = F.listIterator(); 205 while (it.hasNext()) { 206 p = it.next(); 207 if (p.length() > 0) { 208 p = engine.basePrimitivePart(p); //p.monic(); 209 p = p.abs(); 210 if (p.isConstant()) { 211 G.clear(); 212 G.add(p); 213 return G; // since no threads are activated 214 } 215 G.add(p); 216 if (pairlist == null) { 217 //pairlist = new OrderedPairlist<C>(modv, p.ring); 218 pairlist = strategy.create(modv, p.ring); 219 } 220 // putOne not required 221 pairlist.put(p); 222 } else { 223 l--; 224 } 225 } 226 if (l <= 1) { 227 return G; // since no threads are activated 228 } 229 */ 230 logger.info("start " + pairlist); 231 232 Terminator fin = new Terminator(threads); 233 PseudoReducer<C> R; 234 for (int i = 0; i < threads; i++) { 235 R = new PseudoReducer<C>(fin, G, pairlist, engine); 236 pool.addJob(R); 237 } 238 fin.waitDone(); 239 if (Thread.currentThread().isInterrupted()) { 240 throw new RuntimeException("interrupt before minimalGB"); 241 } 242 logger.debug("#parallel list = " + G.size()); 243 G = minimalGB(G); 244 logger.info("" + pairlist); 245 return G; 246 } 247 248 249 /** 250 * Minimal ordered Groebner basis. 251 * @param Gp a Groebner base. 252 * @return a reduced Groebner base of Gp. 253 */ 254 @Override 255 public List<GenPolynomial<C>> minimalGB(List<GenPolynomial<C>> Gp) { 256 List<GenPolynomial<C>> G = normalizeZerosOnes(Gp); 257 /* 258 if (Gp == null || Gp.size() <= 1) { 259 return Gp; 260 } 261 // remove zero polynomials 262 List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>(Gp.size()); 263 for (GenPolynomial<C> a : Gp) { 264 if (a != null && !a.isZERO()) { // always true in GB() 265 // already positive a = a.abs(); 266 G.add(a); 267 } 268 } 269 */ 270 if (G.size() <= 1) { 271 return G; 272 } 273 // remove top reducible polynomials 274 GenPolynomial<C> a; 275 List<GenPolynomial<C>> F; 276 F = new ArrayList<GenPolynomial<C>>(G.size()); 277 while (G.size() > 0) { 278 a = G.remove(0); 279 if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) { 280 // drop polynomial 281 if (debug) { 282 System.out.println("dropped " + a); 283 List<GenPolynomial<C>> ff; 284 ff = new ArrayList<GenPolynomial<C>>(G); 285 ff.addAll(F); 286 a = red.normalform(ff, a); 287 if (!a.isZERO()) { 288 System.out.println("error, nf(a) " + a); 289 } 290 } 291 } else { 292 F.add(a); 293 } 294 } 295 G = F; 296 if (G.size() <= 1) { 297 return G; 298 } 299 Collections.reverse(G); // important for lex GB 300 // reduce remaining polynomials 301 @SuppressWarnings("cast") 302 PseudoMiReducer<C>[] mirs = (PseudoMiReducer<C>[]) new PseudoMiReducer[G.size()]; 303 int i = 0; 304 F = new ArrayList<GenPolynomial<C>>(G.size()); 305 while (G.size() > 0) { 306 a = G.remove(0); 307 List<GenPolynomial<C>> R = new ArrayList<GenPolynomial<C>>(G.size() + F.size()); 308 R.addAll(G); 309 R.addAll(F); 310 // System.out.println("doing " + a.length()); 311 mirs[i] = new PseudoMiReducer<C>(R, a, engine); 312 pool.addJob(mirs[i]); 313 i++; 314 F.add(a); 315 } 316 G = F; 317 F = new ArrayList<GenPolynomial<C>>(G.size()); 318 for (i = 0; i < mirs.length; i++) { 319 a = mirs[i].getNF(); 320 F.add(a); 321 } 322 return F; 323 } 324 325} 326 327 328/** 329 * Pseudo GB Reducing worker threads. 330 */ 331class PseudoReducer<C extends GcdRingElem<C>> implements Runnable { 332 333 334 private final List<GenPolynomial<C>> G; 335 336 337 private final PairList<C> pairlist; 338 339 340 private final Terminator fin; 341 342 343 private final PseudoReductionPar<C> red; 344 345 346 private final GreatestCommonDivisorAbstract<C> engine; 347 348 349 private static final Logger logger = Logger.getLogger(PseudoReducer.class); 350 351 352 PseudoReducer(Terminator fin, List<GenPolynomial<C>> G, PairList<C> L, 353 GreatestCommonDivisorAbstract<C> engine) { 354 this.fin = fin; 355 this.G = G; 356 pairlist = L; 357 red = new PseudoReductionPar<C>(); 358 this.engine = engine; 359 fin.initIdle(1); 360 } 361 362 363 /** 364 * to string 365 */ 366 @Override 367 public String toString() { 368 return "PseudoReducer"; 369 } 370 371 372 public void run() { 373 Pair<C> pair; 374 GenPolynomial<C> pi; 375 GenPolynomial<C> pj; 376 GenPolynomial<C> S; 377 GenPolynomial<C> H; 378 //boolean set = false; 379 int reduction = 0; 380 int sleeps = 0; 381 while (pairlist.hasNext() || fin.hasJobs()) { 382 while (!pairlist.hasNext()) { 383 // wait 384 //fin.beIdle(); set = true; 385 try { 386 sleeps++; 387 if (sleeps % 10 == 0) { 388 logger.info(" reducer is sleeping"); 389 } else { 390 logger.debug("r"); 391 } 392 Thread.sleep(100); 393 } catch (InterruptedException e) { 394 break; 395 } 396 if (!fin.hasJobs()) { 397 break; 398 } 399 } 400 if (!pairlist.hasNext() && !fin.hasJobs()) { 401 break; 402 } 403 404 fin.notIdle(); // before pairlist get 405 pair = pairlist.removeNext(); 406 if (Thread.currentThread().isInterrupted()) { 407 fin.initIdle(1); 408 throw new RuntimeException("interrupt after removeNext"); 409 } 410 if (pair == null) { 411 fin.initIdle(1); 412 continue; 413 } 414 415 pi = pair.pi; 416 pj = pair.pj; 417 if (logger.isDebugEnabled()) { 418 logger.debug("pi = " + pi); 419 logger.debug("pj = " + pj); 420 } 421 422 S = red.SPolynomial(pi, pj); 423 if (S.isZERO()) { 424 pair.setZero(); 425 fin.initIdle(1); 426 continue; 427 } 428 if (logger.isDebugEnabled()) { 429 logger.debug("ht(S) = " + S.leadingExpVector()); 430 } 431 432 H = red.normalform(G, S); //mod 433 reduction++; 434 if (H.isZERO()) { 435 pair.setZero(); 436 fin.initIdle(1); 437 continue; 438 } 439 if (logger.isDebugEnabled()) { 440 logger.info("ht(H) = " + H.leadingExpVector()); 441 } 442 443 H = engine.basePrimitivePart(H); //H.monic(); 444 H = H.abs(); 445 // System.out.println("H = " + H); 446 if (H.isONE()) { 447 // putOne not required 448 pairlist.put(H); 449 synchronized (G) { 450 G.clear(); 451 G.add(H); 452 } 453 fin.allIdle(); 454 return; 455 } 456 if (logger.isDebugEnabled()) { 457 logger.debug("H = " + H); 458 } 459 synchronized (G) { 460 G.add(H); 461 } 462 pairlist.put(H); 463 fin.initIdle(1); 464 } 465 fin.allIdle(); 466 logger.info("terminated, done " + reduction + " reductions"); 467 } 468} 469 470 471/** 472 * Pseudo Reducing worker threads for minimal GB. 473 */ 474class PseudoMiReducer<C extends GcdRingElem<C>> implements Runnable { 475 476 477 private final List<GenPolynomial<C>> G; 478 479 480 private GenPolynomial<C> H; 481 482 483 private final PseudoReductionPar<C> red; 484 485 486 private final Semaphore done = new Semaphore(0); 487 488 489 private final GreatestCommonDivisorAbstract<C> engine; 490 491 492 private static final Logger logger = Logger.getLogger(PseudoMiReducer.class); 493 494 495 PseudoMiReducer(List<GenPolynomial<C>> G, GenPolynomial<C> p, GreatestCommonDivisorAbstract<C> engine) { 496 this.G = G; 497 this.engine = engine; 498 H = p; 499 red = new PseudoReductionPar<C>(); 500 } 501 502 503 /** 504 * to string 505 */ 506 @Override 507 public String toString() { 508 return "PseudoMiReducer"; 509 } 510 511 512 /** 513 * getNF. Blocks until the normal form is computed. 514 * @return the computed normal form. 515 */ 516 public GenPolynomial<C> getNF() { 517 try { 518 done.acquire(); //done.P(); 519 } catch (InterruptedException e) { 520 throw new RuntimeException("interrupt in getNF"); 521 } 522 return H; 523 } 524 525 526 public void run() { 527 if (logger.isDebugEnabled()) { 528 logger.debug("ht(H) = " + H.leadingExpVector()); 529 } 530 try { 531 H = red.normalform(G, H); //mod 532 H = engine.basePrimitivePart(H); //H.monic(); 533 H = H.abs(); 534 done.release(); //done.V(); 535 } catch (RuntimeException e) { 536 Thread.currentThread().interrupt(); 537 //throw new RuntimeException("interrupt in getNF"); 538 } 539 if (logger.isDebugEnabled()) { 540 logger.debug("ht(H) = " + H.leadingExpVector()); 541 } 542 // H = H.monic(); 543 } 544 545}