Source code

001/*
002 * $Id: WordPseudoReductionSeq.java 5303 2015-08-16 17:11:07Z kredel $
003 */
004
005package edu.jas.gbufd;
006
007
008import java.util.List;
009import java.util.Map;
010
011import org.apache.log4j.Logger;
012
013import edu.jas.gb.WordReductionAbstract;
014import edu.jas.poly.GenPolynomial;
015import edu.jas.poly.GenWordPolynomial;
016import edu.jas.poly.PolyUtil;
017import edu.jas.poly.Word;
018import edu.jas.structure.RingElem;
019
020
021/**
022 * Polynomial word reduction sequential use algorithm. Implements normalform.
023 * @param <C> coefficient type
024 * @author Heinz Kredel
025 */
026
027public class WordPseudoReductionSeq<C extends RingElem<C>> extends WordReductionAbstract<C> implements
028                WordPseudoReduction<C> {
029
030
031    private static final Logger logger = Logger.getLogger(WordPseudoReductionSeq.class);
032
033
034    private static boolean debug = logger.isDebugEnabled();
035
036
037    /**
038     * Constructor.
039     */
040    public WordPseudoReductionSeq() {
041    }
042
043
044    /**
045     * Normalform.
046     * @param Ap polynomial.
047     * @param Pp polynomial list.
048     * @return nf(Ap) with respect to Pp.
049     */
050    //@SuppressWarnings("unchecked")
051    public GenWordPolynomial<C> normalform(List<GenWordPolynomial<C>> Pp, GenWordPolynomial<C> Ap) {
052        if (Pp == null || Pp.isEmpty()) {
053            return Ap;
054        }
055        if (Ap == null || Ap.isZERO()) {
056            return Ap;
057        }
058        if (!Ap.ring.coFac.isCommutative()) {
059            throw new IllegalArgumentException("coefficient ring not commutative");
060        }
061        Map.Entry<Word, C> m;
062        GenWordPolynomial<C>[] P = new GenWordPolynomial[0];
063        synchronized (Pp) {
064            P = Pp.toArray(P);
065        }
066        int l = P.length;
067        Word[] htl = new Word[l];
068        C[] lbc = (C[]) new RingElem[l];
069        GenWordPolynomial<C>[] p = new GenWordPolynomial[l];
070        int i;
071        int j = 0;
072        for (i = 0; i < l; i++) {
073            p[i] = P[i];
074            m = p[i].leadingMonomial();
075            if (m != null) {
076                p[j] = p[i];
077                htl[j] = m.getKey();
078                lbc[j] = m.getValue();
079                j++;
080            }
081        }
082        l = j;
083        Word e;
084        C a;
085        boolean mt = false;
086        GenWordPolynomial<C> R = Ap.ring.getZERO().copy();
087        C cone = Ap.ring.coFac.getONE();
088        GenWordPolynomial<C> Q = null;
089        GenWordPolynomial<C> S = Ap.copy();
090        while (S.length() > 0) {
091            m = S.leadingMonomial();
092            e = m.getKey();
093            a = m.getValue();
094            for (i = 0; i < l; i++) {
095                mt = e.multipleOf(htl[i]);
096                if (mt)
097                    break;
098            }
099            if (!mt) {
100                //logger.debug("irred");
101                //R = R.sum(a, e);
102                //S = S.subtract(a, e);
103                R.doPutToMap(e, a);
104                S.doRemoveFromMap(e, a);
105                // System.out.println(" S = " + S);
106            } else {
107                Word[] elr = e.divideWord(htl[i]);
108                e = elr[0];
109                Word f = elr[1];
110                if (debug) {
111                    logger.info("red divideWord: e = " + e + ", f = " + f);
112                }
113                C c = lbc[i];
114                if (a.remainder(c).isZERO()) {
115                    a = a.divide(c);
116                    Q = p[i].multiply(a, e, cone, f);
117                } else {
118                    R = R.multiply(c);
119                    S = S.multiply(c);
120                    Q = p[i].multiply(a, e, cone, f);
121                }
122                S = S.subtract(Q);
123            }
124        }
125        return R;
126    }
127
128
129    /**
130     * Normalform with left and right recording.
131     * @param lrow left recording matrix, is modified.
132     * @param rrow right recording matrix, is modified.
133     * @param Pp a polynomial list for reduction.
134     * @param Ap a polynomial.
135     * @return nf(Pp,Ap), the normal form of Ap wrt. Pp.
136     */
137    //@SuppressWarnings("unchecked")
138    public GenWordPolynomial<C> normalform(List<GenWordPolynomial<C>> lrow, List<GenWordPolynomial<C>> rrow,
139                    List<GenWordPolynomial<C>> Pp, GenWordPolynomial<C> Ap) {
140        if (Pp == null || Pp.isEmpty()) {
141            return Ap;
142        }
143        if (Ap == null || Ap.isZERO()) {
144            return Ap;
145        }
146        if (!Ap.ring.coFac.isCommutative()) {
147            throw new IllegalArgumentException("coefficient ring not commutative");
148        }
149        GenWordPolynomial<C>[] P = new GenWordPolynomial[0];
150        synchronized (Pp) {
151            P = Pp.toArray(P);
152        }
153        int l = P.length;
154        Word[] htl = new Word[l];
155        C[] lbc = (C[]) new RingElem[l];
156        GenWordPolynomial<C>[] p = new GenWordPolynomial[l];
157        Map.Entry<Word, C> m;
158        int j = 0;
159        int i;
160        for (i = 0; i < l; i++) {
161            p[i] = P[i];
162            m = p[i].leadingMonomial();
163            if (m != null) {
164                p[j] = p[i];
165                htl[j] = m.getKey();
166                lbc[j] = m.getValue();
167                j++;
168            }
169        }
170        l = j;
171        Word e;
172        C a;
173        boolean mt = false;
174        GenWordPolynomial<C> zero = Ap.ring.getZERO().copy();
175        GenWordPolynomial<C> R = Ap.ring.getZERO();
176        C cone = Ap.ring.coFac.getONE();
177        GenWordPolynomial<C> fac = null;
178        GenWordPolynomial<C> Q = null;
179        GenWordPolynomial<C> S = Ap.copy();
180        while (S.length() > 0) {
181            m = S.leadingMonomial();
182            e = m.getKey();
183            a = m.getValue();
184            for (i = 0; i < l; i++) {
185                mt = e.multipleOf(htl[i]);
186                if (mt)
187                    break;
188            }
189            if (!mt) {
190                //logger.debug("irred");
191                //R = R.sum(a, e);
192                //S = S.subtract(a, e);
193                R.doPutToMap(e, a);
194                S.doRemoveFromMap(e, a);
195                // System.out.println(" S = " + S);
196            } else {
197                Word[] elr = e.divideWord(htl[i]);
198                e = elr[0];
199                Word f = elr[1];
200                if (debug) {
201                    logger.info("redRec divideWord: e = " + e + ", f = " + f);
202                }
203                C c = lbc[i];
204                if (a.remainder(c).isZERO()) {
205                    a = a.divide(c);
206                    Q = p[i].multiply(a, e, cone, f);
207                } else {
208                    R = R.multiply(c);
209                    S = S.multiply(c);
210                    Q = p[i].multiply(a, e, cone, f);
211                }
212                S = S.subtract(Q);
213                // left row
214                fac = lrow.get(i);
215                if (fac == null) {
216                    fac = zero.sum(cone, e);
217                } else {
218                    fac = fac.sum(cone, e);
219                }
220                lrow.set(i, fac);
221                // right row
222                fac = rrow.get(i);
223                if (fac == null) {
224                    fac = zero.sum(a, f);
225                } else {
226                    fac = fac.sum(a, f);
227                }
228                rrow.set(i, fac);
229            }
230        }
231        return R;
232    }
233
234
235    /**
236     * Normalform with multiplication factor.
237     * @param Pp polynomial list.
238     * @param Ap polynomial.
239     * @return ( nf(Ap), mf ) with respect to Pp and mf as multiplication factor
240     *         for Ap.
241     */
242    public WordPseudoReductionEntry<C> normalformFactor(List<GenWordPolynomial<C>> Pp, GenWordPolynomial<C> Ap) {
243        throw new UnsupportedOperationException("normalformFactor not imlemented");
244    }
245
246
247    /**
248     * Normalform with polynomial coefficients.
249     * @param Ap polynomial.
250     * @param Pp polynomial list.
251     * @return nf(Ap) with respect to Pp.
252     */
253    //@SuppressWarnings("unchecked")
254    public GenWordPolynomial<GenPolynomial<C>> normalformRecursive(
255                    List<GenWordPolynomial<GenPolynomial<C>>> Pp, GenWordPolynomial<GenPolynomial<C>> Ap) {
256        if (Pp == null || Pp.isEmpty()) {
257            return Ap;
258        }
259        if (Ap == null || Ap.isZERO()) {
260            return Ap;
261        }
262        if (!Ap.ring.coFac.isCommutative()) {
263            throw new IllegalArgumentException("coefficient ring not commutative");
264        }
265        Map.Entry<Word, GenPolynomial<C>> m;
266        GenWordPolynomial<GenPolynomial<C>>[] P = new GenWordPolynomial[0];
267        synchronized (Pp) {
268            P = Pp.toArray(P);
269        }
270        int l = P.length;
271        Word[] htl = new Word[l];
272        GenPolynomial<C>[] lbc = new GenPolynomial[l]; //(GenPolynomial<C>[]) 
273        GenWordPolynomial<GenPolynomial<C>>[] p = new GenWordPolynomial[l];
274        int i;
275        int j = 0;
276        for (i = 0; i < l; i++) {
277            p[i] = P[i];
278            m = p[i].leadingMonomial();
279            if (m != null) {
280                p[j] = p[i];
281                htl[j] = m.getKey();
282                lbc[j] = m.getValue();
283                j++;
284            }
285        }
286        l = j;
287        Word e, fr, fl;
288        GenPolynomial<C> a, b = null;
289        boolean mt = false;
290        GenWordPolynomial<GenPolynomial<C>> R = Ap.ring.getZERO().copy();
291        GenPolynomial<C> cone = Ap.ring.coFac.getONE();
292        GenWordPolynomial<GenPolynomial<C>> Q = null;
293        GenWordPolynomial<GenPolynomial<C>> S = Ap.copy();
294        GenWordPolynomial<GenPolynomial<C>> Sp;
295        while (S.length() > 0) {
296            m = S.leadingMonomial();
297            e = m.getKey();
298            a = m.getValue();
299            for (i = 0; i < l; i++) {
300                mt = e.multipleOf(htl[i]);
301                if (mt)
302                    break;
303            }
304            if (!mt) {
305                //logger.debug("irred");
306                //R = R.sum(a, e);
307                //S = S.subtract(a, e);
308                R.doPutToMap(e, a);
309                S.doRemoveFromMap(e, a);
310                // System.out.println(" S = " + S);
311            } else {
312                Word[] elr = e.divideWord(htl[i]);
313                fl = elr[0];
314                fr = elr[1];
315                if (debug) {
316                    logger.info("redRec divideWord: e = " + e + ", fl = " + fl + ", fr = " + fr);
317                }
318                GenPolynomial<C> c = lbc[i];
319                if (PolyUtil.<C> baseSparsePseudoRemainder(a, c).isZERO()) {
320                    b = PolyUtil.<C> basePseudoDivide(a, c);
321                    Q = p[i].multiply(b, fl, cone, fr);
322                } else {
323                    R = R.multiply(c);
324                    S = S.multiply(c);
325                    Q = p[i].multiply(a, fl, cone, fr);
326                }
327                Sp = S.subtract(Q);
328                if (e.equals(Sp.leadingWord())) { // TODO: avoid not possible in general
329                    //logger.info("redRec: e = " + e + ", hti = " + htl[i] + ", fl = " + fl + ", fr = " + fr);
330                    //logger.info("redRec: S = " + S + ", Sp = " + Sp + ", a = " + a + ", b = " + b + ", c = " + c);
331                    //throw new RuntimeException("degree not descending");
332                    R = R.multiply(c);
333                    S = S.multiply(c);
334                    Q = p[i].multiply(a, fl, cone, fr);
335                    Sp = S.subtract(Q);
336                }
337                S = Sp;
338            }
339        }
340        return R;
341    }
342
343
344    @Override
345    public GenWordPolynomial<C> leftNormalform(List<GenWordPolynomial<C>> Pp, GenWordPolynomial<C> Ap) {
346        throw new UnsupportedOperationException("leftNormalform not imlemented");
347    }
348
349
350    @Override
351    public GenWordPolynomial<C> leftNormalform(List<GenWordPolynomial<C>> lrow,
352                    List<GenWordPolynomial<C>> Pp, GenWordPolynomial<C> Ap) {
353        throw new UnsupportedOperationException("leftNormalform not imlemented");
354    }
355
356
357    @Override
358    public GenWordPolynomial<C> rightNormalform(List<GenWordPolynomial<C>> Pp, GenWordPolynomial<C> Ap) {
359        throw new UnsupportedOperationException("rightNormalform not imlemented");
360    }
361
362
363    @Override
364    public GenWordPolynomial<C> rightNormalform(List<GenWordPolynomial<C>> rrow,
365                    List<GenWordPolynomial<C>> Pp, GenWordPolynomial<C> Ap) {
366        throw new UnsupportedOperationException("rightNormalform not imlemented");
367    }
368
369}