001/*
002 * $Id: GroebnerBaseSeqPairParallel.java 4059 2012-07-27 11:16:42Z kredel $
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;
013
014import org.apache.log4j.Logger;
015
016import edu.jas.poly.ExpVector;
017import edu.jas.poly.GenPolynomial;
018import edu.jas.structure.RingElem;
019import edu.jas.util.Terminator;
020import edu.jas.util.ThreadPool;
021
022
023/**
024 * Groebner Base parallel algorithm. Makes some effort to produce the same
025 * sequence of critical pairs as in the sequential version. However already
026 * reduced pairs are not rereduced if new polynomials appear. Implements a
027 * shared memory parallel version of Groebner bases. Slaves maintain pairlist.
028 * @param <C> coefficient type
029 * @author Heinz Kredel
030 */
031
032public class GroebnerBaseSeqPairParallel<C extends RingElem<C>> extends GroebnerBaseAbstract<C> {
033
034
035    private static final Logger logger = Logger.getLogger(GroebnerBaseSeqPairParallel.class);
036
037
038    /**
039     * Number of threads to use.
040     */
041    protected final int threads;
042
043
044    /**
045     * Pool of threads to use.
046     */
047    protected transient final ThreadPool pool;
048
049
050    /**
051     * Constructor.
052     */
053    public GroebnerBaseSeqPairParallel() {
054        this(2);
055    }
056
057
058    /**
059     * Constructor.
060     * @param threads number of threads to use.
061     */
062    public GroebnerBaseSeqPairParallel(int threads) {
063        this(threads, new ThreadPool(threads));
064    }
065
066
067    /**
068     * Constructor.
069     * @param threads number of threads to use.
070     * @param pool ThreadPool to use.
071     */
072    public GroebnerBaseSeqPairParallel(int threads, ThreadPool pool) {
073        this(threads, pool, new ReductionPar<C>());
074    }
075
076
077    /**
078     * Constructor.
079     * @param threads number of threads to use.
080     * @param red parallelism aware reduction engine
081     */
082    public GroebnerBaseSeqPairParallel(int threads, Reduction<C> red) {
083        this(threads, new ThreadPool(threads), red);
084    }
085
086
087    /**
088     * Constructor.
089     * @param threads number of threads to use.
090     * @param pool ThreadPool to use.
091     * @param red parallelism aware reduction engine
092     */
093    public GroebnerBaseSeqPairParallel(int threads, ThreadPool pool, Reduction<C> red) {
094        super(red);
095        if (!(red instanceof ReductionPar)) {
096            logger.warn("parallel GB should use parallel aware reduction");
097        }
098        if (threads < 1) {
099            threads = 1;
100        }
101        this.threads = threads;
102        this.pool = pool;
103    }
104
105
106    /**
107     * Cleanup and terminate ThreadPool.
108     */
109    @Override
110    public void terminate() {
111        if (pool == null) {
112            return;
113        }
114        pool.terminate();
115    }
116
117
118    /**
119     * Cancel ThreadPool.
120     */
121    @Override
122    public int cancel() {
123        if (pool == null) {
124            return 0;
125        }
126        int s = pool.cancel();
127        return s;
128    }
129
130
131    /**
132     * Parallel Groebner base using sequential pair order class. Slaves maintain
133     * pairlist.
134     * @param modv number of module variables.
135     * @param F polynomial list.
136     * @return GB(F) a Groebner base of F.
137     */
138    public List<GenPolynomial<C>> GB(int modv, List<GenPolynomial<C>> F) {
139        GenPolynomial<C> p;
140        List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>();
141        CriticalPairList<C> pairlist = null;
142        int l = F.size();
143        ListIterator<GenPolynomial<C>> it = F.listIterator();
144        while (it.hasNext()) {
145            p = it.next();
146            if (p.length() > 0) {
147                p = p.monic();
148                if (p.isONE()) {
149                    G.clear();
150                    G.add(p);
151                    return G; // since no threads activated jet
152                }
153                G.add(p);
154                if (pairlist == null) {
155                    pairlist = new CriticalPairList<C>(modv, p.ring);
156                    if (!p.ring.coFac.isField()) {
157                        throw new IllegalArgumentException("coefficients not from a field");
158                    }
159                }
160                // putOne not required
161                pairlist.put(p);
162            } else {
163                l--;
164            }
165        }
166        if (l <= 1) {
167            return G; // since no threads activated jet
168        }
169
170        Terminator fin = new Terminator(threads);
171        ReducerSeqPair<C> R;
172        for (int i = 0; i < threads; i++) {
173            R = new ReducerSeqPair<C>(fin, G, pairlist);
174            pool.addJob(R);
175        }
176        fin.waitDone();
177        if (Thread.currentThread().isInterrupted()) {
178            throw new RuntimeException("interrupt before minimalGB");
179        }
180        logger.debug("#parallel list = " + G.size());
181        G = minimalGB(G);
182        // not in this context // pool.terminate();
183        logger.info("" + pairlist);
184        return G;
185    }
186
187
188    /**
189     * Minimal ordered groebner basis, parallel.
190     * @param Fp a Groebner base.
191     * @return minimalGB(F) a minimal Groebner base of Fp.
192     */
193    @Override
194    public List<GenPolynomial<C>> minimalGB(List<GenPolynomial<C>> Fp) {
195        GenPolynomial<C> a;
196        ArrayList<GenPolynomial<C>> G;
197        G = new ArrayList<GenPolynomial<C>>(Fp.size());
198        ListIterator<GenPolynomial<C>> it = Fp.listIterator();
199        while (it.hasNext()) {
200            a = it.next();
201            if (a.length() != 0) { // always true
202                // already monic  a = a.monic();
203                G.add(a);
204            }
205        }
206        if (G.size() <= 1) {
207            return G;
208        }
209
210        ExpVector e;
211        ExpVector f;
212        GenPolynomial<C> p;
213        ArrayList<GenPolynomial<C>> F;
214        F = new ArrayList<GenPolynomial<C>>(G.size());
215        boolean mt;
216        while (G.size() > 0) {
217            a = G.remove(0);
218            e = a.leadingExpVector();
219
220            it = G.listIterator();
221            mt = false;
222            while (it.hasNext() && !mt) {
223                p = it.next();
224                f = p.leadingExpVector();
225                mt = e.multipleOf(f);
226            }
227            it = F.listIterator();
228            while (it.hasNext() && !mt) {
229                p = it.next();
230                f = p.leadingExpVector();
231                mt = e.multipleOf(f);
232            }
233            if (!mt) {
234                F.add(a); // no thread at this point
235            } else {
236                // System.out.println("dropped " + a.length());
237            }
238        }
239        G = F;
240        if (G.size() <= 1) {
241            return G;
242        }
243        Collections.reverse(G); // important for lex GB
244
245        MiReducerSeqPair<C>[] mirs = (MiReducerSeqPair<C>[]) new MiReducerSeqPair[G.size()];
246        int i = 0;
247        F = new ArrayList<GenPolynomial<C>>(G.size());
248        while (G.size() > 0) {
249            a = G.remove(0);
250            // System.out.println("doing " + a.length());
251            List<GenPolynomial<C>> R = new ArrayList<GenPolynomial<C>>(G.size() + F.size());
252            R.addAll(G);
253            R.addAll(F);
254            mirs[i] = new MiReducerSeqPair<C>(R, a);
255            pool.addJob(mirs[i]);
256            i++;
257            F.add(a);
258        }
259        G = F;
260        F = new ArrayList<GenPolynomial<C>>(G.size());
261        for (i = 0; i < mirs.length; i++) {
262            a = mirs[i].getNF();
263            F.add(a);
264        }
265        return F;
266    }
267
268}
269
270
271/**
272 * Reducing worker threads.
273 */
274class ReducerSeqPair<C extends RingElem<C>> implements Runnable {
275
276
277    private final List<GenPolynomial<C>> G;
278
279
280    private final CriticalPairList<C> pairlist;
281
282
283    private final Terminator fin;
284
285
286    private final ReductionPar<C> red;
287
288
289    private static final Logger logger = Logger.getLogger(ReducerSeqPair.class);
290
291
292    ReducerSeqPair(Terminator fin, List<GenPolynomial<C>> G, CriticalPairList<C> L) {
293        this.fin = fin;
294        this.G = G;
295        pairlist = L;
296        red = new ReductionPar<C>();
297    }
298
299
300    /**
301     * to string
302     */
303    @Override
304    public String toString() {
305        return "ReducerSeqPair";
306    }
307
308
309    public void run() {
310        CriticalPair<C> pair;
311        GenPolynomial<C> S;
312        GenPolynomial<C> H;
313        boolean set = false;
314        int reduction = 0;
315        int sleeps = 0;
316        while (pairlist.hasNext() || fin.hasJobs()) {
317            while (!pairlist.hasNext()) {
318                pairlist.update();
319                // wait
320                fin.beIdle();
321                set = true;
322                try {
323                    sleeps++;
324                    if (sleeps % 10 == 0) {
325                        logger.info(" reducer is sleeping");
326                    } else {
327                        logger.debug("r");
328                    }
329                    Thread.sleep(100);
330                } catch (InterruptedException e) {
331                    break;
332                }
333                if (!fin.hasJobs()) {
334                    break;
335                }
336                if (Thread.currentThread().isInterrupted()) {
337                    throw new RuntimeException("interrupt after sleep");
338                }
339            }
340            if (!pairlist.hasNext() && !fin.hasJobs()) {
341                break;
342            }
343            if (set) {
344                fin.notIdle();
345                set = false;
346            }
347            pair = pairlist.getNext();
348            if (Thread.currentThread().isInterrupted()) {
349                throw new RuntimeException("interrupt after getNext");
350            }
351            if (pair == null) {
352                pairlist.update();
353                continue;
354            }
355            if (logger.isDebugEnabled()) {
356                logger.debug("pi = " + pair.pi);
357                logger.debug("pj = " + pair.pj);
358            }
359            S = red.SPolynomial(pair.pi, pair.pj);
360            if (S.isZERO()) {
361                pairlist.record(pair, S);
362                continue;
363            }
364            if (logger.isDebugEnabled()) {
365                logger.debug("ht(S) = " + S.leadingExpVector());
366            }
367            H = red.normalform(G, S); //mod
368            reduction++;
369            if (H.isZERO()) {
370                pairlist.record(pair, H);
371                continue;
372            }
373            if (logger.isDebugEnabled()) {
374                logger.debug("ht(H) = " + H.leadingExpVector());
375            }
376            H = H.monic();
377            // System.out.println("H   = " + H);
378            if (H.isONE()) {
379                // pairlist.update( pair, H );
380                pairlist.putOne(); // not really required
381                synchronized (G) {
382                    G.clear();
383                    G.add(H);
384                }
385                fin.allIdle();
386                return;
387            }
388            if (logger.isDebugEnabled()) {
389                logger.debug("H = " + H);
390            }
391            synchronized (G) {
392                G.add(H);
393            }
394            pairlist.update(pair, H);
395            //pairlist.record( pair, H );
396            //pairlist.update();
397        }
398        logger.info("terminated, done " + reduction + " reductions");
399    }
400}
401
402
403/**
404 * Reducing worker threads for minimal GB.
405 */
406class MiReducerSeqPair<C extends RingElem<C>> implements Runnable {
407
408
409    private final List<GenPolynomial<C>> G;
410
411
412    private GenPolynomial<C> H;
413
414
415    private final ReductionPar<C> red;
416
417
418    private final Semaphore done = new Semaphore(0);
419
420
421    private static final Logger logger = Logger.getLogger(MiReducerSeqPair.class);
422
423
424    MiReducerSeqPair(List<GenPolynomial<C>> G, GenPolynomial<C> p) {
425        this.G = G;
426        H = p;
427        red = new ReductionPar<C>();
428    }
429
430
431    /**
432     * to string
433     */
434    @Override
435    public String toString() {
436        return "MiReducerSeqpair";
437    }
438
439
440    /**
441     * getNF. Blocks until the normal form is computed.
442     * @return the computed normal form.
443     */
444    public GenPolynomial<C> getNF() {
445        try {
446            done.acquire(); //done.P();
447        } catch (InterruptedException e) {
448            throw new RuntimeException("interrupt in getNF");
449        }
450        return H;
451    }
452
453
454    public void run() {
455        if (logger.isDebugEnabled()) {
456            logger.debug("ht(H) = " + H.leadingExpVector());
457        }
458        try {
459            H = red.normalform(G, H); //mod
460            done.release(); //done.V();
461        } catch (RuntimeException e) {
462            Thread.currentThread().interrupt();
463            //throw new RuntimeException("interrupt in getNF");
464        }
465        if (logger.isDebugEnabled()) {
466            logger.debug("ht(H) = " + H.leadingExpVector());
467        }
468        // H = H.monic();
469    }
470
471}