Source code

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