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.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);
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);
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     * Twosided Groebner base using pairlist class.
301     * @param modv number of module variables.
302     * @param Fp solvable polynomial list.
303     * @return tsGB(Fp) a twosided Groebner base of F.
304     */
305    @SuppressWarnings("unchecked")
306    public List<GenSolvablePolynomial<C>> twosidedGB(int modv, List<GenSolvablePolynomial<C>> Fp) {
307        List<GenSolvablePolynomial<C>> G = normalizeZerosOnes(Fp);
308        G = PolynomialList.castToSolvableList(PolyUtil.<C> monic(PolynomialList.castToList(G)));
309        if (G.size() < 1) { // 0 not 1
310            return G;
311        }
312        if (G.size() <= 1) { 
313            if (G.get(0).isONE()) {
314                return G; 
315            }
316        }
317        GenSolvablePolynomialRing<C> ring = G.get(0).ring;
318        if (!ring.coFac.isField() && ring.coFac.isCommutative()) {
319            throw new IllegalArgumentException("coefficients not from a field");
320        }
321        // add also coefficient generators
322        List<GenSolvablePolynomial<C>> X;
323        X = PolynomialList.castToSolvableList(ring.generators(modv)); 
324        logger.info("right multipliers = {}", X);
325        List<GenSolvablePolynomial<C>> F = new ArrayList<GenSolvablePolynomial<C>>(G.size() * (1 + X.size()));
326        F.addAll(G); 
327        GenSolvablePolynomial<C> p, x, q;
328        for (int i = 0; i < F.size(); i++) { // F changes
329            p = F.get(i);
330            for (int j = 0; j < X.size(); j++) {
331                x = X.get(j);
332                if (x.isONE()) {
333                    continue;
334                }
335                q = p.multiply(x);
336                q = sred.leftNormalform(F, q);
337                if (!q.isZERO()) {
338                    q = q.monic();
339                    if (q.isONE()) {
340                        G.clear();
341                        G.add(q);
342                        return G;
343                    } 
344                    F.add(q);
345                }
346            }
347        }
348        //System.out.println("F generated = " + F);
349        G = F;
350        if (G.size() <= 1) { // 1 okay here
351            return G;
352        }
353        PairList<C> pairlist = strategy.create(modv, ring);
354        pairlist.put(PolynomialList.castToList(G));
355        logger.info("start {}", pairlist);
356
357        Terminator fin = new Terminator(threads);
358        TwosidedSolvableReducer<C> R;
359        for (int i = 0; i < threads; i++) {
360            R = new TwosidedSolvableReducer<C>(fin, modv, X, G, pairlist);
361            pool.execute(R);
362        }
363        fin.waitDone();
364        logger.debug("#parallel list = {}", G.size());
365        G = leftMinimalGB(G);
366        // not in this context // pool.terminate();
367        logger.info("end   {}", pairlist);
368        return G;
369    }
370
371}
372
373
374/**
375 * Reducing left worker threads.
376 * @param <C> coefficient type
377 */
378class LeftSolvableReducer<C extends RingElem<C>> implements Runnable {
379
380
381    private final List<GenSolvablePolynomial<C>> G;
382
383
384    private final PairList<C> pairlist;
385
386
387    private final Terminator pool;
388
389
390    private final SolvableReductionPar<C> sred;
391
392
393    private static final Logger logger = LogManager.getLogger(LeftSolvableReducer.class);
394
395
396    private static final boolean debug = logger.isDebugEnabled();
397
398
399    LeftSolvableReducer(Terminator fin, List<GenSolvablePolynomial<C>> G, PairList<C> L) {
400        pool = fin;
401        this.G = G;
402        pairlist = L;
403        sred = new SolvableReductionPar<C>();
404    }
405
406
407    @SuppressWarnings("unchecked")
408    public void run() {
409        Pair<C> pair;
410        GenSolvablePolynomial<C> S;
411        GenSolvablePolynomial<C> H;
412        boolean set = false;
413        int reduction = 0;
414        int sleeps = 0;
415        while (pairlist.hasNext() || pool.hasJobs()) {
416            while (!pairlist.hasNext()) {
417                // wait
418                pool.beIdle();
419                set = true;
420                try {
421                    sleeps++;
422                    if (sleeps % 10 == 0) {
423                        logger.info(" reducer is sleeping");
424                    } else {
425                        logger.debug("r");
426                    }
427                    Thread.sleep(100);
428                } catch (InterruptedException e) {
429                    pool.allIdle();
430                    logger.info("shutdown {} after: {}", pool, e);
431                    //throw new RuntimeException("interrupt 1 in pairlist.hasNext loop");
432                    break;
433                }
434                if (Thread.currentThread().isInterrupted()) {
435                    //pool.initIdle(1);
436                    pool.allIdle();
437                    logger.info("shutdown after .isInterrupted(): {}", pool);
438                    //throw new RuntimeException("interrupt 2 in pairlist.hasNext loop");
439                    break;
440                }
441                if (!pool.hasJobs()) {
442                    break;
443                }
444            }
445            if (!pairlist.hasNext() && !pool.hasJobs()) {
446                break;
447            }
448            if (set) {
449                pool.notIdle();
450                set = false;
451            }
452            pair = pairlist.removeNext();
453            if (pair == null) {
454                continue;
455            }
456            if (debug) {
457                logger.debug("pi = {}", pair.pi);
458                logger.debug("pj = {}", pair.pj);
459            }
460            S = sred.leftSPolynomial((GenSolvablePolynomial<C>) pair.pi, (GenSolvablePolynomial<C>) pair.pj);
461            if (S.isZERO()) {
462                continue;
463            }
464            if (debug) {
465                logger.debug("ht(S) = {}", S.leadingExpVector());
466            }
467            H = sred.leftNormalform(G, S); //mod
468            reduction++;
469            if (H.isZERO()) {
470                continue;
471            }
472            if (debug) {
473                logger.debug("ht(H) = {}", H.leadingExpVector());
474            }
475            H = H.monic();
476            // System.out.println("H   = " + H);
477            if (H.isONE()) {
478                pairlist.putOne(); // not really required
479                synchronized (G) {
480                    G.clear();
481                    G.add(H);
482                }
483                pool.allIdle();
484                return;
485            }
486            if (debug) {
487                logger.debug("H = {}", H);
488            }
489            synchronized (G) {
490                G.add(H);
491            }
492            pairlist.put(H);
493        }
494        logger.info("terminated, done {} reductions", reduction);
495    }
496}
497
498
499/**
500 * Reducing twosided worker threads.
501 * @param <C> coefficient type
502 */
503class TwosidedSolvableReducer<C extends RingElem<C>> implements Runnable {
504
505
506    private final List<GenSolvablePolynomial<C>> X;
507
508
509    private final List<GenSolvablePolynomial<C>> G;
510
511
512    private final PairList<C> pairlist;
513
514
515    private final int modv;
516
517
518    private final Terminator pool;
519
520
521    private final SolvableReductionPar<C> sred;
522
523
524    private static final Logger logger = LogManager.getLogger(TwosidedSolvableReducer.class);
525
526
527    private static final boolean debug = logger.isDebugEnabled();
528
529
530    TwosidedSolvableReducer(Terminator fin, int modv, List<GenSolvablePolynomial<C>> X,
531                    List<GenSolvablePolynomial<C>> G, PairList<C> L) {
532        pool = fin;
533        this.modv = modv;
534        this.X = X;
535        this.G = G;
536        pairlist = L;
537        sred = new SolvableReductionPar<C>();
538    }
539
540
541    public void run() {
542        GenSolvablePolynomial<C> p, x, S, H;
543        Pair<C> pair;
544        boolean set = false;
545        int reduction = 0;
546        int sleeps = 0;
547        logger.debug("modv = {}", modv); // avoid "unused"
548        while (pairlist.hasNext() || pool.hasJobs()) {
549            while (!pairlist.hasNext()) {
550                // wait
551                pool.beIdle();
552                set = true;
553                try {
554                    sleeps++;
555                    if (sleeps % 10 == 0) {
556                        logger.info(" reducer is sleeping");
557                    } else {
558                        logger.debug("r");
559                    }
560                    Thread.sleep(50);
561                } catch (InterruptedException e) {
562                    break;
563                }
564                if (!pool.hasJobs()) {
565                    break;
566                }
567            }
568            if (!pairlist.hasNext() && !pool.hasJobs()) {
569                break;
570            }
571            if (set) {
572                pool.notIdle();
573                set = false;
574            }
575            pair = pairlist.removeNext();
576            if (pair == null) {
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                continue;
586            }
587            if (debug) {
588                logger.debug("ht(S) = {}", S.leadingExpVector());
589            }
590            H = sred.leftNormalform(G, S); //mod
591            reduction++;
592            if (H.isZERO()) {
593                continue;
594            }
595            if (debug) {
596                logger.debug("ht(H) = {}", H.leadingExpVector());
597            }
598            H = H.monic();
599            // System.out.println("H   = " + H);
600            if (H.isONE()) {
601                pairlist.putOne(); // not really required
602                synchronized (G) {
603                    G.clear();
604                    G.add(H);
605                }
606                pool.allIdle();
607                return;
608            }
609            if (debug) {
610                logger.debug("H = {}", H);
611            }
612            synchronized (G) {
613                G.add(H);
614            }
615            pairlist.put(H);
616            for (int j = 0; j < X.size(); j++) {
617                x = X.get(j);
618                p = H.multiply(x);
619                p = sred.leftNormalform(G, p);
620                if (!p.isZERO()) {
621                    p = p.monic();
622                    if (p.isONE()) {
623                        synchronized (G) {
624                            G.clear();
625                            G.add(p);
626                        }
627                        pool.allIdle();
628                        return;
629                    }
630                    synchronized (G) {
631                        G.add(p);
632                    }
633                    pairlist.put(p);
634                }
635            }
636        }
637        logger.info("terminated, done {} reductions", reduction);
638    }
639}
640
641
642/**
643 * Reducing worker threads for minimal GB.
644 * @param <C> coefficient type
645 */
646class SolvableMiReducer<C extends RingElem<C>> implements Runnable {
647
648
649    private final List<GenSolvablePolynomial<C>> G;
650
651
652    private GenSolvablePolynomial<C> H;
653
654
655    private final SolvableReductionPar<C> sred;
656
657
658    private final Semaphore done = new Semaphore(0);
659
660
661    private static final Logger logger = LogManager.getLogger(SolvableMiReducer.class);
662
663
664    private static final boolean debug = logger.isDebugEnabled();
665
666
667    SolvableMiReducer(List<GenSolvablePolynomial<C>> G, GenSolvablePolynomial<C> p) {
668        this.G = G;
669        H = p;
670        sred = new SolvableReductionPar<C>();
671    }
672
673
674    /**
675     * getNF. Blocks until the normal form is computed.
676     * @return the computed normal form.
677     */
678    public GenSolvablePolynomial<C> getNF() {
679        try {
680            done.acquire(); //done.P();
681        } catch (InterruptedException e) {
682        }
683        return H;
684    }
685
686
687    public void run() {
688        if (debug) {
689            logger.debug("ht(H) = {}", H.leadingExpVector());
690        }
691        H = sred.leftNormalform(G, H); //mod
692        done.release(); //done.V();
693        if (debug) {
694            logger.debug("ht(H) = {}", H.leadingExpVector());
695        }
696        // H = H.monic();
697    }
698
699}