001/*
002 * $Id$
003 */
004
005package edu.jas.gbufd;
006
007
008import java.util.ArrayList;
009import java.util.Collections;
010import java.util.List;
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.gb.GroebnerBaseAbstract;
021import edu.jas.gb.OrderedPairlist;
022import edu.jas.gb.Pair;
023import edu.jas.gb.PairList;
024import edu.jas.poly.ExpVector;
025import edu.jas.poly.GenPolynomial;
026import edu.jas.poly.GenPolynomialRing;
027import edu.jas.structure.GcdRingElem;
028import edu.jas.structure.RingFactory;
029import edu.jas.ufd.GCDFactory;
030import edu.jas.ufd.GreatestCommonDivisorAbstract;
031import edu.jas.util.Terminator;
032
033
034/**
035 * Groebner Base with recursive pseudo reduction multi-threaded parallel
036 * algorithm. Implements coefficient fraction free Groebner bases.
037 * Coefficients can for example be (commutative) multivariate polynomials. 
038 * @param <C> coefficient type
039 * @author Heinz Kredel
040 * 
041 * @see edu.jas.application.GBAlgorithmBuilder
042 * @see edu.jas.gbufd.GBFactory
043 */
044
045public class GroebnerBasePseudoRecParallel<C extends GcdRingElem<C>> extends
046                GroebnerBaseAbstract<GenPolynomial<C>> {
047
048
049    private static final Logger logger = LogManager.getLogger(GroebnerBasePseudoRecParallel.class);
050
051
052    private static final boolean debug = logger.isDebugEnabled();
053
054
055    /**
056     * Number of threads to use.
057     */
058    protected final int threads;
059
060
061    /**
062     * Pool of threads to use.
063     */
064    protected transient final ExecutorService pool;
065
066
067    /**
068     * Greatest common divisor engine for coefficient content and primitive
069     * parts.
070     */
071    protected final GreatestCommonDivisorAbstract<C> engine;
072
073
074    /**
075     * Pseudo reduction engine.
076     */
077    protected final PseudoReduction<C> redRec;
078
079
080    /**
081     * Pseudo reduction engine.
082     */
083    protected final PseudoReduction<GenPolynomial<C>> red;
084
085
086    /**
087     * Coefficient ring factory.
088     */
089    protected final RingFactory<GenPolynomial<C>> cofac;
090
091
092    /**
093     * Base coefficient ring factory.
094     */
095    protected final RingFactory<C> baseCofac;
096
097
098    /**
099     * Constructor.
100     * @param threads number of threads to use.
101     * @param rf coefficient ring factory.
102     */
103    public GroebnerBasePseudoRecParallel(int threads, RingFactory<GenPolynomial<C>> rf) {
104        this(threads, rf, new PseudoReductionPar<GenPolynomial<C>>(), Executors.newFixedThreadPool(threads),
105                        new OrderedPairlist<GenPolynomial<C>>(new GenPolynomialRing<GenPolynomial<C>>(rf, 1))); // 1=hack
106    }
107
108
109    /**
110     * Constructor.
111     * @param threads number of threads to use.
112     * @param rf coefficient ring factory. <b>Note:</b> red must be an instance
113     *            of PseudoReductionPar.
114     * @param red pseudo reduction engine.
115     */
116    public GroebnerBasePseudoRecParallel(int threads, RingFactory<GenPolynomial<C>> rf,
117                    PseudoReduction<GenPolynomial<C>> red) {
118        this(threads, rf, red, Executors.newFixedThreadPool(threads));
119    }
120
121
122    /**
123     * Constructor.
124     * @param threads number of threads to use.
125     * @param rf coefficient ring factory. <b>Note:</b> red must be an instance
126     *            of PseudoReductionPar.
127     * @param red pseudo reduction engine.
128     * @param pool ExecutorService to use.
129     */
130    public GroebnerBasePseudoRecParallel(int threads, RingFactory<GenPolynomial<C>> rf,
131                    PseudoReduction<GenPolynomial<C>> red, ExecutorService pool) {
132        this(threads, rf, red, pool, new OrderedPairlist<GenPolynomial<C>>(
133                        new GenPolynomialRing<GenPolynomial<C>>(rf, 1))); // 1=hack
134    }
135
136
137    /**
138     * Constructor.
139     * @param threads number of threads to use.
140     * @param rf coefficient ring factory. <b>Note:</b> red must be an instance
141     *            of PseudoReductionPar.
142     * @param pl pair selection strategy
143     */
144    public GroebnerBasePseudoRecParallel(int threads, RingFactory<GenPolynomial<C>> rf,
145                    PairList<GenPolynomial<C>> pl) {
146        this(threads, rf, new PseudoReductionPar<GenPolynomial<C>>(), Executors.newFixedThreadPool(threads), pl);
147    }
148
149
150    /**
151     * Constructor.
152     * @param threads number of threads to use.
153     * @param rf coefficient ring factory. <b>Note:</b> red must be an instance
154     *            of PseudoReductionPar.
155     * @param red pseudo reduction engine.
156     * @param pool ExecutorService to use.
157     * @param pl pair selection strategy
158     */
159    @SuppressWarnings("unchecked")
160    public GroebnerBasePseudoRecParallel(int threads, RingFactory<GenPolynomial<C>> rf,
161                    PseudoReduction<GenPolynomial<C>> red, ExecutorService pool, PairList<GenPolynomial<C>> pl) {
162        super(red, pl);
163        if (!(red instanceof PseudoReductionPar)) {
164            logger.warn("parallel GB should use parallel aware reduction");
165        }
166        this.red = red;
167        this.redRec = (PseudoReduction<C>) (PseudoReduction) red;
168        cofac = rf;
169        if (threads < 1) {
170            threads = 1;
171        }
172        this.threads = threads;
173        GenPolynomialRing<C> rp = (GenPolynomialRing<C>) cofac;
174        baseCofac = rp.coFac;
175        //engine = (GreatestCommonDivisorAbstract<C>)GCDFactory.<C>getImplementation( baseCofac );
176        //not used: 
177        engine = GCDFactory.<C> getProxy(baseCofac);
178        this.pool = pool;
179    }
180
181
182    /**
183     * Cleanup and terminate ExecutorService.
184     */
185    @Override
186    public void terminate() {
187        if (pool == null) {
188            return;
189        }
190        pool.shutdown();
191        try {
192            while (!pool.isTerminated()) {
193                //logger.info("await");
194                boolean rest = pool.awaitTermination(1000L, TimeUnit.MILLISECONDS);
195            }
196        } catch (InterruptedException e) {
197            e.printStackTrace();
198        }
199        logger.info("pool = {}", pool);
200    }
201
202
203    /**
204     * Cancel ExecutorService.
205     */
206    @Override
207    public int cancel() {
208        if (pool == null) {
209            return 0;
210        }
211        int s = pool.shutdownNow().size();
212        logger.info("pool = {}", pool);
213        return s;
214    }
215
216
217    /**
218     * Groebner base using pairlist class.
219     * @param modv module variable number.
220     * @param F polynomial list.
221     * @return GB(F) a Groebner base of F.
222     */
223    public List<GenPolynomial<GenPolynomial<C>>> GB(int modv, List<GenPolynomial<GenPolynomial<C>>> F) {
224        List<GenPolynomial<GenPolynomial<C>>> G = normalizeZerosOnes(F);
225        G = engine.recursivePrimitivePart(G);
226        if (G.size() <= 1) {
227            return G;
228        }
229        GenPolynomialRing<GenPolynomial<C>> ring = G.get(0).ring;
230        if (ring.coFac.isField()) { // remove ?
231            throw new IllegalArgumentException("coefficients from a field");
232        }
233        PairList<GenPolynomial<C>> pairlist = strategy.create(modv, ring);
234        pairlist.put(G);
235        logger.info("start {}", pairlist);
236
237        Terminator fin = new Terminator(threads);
238        PseudoReducerRec<C> R;
239        for (int i = 0; i < threads; i++) {
240            R = new PseudoReducerRec<C>(fin, G, pairlist, engine);
241            pool.execute(R);
242        }
243        fin.waitDone();
244        if (Thread.currentThread().isInterrupted()) {
245            throw new RuntimeException("interrupt before minimalGB");
246        }
247        logger.debug("#parallel list = {}", G.size());
248        G = minimalGB(G);
249        logger.info("{}", pairlist);
250        return G;
251    }
252
253
254    /**
255     * Minimal ordered Groebner basis.
256     * @param Gp a Groebner base.
257     * @return a reduced Groebner base of Gp.
258     */
259    @Override
260    public List<GenPolynomial<GenPolynomial<C>>> minimalGB(List<GenPolynomial<GenPolynomial<C>>> Gp) {
261        List<GenPolynomial<GenPolynomial<C>>> G = normalizeZerosOnes(Gp);
262        if (G.size() <= 1) {
263            return G;
264        }
265        // remove top reducible polynomials
266        GenPolynomial<GenPolynomial<C>> a;
267        List<GenPolynomial<GenPolynomial<C>>> F;
268        F = new ArrayList<GenPolynomial<GenPolynomial<C>>>(G.size());
269        while (G.size() > 0) {
270            a = G.remove(0);
271            if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) {
272                // drop polynomial 
273                if (debug) {
274                    System.out.println("dropped " + a);
275                    List<GenPolynomial<GenPolynomial<C>>> ff;
276                    ff = new ArrayList<GenPolynomial<GenPolynomial<C>>>(G);
277                    ff.addAll(F);
278                    //a = red.normalform(ff, a);
279                    a = redRec.normalformRecursive(ff, a);
280                    if (!a.isZERO()) {
281                        System.out.println("error, nf(a) " + a);
282                    }
283                }
284            } else {
285                F.add(a);
286            }
287        }
288        G = F;
289        if (G.size() <= 1) {
290            return G;
291        }
292        Collections.reverse(G); // important for lex GB
293        // reduce remaining polynomials
294        @SuppressWarnings("unchecked")
295        PseudoMiReducerRec<C>[] mirs = (PseudoMiReducerRec<C>[]) new PseudoMiReducerRec[G.size()];
296        int i = 0;
297        F = new ArrayList<GenPolynomial<GenPolynomial<C>>>(G.size());
298        while (G.size() > 0) {
299            a = G.remove(0);
300            List<GenPolynomial<GenPolynomial<C>>> R = new ArrayList<GenPolynomial<GenPolynomial<C>>>(G.size()
301                            + F.size());
302            R.addAll(G);
303            R.addAll(F);
304            // System.out.println("doing " + a.length());
305            mirs[i] = new PseudoMiReducerRec<C>(R, a, engine);
306            pool.execute(mirs[i]);
307            i++;
308            F.add(a);
309        }
310        G = F;
311        F = new ArrayList<GenPolynomial<GenPolynomial<C>>>(G.size());
312        for (i = 0; i < mirs.length; i++) {
313            a = mirs[i].getNF();
314            F.add(a);
315        }
316        Collections.reverse(F); // undo reverse
317        return F;
318    }
319
320
321    /**
322     * Groebner base simple test.
323     * @param modv module variable number.
324     * @param F recursive polynomial list.
325     * @return true, if F is a Groebner base, else false.
326     */
327    @Override
328    public boolean isGBsimple(int modv, List<GenPolynomial<GenPolynomial<C>>> F) {
329        if (F == null || F.isEmpty()) {
330            return true;
331        }
332        GenPolynomial<GenPolynomial<C>> pi, pj, s, h;
333        ExpVector ei, ej, eij;
334        for (int i = 0; i < F.size(); i++) {
335            pi = F.get(i);
336            ei = pi.leadingExpVector();
337            for (int j = i + 1; j < F.size(); j++) {
338                pj = F.get(j);
339                ej = pj.leadingExpVector();
340                if (!red.moduleCriterion(modv, ei, ej)) {
341                    continue;
342                }
343                eij = ei.lcm(ej);
344                if (!red.criterion4(ei, ej, eij)) {
345                    continue;
346                }
347                //if (!criterion3(i, j, eij, F)) {
348                //    continue;
349                //}
350                s = red.SPolynomial(pi, pj);
351                if (s.isZERO()) {
352                    continue;
353                }
354                //System.out.println("i, j = " + i + ", " + j); 
355                h = redRec.normalformRecursive(F, s);
356                if (!h.isZERO()) {
357                    logger.info("no GB: pi = {}, pj = {}", pi, pj);
358                    logger.info("s  = {}, h = {}", s, h);
359                    return false;
360                }
361            }
362        }
363        return true;
364    }
365
366}
367
368
369/**
370 * Pseudo GB Reducing worker threads.
371 */
372class PseudoReducerRec<C extends GcdRingElem<C>> implements Runnable {
373
374
375    private final List<GenPolynomial<GenPolynomial<C>>> G;
376
377
378    private final PairList<GenPolynomial<C>> pairlist;
379
380
381    private final Terminator fin;
382
383
384    private final PseudoReductionPar<GenPolynomial<C>> red;
385
386
387    private final PseudoReductionPar<C> redRec;
388
389
390    private final GreatestCommonDivisorAbstract<C> engine;
391
392
393    private static final Logger logger = LogManager.getLogger(PseudoReducerRec.class);
394
395
396    PseudoReducerRec(Terminator fin, List<GenPolynomial<GenPolynomial<C>>> G, PairList<GenPolynomial<C>> L,
397                    GreatestCommonDivisorAbstract<C> engine) {
398        this.fin = fin;
399        this.G = G;
400        pairlist = L;
401        red = new PseudoReductionPar<GenPolynomial<C>>();
402        redRec = new PseudoReductionPar<C>();
403        this.engine = engine;
404        fin.initIdle(1);
405    }
406
407
408    /**
409     * to string
410     */
411    @Override
412    public String toString() {
413        return "PseudoReducer";
414    }
415
416
417    public void run() {
418        Pair<GenPolynomial<C>> pair;
419        GenPolynomial<GenPolynomial<C>> pi, pj, S, H;
420        //boolean set = false;
421        int reduction = 0;
422        int sleeps = 0;
423        while (pairlist.hasNext() || fin.hasJobs()) {
424            while (!pairlist.hasNext()) {
425                // wait
426                //fin.beIdle(); set = true;
427                try {
428                    sleeps++;
429                    if (sleeps % 10 == 0) {
430                        logger.info(" reducer is sleeping");
431                    } else {
432                        logger.debug("r");
433                    }
434                    Thread.sleep(100);
435                } catch (InterruptedException e) {
436                    break;
437                }
438                if (!fin.hasJobs()) {
439                    break;
440                }
441            }
442            if (!pairlist.hasNext() && !fin.hasJobs()) {
443                break;
444            }
445
446            fin.notIdle(); // before pairlist get
447            pair = pairlist.removeNext();
448            if (Thread.currentThread().isInterrupted()) {
449                fin.initIdle(1);
450                throw new RuntimeException("interrupt after removeNext");
451            }
452            if (pair == null) {
453                fin.initIdle(1);
454                continue;
455            }
456
457            pi = pair.pi;
458            pj = pair.pj;
459            logger.debug("pi = {}, pj = {}", pi, pj);
460
461            S = red.SPolynomial(pi, pj);
462            if (S.isZERO()) {
463                pair.setZero();
464                fin.initIdle(1);
465                continue;
466            }
467            logger.debug("ht(S) = {}", S.leadingExpVector());
468
469            //H = red.normalform(G, S); //mod
470            H = redRec.normalformRecursive(G, S);
471            reduction++;
472            if (H.isZERO()) {
473                pair.setZero();
474                fin.initIdle(1);
475                continue;
476            }
477            if (logger.isDebugEnabled()) {
478                logger.info("ht(H) = {}", H.leadingExpVector());
479            }
480
481            H = engine.recursivePrimitivePart(H); //H.monic();
482            H = H.abs();
483            // System.out.println("H   = " + H);
484            if (H.isONE()) {
485                // putOne not required
486                pairlist.put(H);
487                synchronized (G) {
488                    G.clear();
489                    G.add(H);
490                }
491                fin.allIdle();
492                return;
493            }
494            logger.debug("H = {}", H);
495            synchronized (G) {
496                G.add(H);
497            }
498            pairlist.put(H);
499            fin.initIdle(1);
500        }
501        fin.allIdle();
502        logger.info("terminated, done {} reductions", reduction);
503    }
504}
505
506
507/**
508 * Pseudo Reducing worker threads for minimal GB.
509 */
510class PseudoMiReducerRec<C extends GcdRingElem<C>> implements Runnable {
511
512
513    private final List<GenPolynomial<GenPolynomial<C>>> G;
514
515
516    private GenPolynomial<GenPolynomial<C>> H;
517
518
519    //private final PseudoReductionPar<GenPolynomial<C>> red;
520
521
522    private final PseudoReductionPar<C> redRec;
523
524
525    private final Semaphore done = new Semaphore(0);
526
527
528    private final GreatestCommonDivisorAbstract<C> engine;
529
530
531    private static final Logger logger = LogManager.getLogger(PseudoMiReducerRec.class);
532
533
534    PseudoMiReducerRec(List<GenPolynomial<GenPolynomial<C>>> G, GenPolynomial<GenPolynomial<C>> p,
535                    GreatestCommonDivisorAbstract<C> engine) {
536        this.G = G;
537        this.engine = engine;
538        H = p;
539        //red = new PseudoReductionPar<GenPolynomial<C>>();
540        redRec = new PseudoReductionPar<C>();
541    }
542
543
544    /**
545     * to string
546     */
547    @Override
548    public String toString() {
549        return "PseudoMiReducerRec";
550    }
551
552
553    /**
554     * getNF. Blocks until the normal form is computed.
555     * @return the computed normal form.
556     */
557    public GenPolynomial<GenPolynomial<C>> getNF() {
558        try {
559            done.acquire(); //done.P();
560        } catch (InterruptedException e) {
561            throw new RuntimeException("interrupt in getNF");
562        }
563        return H;
564    }
565
566
567    public void run() {
568        logger.debug("ht(H) = {}", H.leadingExpVector());
569        try {
570            //H = red.normalform(G, H); //mod
571            H = redRec.normalformRecursive(G, H);
572            H = engine.recursivePrimitivePart(H); //H.monic();
573            H = H.abs();
574            done.release(); //done.V();
575        } catch (RuntimeException e) {
576            Thread.currentThread().interrupt();
577            //throw new RuntimeException("interrupt in getNF");
578        }
579        logger.debug("ht(H) = {}", H.leadingExpVector());
580        // H = H.monic();
581    }
582
583}