001/*
002 * $Id: WordReductionSeq.java 5364 2015-12-26 12:36:37Z kredel $
003 */
004
005package edu.jas.gb;
006
007
008import java.util.ArrayList;
009import java.util.List;
010import java.util.Map;
011
012import org.apache.log4j.Logger;
013
014import edu.jas.poly.GenWordPolynomial;
015import edu.jas.poly.Word;
016import edu.jas.structure.RingElem;
017
018
019/**
020 * Polynomial word reduction sequential use algorithm. Implements normalform.
021 * @param <C> coefficient type
022 * @author Heinz Kredel
023 */
024
025public class WordReductionSeq<C extends RingElem<C>> // should be FieldElem<C>>
026                extends WordReductionAbstract<C> {
027
028
029    private static final Logger logger = Logger.getLogger(WordReductionSeq.class);
030
031
032    private static boolean debug = logger.isDebugEnabled();
033
034
035    /**
036     * Constructor.
037     */
038    public WordReductionSeq() {
039    }
040
041
042    /**
043     * Normalform.
044     * @param Ap polynomial.
045     * @param Pp polynomial list.
046     * @return nf(Ap) with respect to Pp.
047     */
048    @SuppressWarnings("unchecked")
049    public GenWordPolynomial<C> normalform(List<GenWordPolynomial<C>> Pp, GenWordPolynomial<C> Ap) {
050        if (Pp == null || Pp.isEmpty()) {
051            return Ap;
052        }
053        if (Ap == null || Ap.isZERO()) {
054            return Ap;
055        }
056        if (!Ap.ring.coFac.isField()) {
057            throw new IllegalArgumentException("coefficients not from a field");
058        }
059        Map.Entry<Word, C> m;
060        int l;
061        GenWordPolynomial<C>[] P;
062        synchronized (Pp) {
063            l = Pp.size();
064            P = new GenWordPolynomial[l];
065            //P = Pp.toArray();
066            for (int i = 0; i < Pp.size(); i++) {
067                P[i] = Pp.get(i);
068            }
069        }
070        Word[] htl = new Word[l];
071        C[] lbc = (C[]) new RingElem[l]; // want C[]
072        GenWordPolynomial<C>[] p = new GenWordPolynomial[l];
073        int i;
074        int j = 0;
075        for (i = 0; i < l; i++) {
076            p[i] = P[i];
077            m = p[i].leadingMonomial();
078            if (m != null) {
079                p[j] = p[i];
080                htl[j] = m.getKey();
081                lbc[j] = m.getValue();
082                j++;
083            }
084        }
085        l = j;
086        Word e, f, g;
087        C a;
088        boolean mt = false;
089        GenWordPolynomial<C> R = Ap.ring.getZERO();
090        C cone = Ap.ring.coFac.getONE();
091
092        //GenWordPolynomial<C> T = null;
093        GenWordPolynomial<C> Q = null;
094        GenWordPolynomial<C> S = Ap;
095        while (S.length() > 0) {
096            m = S.leadingMonomial();
097            e = m.getKey();
098            a = m.getValue();
099            for (i = 0; i < l; i++) {
100                mt = e.multipleOf(htl[i]);
101                if (mt)
102                    break;
103            }
104            if (!mt) {
105                //logger.debug("irred");
106                //T = new OrderedMapPolynomial( a, e );
107                R = R.sum(a, e);
108                S = S.subtract(a, e);
109                // System.out.println(" S = " + S);
110            } else {
111                Word[] elr = e.divideWord(htl[i]);
112                g = e;
113                e = elr[0];
114                f = elr[1];
115                if (debug) {
116                    logger.info("red divideWord: e = " + e + ", f = " + f);
117                }
118                a = a.divide(lbc[i]);
119                Q = p[i].multiply(a, e, cone, f);
120                S = S.subtract(Q);
121                if (!S.isZERO() && g.equals(S.leadingWord())) {
122                    throw new RuntimeException("HT(S) not descending");
123                }
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.isField()) {
148            throw new IllegalArgumentException("coefficients not from a field");
149        }
150        int l = Pp.size();
151        GenWordPolynomial<C>[] P = new GenWordPolynomial[l];
152        synchronized (Pp) {
153            //P = Pp.toArray();
154            for (int i = 0; i < Pp.size(); i++) {
155                P[i] = Pp.get(i);
156            }
157        }
158        Word[] htl = new Word[l];
159        C[] lbc = (C[]) new RingElem[l];
160        GenWordPolynomial<C>[] p = new GenWordPolynomial[l];
161        Map.Entry<Word, C> m;
162        int j = 0;
163        int i;
164        for (i = 0; i < l; i++) {
165            p[i] = P[i];
166            m = p[i].leadingMonomial();
167            if (m != null) {
168                p[j] = p[i];
169                htl[j] = m.getKey();
170                lbc[j] = m.getValue();
171                j++;
172            }
173        }
174        l = j;
175        Word e, g;
176        C a, b, lc, rc;
177        boolean mt = false;
178        GenWordPolynomial<C> zero = Ap.ring.getZERO();
179        GenWordPolynomial<C> one = Ap.ring.getONE();
180        GenWordPolynomial<C> R = Ap.ring.getZERO();
181        C cone = Ap.ring.coFac.getONE();
182        // ensure polynomials at each index
183        for (i = 0; i < lrow.size(); i++) {
184            GenWordPolynomial<C> w = lrow.get(i);
185            if (w == null) {
186                lrow.set(i, zero);
187            }
188            w = rrow.get(i);
189            if (w == null) {
190                rrow.set(i, zero);
191            }
192        }
193
194        GenWordPolynomial<C> fac = null;
195        // GenWordPolynomial<C> T = null;
196        GenWordPolynomial<C> Q = null;
197        GenWordPolynomial<C> S = Ap;
198        while (S.length() > 0) {
199            m = S.leadingMonomial();
200            e = m.getKey();
201            a = m.getValue();
202            for (i = 0; i < l; i++) {
203                mt = e.multipleOf(htl[i]);
204                if (mt)
205                    break;
206            }
207            if (!mt) {
208                //logger.debug("irred");
209                R = R.sum(a, e);
210                S = S.subtract(a, e);
211                // System.out.println("S = " + S);
212            } else {
213                g = e;
214                Word[] elr = e.divideWord(htl[i]);
215                e = elr[0];
216                Word f = elr[1];
217                if (debug) {
218                    logger.info("redRec divideWord: e = " + e + ", f = " + f + ", htl = " + htl[i]);
219                }
220                C c = lbc[i];
221                b = a.divide(c);
222                if (e.isONE()) { // TODO
223                    lc = cone;
224                    rc = b;
225                } else {
226                    lc = b;
227                    rc = cone;
228                }
229                Q = p[i].multiply(lc, e, rc, f);
230                S = S.subtract(Q);
231                //logger.info("redRec: S = " + S + ", R = " + R + ", Q = " + Q);
232                if (!S.isZERO() && g.equals(S.leadingWord())) {
233                    System.out.println("divideWord: e = " + e + ", f = " + f);
234                    System.out.println("R = " + R);
235                    System.out.println("Q = " + Q + ", a = " + a + ", b = " + b + ", c = " + c);
236                    throw new RuntimeException("HT(S) not descending, S = " + S);
237                }
238                // left row
239                fac = lrow.get(i);
240                boolean doset = true;
241                if (!lc.isONE() || !e.isONE()) {
242                    if (!fac.coefficient(e).isZERO()) {
243                        logger.warn("e exists in polynomial: " + fac + ", e = " + e + ", lc = " + lc);
244                        logger.warn("f = " + f + ", rc = " + rc);
245                        logger.warn("S = " + S + ", R = " + R);
246                    }
247                    fac = fac.sum(lc, e);
248                    doset = false;
249                }
250                //logger.info("redRec: left = " + fac + ", lc = " + lc + ", e = " + e);
251                lrow.set(i, fac);
252                // right row
253                fac = rrow.get(i);
254                if (!rc.isONE() || !f.isONE() || doset) {
255                    if (!fac.coefficient(f).isZERO()) {
256                        logger.warn("f exists in polynomial: " + fac + ", f = " + f + ", rc = " + rc);
257                        logger.warn("e = " + e + ", lc = " + lc);
258                        logger.warn("S = " + S + ", R = " + R);
259                    }
260                    fac = fac.sum(rc, f);
261                }
262                //logger.info("redRec: right = " + fac + ", rc = " + rc + ", f = " + f);
263                rrow.set(i, fac);
264            }
265        }
266        // set factor to one if other non-zero
267        for (i = 0; i < lrow.size(); i++) {
268            GenWordPolynomial<C> lw = lrow.get(i);
269            GenWordPolynomial<C> rw = rrow.get(i);
270            if (!lw.isZERO() && rw.isZERO()) {
271                rrow.set(i, one);
272            }
273            if (lw.isZERO() && !rw.isZERO()) {
274                lrow.set(i, one);
275            }
276        }
277        return R;
278    }
279
280
281    /**
282     * Left normalform with recording.
283     * @param Pp a polynomial list for reduction.
284     * @param Ap a polynomial.
285     * @return nf(Pp,Ap), the left normal form of Ap wrt. Pp.
286     */
287    public GenWordPolynomial<C> leftNormalform(List<GenWordPolynomial<C>> Pp, GenWordPolynomial<C> Ap) {
288        if (Pp == null || Pp.isEmpty()) {
289            return Ap;
290        }
291        if (Ap == null || Ap.isZERO()) {
292            return Ap;
293        }
294        List<GenWordPolynomial<C>> lrow = new ArrayList<GenWordPolynomial<C>>(Pp.size());
295        for (int i = 0; i < Pp.size(); i++) {
296            lrow.add(Ap.ring.getZERO());
297        }
298        GenWordPolynomial<C> r = leftNormalform(lrow, Pp, Ap);
299        return r;
300    }
301
302
303    /**
304     * Left normalform with recording.
305     * @param lrow left recording matrix, is modified.
306     * @param Pp a polynomial list for reduction.
307     * @param Ap a polynomial.
308     * @return nf(Pp,Ap), the left normal form of Ap wrt. Pp.
309     */
310    @SuppressWarnings("unchecked")
311    public GenWordPolynomial<C> leftNormalform(List<GenWordPolynomial<C>> lrow,
312                    List<GenWordPolynomial<C>> Pp, GenWordPolynomial<C> Ap) {
313        if (Pp == null || Pp.isEmpty()) {
314            return Ap;
315        }
316        if (Ap == null || Ap.isZERO()) {
317            return Ap;
318        }
319        if (!Ap.ring.coFac.isField()) {
320            throw new IllegalArgumentException("coefficients not from a field");
321        }
322        int l = Pp.size();
323        GenWordPolynomial<C>[] P = new GenWordPolynomial[l];
324        synchronized (Pp) {
325            //P = Pp.toArray();
326            for (int i = 0; i < Pp.size(); i++) {
327                P[i] = Pp.get(i);
328            }
329        }
330        Word[] htl = new Word[l];
331        C[] lbc = (C[]) new RingElem[l]; // want C[]
332        GenWordPolynomial<C>[] p = new GenWordPolynomial[l];
333        Map.Entry<Word, C> m;
334        int j = 0;
335        int i;
336        for (i = 0; i < l; i++) {
337            p[i] = P[i];
338            m = p[i].leadingMonomial();
339            if (m != null) {
340                p[j] = p[i];
341                htl[j] = m.getKey();
342                lbc[j] = m.getValue();
343                j++;
344            }
345        }
346        l = j;
347        Word e;
348        C a;
349        boolean mt = false;
350        GenWordPolynomial<C> zero = Ap.ring.getZERO();
351        GenWordPolynomial<C> R = Ap.ring.getZERO();
352        C cone = Ap.ring.coFac.getONE();
353
354        GenWordPolynomial<C> fac = null;
355        // GenWordPolynomial<C> T = null;
356        GenWordPolynomial<C> Q = null;
357        GenWordPolynomial<C> S = Ap;
358        while (S.length() > 0) {
359            m = S.leadingMonomial();
360            e = m.getKey();
361            a = m.getValue();
362            for (i = 0; i < l; i++) {
363                mt = e.multipleOf(htl[i]);
364                if (mt)
365                    break;
366            }
367            if (!mt) {
368                //logger.info("irred_1");
369                R = R.sum(a, e);
370                S = S.subtract(a, e);
371                // System.out.println(" S = " + S);
372            } else {
373                Word g = e;
374                Word[] elr = e.divideWord(htl[i]);
375                e = elr[0];
376                Word f = elr[1];
377                if (debug) {
378                    logger.info("redRec divideWord: e = " + e + ", f = " + f);
379                }
380                if (f.isONE()) {
381                    C c = lbc[i];
382                    //System.out.println("a = " + a + ", c = " + c);
383                    a = a.divide(c);
384                    //System.out.println("a/c = " + a);
385                    Q = p[i].multiply(a, e, cone, f);
386                    S = S.subtract(Q);
387                    // left row
388                    fac = lrow.get(i);
389                    if (fac == null) {
390                        fac = zero.sum(a, e);
391                    } else {
392                        fac = fac.sum(a, e);
393                    }
394                    lrow.set(i, fac);
395                } else {
396                    //logger.info("irred_2");
397                    R = R.sum(a, g);
398                    S = S.subtract(a, g);
399                }
400            }
401        }
402        return R;
403    }
404
405
406    /**
407     * Right normalform with recording.
408     * @param Pp a polynomial list for reduction.
409     * @param Ap a polynomial.
410     * @return nf(Pp,Ap), the right normal form of Ap wrt. Pp.
411     */
412    public GenWordPolynomial<C> rightNormalform(List<GenWordPolynomial<C>> Pp, GenWordPolynomial<C> Ap) {
413        if (Pp == null || Pp.isEmpty()) {
414            return Ap;
415        }
416        if (Ap == null || Ap.isZERO()) {
417            return Ap;
418        }
419        List<GenWordPolynomial<C>> lrow = new ArrayList<GenWordPolynomial<C>>(Pp.size());
420        for (int i = 0; i < Pp.size(); i++) {
421            lrow.add(Ap.ring.getZERO());
422        }
423        GenWordPolynomial<C> r = rightNormalform(lrow, Pp, Ap);
424        return r;
425    }
426
427
428    /**
429     * Right normalform with recording.
430     * @param rrow right recording matrix, is modified.
431     * @param Pp a polynomial list for reduction.
432     * @param Ap a polynomial.
433     * @return nf(Pp,Ap), the right normal form of Ap wrt. Pp.
434     */
435    @SuppressWarnings("unchecked")
436    public GenWordPolynomial<C> rightNormalform(List<GenWordPolynomial<C>> rrow,
437                    List<GenWordPolynomial<C>> Pp, GenWordPolynomial<C> Ap) {
438        if (Pp == null || Pp.isEmpty()) {
439            return Ap;
440        }
441        if (Ap == null || Ap.isZERO()) {
442            return Ap;
443        }
444        if (!Ap.ring.coFac.isField()) {
445            throw new IllegalArgumentException("coefficients not from a field");
446        }
447        int l = Pp.size();
448        GenWordPolynomial<C>[] P = new GenWordPolynomial[l];
449        synchronized (Pp) {
450            //P = Pp.toArray();
451            for (int i = 0; i < Pp.size(); i++) {
452                P[i] = Pp.get(i);
453            }
454        }
455        Word[] htl = new Word[l];
456        C[] lbc = (C[]) new RingElem[l]; // want C[]
457        GenWordPolynomial<C>[] p = new GenWordPolynomial[l];
458        Map.Entry<Word, C> m;
459        int j = 0;
460        int i;
461        for (i = 0; i < l; i++) {
462            p[i] = P[i];
463            m = p[i].leadingMonomial();
464            if (m != null) {
465                p[j] = p[i];
466                htl[j] = m.getKey();
467                lbc[j] = m.getValue();
468                j++;
469            }
470        }
471        l = j;
472        Word e;
473        C a;
474        boolean mt = false;
475        GenWordPolynomial<C> zero = Ap.ring.getZERO();
476        GenWordPolynomial<C> R = Ap.ring.getZERO();
477        C cone = Ap.ring.coFac.getONE();
478
479        GenWordPolynomial<C> fac = null;
480        // GenWordPolynomial<C> T = null;
481        GenWordPolynomial<C> Q = null;
482        GenWordPolynomial<C> S = Ap;
483        while (S.length() > 0) {
484            m = S.leadingMonomial();
485            e = m.getKey();
486            a = m.getValue();
487            for (i = 0; i < l; i++) {
488                mt = e.multipleOf(htl[i]);
489                if (mt)
490                    break;
491            }
492            if (!mt) {
493                //logger.info("irred_1");
494                R = R.sum(a, e);
495                S = S.subtract(a, e);
496                // System.out.println(" S = " + S);
497            } else {
498                Word g = e;
499                Word[] elr = e.divideWord(htl[i]);
500                e = elr[0];
501                Word f = elr[1];
502                if (debug) {
503                    logger.info("redRec divideWord: e = " + e + ", f = " + f);
504                }
505                if (e.isONE()) {
506                    C c = lbc[i];
507                    //System.out.println("a = " + a + ", c = " + c);
508                    a = a.divide(c);
509                    //System.out.println("a/c = " + a);
510                    Q = p[i].multiply(cone, e, a, f);
511                    S = S.subtract(Q);
512                    // left row
513                    fac = rrow.get(i);
514                    if (fac == null) {
515                        fac = zero.sum(a, f);
516                    } else {
517                        fac = fac.sum(a, f);
518                    }
519                    rrow.set(i, fac);
520                } else {
521                    //logger.info("irred_2");
522                    R = R.sum(a, g);
523                    S = S.subtract(a, g);
524                }
525            }
526        }
527        return R;
528    }
529
530}