Source code

001/*
002 * $Id: SolvableGroebnerBaseSeqPairParallel.java 3990 2012-07-14 12:46:08Z
003 * kredel $
004 */
005
006package edu.jas.gb;
007
008
009import java.util.ArrayList;
010import java.util.List;
011import java.util.ListIterator;
012import java.util.concurrent.Semaphore;
013
014import org.apache.log4j.Logger;
015
016import edu.jas.poly.ExpVector;
017import edu.jas.poly.GenSolvablePolynomial;
018import edu.jas.poly.GenSolvablePolynomialRing;
019import edu.jas.poly.PolynomialList;
020import edu.jas.structure.RingElem;
021import edu.jas.util.Terminator;
022import edu.jas.util.ThreadPool;
023
024
025/**
026 * Solvable Groebner Base parallel algorithm. Makes some effort to produce the
027 * same sequence of critical pairs as in the sequential version. However already
028 * reduced pairs are not rereduced if new polynomials appear. Implements a
029 * shared memory parallel version of Groebner bases. Threads maintain pairlist.
030 * @param <C> coefficient type
031 * @author Heinz Kredel
032 */
033
034public class SolvableGroebnerBaseSeqPairParallel<C extends RingElem<C>> extends
035                SolvableGroebnerBaseAbstract<C> {
036
037
038    private static final Logger logger = Logger.getLogger(SolvableGroebnerBaseSeqPairParallel.class);
039
040
041    //private static final boolean debug = logger.isDebugEnabled();
042
043
044    /**
045     * Number of threads to use.
046     */
047    protected final int threads;
048
049
050    /**
051     * Pool of threads to use.
052     */
053    protected transient final ThreadPool pool;
054
055
056    /**
057     * Constructor.
058     */
059    public SolvableGroebnerBaseSeqPairParallel() {
060        this(2);
061    }
062
063
064    /**
065     * Constructor.
066     * @param threads number of threads to use.
067     */
068    public SolvableGroebnerBaseSeqPairParallel(int threads) {
069        this(threads, new ThreadPool(threads));
070    }
071
072
073    /**
074     * Constructor.
075     * @param threads number of threads to use.
076     * @param pool ThreadPool to use.
077     */
078    public SolvableGroebnerBaseSeqPairParallel(int threads, ThreadPool pool) {
079        this(threads, pool, new SolvableReductionPar<C>());
080    }
081
082
083    /**
084     * Constructor.
085     * @param threads number of threads to use.
086     * @param red parallelism aware reduction engine
087     */
088    public SolvableGroebnerBaseSeqPairParallel(int threads, SolvableReduction<C> red) {
089        this(threads, new ThreadPool(threads), red);
090    }
091
092
093    /**
094     * Constructor.
095     * @param threads number of threads to use.
096     * @param pool ThreadPool to use.
097     * @param sred parallelism aware reduction engine
098     */
099    public SolvableGroebnerBaseSeqPairParallel(int threads, ThreadPool pool, 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    @Override
116    public void terminate() {
117        if (pool == null) {
118            return;
119        }
120        pool.terminate();
121    }
122
123
124    /**
125     * Parallel Groebner base using sequential pair order class. Threads
126     * maintain pairlist.
127     * @param modv number of module variables.
128     * @param F polynomial list.
129     * @return GB(F) a Groebner base of F.
130     */
131    public List<GenSolvablePolynomial<C>> leftGB(int modv, List<GenSolvablePolynomial<C>> F) {
132        GenSolvablePolynomial<C> p;
133        List<GenSolvablePolynomial<C>> G = new ArrayList<GenSolvablePolynomial<C>>();
134        CriticalPairList<C> pairlist = null;
135        int l = F.size();
136        ListIterator<GenSolvablePolynomial<C>> it = F.listIterator();
137        while (it.hasNext()) {
138            p = it.next();
139            if (p.length() > 0) {
140                p = p.monic();
141                if (p.isONE()) {
142                    G.clear();
143                    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>> leftMinimalGB(List<GenSolvablePolynomial<C>> Fp) {
185        GenSolvablePolynomial<C> a;
186        ArrayList<GenSolvablePolynomial<C>> G;
187        G = new ArrayList<GenSolvablePolynomial<C>>(Fp.size());
188        ListIterator<GenSolvablePolynomial<C>> it = Fp.listIterator();
189        while (it.hasNext()) {
190            a = it.next();
191            if (a.length() != 0) { // always true
192                // already monic  a = a.monic();
193                G.add(a);
194            }
195        }
196        if (G.size() <= 1) {
197            return G;
198        }
199
200        ExpVector e;
201        ExpVector f;
202        GenSolvablePolynomial<C> p;
203        ArrayList<GenSolvablePolynomial<C>> F;
204        F = new ArrayList<GenSolvablePolynomial<C>>(G.size());
205        boolean mt;
206        while (G.size() > 0) {
207            a = G.remove(0);
208            e = a.leadingExpVector();
209
210            it = G.listIterator();
211            mt = false;
212            while (it.hasNext() && !mt) {
213                p = it.next();
214                f = p.leadingExpVector();
215                mt = e.multipleOf(f);
216            }
217            it = F.listIterator();
218            while (it.hasNext() && !mt) {
219                p = it.next();
220                f = p.leadingExpVector();
221                mt = e.multipleOf(f);
222            }
223            if (!mt) {
224                F.add(a); // no thread at this point
225            } else {
226                // System.out.println("dropped " + a.length());
227            }
228        }
229        G = F;
230        if (G.size() <= 1) {
231            return G;
232        }
233
234        @SuppressWarnings("cast")
235        SolvableMiReducerSeqPair<C>[] mirs = (SolvableMiReducerSeqPair<C>[]) new SolvableMiReducerSeqPair[G
236                        .size()];
237        int i = 0;
238        F = new ArrayList<GenSolvablePolynomial<C>>(G.size());
239        while (G.size() > 0) {
240            a = G.remove(0);
241            // System.out.println("doing " + a.length());
242            List<GenSolvablePolynomial<C>> R = new ArrayList<GenSolvablePolynomial<C>>(G.size() + F.size());
243            R.addAll(G);
244            R.addAll(F);
245            mirs[i] = new SolvableMiReducerSeqPair<C>(R, a);
246            pool.addJob(mirs[i]);
247            i++;
248            F.add(a);
249        }
250        G = F;
251        F = new ArrayList<GenSolvablePolynomial<C>>(G.size());
252        for (i = 0; i < mirs.length; i++) {
253            a = mirs[i].getNF();
254            F.add(a);
255        }
256        return F;
257    }
258
259
260    /**
261     * Solvable Extended Groebner base using critical pair class.
262     * @param modv module variable number.
263     * @param F solvable polynomial list.
264     * @return a container for an extended left Groebner base of F.
265     */
266    public SolvableExtendedGB<C> extLeftGB(int modv, List<GenSolvablePolynomial<C>> F) {
267        throw new UnsupportedOperationException("parallel extLeftGB not implemented");
268    }
269
270
271    /**
272     * Twosided Groebner base using pairlist class.
273     * @param modv number of module variables.
274     * @param Fp solvable polynomial list.
275     * @return tsGB(Fp) a twosided Groebner base of F.
276     */
277    public List<GenSolvablePolynomial<C>> twosidedGB(int modv, List<GenSolvablePolynomial<C>> Fp) {
278        if (Fp == null || Fp.size() == 0) { // 0 not 1
279            return new ArrayList<GenSolvablePolynomial<C>>();
280        }
281        GenSolvablePolynomialRing<C> ring = Fp.get(0).ring; // assert != null
282        // add also coefficient generators
283        List<GenSolvablePolynomial<C>> X;
284        X = PolynomialList.castToSolvableList(ring.generators(modv)); 
285        logger.info("right multipliers = " + X);
286        List<GenSolvablePolynomial<C>> F = new ArrayList<GenSolvablePolynomial<C>>(Fp.size() * (1 + X.size()));
287        F.addAll(Fp);
288        GenSolvablePolynomial<C> p, x, q;
289        for (int i = 0; i < F.size(); i++) { // F changes
290            p = F.get(i);
291            for (int j = 0; j < X.size(); j++) {
292                x = X.get(j);
293                if (x.isONE()) {
294                    continue;
295                }
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 = new ArrayList<GenSolvablePolynomial<C>>();
305        CriticalPairList<C> pairlist = null;
306        int l = F.size();
307        ListIterator<GenSolvablePolynomial<C>> it = F.listIterator();
308        while (it.hasNext()) {
309            p = it.next();
310            if (p.length() > 0) {
311                p = p.monic();
312                if (p.isONE()) {
313                    G.clear();
314                    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 */
355class LeftSolvableReducerSeqPair<C extends RingElem<C>> implements Runnable {
356
357
358    private final List<GenSolvablePolynomial<C>> G;
359
360
361    private final CriticalPairList<C> pairlist;
362
363
364    private final Terminator pool;
365
366
367    private final SolvableReductionPar<C> sred;
368
369
370    private static final Logger logger = Logger.getLogger(LeftSolvableReducerSeqPair.class);
371
372
373    private static final boolean debug = logger.isDebugEnabled();
374
375
376    LeftSolvableReducerSeqPair(Terminator fin, List<GenSolvablePolynomial<C>> G, CriticalPairList<C> L) {
377        pool = fin;
378        this.G = G;
379        pairlist = L;
380        sred = new SolvableReductionPar<C>();
381    }
382
383
384    @SuppressWarnings("unchecked")
385    public void run() {
386        CriticalPair<C> pair;
387        GenSolvablePolynomial<C> S;
388        GenSolvablePolynomial<C> H;
389        boolean set = false;
390        int reduction = 0;
391        int sleeps = 0;
392        while (pairlist.hasNext() || pool.hasJobs()) {
393            while (!pairlist.hasNext()) {
394                pairlist.update();
395                // wait
396                pool.beIdle();
397                set = true;
398                try {
399                    sleeps++;
400                    if (sleeps % 10 == 0) {
401                        logger.info(" reducer is sleeping");
402                    } else {
403                        logger.debug("r");
404                    }
405                    Thread.sleep(100);
406                } catch (InterruptedException e) {
407                    break;
408                }
409                if (!pool.hasJobs()) {
410                    break;
411                }
412            }
413            if (!pairlist.hasNext() && !pool.hasJobs()) {
414                break;
415            }
416            if (set) {
417                pool.notIdle();
418                set = false;
419            }
420            pair = pairlist.getNext();
421            if (pair == null) {
422                pairlist.update();
423                continue;
424            }
425            if (debug) {
426                logger.debug("pi = " + pair.pi);
427                logger.debug("pj = " + pair.pj);
428            }
429            S = sred.leftSPolynomial((GenSolvablePolynomial<C>) pair.pi, (GenSolvablePolynomial<C>) pair.pj);
430            if (S.isZERO()) {
431                pairlist.record(pair, S);
432                continue;
433            }
434            if (debug) {
435                logger.debug("ht(S) = " + S.leadingExpVector());
436            }
437            H = sred.leftNormalform(G, S); //mod
438            reduction++;
439            if (H.isZERO()) {
440                pairlist.record(pair, H);
441                continue;
442            }
443            if (debug) {
444                logger.debug("ht(H) = " + H.leadingExpVector());
445            }
446            H = H.monic();
447            // System.out.println("H   = " + H);
448            if (H.isONE()) {
449                // pairlist.update( pair, H );
450                pairlist.putOne(); // not really required
451                synchronized (G) {
452                    G.clear();
453                    G.add(H);
454                }
455                pool.allIdle();
456                return;
457            }
458            if (debug) {
459                logger.debug("H = " + H);
460            }
461            synchronized (G) {
462                G.add(H);
463            }
464            pairlist.update(pair, H);
465            //pairlist.record( pair, H );
466            //pairlist.update();
467        }
468        logger.info("terminated, done " + reduction + " reductions");
469    }
470}
471
472
473/**
474 * Reducing twosided worker threads.
475 * @param <C> coefficient type
476 */
477class TwosidedSolvableReducerSeqPair<C extends RingElem<C>> implements Runnable {
478
479
480    private final List<GenSolvablePolynomial<C>> X;
481
482
483    private final List<GenSolvablePolynomial<C>> G;
484
485
486    private final CriticalPairList<C> pairlist;
487
488
489    private final Terminator pool;
490
491
492    private final SolvableReductionPar<C> sred;
493
494
495    private static final Logger logger = Logger.getLogger(TwosidedSolvableReducerSeqPair.class);
496
497
498    private static final boolean debug = logger.isDebugEnabled();
499
500
501    TwosidedSolvableReducerSeqPair(Terminator fin, List<GenSolvablePolynomial<C>> X,
502                    List<GenSolvablePolynomial<C>> G, CriticalPairList<C> L) {
503        pool = fin;
504        this.X = X;
505        this.G = G;
506        pairlist = L;
507        sred = new SolvableReductionPar<C>();
508    }
509
510
511    public void run() {
512        GenSolvablePolynomial<C> p, x;
513        CriticalPair<C> pair;
514        GenSolvablePolynomial<C> S;
515        GenSolvablePolynomial<C> H;
516        boolean set = false;
517        int reduction = 0;
518        int sleeps = 0;
519        while (pairlist.hasNext() || pool.hasJobs()) {
520            while (!pairlist.hasNext()) {
521                pairlist.update();
522                // wait
523                pool.beIdle();
524                set = true;
525                try {
526                    sleeps++;
527                    if (sleeps % 10 == 0) {
528                        logger.info(" reducer is sleeping");
529                    } else {
530                        logger.debug("r");
531                    }
532                    Thread.sleep(50);
533                } catch (InterruptedException e) {
534                    break;
535                }
536                if (!pool.hasJobs()) {
537                    break;
538                }
539            }
540            if (!pairlist.hasNext() && !pool.hasJobs()) {
541                break;
542            }
543            if (set) {
544                pool.notIdle();
545                set = false;
546            }
547            pair = pairlist.getNext();
548            if (pair == null) {
549                pairlist.update();
550                continue;
551            }
552            if (debug) {
553                logger.debug("pi = " + pair.pi);
554                logger.debug("pj = " + pair.pj);
555            }
556            S = sred.leftSPolynomial((GenSolvablePolynomial<C>) pair.pi, (GenSolvablePolynomial<C>) pair.pj);
557            if (S.isZERO()) {
558                pairlist.record(pair, S);
559                continue;
560            }
561            if (debug) {
562                logger.debug("ht(S) = " + S.leadingExpVector());
563            }
564            H = sred.leftNormalform(G, S); //mod
565            reduction++;
566            if (H.isZERO()) {
567                pairlist.record(pair, H);
568                continue;
569            }
570            if (debug) {
571                logger.debug("ht(H) = " + H.leadingExpVector());
572            }
573            H = H.monic();
574            // System.out.println("H   = " + H);
575            if (H.isONE()) {
576                // pairlist.update( pair, H );
577                pairlist.putOne(); // not really required
578                synchronized (G) {
579                    G.clear();
580                    G.add(H);
581                }
582                pool.allIdle();
583                return;
584            }
585            if (debug) {
586                logger.debug("H = " + H);
587            }
588            synchronized (G) {
589                G.add(H);
590            }
591            pairlist.update(pair, H);
592            for (int j = 0; j < X.size(); j++) {
593                x = X.get(j);
594                if (x.isONE()) {
595                    continue;
596                }
597                p = H.multiply(x);
598                p = sred.leftNormalform(G, p);
599                if (!p.isZERO()) {
600                    p = p.monic();
601                    if (p.isONE()) {
602                        synchronized (G) {
603                            G.clear();
604                            G.add(p);
605                        }
606                        pool.allIdle();
607                        return;
608                    }
609                    synchronized (G) {
610                        G.add(p);
611                    }
612                    pairlist.put(p);
613                }
614            }
615        }
616        logger.info("terminated, done " + reduction + " reductions");
617    }
618}
619
620
621/**
622 * Reducing worker threads for minimal GB.
623 * @param <C> coefficient type
624 */
625class SolvableMiReducerSeqPair<C extends RingElem<C>> implements Runnable {
626
627
628    private final List<GenSolvablePolynomial<C>> G;
629
630
631    private GenSolvablePolynomial<C> H;
632
633
634    private final SolvableReductionPar<C> sred;
635
636
637    private final Semaphore done = new Semaphore(0);
638
639
640    private static final Logger logger = Logger.getLogger(SolvableMiReducerSeqPair.class);
641
642
643    private static final boolean debug = logger.isDebugEnabled();
644
645
646    SolvableMiReducerSeqPair(List<GenSolvablePolynomial<C>> G, GenSolvablePolynomial<C> p) {
647        this.G = G;
648        H = p;
649        sred = new SolvableReductionPar<C>();
650    }
651
652
653    /**
654     * getNF. Blocks until the normal form is computed.
655     * @return the computed normal form.
656     */
657    public GenSolvablePolynomial<C> getNF() {
658        try {
659            done.acquire(); //done.P();
660        } catch (InterruptedException e) {
661        }
662        return H;
663    }
664
665
666    public void run() {
667        if (debug) {
668            logger.debug("ht(H) = " + H.leadingExpVector());
669        }
670        H = sred.leftNormalform(G, H); //mod
671        done.release(); //done.V();
672        if (debug) {
673            logger.debug("ht(H) = " + H.leadingExpVector());
674        }
675        // H = H.monic();
676    }
677
678}