Source code

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