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