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