001/*
002 * $Id: GroebnerBaseSeqQuotient.java 4290 2012-11-04 14:47:45Z kredel $
003 */
004
005package edu.jas.gbufd;
006
007
008import java.util.ArrayList;
009import java.util.List;
010
011import org.apache.log4j.Logger;
012
013import edu.jas.gb.GroebnerBaseAbstract;
014import edu.jas.poly.GenPolynomial;
015import edu.jas.poly.GenPolynomialRing;
016import edu.jas.poly.PolyUtil;
017import edu.jas.structure.GcdRingElem;
018import edu.jas.ufd.PolyUfdUtil;
019import edu.jas.ufd.Quotient;
020import edu.jas.ufd.QuotientRing;
021
022
023/**
024 * Groebner Base sequential algorithm for rational function coefficients,
025 * fraction free computation. Implements Groebner bases.
026 * @param <C> Quotient coefficient type
027 * @author Heinz Kredel
028 */
029
030public class GroebnerBaseSeqQuotient<C extends GcdRingElem<C>> extends GroebnerBaseAbstract<Quotient<C>> {
031
032
033    private static final Logger logger = Logger.getLogger(GroebnerBaseSeqQuotient.class);
034
035
036    private final boolean debug = logger.isDebugEnabled();
037
038
039    public final GroebnerBaseAbstract<GenPolynomial<C>> bba;
040
041
042    /**
043     * Constructor.
044     * @param rf quotient coefficient ring factory.
045     */
046    public GroebnerBaseSeqQuotient(QuotientRing<C> rf) {
047        super();
048        bba = new GroebnerBasePseudoRecSeq<C>(rf.ring);
049    }
050
051
052    /**
053     * Get the String representation with GB engines.
054     * @see java.lang.Object#toString()
055     */
056    @Override
057    public String toString() {
058        return this.getClass().getSimpleName() + "(" + bba.toString() + ")";
059    }
060
061
062    /**
063     * Groebner base using fraction free computation.
064     * @param modv module variable number.
065     * @param F polynomial list.
066     * @return GB(F) a Groebner base of F.
067     */
068    @Override
069    public List<GenPolynomial<Quotient<C>>> GB(int modv, List<GenPolynomial<Quotient<C>>> F) {
070        List<GenPolynomial<Quotient<C>>> G = F;
071        if (F == null || F.isEmpty()) {
072            return G;
073        }
074        GenPolynomialRing<Quotient<C>> rring = F.get(0).ring;
075        QuotientRing<C> cf = (QuotientRing<C>) rring.coFac;
076        GenPolynomialRing<GenPolynomial<C>> iring = new GenPolynomialRing<GenPolynomial<C>>(cf.ring, rring);
077        List<GenPolynomial<GenPolynomial<C>>> Fi = PolyUfdUtil.<C> integralFromQuotientCoefficients(iring, F);
078        //System.out.println("Fi = " + Fi);
079        logger.info("#Fi = " + Fi.size());
080
081        List<GenPolynomial<GenPolynomial<C>>> Gi = bba.GB(modv, Fi);
082        //System.out.println("Gi = " + Gi);
083        logger.info("#Gi = " + Gi.size());
084
085        G = PolyUfdUtil.<C> quotientFromIntegralCoefficients(rring, Gi);
086        G = PolyUtil.<Quotient<C>> monic(G);
087        return G;
088    }
089
090
091    /**
092     * Minimal ordered Groebner basis.
093     * @param Gp a Groebner base.
094     * @return a reduced Groebner base of Gp.
095     */
096    @Override
097    public List<GenPolynomial<Quotient<C>>> minimalGB(List<GenPolynomial<Quotient<C>>> Gp) {
098        if (Gp == null || Gp.size() <= 1) {
099            return Gp;
100        }
101        // remove zero polynomials
102        List<GenPolynomial<Quotient<C>>> G = new ArrayList<GenPolynomial<Quotient<C>>>(Gp.size());
103        for (GenPolynomial<Quotient<C>> a : Gp) {
104            if (a != null && !a.isZERO()) { // always true in GB()
105                // already positive a = a.abs();
106                G.add(a);
107            }
108        }
109        if (G.size() <= 1) {
110            return G;
111        }
112        // remove top reducible polynomials
113        GenPolynomial<Quotient<C>> a;
114        List<GenPolynomial<Quotient<C>>> F;
115        F = new ArrayList<GenPolynomial<Quotient<C>>>(G.size());
116        while (G.size() > 0) {
117            a = G.remove(0);
118            if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) {
119                // drop polynomial 
120                if (debug) {
121                    System.out.println("dropped " + a);
122                    List<GenPolynomial<Quotient<C>>> ff;
123                    ff = new ArrayList<GenPolynomial<Quotient<C>>>(G);
124                    ff.addAll(F);
125                    a = red.normalform(ff, a);
126                    if (!a.isZERO()) {
127                        System.out.println("error, nf(a) " + a);
128                    }
129                }
130            } else {
131                F.add(a);
132            }
133        }
134        G = F;
135        if (G.size() <= 1) {
136            return G;
137        }
138
139        // reduce remaining polynomials
140        GenPolynomialRing<Quotient<C>> rring = G.get(0).ring;
141        QuotientRing<C> cf = (QuotientRing<C>) rring.coFac;
142        GenPolynomialRing<GenPolynomial<C>> iring = new GenPolynomialRing<GenPolynomial<C>>(cf.ring, rring);
143        List<GenPolynomial<GenPolynomial<C>>> Fi = PolyUfdUtil.integralFromQuotientCoefficients(iring, F);
144        logger.info("#Fi = " + Fi.size());
145
146        List<GenPolynomial<GenPolynomial<C>>> Gi = bba.minimalGB(Fi);
147        logger.info("#Gi = " + Gi.size());
148
149        G = PolyUfdUtil.<C> quotientFromIntegralCoefficients(rring, Gi);
150        G = PolyUtil.<Quotient<C>> monic(G);
151        return G;
152    }
153
154
155    /**
156     * Cleanup and terminate ThreadPool.
157     */
158    @Override
159    public void terminate() {
160        bba.terminate();
161    }
162
163
164    /**
165     * Cancel ThreadPool.
166     */
167    @Override
168    public int cancel() {
169        return bba.cancel();
170    }
171
172}