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