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