Source code

001/*
002 * $Id: WordReductionAbstract.java 4152 2012-09-02 11:15:48Z kredel $
003 */
004
005package edu.jas.gb;
006
007
008import java.util.ArrayList;
009import java.util.LinkedList;
010import java.util.List;
011import java.util.Map;
012
013import org.apache.log4j.Logger;
014
015import edu.jas.poly.Word;
016import edu.jas.poly.GenWordPolynomial;
017import edu.jas.poly.OverlapList;
018import edu.jas.poly.Overlap;
019import edu.jas.structure.RingElem;
020
021
022/**
023 * Polynomial word reduction abstract class. Implements common S-Polynomial,
024 * normalform, module criterion and irreducible set.
025 * @param <C> coefficient type
026 * @author Heinz Kredel
027 */
028
029public abstract class WordReductionAbstract<C extends RingElem<C>> implements WordReduction<C> {
030
031
032    private static final Logger logger = Logger.getLogger(WordReductionAbstract.class);
033
034
035    private final boolean debug = logger.isDebugEnabled();
036
037
038    /**
039     * Constructor.
040     */
041    public WordReductionAbstract() {
042    }
043
044
045    /**
046     * S-Polynomials of non-commutative polynomials.
047     * @param Ap word polynomial.
048     * @param Bp word polynomial.
049     * @return list of all spol(Ap,Bp) the S-polynomials of Ap and Bp.
050     */
051    public List<GenWordPolynomial<C>> SPolynomials(GenWordPolynomial<C> Ap, 
052                                                   GenWordPolynomial<C> Bp) {
053        List<GenWordPolynomial<C>> sp = new ArrayList<GenWordPolynomial<C>>();
054        Map.Entry<Word, C> ma = Ap.leadingMonomial();
055        Map.Entry<Word, C> mb = Bp.leadingMonomial();
056        Word e = ma.getKey();
057        Word f = mb.getKey();
058        C a = ma.getValue();
059        C b = mb.getValue();
060        OverlapList oll = e.overlap(f); 
061        if ( oll.ols.isEmpty() ) {
062            return sp;
063        }
064        for ( Overlap ol : oll.ols ) {
065            GenWordPolynomial<C> s = SPolynomial(ol, b, Ap, a, Bp);
066            sp.add(s);
067        }
068        return sp;
069    }
070
071
072    /**
073     * S-Polynomials of non-commutative polynomials.
074     * @param a leading base coefficient of B.
075     * @param l1 word.
076     * @param A word polynomial.
077     * @param r1 word.
078     * @param b leading base coefficient of A.
079     * @param l2 word.
080     * @param B word polynomial.
081     * @param r2 word.
082     * @return list of all spol(Ap,Bp) the S-polynomials of Ap and Bp.
083     */
084    public GenWordPolynomial<C> SPolynomial(C a, Word l1, GenWordPolynomial<C> A, Word r1,
085                                            C b, Word l2, GenWordPolynomial<C> B, Word r2) {
086        C one = A.ring.coFac.getONE();
087        GenWordPolynomial<C> s1 = A.multiply(a,l1,one,r1);
088        GenWordPolynomial<C> s2 = B.multiply(b,l2,one,r2);
089        GenWordPolynomial<C> s = s1.subtract(s2);
090        return s;
091    }
092
093
094    /**
095     * S-Polynomials of non-commutative polynomials.
096     * @param ol Overlap tuple.
097     * @param a leading base coefficient of B.
098     * @param A word polynomial.
099     * @param b leading base coefficient of A.
100     * @param B word polynomial.
101     * @return list of all spol(Ap,Bp) the S-polynomials of Ap and Bp.
102     */
103    public GenWordPolynomial<C> SPolynomial(Overlap ol, C a, GenWordPolynomial<C> A,
104                                                        C b, GenWordPolynomial<C> B) {
105        C one = A.ring.coFac.getONE();
106        GenWordPolynomial<C> s1 = A.multiply(a,ol.l1,one,ol.r1);
107        GenWordPolynomial<C> s2 = B.multiply(b,ol.l2,one,ol.r2);
108        GenWordPolynomial<C> s = s1.subtract(s2);
109        return s;
110    }
111
112
113    /**
114     * Normalform Set.
115     * @param Ap polynomial list.
116     * @param Pp polynomial list.
117     * @return list of nf(a) with respect to Pp for all a in Ap.
118     */
119    public List<GenWordPolynomial<C>> normalform(List<GenWordPolynomial<C>> Pp, List<GenWordPolynomial<C>> Ap) {
120        if (Pp == null || Pp.isEmpty()) {
121            return Ap;
122        }
123        if (Ap == null || Ap.isEmpty()) {
124            return Ap;
125        }
126        ArrayList<GenWordPolynomial<C>> red = new ArrayList<GenWordPolynomial<C>>();
127        for (GenWordPolynomial<C> A : Ap) {
128            A = normalform(Pp, A);
129            red.add(A);
130        }
131        return red;
132    }
133
134
135    /**
136     * Is top reducible.
137     * @param A polynomial.
138     * @param P polynomial list.
139     * @return true if A is top reducible with respect to P.
140     */
141    public boolean isTopReducible(List<GenWordPolynomial<C>> P, GenWordPolynomial<C> A) {
142        if (P == null || P.isEmpty()) {
143            return false;
144        }
145        if (A == null || A.isZERO()) {
146            return false;
147        }
148        boolean mt = false;
149        Word e = A.leadingWord();
150        for (GenWordPolynomial<C> p : P) {
151            mt = e.multipleOf(p.leadingWord());
152            if (mt) {
153                return true;
154            }
155        }
156        return false;
157    }
158
159
160    /**
161     * Is reducible.
162     * @param Ap polynomial.
163     * @param Pp polynomial list.
164     * @return true if Ap is reducible with respect to Pp.
165     */
166    public boolean isReducible(List<GenWordPolynomial<C>> Pp, GenWordPolynomial<C> Ap) {
167        return !isNormalform(Pp, Ap);
168    }
169
170
171    /**
172     * Is in Normalform.
173     * @param Ap polynomial.
174     * @param Pp polynomial list.
175     * @return true if Ap is in normalform with respect to Pp.
176     */
177    @SuppressWarnings("unchecked")
178    public boolean isNormalform(List<GenWordPolynomial<C>> Pp, GenWordPolynomial<C> Ap) {
179        if (Pp == null || Pp.isEmpty()) {
180            return true;
181        }
182        if (Ap == null || Ap.isZERO()) {
183            return true;
184        }
185        int l;
186        GenWordPolynomial<C>[] P;
187        synchronized (Pp) {
188            l = Pp.size();
189            P = new GenWordPolynomial[l];
190            //P = Pp.toArray();
191            for (int i = 0; i < Pp.size(); i++) {
192                P[i] = Pp.get(i);
193            }
194        }
195        Word[] htl = new Word[l];
196        GenWordPolynomial<C>[] p = new GenWordPolynomial[l];
197        Map.Entry<Word, C> m;
198        int i;
199        int j = 0;
200        for (i = 0; i < l; i++) {
201            p[i] = P[i];
202            m = p[i].leadingMonomial();
203            if (m != null) {
204                p[j] = p[i];
205                htl[j] = m.getKey();
206                j++;
207            }
208        }
209        l = j;
210        boolean mt = false;
211        for (Word e : Ap.getMap().keySet()) {
212            for (i = 0; i < l; i++) {
213                mt = e.multipleOf(htl[i]);
214                if (mt) {
215                    return false;
216                }
217            }
218        }
219        return true;
220    }
221
222
223    /**
224     * Is in Normalform.
225     * @param Pp polynomial list.
226     * @return true if each Ap in Pp is in normalform with respect to Pp\{Ap}.
227     */
228    public boolean isNormalform(List<GenWordPolynomial<C>> Pp) {
229        if (Pp == null || Pp.isEmpty()) {
230            return true;
231        }
232        GenWordPolynomial<C> Ap;
233        List<GenWordPolynomial<C>> P = new LinkedList<GenWordPolynomial<C>>(Pp);
234        int s = P.size();
235        for (int i = 0; i < s; i++) {
236            Ap = P.remove(i);
237            if (!isNormalform(P, Ap)) {
238                return false;
239            }
240            P.add(Ap);
241        }
242        return true;
243    }
244
245
246    /**
247     * Irreducible set.
248     * @param Pp polynomial list.
249     * @return a list P of monic polynomials which are in normalform wrt. P and
250     *         with ideal(Pp) = ideal(P).
251     */
252    public List<GenWordPolynomial<C>> irreducibleSet(List<GenWordPolynomial<C>> Pp) {
253        ArrayList<GenWordPolynomial<C>> P = new ArrayList<GenWordPolynomial<C>>();
254        for (GenWordPolynomial<C> a : Pp) {
255            if (a.length() != 0) {
256                a = a.monic();
257                if (a.isONE()) {
258                    P.clear();
259                    P.add(a);
260                    return P;
261                }
262                P.add(a);
263            }
264        }
265        int l = P.size();
266        if (l <= 1)
267            return P;
268
269        int irr = 0;
270        Word e;
271        Word f;
272        GenWordPolynomial<C> a;
273        logger.debug("irr = ");
274        while (irr != l) {
275            //it = P.listIterator(); 
276            //a = P.get(0); //it.next();
277            a = P.remove(0);
278            e = a.leadingWord();
279            a = normalform(P, a);
280            logger.debug(String.valueOf(irr));
281            if (a.length() == 0) {
282                l--;
283                if (l <= 1) {
284                    return P;
285                }
286            } else {
287                f = a.leadingWord();
288                if (f.signum() == 0) {
289                    P = new ArrayList<GenWordPolynomial<C>>();
290                    P.add(a.monic());
291                    return P;
292                }
293                if (e.equals(f)) {
294                    irr++;
295                } else {
296                    irr = 0;
297                    a = a.monic();
298                }
299                P.add(a);
300            }
301        }
302        //System.out.println();
303        return P;
304    }
305
306
307    /**
308     * Is reduction of normal form.
309     * @param lrow left recording matrix.
310     * @param rrow right recording matrix.
311     * @param Pp a polynomial list for reduction.
312     * @param Ap a polynomial.
313     * @param Np nf(Pp,Ap), a normal form of Ap wrt. Pp.
314     * @return true, if Np + sum( row[i]*Pp[i] ) == Ap, else false.
315     */
316    public boolean isReductionNF(List<GenWordPolynomial<C>> lrow, List<GenWordPolynomial<C>> rrow, 
317                                 List<GenWordPolynomial<C>> Pp, 
318                                 GenWordPolynomial<C> Ap, GenWordPolynomial<C> Np) {
319        if (lrow == null && rrow == null && Pp == null) {
320            if (Ap == null) {
321                return (Np == null);
322            }
323            return Ap.equals(Np);
324        }
325        if (lrow == null || rrow == null || Pp == null) {
326            return false;
327        }
328        if (lrow.size() != Pp.size() || rrow.size() != Pp.size()) {
329            return false;
330        }
331        GenWordPolynomial<C> t = Np;
332        //System.out.println("t0 = " + t );
333        GenWordPolynomial<C> r, rl, rr;
334        GenWordPolynomial<C> p;
335        for (int m = 0; m < Pp.size(); m++) {
336            rl = lrow.get(m);
337            rr = rrow.get(m);
338            p = Pp.get(m);
339            if (rl != null && rr != null && p != null) {
340                if (t == null) {
341                    t = p.multiply(rl,rr);
342                } else {
343                    t = t.sum(p.multiply(rl,rr));
344                }
345            }
346            //System.out.println("r = " + r );
347            //System.out.println("p = " + p );
348        }
349        //System.out.println("t+ = " + t );
350        if (t == null) {
351            if (Ap == null) {
352                return true;
353            }
354            return Ap.isZERO();
355        }
356        r = t.subtract(Ap);
357        boolean z = r.isZERO();
358        if (!z) {
359            logger.info("t = " + t);
360            logger.info("a = " + Ap);
361            logger.info("t-a = " + r);
362        }
363        return z;
364    }
365}