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