Source code

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