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