Source code

001/*
002 * $Id: GroebnerBasePseudoRecSeq.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.ExpVector;
019import edu.jas.poly.GenPolynomial;
020import edu.jas.poly.GenPolynomialRing;
021import edu.jas.structure.GcdRingElem;
022import edu.jas.structure.RingFactory;
023import edu.jas.ufd.GCDFactory;
024import edu.jas.ufd.GreatestCommonDivisorAbstract;
025
026
027/**
028 * Groebner Base with pseudo reduction sequential algorithm for integral
029 * function coefficients. Implements polynomial fraction free coefficients
030 * Groebner bases. Coefficients can for example be 
031 * (commutative) multivariate polynomials.
032 * @param <C> base coefficient type
033 * @author Heinz Kredel
034 * 
035 * @see edu.jas.application.GBAlgorithmBuilder
036 * @see edu.jas.gbufd.GBFactory
037 */
038
039public class GroebnerBasePseudoRecSeq<C extends GcdRingElem<C>> extends
040                GroebnerBaseAbstract<GenPolynomial<C>> {
041
042
043    private static final Logger logger = Logger.getLogger(GroebnerBasePseudoRecSeq.class);
044
045
046    private final boolean debug = logger.isDebugEnabled();
047
048
049    /**
050     * Greatest common divisor engine for coefficient content and primitive
051     * parts.
052     */
053    protected final GreatestCommonDivisorAbstract<C> engine;
054
055
056    /**
057     * Pseudo reduction engine.
058     */
059    protected final PseudoReduction<C> redRec;
060
061
062    /**
063     * Pseudo reduction engine.
064     */
065    protected final PseudoReduction<GenPolynomial<C>> red;
066
067
068    /**
069     * Coefficient ring factory.
070     */
071    protected final RingFactory<GenPolynomial<C>> cofac;
072
073
074    /**
075     * Base coefficient ring factory.
076     */
077    protected final RingFactory<C> baseCofac;
078
079
080    /**
081     * Constructor.
082     * @param rf coefficient ring factory.
083     */
084    public GroebnerBasePseudoRecSeq(RingFactory<GenPolynomial<C>> rf) {
085        this(new PseudoReductionSeq<GenPolynomial<C>>(), rf, new OrderedPairlist<GenPolynomial<C>>(
086                        new GenPolynomialRing<GenPolynomial<C>>(rf, 1))); // 1=hack
087    }
088
089
090    /**
091     * Constructor.
092     * @param rf coefficient ring factory.
093     * @param pl pair selection strategy
094     */
095    public GroebnerBasePseudoRecSeq(RingFactory<GenPolynomial<C>> rf, PairList<GenPolynomial<C>> pl) {
096        this(new PseudoReductionSeq<GenPolynomial<C>>(), rf, pl);
097    }
098
099
100    /**
101     * Constructor.
102     * @param red pseudo reduction engine. <b>Note:</b> red must be an instance
103     *            of PseudoReductionSeq.
104     * @param rf coefficient ring factory.
105     * @param pl pair selection strategy
106     */
107    @SuppressWarnings("cast")
108    public GroebnerBasePseudoRecSeq(PseudoReduction<GenPolynomial<C>> red, RingFactory<GenPolynomial<C>> rf,
109                    PairList<GenPolynomial<C>> pl) {
110        super(red, pl);
111        this.red = red;
112        this.redRec = (PseudoReduction<C>) (PseudoReduction) red;
113        cofac = rf;
114        GenPolynomialRing<C> rp = (GenPolynomialRing<C>) cofac;
115        baseCofac = rp.coFac;
116        //engine = (GreatestCommonDivisorAbstract<C>)GCDFactory.<C>getImplementation( baseCofac );
117        //not used: 
118        engine = GCDFactory.<C> getProxy(baseCofac);
119    }
120
121
122    /**
123     * Groebner base using pairlist class.
124     * @param modv module variable number.
125     * @param F polynomial list.
126     * @return GB(F) a Groebner base of F.
127     */
128    //@Override
129    public List<GenPolynomial<GenPolynomial<C>>> GB(int modv, List<GenPolynomial<GenPolynomial<C>>> F) {
130        List<GenPolynomial<GenPolynomial<C>>> G = normalizeZerosOnes(F);
131        G = engine.recursivePrimitivePart(G);
132        if (G.size() <= 1) {
133            return G;
134        }
135        GenPolynomialRing<GenPolynomial<C>> ring = G.get(0).ring;
136        if (ring.coFac.isField()) { // TODO remove
137            throw new IllegalArgumentException("coefficients from a field");
138        }
139        PairList<GenPolynomial<C>> pairlist = strategy.create(modv, ring);
140        pairlist.put(G);
141
142        /*
143        GenPolynomial<GenPolynomial<C>> p;
144        List<GenPolynomial<GenPolynomial<C>>> G = new ArrayList<GenPolynomial<GenPolynomial<C>>>();
145        PairList<GenPolynomial<C>> pairlist = null;
146        int l = F.size();
147        ListIterator<GenPolynomial<GenPolynomial<C>>> it = F.listIterator();
148        while (it.hasNext()) {
149            p = it.next();
150            if (p.length() > 0) {
151                p = engine.recursivePrimitivePart(p); //p.monic();
152                p = p.abs();
153                if (p.isConstant()) {
154                    G.clear();
155                    G.add(p);
156                    return G; // since no threads are activated
157                }
158                G.add(p);
159                if (pairlist == null) {
160                    //pairlist = new OrderedPairlist<GenPolynomial<C>>(modv, p.ring);
161                    pairlist = strategy.create(modv, p.ring);
162                }
163                // putOne not required
164                pairlist.put(p);
165            } else {
166                l--;
167            }
168        }
169        if (l <= 1) {
170            return G; // since no threads are activated
171        }
172        */
173
174        Pair<GenPolynomial<C>> pair;
175        GenPolynomial<GenPolynomial<C>> pi, pj, S, H;
176        while (pairlist.hasNext()) {
177            pair = pairlist.removeNext();
178            if (pair == null)
179                continue;
180
181            pi = pair.pi;
182            pj = pair.pj;
183            if (debug) {
184                logger.debug("pi    = " + pi);
185                logger.debug("pj    = " + pj);
186            }
187
188            S = red.SPolynomial(pi, pj);
189            if (S.isZERO()) {
190                pair.setZero();
191                continue;
192            }
193            if (debug) {
194                logger.info("ht(S) = " + S.leadingExpVector());
195            }
196
197            H = redRec.normalformRecursive(G, S);
198            if (H.isZERO()) {
199                pair.setZero();
200                continue;
201            }
202            if (debug) {
203                logger.info("ht(H) = " + H.leadingExpVector());
204            }
205            H = engine.recursivePrimitivePart(H);
206            H = H.abs();
207            if (H.isConstant()) {
208                G.clear();
209                G.add(H);
210                return G; // since no threads are activated
211            }
212            if (debug) {
213                logger.debug("H = " + H);
214            }
215            if (H.length() > 0) {
216                //l++;
217                G.add(H);
218                pairlist.put(H);
219            }
220        }
221        logger.debug("#sequential list = " + G.size());
222        G = minimalGB(G);
223        logger.info("" + pairlist);
224        return G;
225    }
226
227
228    /**
229     * Minimal ordered Groebner basis.
230     * @param Gp a Groebner base.
231     * @return a reduced Groebner base of Gp.
232     */
233    @Override
234    public List<GenPolynomial<GenPolynomial<C>>> minimalGB(List<GenPolynomial<GenPolynomial<C>>> Gp) {
235        List<GenPolynomial<GenPolynomial<C>>> G = normalizeZerosOnes(Gp);
236        /*
237        if (Gp == null || Gp.size() <= 1) {
238            return Gp;
239        }
240        // remove zero polynomials
241        List<GenPolynomial<GenPolynomial<C>>> G = new ArrayList<GenPolynomial<GenPolynomial<C>>>(Gp.size());
242        for (GenPolynomial<GenPolynomial<C>> a : Gp) {
243            if (a != null && !a.isZERO()) { // always true in GB()
244                // already positive a = a.abs();
245                G.add(a);
246            }
247        }
248        */
249        if (G.size() <= 1) {
250            return G;
251        }
252        // remove top reducible polynomials
253        GenPolynomial<GenPolynomial<C>> a;
254        List<GenPolynomial<GenPolynomial<C>>> F;
255        F = new ArrayList<GenPolynomial<GenPolynomial<C>>>(G.size());
256        while (G.size() > 0) {
257            a = G.remove(0);
258            if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) {
259                // drop polynomial 
260                if (debug) {
261                    System.out.println("dropped " + a);
262                    List<GenPolynomial<GenPolynomial<C>>> ff;
263                    ff = new ArrayList<GenPolynomial<GenPolynomial<C>>>(G);
264                    ff.addAll(F);
265                    a = redRec.normalformRecursive(ff, a);
266                    if (!a.isZERO()) {
267                        System.out.println("error, nf(a) " + a);
268                    }
269                }
270            } else {
271                F.add(a);
272            }
273        }
274        G = F;
275        if (G.size() <= 1) {
276            return G;
277        }
278        Collections.reverse(G); // important for lex GB
279        // reduce remaining polynomials
280        int len = G.size();
281        int i = 0;
282        while (i < len) {
283            a = G.remove(0);
284            //System.out.println("doing " + a.length());
285            a = redRec.normalformRecursive(G, a);
286            a = engine.recursivePrimitivePart(a); //a.monic(); was not required
287            a = a.abs();
288            //a = redRec.normalformRecursive( F, a );
289            G.add(a); // adds as last
290            i++;
291        }
292        return G;
293    }
294
295
296    /**
297     * Groebner base simple test.
298     * @param modv module variable number.
299     * @param F recursive polynomial list.
300     * @return true, if F is a Groebner base, else false.
301     */
302    @Override
303    public boolean isGBsimple(int modv, List<GenPolynomial<GenPolynomial<C>>> F) {
304        if (F == null || F.isEmpty()) {
305            return true;
306        }
307        GenPolynomial<GenPolynomial<C>> pi, pj, s, h;
308        ExpVector ei, ej, eij;
309        for (int i = 0; i < F.size(); i++) {
310            pi = F.get(i);
311            ei = pi.leadingExpVector();
312            for (int j = i + 1; j < F.size(); j++) {
313                pj = F.get(j);
314                ej = pj.leadingExpVector();
315                if (!red.moduleCriterion(modv, ei, ej)) {
316                    continue;
317                }
318                eij = ei.lcm(ej);
319                if (!red.criterion4(ei, ej, eij)) {
320                    continue;
321                }
322                //if (!criterion3(i, j, eij, F)) {
323                //    continue;
324                //}
325                s = red.SPolynomial(pi, pj);
326                if (s.isZERO()) {
327                    continue;
328                }
329                //System.out.println("i, j = " + i + ", " + j); 
330                h = redRec.normalformRecursive(F, s);
331                if (!h.isZERO()) {
332                    logger.info("no GB: pi = " + pi + ", pj = " + pj);
333                    logger.info("s  = " + s + ", h = " + h);
334                    return false;
335                }
336            }
337        }
338        return true;
339    }
340
341}