Source code

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