Source code

001/*
002 * $Id: WordGroebnerBasePseudoRecSeq.java 5208 2015-04-05 10:36:25Z 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.OrderedWordPairlist;
015import edu.jas.gb.WordGroebnerBaseAbstract;
016import edu.jas.gb.WordPair;
017import edu.jas.gb.WordPairList;
018import edu.jas.poly.GenPolynomial;
019import edu.jas.poly.GenPolynomialRing;
020import edu.jas.poly.GenWordPolynomial;
021import edu.jas.poly.GenWordPolynomialRing;
022import edu.jas.poly.PolyUtil;
023import edu.jas.structure.GcdRingElem;
024import edu.jas.structure.RingFactory;
025import edu.jas.ufd.GCDFactory;
026import edu.jas.ufd.GreatestCommonDivisorAbstract;
027
028
029/**
030 * Non-commutative word Groebner Base sequential algorithm. Implements Groebner
031 * bases and GB test. Coefficients can for example be (commutative) multivariate
032 * polynomials.
033 * @param <C> coefficient type
034 * @author Heinz Kredel
035 */
036
037public class WordGroebnerBasePseudoRecSeq<C extends GcdRingElem<C>> extends
038                WordGroebnerBaseAbstract<GenPolynomial<C>> {
039
040
041    private static final Logger logger = Logger.getLogger(WordGroebnerBasePseudoRecSeq.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     * Reduction engine.
056     */
057    protected final WordPseudoReduction<C> redRec;
058
059
060    /**
061     * Reduction engine.
062     */
063    protected final WordPseudoReduction<GenPolynomial<C>> red;
064
065
066    /**
067     * Coefficient ring factory.
068     */
069    //protected final RingFactory<GenPolynomial<C>> cofac;
070    protected final GenPolynomialRing<C> cofac;
071
072
073    /**
074     * Constructor.
075     * @param rf coefficient ring factory.
076     */
077    public WordGroebnerBasePseudoRecSeq(RingFactory<GenPolynomial<C>> rf) {
078        this(rf, new WordPseudoReductionSeq<GenPolynomial<C>>());
079    }
080
081
082    /**
083     * Constructor.
084     * @param rf coefficient ring factory.
085     * @param red Reduction engine
086     */
087    public WordGroebnerBasePseudoRecSeq(RingFactory<GenPolynomial<C>> rf,
088                    WordPseudoReductionSeq<GenPolynomial<C>> red) {
089        this(rf, red, new OrderedWordPairlist<GenPolynomial<C>>());
090    }
091
092
093    /**
094     * Constructor.
095     * @param rf coefficient ring factory.
096     * @param red Reduction engine
097     * @param pl pair selection strategy
098     */
099    @SuppressWarnings("cast")
100    public WordGroebnerBasePseudoRecSeq(RingFactory<GenPolynomial<C>> rf,
101                    WordPseudoReductionSeq<GenPolynomial<C>> red, WordPairList<GenPolynomial<C>> pl) {
102        super(red, pl);
103        this.red = red;
104        redRec = (WordPseudoReduction<C>) (WordPseudoReduction) red;
105        cofac = (GenPolynomialRing<C>) rf;
106        if (!cofac.isCommutative()) {
107            logger.warn("reduction not correct for " + cofac.toScript());
108        }
109        engine = GCDFactory.<C> getImplementation(cofac.coFac);
110        //not used: engine = GCDFactory.<C>getProxy(cofac.coFac);
111    }
112
113
114    /**
115     * Word Groebner base using word pairlist class.
116     * @param F word polynomial list.
117     * @return GB(F) a finite non-commutative Groebner base of F, if it exists.
118     */
119    @Override
120    public List<GenWordPolynomial<GenPolynomial<C>>> GB(List<GenWordPolynomial<GenPolynomial<C>>> F) {
121        List<GenWordPolynomial<GenPolynomial<C>>> G = normalizeZerosOnes(F);
122        //G = PolyUtil.<C> wordMonic(G);
123        G = recursivePrimitivePart(G);
124        G = normalizeZerosOnes(G);
125        if (G.size() <= 1) {
126            return G;
127        }
128        GenWordPolynomialRing<GenPolynomial<C>> ring = G.get(0).ring;
129        if (!ring.coFac.isCommutative()) {
130            throw new IllegalArgumentException("coefficient ring not commutative");
131        }
132        //Collections.sort(G);
133        OrderedWordPairlist<GenPolynomial<C>> pairlist = (OrderedWordPairlist<GenPolynomial<C>>) strategy
134                        .create(ring);
135        pairlist.put(G);
136        logger.info("start " + pairlist);
137
138        WordPair<GenPolynomial<C>> pair;
139        GenWordPolynomial<GenPolynomial<C>> pi;
140        GenWordPolynomial<GenPolynomial<C>> pj;
141        List<GenWordPolynomial<GenPolynomial<C>>> S;
142        GenWordPolynomial<GenPolynomial<C>> H;
143        while (pairlist.hasNext()) {
144            pair = pairlist.removeNext();
145            //logger.debug("pair = " + pair);
146            if (pair == null) {
147                continue;
148            }
149            pi = pair.pi;
150            pj = pair.pj;
151            if (debug) {
152                logger.info("pi   = " + pi + ", pj = " + pj);
153                //logger.info("pj    = " + pj);
154            }
155
156            S = red.SPolynomials(pi, pj);
157            if (S.isEmpty()) {
158                continue;
159            }
160            for (GenWordPolynomial<GenPolynomial<C>> s : S) {
161                if (s.isZERO()) {
162                    //pair.setZero();
163                    continue;
164                }
165                if (debug) {
166                    logger.info("ht(S) = " + s.leadingWord());
167                }
168                boolean t = pairlist.criterion3(pair.i, pair.j, s.leadingWord());
169                //System.out.println("criterion3(" + pair.i + "," + pair.j + ") = " + t);
170                //if ( !t ) {
171                //    continue;  
172                //}
173
174                H = redRec.normalformRecursive(G, s);
175                if (debug) {
176                    //logger.info("pair = " + pair); 
177                    //logger.info("ht(S) = " + S.monic()); //.leadingWord() );
178                    logger.info("ht(H) = " + H.monic()); //.leadingWord() );
179                }
180                if (H.isZERO()) {
181                    //pair.setZero();
182                    continue;
183                }
184                if (!t) {
185                    logger.info("criterion3(" + pair.i + "," + pair.j + ") wrong: " + s.leadingWord()
186                                    + " --> '" + H.leadingWord() + "'");
187                }
188
189                //H = H.monic();
190                H = recursivePrimitivePart(H);
191                H = H.abs();
192                if (debug) {
193                    logger.info("ht(H) = " + H.leadingWord());
194                }
195                if (H.isONE()) {
196                    G.clear();
197                    G.add(H);
198                    return G; // since no threads are activated
199                }
200                if (debug) {
201                    logger.info("H = " + H);
202                }
203                if (H.length() > 0) {
204                    //l++;
205                    G.add(H);
206                    pairlist.put(H);
207                }
208            }
209        }
210        //logger.info("#sequential list = " + G.size());
211        G = minimalGB(G);
212        logger.info("" + pairlist);
213        //Collections.sort(G);
214        //Collections.reverse(G);
215        return G;
216    }
217
218
219    /**
220     * Minimal ordered Groebner basis.
221     * @param Gp a Groebner base.
222     * @return a reduced Groebner base of Gp.
223     */
224    @Override
225    public List<GenWordPolynomial<GenPolynomial<C>>> minimalGB(List<GenWordPolynomial<GenPolynomial<C>>> Gp) {
226        if (Gp == null || Gp.size() <= 1) {
227            return Gp;
228        }
229        // remove zero polynomials
230        List<GenWordPolynomial<GenPolynomial<C>>> G = new ArrayList<GenWordPolynomial<GenPolynomial<C>>>(
231                        Gp.size());
232        for (GenWordPolynomial<GenPolynomial<C>> a : Gp) {
233            if (a != null && !a.isZERO()) { // always true in GB()
234                // already positive a = a.abs();
235                G.add(a);
236            }
237        }
238        if (G.size() <= 1) {
239            return G;
240        }
241        // remove top reducible polynomials
242        GenWordPolynomial<GenPolynomial<C>> a;
243        List<GenWordPolynomial<GenPolynomial<C>>> F;
244        F = new ArrayList<GenWordPolynomial<GenPolynomial<C>>>(G.size());
245        while (G.size() > 0) {
246            a = G.remove(0);
247            if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) {
248                // drop polynomial 
249                if (debug) {
250                    System.out.println("dropped " + a);
251                    List<GenWordPolynomial<GenPolynomial<C>>> ff;
252                    ff = new ArrayList<GenWordPolynomial<GenPolynomial<C>>>(G);
253                    ff.addAll(F);
254                    a = redRec.normalformRecursive(ff, a);
255                    if (!a.isZERO()) {
256                        System.out.println("error, nf(a) " + a);
257                    }
258                }
259            } else {
260                F.add(a);
261            }
262        }
263        G = F;
264        if (G.size() <= 1) {
265            return G;
266        }
267        // reduce remaining polynomials
268        Collections.reverse(G); // important for lex GB
269        int len = G.size();
270        if (debug) {
271            System.out.println("#G " + len);
272            for (GenWordPolynomial<GenPolynomial<C>> aa : G) {
273                System.out.println("aa = " + aa.length() + ", lt = " + aa.getMap().keySet());
274            }
275        }
276        int i = 0;
277        while (i < len) {
278            a = G.remove(0);
279            if (debug) {
280                System.out.println("doing " + a.length() + ", lt = " + a.leadingWord());
281            }
282            a = redRec.normalformRecursive(G, a);
283            G.add(a); // adds as last
284            i++;
285        }
286        return G;
287    }
288
289
290    /**
291     * Wird Groebner base simple test.
292     * @param F recursive polynomial list.
293     * @return true, if F is a Groebner base, else false.
294     */
295    @Override
296    public boolean isGB(List<GenWordPolynomial<GenPolynomial<C>>> F) {
297        if (F == null || F.isEmpty()) {
298            return true;
299        }
300        GenWordPolynomial<GenPolynomial<C>> pi, pj, h;
301        List<GenWordPolynomial<GenPolynomial<C>>> S;
302        for (int i = 0; i < F.size(); i++) {
303            pi = F.get(i);
304            for (int j = 0; j < F.size(); j++) {
305                if (i == j) {
306                    continue;
307                }
308                pj = F.get(j);
309
310                S = red.SPolynomials(pi, pj);
311                if (S.isEmpty()) {
312                    continue;
313                }
314                for (GenWordPolynomial<GenPolynomial<C>> s : S) {
315                    //System.out.println("i, j = " + i + ", " + j); 
316                    h = redRec.normalformRecursive(F, s);
317                    if (!h.isZERO()) {
318                        logger.info("no GB: pi = " + pi + ", pj = " + pj);
319                        logger.info("s  = " + s + ", h = " + h);
320                        return false;
321                    }
322                }
323            }
324        }
325        return true;
326    }
327
328
329    /**
330     * GenWordPolynomial recursive coefficient content.
331     * @param P recursive GenWordPolynomial.
332     * @return cont(P).
333     */
334    public GenPolynomial<C> recursiveContent(GenWordPolynomial<GenPolynomial<C>> P) {
335        if (P == null) {
336            throw new IllegalArgumentException(this.getClass().getName() + " P != null");
337        }
338        if (P.isZERO()) {
339            return P.ring.getZEROCoefficient();
340        }
341        GenPolynomial<C> d = null;
342        for (GenPolynomial<C> c : P.getMap().values()) {
343            //System.out.println("value c = " + c.leadingExpVector());
344            if (d == null) {
345                d = c;
346            } else {
347                d = engine.gcd(d, c);
348            }
349            if (d.isONE()) {
350                return d;
351            }
352        }
353        if (d.signum() < 0) {
354            d = d.negate();
355        }
356        return d;
357    }
358
359
360    /**
361     * GenWordPolynomial recursive coefficient primitive part.
362     * @param P recursive GenWordPolynomial.
363     * @return pp(P).
364     */
365    public GenWordPolynomial<GenPolynomial<C>> recursivePrimitivePart(GenWordPolynomial<GenPolynomial<C>> P) {
366        if (P == null) {
367            throw new IllegalArgumentException(this.getClass().getName() + " P != null");
368        }
369        if (P.isZERO()) {
370            return P;
371        }
372        GenPolynomial<C> d = recursiveContent(P);
373        if (d.isONE()) {
374            return P;
375        }
376        //GenWordPolynomial<GenPolynomial<C>> pp = P.divide(d);
377        GenWordPolynomial<GenPolynomial<C>> pp = PolyUtil.<C> recursiveDivide(P, d);
378        if (debug) {
379            GenWordPolynomial<GenPolynomial<C>> p = pp.multiply(d);
380            if (!p.equals(P)) {
381                throw new ArithmeticException("pp(p)*cont(p) != p: ");
382            }
383        }
384        return pp;
385    }
386
387
388    /**
389     * List of GenWordPolynomial recursive coefficient primitive part.
390     * @param F list of recursive GenWordPolynomials.
391     * @return pp(F).
392     */
393    public List<GenWordPolynomial<GenPolynomial<C>>> recursivePrimitivePart(
394                    List<GenWordPolynomial<GenPolynomial<C>>> F) {
395        if (F == null || F.isEmpty()) {
396            return F;
397        }
398        List<GenWordPolynomial<GenPolynomial<C>>> Pp = new ArrayList<GenWordPolynomial<GenPolynomial<C>>>(
399                        F.size());
400        for (GenWordPolynomial<GenPolynomial<C>> f : F) {
401            GenWordPolynomial<GenPolynomial<C>> p = recursivePrimitivePart(f);
402            Pp.add(p);
403        }
404        return Pp;
405    }
406
407}