Source code

001/*
002 * $Id$
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   = {}, pj = {}", pi, 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({},{}) wrong: {} --> '{}'", pair.i, pair.j, s.leadingWord(), H.leadingWord());
186                }
187
188                //H = H.monic();
189                H = recursivePrimitivePart(H);
190                H = H.abs();
191                if (debug) {
192                    logger.info("ht(H) = {}", H.leadingWord());
193                }
194                if (H.isONE()) {
195                    G.clear();
196                    G.add(H);
197                    return G; // since no threads are activated
198                }
199                if (debug) {
200                    logger.info("H = {}", H);
201                }
202                if (H.length() > 0) {
203                    //l++;
204                    G.add(H);
205                    pairlist.put(H);
206                }
207            }
208        }
209        //logger.info("#sequential list = {}", G.size());
210        G = minimalGB(G);
211        logger.info("{}", pairlist);
212        //Collections.sort(G);
213        //Collections.reverse(G);
214        return G;
215    }
216
217
218    /**
219     * Minimal ordered Groebner basis.
220     * @param Gp a Groebner base.
221     * @return a reduced Groebner base of Gp.
222     */
223    @Override
224    public List<GenWordPolynomial<GenPolynomial<C>>> minimalGB(List<GenWordPolynomial<GenPolynomial<C>>> Gp) {
225        if (Gp == null || Gp.size() <= 1) {
226            return Gp;
227        }
228        // remove zero polynomials
229        List<GenWordPolynomial<GenPolynomial<C>>> G = new ArrayList<GenWordPolynomial<GenPolynomial<C>>>(
230                        Gp.size());
231        for (GenWordPolynomial<GenPolynomial<C>> a : Gp) {
232            if (a != null && !a.isZERO()) { // always true in GB()
233                // already positive a = a.abs();
234                G.add(a);
235            }
236        }
237        if (G.size() <= 1) {
238            return G;
239        }
240        // remove top reducible polynomials
241        GenWordPolynomial<GenPolynomial<C>> a;
242        List<GenWordPolynomial<GenPolynomial<C>>> F;
243        F = new ArrayList<GenWordPolynomial<GenPolynomial<C>>>(G.size());
244        while (G.size() > 0) {
245            a = G.remove(0);
246            if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) {
247                // drop polynomial 
248                if (debug) {
249                    System.out.println("dropped " + a);
250                    List<GenWordPolynomial<GenPolynomial<C>>> ff;
251                    ff = new ArrayList<GenWordPolynomial<GenPolynomial<C>>>(G);
252                    ff.addAll(F);
253                    a = redRec.normalformRecursive(ff, a);
254                    if (!a.isZERO()) {
255                        System.out.println("error, nf(a) " + a);
256                    }
257                }
258            } else {
259                F.add(a);
260            }
261        }
262        G = F;
263        if (G.size() <= 1) {
264            return G;
265        }
266        // reduce remaining polynomials
267        Collections.reverse(G); // important for lex GB
268        int len = G.size();
269        if (debug) {
270            System.out.println("#G " + len);
271            for (GenWordPolynomial<GenPolynomial<C>> aa : G) {
272                System.out.println("aa = " + aa.length() + ", lt = " + aa.getMap().keySet());
273            }
274        }
275        int i = 0;
276        while (i < len) {
277            a = G.remove(0);
278            if (debug) {
279                System.out.println("doing " + a.length() + ", lt = " + a.leadingWord());
280            }
281            a = redRec.normalformRecursive(G, a);
282            G.add(a); // adds as last
283            i++;
284        }
285        return G;
286    }
287
288
289    /**
290     * Wird Groebner base simple test.
291     * @param F recursive polynomial list.
292     * @return true, if F is a Groebner base, else false.
293     */
294    @Override
295    public boolean isGB(List<GenWordPolynomial<GenPolynomial<C>>> F) {
296        if (F == null || F.isEmpty()) {
297            return true;
298        }
299        GenWordPolynomial<GenPolynomial<C>> pi, pj, h;
300        List<GenWordPolynomial<GenPolynomial<C>>> S;
301        for (int i = 0; i < F.size(); i++) {
302            pi = F.get(i);
303            for (int j = 0; j < F.size(); j++) {
304                if (i == j) {
305                    continue;
306                }
307                pj = F.get(j);
308
309                S = red.SPolynomials(pi, pj);
310                if (S.isEmpty()) {
311                    continue;
312                }
313                for (GenWordPolynomial<GenPolynomial<C>> s : S) {
314                    //System.out.println("i, j = " + i + ", " + j); 
315                    h = redRec.normalformRecursive(F, s);
316                    if (!h.isZERO()) {
317                        logger.info("no GB: pi = {}, pj = {}", pi, pj);
318                        logger.info("s  = {}, h = {}", s, h);
319                        return false;
320                    }
321                }
322            }
323        }
324        return true;
325    }
326
327
328    /**
329     * GenWordPolynomial recursive coefficient content.
330     * @param P recursive GenWordPolynomial.
331     * @return cont(P).
332     */
333    public GenPolynomial<C> recursiveContent(GenWordPolynomial<GenPolynomial<C>> P) {
334        if (P == null) {
335            throw new IllegalArgumentException(this.getClass().getName() + " P != null");
336        }
337        if (P.isZERO()) {
338            return P.ring.getZEROCoefficient();
339        }
340        GenPolynomial<C> d = null;
341        for (GenPolynomial<C> c : P.getMap().values()) {
342            //System.out.println("value c = " + c.leadingExpVector());
343            if (d == null) {
344                d = c;
345            } else {
346                d = engine.gcd(d, c);
347            }
348            if (d.isONE()) {
349                return d;
350            }
351        }
352        if (d.signum() < 0) {
353            d = d.negate();
354        }
355        return d;
356    }
357
358
359    /**
360     * GenWordPolynomial recursive coefficient primitive part.
361     * @param P recursive GenWordPolynomial.
362     * @return pp(P).
363     */
364    public GenWordPolynomial<GenPolynomial<C>> recursivePrimitivePart(GenWordPolynomial<GenPolynomial<C>> P) {
365        if (P == null) {
366            throw new IllegalArgumentException(this.getClass().getName() + " P != null");
367        }
368        if (P.isZERO()) {
369            return P;
370        }
371        GenPolynomial<C> d = recursiveContent(P);
372        if (d.isONE()) {
373            return P;
374        }
375        //GenWordPolynomial<GenPolynomial<C>> pp = P.divide(d);
376        GenWordPolynomial<GenPolynomial<C>> pp = PolyUtil.<C> recursiveDivide(P, d);
377        if (debug) {
378            GenWordPolynomial<GenPolynomial<C>> p = pp.multiply(d);
379            if (!p.equals(P)) {
380                throw new ArithmeticException("pp(p)*cont(p) != p: ");
381            }
382        }
383        return pp;
384    }
385
386
387    /**
388     * List of GenWordPolynomial recursive coefficient primitive part.
389     * @param F list of recursive GenWordPolynomials.
390     * @return pp(F).
391     */
392    public List<GenWordPolynomial<GenPolynomial<C>>> recursivePrimitivePart(
393                    List<GenWordPolynomial<GenPolynomial<C>>> F) {
394        if (F == null || F.isEmpty()) {
395            return F;
396        }
397        List<GenWordPolynomial<GenPolynomial<C>>> Pp = new ArrayList<GenWordPolynomial<GenPolynomial<C>>>(
398                        F.size());
399        for (GenWordPolynomial<GenPolynomial<C>> f : F) {
400            GenWordPolynomial<GenPolynomial<C>> p = recursivePrimitivePart(f);
401            Pp.add(p);
402        }
403        return Pp;
404    }
405
406}