001 /*
002 * $Id: SolvableGroebnerBaseSeqPairParallel.java 3413 2010-12-19 12:46:49Z kredel $
003 */
004
005 package edu.jas.gb;
006
007 import java.util.ArrayList;
008 import java.util.List;
009 import java.util.ListIterator;
010 import java.util.concurrent.Semaphore;
011
012 import org.apache.log4j.Logger;
013
014 import edu.jas.structure.RingElem;
015
016 import edu.jas.poly.ExpVector;
017 import edu.jas.poly.GenSolvablePolynomial;
018 import edu.jas.poly.GenSolvablePolynomialRing;
019
020 import edu.jas.util.Terminator;
021 import edu.jas.util.ThreadPool;
022
023
024 /**
025 * Solvable Groebner Base parallel algorithm.
026 * Makes some effort to produce the same sequence of critical pairs
027 * as in the sequential version.
028 * However already reduced pairs are not rereduced if new
029 * polynomials appear.
030 * Implements a shared memory parallel version of Groebner bases.
031 * Threads maintain pairlist.
032 * @param <C> coefficient type
033 * @author Heinz Kredel
034 */
035
036 public class SolvableGroebnerBaseSeqPairParallel<C extends RingElem<C>>
037 extends SolvableGroebnerBaseAbstract<C> {
038
039 private static final Logger logger = Logger.getLogger(SolvableGroebnerBaseSeqPairParallel.class);
040 //private static final boolean debug = logger.isDebugEnabled();
041
042
043 /**
044 * Number of threads to use.
045 */
046 protected final int threads;
047
048
049 /**
050 * Pool of threads to use.
051 */
052 protected final ThreadPool pool;
053
054
055 /**
056 * Constructor.
057 */
058 public SolvableGroebnerBaseSeqPairParallel() {
059 this(2);
060 }
061
062
063 /**
064 * Constructor.
065 * @param threads number of threads to use.
066 */
067 public SolvableGroebnerBaseSeqPairParallel(int threads) {
068 this(threads, new ThreadPool(threads) );
069 }
070
071
072 /**
073 * Constructor.
074 * @param threads number of threads to use.
075 * @param pool ThreadPool to use.
076 */
077 public SolvableGroebnerBaseSeqPairParallel(int threads, ThreadPool pool) {
078 this(threads, pool, new SolvableReductionPar<C>() );
079 }
080
081
082 /**
083 * Constructor.
084 * @param threads number of threads to use.
085 * @param red parallelism aware reduction engine
086 */
087 public SolvableGroebnerBaseSeqPairParallel(int threads, SolvableReduction<C> red) {
088 this(threads, new ThreadPool(threads), red );
089 }
090
091
092 /**
093 * Constructor.
094 * @param threads number of threads to use.
095 * @param pool ThreadPool to use.
096 * @param sred parallelism aware reduction engine
097 */
098 public SolvableGroebnerBaseSeqPairParallel(int threads, ThreadPool pool,
099 SolvableReduction<C> sred) {
100 super(sred);
101 if ( ! (sred instanceof SolvableReductionPar) ) {
102 logger.warn("parallel GB should use parallel aware reduction");
103 }
104 if ( threads < 1 ) {
105 threads = 1;
106 }
107 this.threads = threads;
108 this.pool = pool;
109 }
110
111
112 /**
113 * Cleanup and terminate ThreadPool.
114 */
115 public void terminate() {
116 if ( pool == null ) {
117 return;
118 }
119 pool.terminate();
120 }
121
122
123 /**
124 * Parallel Groebner base using sequential pair order class.
125 * Threads maintain pairlist.
126 * @param modv number of module variables.
127 * @param F polynomial list.
128 * @return GB(F) a Groebner base of F.
129 */
130 public List<GenSolvablePolynomial<C>>
131 leftGB( int modv,
132 List<GenSolvablePolynomial<C>> F ) {
133 GenSolvablePolynomial<C> p;
134 List<GenSolvablePolynomial<C>> G = new ArrayList<GenSolvablePolynomial<C>>();
135 CriticalPairList<C> pairlist = null;
136 int l = F.size();
137 ListIterator<GenSolvablePolynomial<C>> it = F.listIterator();
138 while ( it.hasNext() ) {
139 p = it.next();
140 if ( p.length() > 0 ) {
141 p = (GenSolvablePolynomial<C>)p.monic();
142 if ( p.isONE() ) {
143 G.clear(); G.add( p );
144 return G; // since no threads activated jet
145 }
146 G.add( p );
147 if ( pairlist == null ) {
148 pairlist = new CriticalPairList<C>( modv, p.ring );
149 if ( ! p.ring.coFac.isField() ) {
150 throw new IllegalArgumentException("coefficients not from a field");
151 }
152 }
153 // putOne not required
154 pairlist.put( p );
155 } else {
156 l--;
157 }
158 }
159 if ( l <= 1 ) {
160 return G; // since no threads activated jet
161 }
162
163 Terminator fin = new Terminator(threads);
164 LeftSolvableReducerSeqPair<C> R;
165 for ( int i = 0; i < threads; i++ ) {
166 R = new LeftSolvableReducerSeqPair<C>( fin, G, pairlist );
167 pool.addJob( R );
168 }
169 fin.waitDone();
170 logger.debug("#parallel list = "+G.size());
171 G = leftMinimalGB(G);
172 // not in this context // pool.terminate();
173 logger.info("" + pairlist);
174 return G;
175 }
176
177
178 /**
179 * Minimal ordered groebner basis, parallel.
180 * @param Fp a Groebner base.
181 * @return minimalGB(F) a minimal Groebner base of Fp.
182 */
183 @Override
184 public List<GenSolvablePolynomial<C>>
185 leftMinimalGB(List<GenSolvablePolynomial<C>> Fp) {
186 GenSolvablePolynomial<C> a;
187 ArrayList<GenSolvablePolynomial<C>> G;
188 G = new ArrayList<GenSolvablePolynomial<C>>( Fp.size() );
189 ListIterator<GenSolvablePolynomial<C>> it = Fp.listIterator();
190 while ( it.hasNext() ) {
191 a = it.next();
192 if ( a.length() != 0 ) { // always true
193 // already monic a = a.monic();
194 G.add( a );
195 }
196 }
197 if ( G.size() <= 1 ) {
198 return G;
199 }
200
201 ExpVector e;
202 ExpVector f;
203 GenSolvablePolynomial<C> p;
204 ArrayList<GenSolvablePolynomial<C>> F;
205 F = new ArrayList<GenSolvablePolynomial<C>>( G.size() );
206 boolean mt;
207 while ( G.size() > 0 ) {
208 a = G.remove(0);
209 e = a.leadingExpVector();
210
211 it = G.listIterator();
212 mt = false;
213 while ( it.hasNext() && ! mt ) {
214 p = it.next();
215 f = p.leadingExpVector();
216 mt = e.multipleOf( f );
217 }
218 it = F.listIterator();
219 while ( it.hasNext() && ! mt ) {
220 p = it.next();
221 f = p.leadingExpVector();
222 mt = e.multipleOf( f );
223 }
224 if ( ! mt ) {
225 F.add( a ); // no thread at this point
226 } else {
227 // System.out.println("dropped " + a.length());
228 }
229 }
230 G = F;
231 if ( G.size() <= 1 ) {
232 return G;
233 }
234
235 SolvableMiReducerSeqPair<C>[] mirs = (SolvableMiReducerSeqPair<C>[]) new SolvableMiReducerSeqPair[ G.size() ];
236 int i = 0;
237 F = new ArrayList<GenSolvablePolynomial<C>>( G.size() );
238 while ( G.size() > 0 ) {
239 a = G.remove(0);
240 // System.out.println("doing " + a.length());
241 List<GenSolvablePolynomial<C>> R = new ArrayList<GenSolvablePolynomial<C>>(G.size()+F.size());
242 R.addAll(G);
243 R.addAll(F);
244 mirs[i] = new SolvableMiReducerSeqPair<C>(R,a);
245 pool.addJob( mirs[i] );
246 i++;
247 F.add( a );
248 }
249 G = F;
250 F = new ArrayList<GenSolvablePolynomial<C>>( G.size() );
251 for ( i = 0; i < mirs.length; i++ ) {
252 a = mirs[i].getNF();
253 F.add( a );
254 }
255 return F;
256 }
257
258
259 /**
260 * Solvable Extended Groebner base using critical pair class.
261 * @param modv module variable number.
262 * @param F solvable polynomial list.
263 * @return a container for an extended left Groebner base of F.
264 */
265 public SolvableExtendedGB<C>
266 extLeftGB( int modv,
267 List<GenSolvablePolynomial<C>> F ) {
268 throw new UnsupportedOperationException("parallel extLeftGB not implemented");
269 }
270
271
272 /**
273 * Twosided Groebner base using pairlist class.
274 * @param modv number of module variables.
275 * @param Fp solvable polynomial list.
276 * @return tsGB(Fp) a twosided Groebner base of F.
277 */
278 public List<GenSolvablePolynomial<C>>
279 twosidedGB(int modv,
280 List<GenSolvablePolynomial<C>> Fp) {
281 if ( Fp == null || Fp.size() == 0 ) { // 0 not 1
282 return new ArrayList<GenSolvablePolynomial<C>>( );
283 }
284 GenSolvablePolynomialRing<C> fac = Fp.get(0).ring; // assert != null
285 //List<GenSolvablePolynomial<C>> X = generateUnivar( modv, Fp );
286 List<GenSolvablePolynomial<C>> X = fac.univariateList( modv );
287 //System.out.println("X univ = " + X);
288 List<GenSolvablePolynomial<C>> F
289 = new ArrayList<GenSolvablePolynomial<C>>( Fp.size() * (1+X.size()) );
290 F.addAll( Fp );
291 GenSolvablePolynomial<C> p, x, q;
292 for ( int i = 0; i < Fp.size(); i++ ) {
293 p = Fp.get(i);
294 for ( int j = 0; j < X.size(); j++ ) {
295 x = X.get(j);
296 q = p.multiply( x );
297 q = sred.leftNormalform( F, q );
298 if ( !q.isZERO() ) {
299 F.add( q );
300 }
301 }
302 }
303 //System.out.println("F generated = " + F);
304 List<GenSolvablePolynomial<C>> G
305 = new ArrayList<GenSolvablePolynomial<C>>();
306 CriticalPairList<C> pairlist = null;
307 int l = F.size();
308 ListIterator<GenSolvablePolynomial<C>> it = F.listIterator();
309 while ( it.hasNext() ) {
310 p = it.next();
311 if ( p.length() > 0 ) {
312 p = (GenSolvablePolynomial<C>)p.monic();
313 if ( p.isONE() ) {
314 G.clear(); G.add( p );
315 return G; // since no threads are activated
316 }
317 G.add( p );
318 if ( pairlist == null ) {
319 pairlist = new CriticalPairList<C>( modv, p.ring );
320 if ( ! p.ring.coFac.isField() ) {
321 throw new IllegalArgumentException("coefficients not from a field");
322 }
323 }
324 // putOne not required
325 pairlist.put( p );
326 } else {
327 l--;
328 }
329 }
330 //System.out.println("G to check = " + G);
331 if ( l <= 1 ) { // 1 ok
332 return G; // since no threads are activated
333 }
334 Terminator fin = new Terminator(threads);
335 TwosidedSolvableReducerSeqPair<C> R;
336 for ( int i = 0; i < threads; i++ ) {
337 R = new TwosidedSolvableReducerSeqPair<C>( fin, X, G, pairlist );
338 pool.addJob( R );
339 }
340 fin.waitDone();
341 logger.debug("#parallel list = "+G.size());
342 G = leftMinimalGB(G);
343 // not in this context // pool.terminate();
344 logger.info("" + pairlist);
345 return G;
346 }
347
348 }
349
350
351 /**
352 * Reducing left worker threads.
353 * @param <C> coefficient type
354 */
355 class LeftSolvableReducerSeqPair<C extends RingElem<C>> implements Runnable {
356 private List<GenSolvablePolynomial<C>> G;
357 private CriticalPairList<C> pairlist;
358 private Terminator pool;
359 private SolvableReductionPar<C> sred;
360 private static final Logger logger = Logger.getLogger(LeftSolvableReducerSeqPair.class);
361 private static final boolean debug = logger.isDebugEnabled();
362
363 LeftSolvableReducerSeqPair(Terminator fin,
364 List<GenSolvablePolynomial<C>> G,
365 CriticalPairList<C> L) {
366 pool = fin;
367 this.G = G;
368 pairlist = L;
369 sred = new SolvableReductionPar<C>();
370 }
371
372
373 public void run() {
374 CriticalPair<C> pair;
375 GenSolvablePolynomial<C> S;
376 GenSolvablePolynomial<C> H;
377 boolean set = false;
378 int reduction = 0;
379 int sleeps = 0;
380 while ( pairlist.hasNext() || pool.hasJobs() ) {
381 while ( ! pairlist.hasNext() ) {
382 pairlist.update();
383 // wait
384 pool.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 ( ! pool.hasJobs() ) {
397 break;
398 }
399 }
400 if ( ! pairlist.hasNext() && ! pool.hasJobs() ) {
401 break;
402 }
403 if ( set ) {
404 pool.notIdle(); set = false;
405 }
406 pair = pairlist.getNext();
407 if ( pair == null ) {
408 pairlist.update();
409 continue;
410 }
411 if ( debug ) {
412 logger.debug("pi = " + pair.pi );
413 logger.debug("pj = " + pair.pj );
414 }
415 S = sred.leftSPolynomial( (GenSolvablePolynomial<C>)pair.pi,
416 (GenSolvablePolynomial<C>)pair.pj );
417 if ( S.isZERO() ) {
418 pairlist.record( pair, S );
419 continue;
420 }
421 if ( debug ) {
422 logger.debug("ht(S) = " + S.leadingExpVector() );
423 }
424 H = sred.leftNormalform( G, S ); //mod
425 reduction++;
426 if ( H.isZERO() ) {
427 pairlist.record( pair, H );
428 continue;
429 }
430 if ( debug ) {
431 logger.debug("ht(H) = " + H.leadingExpVector() );
432 }
433 H = (GenSolvablePolynomial<C>)H.monic();
434 // System.out.println("H = " + H);
435 if ( H.isONE() ) {
436 // pairlist.update( pair, H );
437 pairlist.putOne(); // not really required
438 synchronized (G) {
439 G.clear(); G.add( H );
440 }
441 pool.allIdle();
442 return;
443 }
444 if ( debug ) {
445 logger.debug("H = " + H );
446 }
447 synchronized (G) {
448 G.add( H );
449 }
450 pairlist.update( pair, H );
451 //pairlist.record( pair, H );
452 //pairlist.update();
453 }
454 logger.info( "terminated, done " + reduction + " reductions");
455 }
456 }
457
458
459 /**
460 * Reducing twosided worker threads.
461 * @param <C> coefficient type
462 */
463 class TwosidedSolvableReducerSeqPair<C extends RingElem<C>> implements Runnable {
464 private List<GenSolvablePolynomial<C>> X;
465 private List<GenSolvablePolynomial<C>> G;
466 private CriticalPairList<C> pairlist;
467 private Terminator pool;
468 private SolvableReductionPar<C> sred;
469 private static final Logger logger = Logger.getLogger(TwosidedSolvableReducerSeqPair.class);
470 private static final boolean debug = logger.isDebugEnabled();
471
472 TwosidedSolvableReducerSeqPair(Terminator fin,
473 List<GenSolvablePolynomial<C>> X,
474 List<GenSolvablePolynomial<C>> G,
475 CriticalPairList<C> L) {
476 pool = fin;
477 this.X = X;
478 this.G = G;
479 pairlist = L;
480 sred = new SolvableReductionPar<C>();
481 }
482
483
484 public void run() {
485 GenSolvablePolynomial<C> p, x, q;
486 CriticalPair<C> pair;
487 GenSolvablePolynomial<C> S;
488 GenSolvablePolynomial<C> H;
489 boolean set = false;
490 int reduction = 0;
491 int sleeps = 0;
492 while ( pairlist.hasNext() || pool.hasJobs() ) {
493 while ( ! pairlist.hasNext() ) {
494 pairlist.update();
495 // wait
496 pool.beIdle(); set = true;
497 try {
498 sleeps++;
499 if ( sleeps % 10 == 0 ) {
500 logger.info(" reducer is sleeping");
501 } else {
502 logger.debug("r");
503 }
504 Thread.sleep(50);
505 } catch (InterruptedException e) {
506 break;
507 }
508 if ( ! pool.hasJobs() ) {
509 break;
510 }
511 }
512 if ( ! pairlist.hasNext() && ! pool.hasJobs() ) {
513 break;
514 }
515 if ( set ) {
516 pool.notIdle(); set = false;
517 }
518 pair = pairlist.getNext();
519 if ( pair == null ) {
520 pairlist.update();
521 continue;
522 }
523 if ( debug ) {
524 logger.debug("pi = " + pair.pi );
525 logger.debug("pj = " + pair.pj );
526 }
527 S = sred.leftSPolynomial( (GenSolvablePolynomial<C>)pair.pi,
528 (GenSolvablePolynomial<C>)pair.pj );
529 if ( S.isZERO() ) {
530 pairlist.record( pair, S );
531 continue;
532 }
533 if ( debug ) {
534 logger.debug("ht(S) = " + S.leadingExpVector() );
535 }
536 H = sred.leftNormalform( G, S ); //mod
537 reduction++;
538 if ( H.isZERO() ) {
539 pairlist.record( pair, H );
540 continue;
541 }
542 if ( debug ) {
543 logger.debug("ht(H) = " + H.leadingExpVector() );
544 }
545 H = (GenSolvablePolynomial<C>)H.monic();
546 // System.out.println("H = " + H);
547 if ( H.isONE() ) {
548 // pairlist.update( pair, H );
549 pairlist.putOne(); // not really required
550 synchronized (G) {
551 G.clear(); G.add( H );
552 }
553 pool.allIdle();
554 return;
555 }
556 if ( debug ) {
557 logger.debug("H = " + H );
558 }
559 synchronized (G) {
560 G.add( H );
561 }
562 pairlist.update( pair, H );
563 for ( int j = 0; j < X.size(); j++ ) {
564 x = X.get(j);
565 p = H.multiply( x );
566 p = sred.leftNormalform( G, p );
567 if ( !p.isZERO() ) {
568 p = (GenSolvablePolynomial<C>)p.monic();
569 if ( p.isONE() ) {
570 synchronized (G) {
571 G.clear(); G.add( p );
572 }
573 pool.allIdle();
574 return;
575 }
576 synchronized (G) {
577 G.add( p );
578 }
579 pairlist.put( p );
580 }
581 }
582 }
583 logger.info( "terminated, done " + reduction + " reductions");
584 }
585 }
586
587
588 /**
589 * Reducing worker threads for minimal GB.
590 * @param <C> coefficient type
591 */
592 class SolvableMiReducerSeqPair<C extends RingElem<C>> implements Runnable {
593 private List<GenSolvablePolynomial<C>> G;
594 private GenSolvablePolynomial<C> H;
595 private SolvableReductionPar<C> sred;
596 private Semaphore done = new Semaphore(0);
597 private static final Logger logger = Logger.getLogger(SolvableMiReducerSeqPair.class);
598 private static final boolean debug = logger.isDebugEnabled();
599
600 SolvableMiReducerSeqPair(List<GenSolvablePolynomial<C>> G, GenSolvablePolynomial<C> p) {
601 this.G = G;
602 H = p;
603 sred = new SolvableReductionPar<C>();
604 }
605
606
607 /**
608 * getNF. Blocks until the normal form is computed.
609 * @return the computed normal form.
610 */
611 public GenSolvablePolynomial<C> getNF() {
612 try { done.acquire(); //done.P();
613 } catch (InterruptedException e) {
614 }
615 return H;
616 }
617
618 public void run() {
619 if ( debug ) {
620 logger.debug("ht(H) = " + H.leadingExpVector() );
621 }
622 H = sred.leftNormalform( G, H ); //mod
623 done.release(); //done.V();
624 if ( debug ) {
625 logger.debug("ht(H) = " + H.leadingExpVector() );
626 }
627 // H = H.monic();
628 }
629
630 }