Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.gb;
006
007
008import java.util.ArrayList;
009import java.util.Collections;
010import java.util.HashSet;
011import java.util.List;
012import java.util.Set;
013import java.util.SortedMap;
014import java.util.TreeMap;
015
016import org.apache.logging.log4j.Logger;
017import org.apache.logging.log4j.LogManager; 
018
019import edu.jas.poly.GenWordPolynomial;
020import edu.jas.poly.GenWordPolynomialRing;
021import edu.jas.poly.Word;
022import edu.jas.structure.RingElem;
023
024
025/**
026 * Non-commutative Groebner Bases abstract class. Implements common Groebner
027 * bases and GB test methods.
028 * @param <C> coefficient type
029 * @author Heinz Kredel
030 */
031
032public abstract class WordGroebnerBaseAbstract<C extends RingElem<C>> implements WordGroebnerBase<C> {
033
034
035    private static final Logger logger = LogManager.getLogger(WordGroebnerBaseAbstract.class);
036
037
038    private static final boolean debug = logger.isDebugEnabled();
039
040
041    /**
042     * Reduction engine.
043     */
044    public final WordReduction<C> red;
045
046
047    /**
048     * Strategy for pair selection.
049     */
050    public final WordPairList<C> strategy;
051
052
053    /**
054     * Constructor.
055     */
056    public WordGroebnerBaseAbstract() {
057        this(new WordReductionSeq<C>());
058    }
059
060
061    /**
062     * Constructor.
063     * @param red Word Reduction engine
064     */
065    public WordGroebnerBaseAbstract(WordReduction<C> red) {
066        this(red, new OrderedWordPairlist<C>());
067    }
068
069
070    /**
071     * Constructor.
072     * @param red Word Reduction engine
073     * @param pl Word pair selection strategy
074     */
075    public WordGroebnerBaseAbstract(WordReduction<C> red, WordPairList<C> pl) {
076        this.red = red;
077        this.strategy = pl;
078    }
079
080
081    /**
082     * Get the String representation with GB engines.
083     * @see java.lang.Object#toString()
084     */
085    @Override
086    public String toString() {
087        return this.getClass().getSimpleName();
088    }
089
090
091    /**
092     * Normalize polynomial list.
093     * @param A list of polynomials.
094     * @return list of polynomials with zeros removed and ones/units reduced.
095     */
096    public List<GenWordPolynomial<C>> normalizeZerosOnes(List<GenWordPolynomial<C>> A) {
097        if (A == null) {
098            return A;
099        }
100        List<GenWordPolynomial<C>> N = new ArrayList<GenWordPolynomial<C>>(A.size());
101        if (A.isEmpty()) {
102            return N;
103        }
104        for (GenWordPolynomial<C> p : A) {
105            if (p == null || p.isZERO()) {
106                continue;
107            }
108            if (p.isUnit()) {
109                N.clear();
110                N.add(p.ring.getONE());
111                return N;
112            }
113            N.add(p.abs());
114        }
115        //N.trimToSize();
116        return N;
117    }
118
119
120    /**
121     * Common zero test, test if univariate leading words exist for all
122     * variables.
123     * @param F polynomial list.
124     * @return -1, 0 or 1 if "dimension"(ideal(F)) &eq; -1, 0 or &ge; 1.
125     */
126    public int commonZeroTest(List<GenWordPolynomial<C>> F) {
127        if (F == null || F.isEmpty()) {
128            return 1;
129        }
130        GenWordPolynomialRing<C> pfac = F.get(0).ring;
131        if (pfac.alphabet.length() <= 0) {
132            return -1;
133        }
134        Set<String> v = new HashSet<String>(); // for non reduced GBs
135        for (GenWordPolynomial<C> p : F) {
136            if (p.isZERO()) {
137                continue;
138            }
139            if (p.isConstant()) { // for non-monic lists
140                return -1;
141            }
142            Word e = p.leadingWord();
143            if (e == null) {
144                continue;
145            }
146            SortedMap<String, Integer> u = e.dependencyOnVariables();
147            if (u == null) {
148                continue;
149            }
150            if (u.size() == 1) {
151                v.add(u.firstKey());
152            }
153        }
154        if (pfac.alphabet.length() == v.size()) {
155            return 0;
156        }
157        return 1;
158    }
159
160
161    /**
162     * Univariate head term degrees.
163     * @param A list of polynomials.
164     * @return a list of the degrees of univariate head terms.
165     */
166    public List<Long> univariateDegrees(List<GenWordPolynomial<C>> A) {
167        List<Long> ud = new ArrayList<Long>();
168        if (A == null || A.size() == 0) {
169            return ud;
170        }
171        GenWordPolynomialRing<C> pfac = A.get(0).ring;
172        if (pfac.alphabet.length() <= 0) {
173            return ud;
174        }
175        SortedMap<String, Long> v = new TreeMap<String, Long>(); // for non reduced GBs
176        for (GenWordPolynomial<C> p : A) {
177            Word e = p.leadingWord();
178            if (e == null) {
179                continue;
180            }
181            SortedMap<String, Integer> u = e.dependencyOnVariables();
182            if (u == null) {
183                continue;
184            }
185            if (u.size() == 1) {
186                Long d = v.get(u.firstKey());
187                if (d == null) { // record only once
188                    v.put(u.firstKey(), Long.valueOf(u.get(u.firstKey())));
189                }
190            }
191        }
192        ud.addAll(v.values());
193        //Collections.reverse(ud);
194        return ud;
195    }
196
197
198    /**
199     * Word Groebner base test.
200     * @param F Word polynomial list.
201     * @return true, if F is a Groebner base, else false.
202     */
203    public boolean isGB(List<GenWordPolynomial<C>> F) {
204        if (F == null || F.size() <= 1) {
205            return true;
206        }
207        for (int i = 0; i < F.size(); i++) {
208            GenWordPolynomial<C> pi = F.get(i);
209            for (int j = i + 1; j < F.size(); j++) {
210                GenWordPolynomial<C> pj = F.get(j);
211                List<GenWordPolynomial<C>> S = red.SPolynomials(pi, pj);
212                for (GenWordPolynomial<C> s : S) {
213                    //System.out.println("s-pol("+i+","+j+"): " + s.leadingWord());
214                    GenWordPolynomial<C> h = red.normalform(F, s);
215                    if (!h.isZERO()) {
216                        logger.info("no GB: pi = {}, pj = {}", pi, pj);
217                        logger.info("s  = {}, h = {}", s, h);
218                        return false;
219                    }
220                }
221                S = red.SPolynomials(pj, pi);
222                for (GenWordPolynomial<C> s : S) {
223                    //System.out.println("s-pol("+j+","+i+"): " + s.leadingWord());
224                    GenWordPolynomial<C> h = red.normalform(F, s);
225                    if (!h.isZERO()) {
226                        logger.info("no GB: pj = {}, pi = {}", pj, pi);
227                        logger.info("s  = {}, h = {}", s, h);
228                        return false;
229                    }
230                }
231            }
232        }
233        return true;
234    }
235
236
237    /**
238     * Groebner base using pairlist class.
239     * @param F polynomial list.
240     * @return GB(F) a Groebner base of F.
241     */
242    public abstract List<GenWordPolynomial<C>> GB(List<GenWordPolynomial<C>> F);
243
244
245    /**
246     * Minimal ordered Groebner basis.
247     * @param Gp a Groebner base.
248     * @return a reduced Groebner base of Gp.
249     */
250    public List<GenWordPolynomial<C>> minimalGB(List<GenWordPolynomial<C>> Gp) {
251        if (Gp == null || Gp.size() <= 1) {
252            return Gp;
253        }
254        // remove zero polynomials
255        List<GenWordPolynomial<C>> G = new ArrayList<GenWordPolynomial<C>>(Gp.size());
256        for (GenWordPolynomial<C> a : Gp) {
257            if (a != null && !a.isZERO()) { // always true in GB()
258                // already positive a = a.abs();
259                G.add(a);
260            }
261        }
262        if (G.size() <= 1) {
263            return G;
264        }
265        // remove top reducible polynomials
266        GenWordPolynomial<C> a;
267        List<GenWordPolynomial<C>> F;
268        F = new ArrayList<GenWordPolynomial<C>>(G.size());
269        while (G.size() > 0) {
270            a = G.remove(0);
271            if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) {
272                // drop polynomial 
273                if (debug) {
274                    System.out.println("dropped " + a);
275                    List<GenWordPolynomial<C>> ff;
276                    ff = new ArrayList<GenWordPolynomial<C>>(G);
277                    ff.addAll(F);
278                    a = red.normalform(ff, a);
279                    if (!a.isZERO()) {
280                        System.out.println("error, nf(a) " + a);
281                    }
282                }
283            } else {
284                F.add(a);
285            }
286        }
287        G = F;
288        if (G.size() <= 1) {
289            return G;
290        }
291        // reduce remaining polynomials
292        Collections.reverse(G); // important for lex GB
293        int len = G.size();
294        if (debug) {
295            System.out.println("#G " + len);
296            for (GenWordPolynomial<C> aa : G) {
297                System.out.println("aa = " + aa.length() + ", lt = " + aa.getMap().keySet());
298            }
299        }
300        int i = 0;
301        while (i < len) {
302            a = G.remove(0);
303            if (debug) {
304                System.out.println("doing " + a.length() + ", lt = " + a.leadingWord());
305            }
306            a = red.normalform(G, a);
307            G.add(a); // adds as last
308            i++;
309        }
310        return G;
311    }
312
313
314    /**
315     * Test for minimal ordered Groebner basis.
316     * @param Gp an ideal base.
317     * @return true, if Gp is a reduced minimal Groebner base.
318     */
319    public boolean isMinimalGB(List<GenWordPolynomial<C>> Gp) {
320        if (Gp == null || Gp.size() == 0) {
321            return true;
322        }
323        // test for zero polynomials
324        for (GenWordPolynomial<C> a : Gp) {
325            if (a == null || a.isZERO()) {
326                if (debug) {
327                    logger.debug("zero polynomial {}", a);
328                }
329                return false;
330            }
331        }
332        // test for top reducible polynomials
333        List<GenWordPolynomial<C>> G = new ArrayList<GenWordPolynomial<C>>(Gp);
334        List<GenWordPolynomial<C>> F = new ArrayList<GenWordPolynomial<C>>(G.size());
335        while (G.size() > 0) {
336            GenWordPolynomial<C> a = G.remove(0);
337            if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) {
338                if (debug) {
339                    logger.debug("top reducible polynomial {}", a);
340                }
341                return false;
342            }
343            F.add(a);
344        }
345        G = F;
346        if (G.size() <= 1) {
347            return true;
348        }
349        // test reducibility of polynomials
350        int len = G.size();
351        int i = 0;
352        while (i < len) {
353            GenWordPolynomial<C> a = G.remove(0);
354            if (!red.isNormalform(G, a)) {
355                if (debug) {
356                    logger.debug("reducible polynomial {}", a);
357                }
358                return false;
359            }
360            G.add(a); // re-adds as last
361            i++;
362        }
363        return true;
364    }
365
366
367    /**
368     * Cleanup and terminate ThreadPool.
369     */
370    public void terminate() {
371        logger.info("terminate not implemented");
372    }
373
374
375    /**
376     * Cancel ThreadPool.
377     */
378    public int cancel() {
379        logger.info("cancel not implemented");
380        return 0;
381    }
382
383}