Source code

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