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