Source code

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