Source code

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