Source code

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