Source code

001/*
002 * $Id: GBAlgorithmBuilder.java 5324 2015-11-23 22:05:26Z kredel $
003 */
004
005package edu.jas.application;
006
007
008import java.io.Serializable;
009
010import org.apache.log4j.Logger;
011
012import edu.jas.arith.BigInteger;
013import edu.jas.arith.BigRational;
014import edu.jas.gb.GBOptimized;
015import edu.jas.gb.GBProxy;
016import edu.jas.gb.GroebnerBaseAbstract;
017import edu.jas.gb.GroebnerBaseParallel;
018import edu.jas.gb.GroebnerBaseSeqIter;
019import edu.jas.gb.OrderedMinPairlist;
020import edu.jas.gb.OrderedPairlist;
021import edu.jas.gb.OrderedSyzPairlist;
022import edu.jas.gb.PairList;
023import edu.jas.gbufd.GBFactory;
024import edu.jas.gbufd.GroebnerBaseFGLM;
025import edu.jas.gbufd.GroebnerBasePseudoParallel;
026import edu.jas.gbufd.GroebnerBaseQuotient;
027import edu.jas.gbufd.GroebnerBaseRational;
028import edu.jas.kern.ComputerThreads;
029import edu.jas.poly.GenPolynomial;
030import edu.jas.poly.GenPolynomialRing;
031import edu.jas.structure.GcdRingElem;
032import edu.jas.structure.RingFactory;
033import edu.jas.ufd.Quotient;
034import edu.jas.ufd.QuotientRing;
035
036
037/**
038 * Builder for commutative Gr&ouml;bner bases algorithm implementations.
039 * @author Heinz Kredel
040 * @usage To create objects that implement the <code>GroebnerBase</code>
041 *        interface one can use the <code>GBFactory</code> or this
042 *        <code>GBAlgorithmBuilder</code>. This class will select and compose an
043 *        appropriate implementation based on the types of polynomial
044 *        coefficients C and the desired properties. To build an implementation
045 *        start with the static method <code>polynomialRing()</code> to define
046 *        the polynomial ring. Then continue to construct the algorithm with the
047 *        methods
048 *        <ul>
049 *        <li><code>optimize()</code> or <code>optimize(boolean)</code> for term
050 *        order (variable order) optimization (true for return of permuted
051 *        polynomials),</li>
052 *        <li><code>normalPairlist()</code> (default),
053 *        <code>syzygyPairlist()</code> or <code>simplePairlist()</code> for
054 *        pair-list selection strategies,</li>
055 *        <li><code>fractionFree()</code> for clearing denominators and
056 *        computing with pseudo reduction,</li>
057 *        <li><code>graded()</code> for using the FGLM algorithm to first
058 *        compute a Gr&ouml;bner base with respect to a graded term order and
059 *        then constructing a Gr&ouml;bner base wrt. a lexicographical term
060 *        order,</li>
061 *        <li><code>iterated()</code> for using the iterative GB algorithm to 
062 *        compute a Gr&ouml;bner base adding one polynomial after another,</li>
063 *        <li><code>parallel()</code> additionaly compute a Gr&ouml;bner base
064 *        over a field or integral domain in parallel,</li>
065 *        <li><code>euclideanDomain()</code> for computing a e-Gr&ouml;bner
066 *        base,</li>
067 *        <li><code>domainAlgorithm(Algo)</code> for computing a d- or
068 *        e-Gr&ouml;bner base,</li>
069 *        </ul>
070 *        Finally call the method <code>build()</code> to obtain an
071 *        implementaton of class <code>GroebnerBaseAbstract</code>. For example
072 * 
073 *        <pre>
074 * 
075 * GenPolynomialRing&lt;C&gt; pf = new GenPolynomialRing&lt;C&gt;(cofac, vars);
076 * GroebnerBaseAbstract&lt;C&gt; engine;
077 * engine = GBAlgorithmBuilder.&lt;C&gt; polynomialRing(pf).fractionFree().parallel().optimize().build();
078 * c = engine.GB(A);
079 * </pre>
080 * 
081 *        For example, if the coefficient type is BigRational, the usage looks
082 *        like
083 * 
084 *        <pre>
085 * 
086 * GenPolynomialRing&lt;BigRational&gt; pf = new GenPolynomialRing&lt;BigRational&gt;(cofac, vars);
087 * GroebnerBaseAbstract&lt;BigRational&gt; engine;
088 * engine = GBAlgorithmBuilder.&lt;BigRational&gt; polynomialRing(pf).fractionFree().parallel().optimize().build();
089 * c = engine.GB(A);
090 * </pre>
091 * 
092 *        <b>Note:</b> Not all combinations are meanigful
093 * 
094 * @see edu.jas.gb.GroebnerBase
095 * @see edu.jas.gbufd.GBFactory
096 */
097
098public class GBAlgorithmBuilder<C extends GcdRingElem<C>> implements Serializable {
099
100
101    private static final Logger logger = Logger.getLogger(GBAlgorithmBuilder.class);
102
103
104    /**
105     * The current GB algorithm implementation.
106     */
107    private GroebnerBaseAbstract<C> algo;
108
109
110    /**
111     * The current polynomial ring.
112     */
113    public final GenPolynomialRing<C> ring;
114
115
116    /**
117     * Requested pairlist strategy.
118     */
119    public final PairList<C> strategy;
120
121
122    /**
123     * Constructor not for use.
124     */
125    protected GBAlgorithmBuilder() {
126        throw new IllegalArgumentException("do not use this constructor");
127    }
128
129
130    /**
131     * Constructor.
132     * @param ring the polynomial ring.
133     */
134    public GBAlgorithmBuilder(GenPolynomialRing<C> ring) {
135        this(ring, null);
136    }
137
138
139    /**
140     * Constructor.
141     * @param ring the polynomial ring.
142     * @param algo already determined algorithm.
143     */
144    public GBAlgorithmBuilder(GenPolynomialRing<C> ring, GroebnerBaseAbstract<C> algo) {
145        this(ring, algo, null);
146    }
147
148
149    /**
150     * Constructor.
151     * @param ring the polynomial ring.
152     * @param algo already determined algorithm.
153     * @param strategy pairlist strategy.
154     */
155    public GBAlgorithmBuilder(GenPolynomialRing<C> ring, GroebnerBaseAbstract<C> algo, PairList<C> strategy) {
156        if (ring == null) {
157            throw new IllegalArgumentException("ring may not be null");
158        }
159        this.ring = ring;
160        this.algo = algo; // null accepted
161        if (strategy == null) {
162            strategy = new OrderedPairlist<C>();
163        }
164        this.strategy = strategy;
165    }
166
167
168    /**
169     * Build the GB algorithm implementaton.
170     * @return GB algorithm implementaton as GroebnerBaseAbstract object.
171     */
172    public GroebnerBaseAbstract<C> build() {
173        if (algo == null) {
174            if (strategy == null) { // should not happen
175                algo = GBFactory.<C> getImplementation(ring.coFac);
176            } else {
177                algo = GBFactory.<C> getImplementation(ring.coFac, strategy);
178            }
179        }
180        return algo;
181    }
182
183
184    /**
185     * Define polynomial ring.
186     * @param fac the commutative polynomial ring.
187     * @return GBAlgorithmBuilder object.
188     */
189    public static <C extends GcdRingElem<C>> GBAlgorithmBuilder<C> polynomialRing(GenPolynomialRing<C> fac) {
190        return new GBAlgorithmBuilder<C>(fac);
191    }
192
193
194    /**
195     * Select syzygy critical pair-list strategy. Gebauer and M&ouml;ller
196     * algorithm.
197     * @return GBAlgorithmBuilder object.
198     */
199    public GBAlgorithmBuilder<C> syzygyPairlist() {
200        return new GBAlgorithmBuilder<C>(ring, algo, new OrderedSyzPairlist<C>());
201    }
202
203
204    /**
205     * Select normal critical pair-list strategy. Buchberger, Winkler and Kredel
206     * algorithm.
207     * @return GBAlgorithmBuilder object.
208     */
209    public GBAlgorithmBuilder<C> normalPairlist() {
210        return new GBAlgorithmBuilder<C>(ring, algo, new OrderedPairlist<C>());
211    }
212
213
214    /**
215     * Select simple critical pair-list strategy. Original Buchberger algorithm.
216     * @return GBAlgorithmBuilder object.
217     */
218    public GBAlgorithmBuilder<C> simplePairlist() {
219        return new GBAlgorithmBuilder<C>(ring, algo, new OrderedMinPairlist<C>());
220    }
221
222
223    /**
224     * Request term order optimization. Call optimize(true) for return of
225     * permuted polynomials.
226     * @return GBAlgorithmBuilder object.
227     */
228    public GBAlgorithmBuilder<C> optimize() {
229        return optimize(true);
230    }
231
232
233    /**
234     * Request term order optimization.
235     * @param rP true for return of permuted polynomials, false for inverse
236     *            permuted polynomials and new GB computation.
237     * @return GBAlgorithmBuilder object.
238     */
239    public GBAlgorithmBuilder<C> optimize(boolean rP) {
240        if (algo == null) {
241            algo = GBFactory.<C> getImplementation(ring.coFac, strategy);
242        }
243        GroebnerBaseAbstract<C> bb = new GBOptimized<C>(algo, rP);
244        return new GBAlgorithmBuilder<C>(ring, bb);
245    }
246
247
248    /**
249     * Request fraction free algorithm. For BigRational and Quotient
250     * coefficients denominators are cleared and pseudo reduction is used.
251     * @return GBAlgorithmBuilder object.
252     */
253    @SuppressWarnings("cast")
254    public GBAlgorithmBuilder<C> fractionFree() {
255        if (algo != null) {
256            logger.warn("selected algorithm ignored: " + algo + ", use fractionFree before");
257        }
258        if (((Object) ring.coFac) instanceof BigRational) {
259            BigRational cf = (BigRational) (Object) ring.coFac;
260            PairList<BigRational> sty = (PairList) strategy;
261            GroebnerBaseAbstract<BigRational> bb = GBFactory.getImplementation(cf, GBFactory.Algo.ffgb, sty);
262            GroebnerBaseAbstract<C> cbb = (GroebnerBaseAbstract<C>) (GroebnerBaseAbstract) bb;
263            return new GBAlgorithmBuilder<C>(ring, cbb);
264        }
265        if (((Object) ring.coFac) instanceof QuotientRing) {
266            QuotientRing<C> cf = (QuotientRing<C>) (Object) ring.coFac;
267            PairList<Quotient<C>> sty = (PairList) strategy;
268            GroebnerBaseAbstract<Quotient<C>> bb = GBFactory.<C> getImplementation(cf, GBFactory.Algo.ffgb,
269                            sty);
270            GroebnerBaseAbstract<C> cbb = (GroebnerBaseAbstract<C>) (GroebnerBaseAbstract) bb;
271            return new GBAlgorithmBuilder<C>(ring, cbb);
272        }
273        logger.warn("no fraction free algorithm implemented for " + ring);
274        return this;
275    }
276
277
278    /**
279     * Request e-GB algorithm.
280     * @return GBAlgorithmBuilder object.
281     */
282    public GBAlgorithmBuilder<C> euclideanDomain() {
283        return domainAlgorithm(GBFactory.Algo.egb);
284    }
285
286
287    /**
288     * Request d-, e- or i-GB algorithm.
289     * @param a algorithm from GBFactory.Algo.
290     * @return GBAlgorithmBuilder object.
291     */
292    @SuppressWarnings("cast")
293    public GBAlgorithmBuilder<C> domainAlgorithm(GBFactory.Algo a) {
294        if (((Object) ring.coFac) instanceof BigInteger) {
295            BigInteger cf = (BigInteger) (Object) ring.coFac;
296            GroebnerBaseAbstract<BigInteger> bb = GBFactory.getImplementation(cf, a);
297            GroebnerBaseAbstract<C> cbb = (GroebnerBaseAbstract<C>) (GroebnerBaseAbstract) bb;
298            return new GBAlgorithmBuilder<C>(ring, cbb);
299        }
300        if (((Object) ring.coFac) instanceof GenPolynomial) {
301            GenPolynomialRing<C> cf = (GenPolynomialRing) (Object) ring.coFac;
302            GroebnerBaseAbstract<GenPolynomial<C>> bb = GBFactory.<C> getImplementation(cf, a);
303            GroebnerBaseAbstract<C> cbb = (GroebnerBaseAbstract<C>) (GroebnerBaseAbstract) bb;
304            return new GBAlgorithmBuilder<C>(ring, cbb);
305        }
306        logger.warn("no domain algorithm implemented for " + ring);
307        return this;
308    }
309
310
311    /**
312     * Request parallel algorithm. Additionaly run a parallel algorithm via
313     * GBProxy.
314     * @return GBAlgorithmBuilder object.
315     */
316    @SuppressWarnings("unchecked")
317    public GBAlgorithmBuilder<C> parallel() {
318        return parallel(ComputerThreads.N_CPUS);
319    }
320
321
322    /**
323     * Request parallel algorithm. Additionaly run a parallel algorithm via
324     * GBProxy.
325     * @param threads number of threads requested.
326     * @return GBAlgorithmBuilder object.
327     */
328    @SuppressWarnings("cast")
329    public GBAlgorithmBuilder<C> parallel(int threads) {
330        if (ComputerThreads.NO_THREADS) {
331            logger.warn("parallel algorithms disabled");
332            return this;
333        }
334        if (algo == null) {
335            algo = GBFactory.<C> getImplementation(ring.coFac, strategy);
336        }
337        if (((RingFactory) ring.coFac) instanceof BigRational) {
338            GroebnerBaseAbstract<C> bb;
339            if (algo instanceof GroebnerBaseRational) { // fraction free requested
340                PairList<BigInteger> pli;
341                if (strategy instanceof OrderedMinPairlist) {
342                    pli = new OrderedMinPairlist<BigInteger>();
343                } else if (strategy instanceof OrderedSyzPairlist) {
344                    pli = new OrderedSyzPairlist<BigInteger>();
345                } else {
346                    pli = new OrderedPairlist<BigInteger>();
347                }
348                bb = (GroebnerBaseAbstract) new GroebnerBaseRational<BigRational>(threads, pli);
349            } else {
350                bb = (GroebnerBaseAbstract) new GroebnerBaseParallel<C>(threads, strategy);
351            }
352            GroebnerBaseAbstract<C> pbb = new GBProxy<C>(algo, bb);
353            return new GBAlgorithmBuilder<C>(ring, pbb);
354        } else if (((RingFactory) ring.coFac) instanceof QuotientRing) {
355            GroebnerBaseAbstract<C> bb;
356            if (algo instanceof GroebnerBaseQuotient) { // fraction free requested
357                PairList<GenPolynomial<C>> pli;
358                if (strategy instanceof OrderedMinPairlist) {
359                    pli = new OrderedMinPairlist<GenPolynomial<C>>();
360                } else if (strategy instanceof OrderedSyzPairlist) {
361                    pli = new OrderedSyzPairlist<GenPolynomial<C>>();
362                } else {
363                    pli = new OrderedPairlist<GenPolynomial<C>>();
364                }
365                QuotientRing<C> fac = (QuotientRing) ring.coFac;
366                bb = (GroebnerBaseAbstract) new GroebnerBaseQuotient<C>(threads, fac, pli); // pl not possible
367            } else {
368                bb = (GroebnerBaseAbstract) new GroebnerBaseParallel<C>(threads, strategy);
369            }
370            GroebnerBaseAbstract<C> pbb = new GBProxy<C>(algo, bb);
371            return new GBAlgorithmBuilder<C>(ring, pbb);
372        } else if (ring.coFac.isField()) {
373            GroebnerBaseAbstract<C> bb = new GroebnerBaseParallel<C>(threads, strategy);
374            GroebnerBaseAbstract<C> pbb = new GBProxy<C>(algo, bb);
375            return new GBAlgorithmBuilder<C>(ring, pbb);
376        } else if (ring.coFac.getONE() instanceof GcdRingElem) {
377            GroebnerBaseAbstract<C> bb = new GroebnerBasePseudoParallel<C>(threads, ring.coFac, strategy);
378            GroebnerBaseAbstract<C> pbb = new GBProxy<C>(algo, bb);
379            return new GBAlgorithmBuilder<C>(ring, pbb);
380        }
381        logger.warn("no parallel algorithm implemented for " + ring);
382        return this;
383    }
384
385
386    /**
387     * Request FGLM algorithm.
388     * @return GBAlgorithmBuilder object.
389     */
390    @SuppressWarnings("unchecked")
391    public GBAlgorithmBuilder<C> graded() {
392        if (ring.coFac.isField()) {
393            GroebnerBaseAbstract<C> bb;
394            if (algo == null) {
395                bb = new GroebnerBaseFGLM<C>();
396            } else {
397                bb = new GroebnerBaseFGLM<C>(algo);
398            }
399            return new GBAlgorithmBuilder<C>(ring, bb);
400        }
401        logger.warn("no FGLM algorithm implemented for " + ring);
402        return this;
403    }
404
405
406    /**
407     * Request iterated GB algorithm.
408     * @return GBAlgorithmBuilder object.
409     */
410    @SuppressWarnings("unchecked")
411    public GBAlgorithmBuilder<C> iterated() {
412        if (ring.coFac.isField()) {
413            GroebnerBaseAbstract<C> bb;
414            if (strategy == null) {
415                bb = new GroebnerBaseSeqIter<C>();
416            } else {
417                bb = new GroebnerBaseSeqIter<C>(strategy); 
418            }
419            if (algo != null) {
420                logger.warn("algo " + algo + " ignored for " + bb);
421            }
422            return new GBAlgorithmBuilder<C>(ring, bb);
423        }
424        logger.warn("no iterated GB algorithm implemented for " + ring);
425        return this;
426    }
427
428
429    /**
430     * String representation of the GB algorithm implementation.
431     * @see java.lang.Object#toString()
432     */
433    @Override
434    public String toString() {
435        StringBuffer s = new StringBuffer(" ");
436        if (algo != null) {
437            s.append(algo.toString());
438            s.append(" for ");
439        }
440        s.append(ring.toString());
441        return s.toString();
442    }
443
444
445    /**
446     * Get a scripting compatible string representation.
447     * @return script compatible representation for this Element.
448     * @see edu.jas.structure.Element#toScript()
449     */
450    public String toScript() {
451        // Python case
452        StringBuffer s = new StringBuffer(" ");
453        if (algo != null) {
454            s.append(algo.toString()); // nonsense
455            s.append(" ");
456        }
457        s.append(ring.toScript());
458        return s.toString();
459    }
460
461}