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