Source code

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