Source code

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