001/*
002 * $Id: GroebnerBasePseudoSeq.java 5061 2015-01-01 19:45:33Z kredel $
003 */
004
005package edu.jas.gbufd;
006
007
008import java.util.ArrayList;
009import java.util.Collections;
010import java.util.List;
011
012import org.apache.log4j.Logger;
013
014import edu.jas.gb.GroebnerBaseAbstract;
015import edu.jas.gb.OrderedPairlist;
016import edu.jas.gb.Pair;
017import edu.jas.gb.PairList;
018import edu.jas.poly.GenPolynomial;
019import edu.jas.poly.GenPolynomialRing;
020import edu.jas.structure.GcdRingElem;
021import edu.jas.structure.RingFactory;
022import edu.jas.ufd.GCDFactory;
023import edu.jas.ufd.GreatestCommonDivisorAbstract;
024
025
026/**
027 * Groebner Base with pseudo reduction sequential algorithm. Implements
028 * coefficient fraction free Groebner bases.
029 * Coefficients can for example be integers or (commutative) univariate polynomials.
030 * @param <C> coefficient type
031 * @author Heinz Kredel
032 * 
033 * @see edu.jas.application.GBAlgorithmBuilder
034 * @see edu.jas.gbufd.GBFactory
035 */
036
037public class GroebnerBasePseudoSeq<C extends GcdRingElem<C>> extends GroebnerBaseAbstract<C> {
038
039
040    private static final Logger logger = Logger.getLogger(GroebnerBasePseudoSeq.class);
041
042
043    private final boolean debug = logger.isDebugEnabled();
044
045
046    /**
047     * Greatest common divisor engine for coefficient content and primitive
048     * parts.
049     */
050    protected final GreatestCommonDivisorAbstract<C> engine;
051
052
053    /**
054     * Pseudo reduction engine.
055     */
056    protected final PseudoReduction<C> red;
057
058
059    /**
060     * Coefficient ring factory.
061     */
062    protected final RingFactory<C> cofac;
063
064
065    /**
066     * Constructor.
067     * @param rf coefficient ring factory.
068     */
069    public GroebnerBasePseudoSeq(RingFactory<C> rf) {
070        this(new PseudoReductionSeq<C>(), rf, new OrderedPairlist<C>());
071    }
072
073
074    /**
075     * Constructor.
076     * @param rf coefficient ring factory.
077     * @param pl pair selection strategy
078     */
079    public GroebnerBasePseudoSeq(RingFactory<C> rf, PairList<C> pl) {
080        this(new PseudoReductionSeq<C>(), rf, pl);
081    }
082
083
084    /**
085     * Constructor.
086     * @param red pseudo reduction engine. <b>Note:</b> red must be an instance
087     *            of PseudoReductionSeq.
088     * @param rf coefficient ring factory.
089     * @param pl pair selection strategy
090     */
091    public GroebnerBasePseudoSeq(PseudoReduction<C> red, RingFactory<C> rf, PairList<C> pl) {
092        super(red, pl);
093        this.red = red;
094        cofac = rf;
095        engine = GCDFactory.<C> getImplementation(rf);
096        //not used: engine = (GreatestCommonDivisorAbstract<C>)GCDFactory.<C>getProxy( rf );
097    }
098
099
100    /**
101     * Groebner base using pairlist class.
102     * @param modv module variable number.
103     * @param F polynomial list.
104     * @return GB(F) a Groebner base of F.
105     */
106    public List<GenPolynomial<C>> GB(int modv, List<GenPolynomial<C>> F) {
107        List<GenPolynomial<C>> G = normalizeZerosOnes(F);
108        G = engine.basePrimitivePart(G);
109        if (G.size() <= 1) {
110            return G;
111        }
112        GenPolynomialRing<C> ring = G.get(0).ring;
113        if (ring.coFac.isField()) { // TODO remove
114            throw new IllegalArgumentException("coefficients from a field");
115        }
116        PairList<C> pairlist = strategy.create(modv, ring);
117        pairlist.put(G);
118
119        /*
120        GenPolynomial<C> p;
121        List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>();
122        PairList<C> pairlist = null;
123        int l = F.size();
124        ListIterator<GenPolynomial<C>> it = F.listIterator();
125        while (it.hasNext()) {
126            p = it.next();
127            if (p.length() > 0) {
128                p = engine.basePrimitivePart(p); //p.monic();
129                p = p.abs();
130                if (p.isConstant()) {
131                    G.clear();
132                    G.add(p);
133                    return G; // since no threads are activated
134                }
135                G.add(p);
136                if (pairlist == null) {
137                    //pairlist = new OrderedPairlist<C>(modv, p.ring);
138                    pairlist = strategy.create(modv, p.ring);
139                }
140                // putOne not required
141                pairlist.put(p);
142            } else {
143                l--;
144            }
145        }
146        if (l <= 1) {
147            return G; // since no threads are activated
148        }
149        */
150
151        Pair<C> pair;
152        GenPolynomial<C> pi, pj, S, H;
153        while (pairlist.hasNext()) {
154            pair = pairlist.removeNext();
155            if (pair == null)
156                continue;
157
158            pi = pair.pi;
159            pj = pair.pj;
160            if (debug) {
161                logger.debug("pi    = " + pi);
162                logger.debug("pj    = " + pj);
163            }
164
165            S = red.SPolynomial(pi, pj);
166            if (S.isZERO()) {
167                pair.setZero();
168                continue;
169            }
170            if (debug) {
171                logger.debug("ht(S) = " + S.leadingExpVector());
172            }
173
174            H = red.normalform(G, S);
175            if (H.isZERO()) {
176                pair.setZero();
177                continue;
178            }
179            if (debug) {
180                logger.debug("ht(H) = " + H.leadingExpVector());
181            }
182            H = engine.basePrimitivePart(H);
183            H = H.abs();
184            if (H.isConstant()) {
185                G.clear();
186                G.add(H);
187                return G; // since no threads are activated
188            }
189            if (logger.isDebugEnabled()) {
190                logger.debug("H = " + H);
191            }
192            if (H.length() > 0) {
193                //l++;
194                G.add(H);
195                pairlist.put(H);
196            }
197        }
198        logger.debug("#sequential list = " + G.size());
199        G = minimalGB(G);
200        logger.info("" + pairlist);
201        return G;
202    }
203
204
205    /**
206     * Minimal ordered Groebner basis.
207     * @param Gp a Groebner base.
208     * @return a reduced Groebner base of Gp.
209     */
210    @Override
211    public List<GenPolynomial<C>> minimalGB(List<GenPolynomial<C>> Gp) {
212        List<GenPolynomial<C>> G = normalizeZerosOnes(Gp);
213        /*        
214        // remove zero polynomials
215        if (Gp == null || Gp.size() <= 1) {
216            return Gp;
217        }
218        List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>(Gp.size());
219        for (GenPolynomial<C> a : Gp) {
220            if (a != null && !a.isZERO()) { // always true in GB()
221                // already positive a = a.abs();
222                G.add(a);
223            }
224        }
225        */
226        if (G.size() <= 1) {
227            return G;
228        }
229        // remove top reducible polynomials
230        GenPolynomial<C> a;
231        List<GenPolynomial<C>> F;
232        F = new ArrayList<GenPolynomial<C>>(G.size());
233        while (G.size() > 0) {
234            a = G.remove(0);
235            if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) {
236                // drop polynomial 
237                if (debug) {
238                    System.out.println("dropped " + a);
239                    List<GenPolynomial<C>> ff;
240                    ff = new ArrayList<GenPolynomial<C>>(G);
241                    ff.addAll(F);
242                    a = red.normalform(ff, a);
243                    if (!a.isZERO()) {
244                        System.out.println("error, nf(a) " + a);
245                    }
246                }
247            } else {
248                F.add(a);
249            }
250        }
251        G = F;
252        if (G.size() <= 1) {
253            return G;
254        }
255        Collections.reverse(G); // important for lex GB
256        // reduce remaining polynomials
257        int len = G.size();
258        int i = 0;
259        while (i < len) {
260            a = G.remove(0);
261            //System.out.println("doing " + a.length());
262            a = red.normalform(G, a);
263            a = engine.basePrimitivePart(a); //a.monic(); not possible
264            a = a.abs();
265            //a = red.normalform( F, a );
266            G.add(a); // adds as last
267            i++;
268        }
269        return G;
270    }
271
272}