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