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