Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.gbufd;
006
007
008import java.util.List;
009import java.util.Map;
010
011import org.apache.logging.log4j.LogManager;
012import org.apache.logging.log4j.Logger;
013
014import edu.jas.gb.SolvableReductionAbstract;
015import edu.jas.poly.ExpVector;
016import edu.jas.poly.GenPolynomial;
017import edu.jas.poly.GenPolynomialRing;
018import edu.jas.poly.GenSolvablePolynomial;
019import edu.jas.poly.GenSolvablePolynomialRing;
020import edu.jas.poly.PolyUtil;
021import edu.jas.structure.GcdRingElem;
022
023
024/**
025 * Polynomial pseudo reduction sequential use algorithm. Coefficients of
026 * polynomials must not be from a field, i.e. the fraction free reduction is
027 * implemented. Implements normalform.
028 * @param <C> coefficient type
029 * @author Heinz Kredel
030 */
031
032public class SolvablePseudoReductionSeq<C extends GcdRingElem<C>> extends SolvableReductionAbstract<C>
033                implements SolvablePseudoReduction<C> {
034
035
036    private static final Logger logger = LogManager.getLogger(SolvablePseudoReductionSeq.class);
037
038
039    private static final boolean debug = logger.isDebugEnabled();
040
041
042    /**
043     * Constructor.
044     */
045    public SolvablePseudoReductionSeq() {
046    }
047
048
049    /**
050     * Left normalform.
051     * @param Ap polynomial.
052     * @param Pp polynomial list.
053     * @return nf(Ap) with respect to Pp.
054     */
055    @SuppressWarnings("unchecked")
056    public GenSolvablePolynomial<C> leftNormalform(List<GenSolvablePolynomial<C>> Pp,
057                    GenSolvablePolynomial<C> Ap) {
058        if (Pp == null || Pp.isEmpty()) {
059            return Ap;
060        }
061        if (Ap == null || Ap.isZERO()) {
062            return Ap;
063        }
064        Map.Entry<ExpVector, C> m;
065        GenSolvablePolynomial<C>[] P = new GenSolvablePolynomial[0];
066        synchronized (Pp) {
067            P = Pp.toArray(P);
068        }
069        int l = P.length;
070        ExpVector[] htl = new ExpVector[l];
071        //C[] lbc = (C[]) new GcdRingElem[l];
072        GenSolvablePolynomial<C>[] p = new GenSolvablePolynomial[l];
073        int i;
074        int j = 0;
075        for (i = 0; i < l; i++) {
076            if (P[i] == null) {
077                continue;
078            }
079            p[i] = P[i];
080            m = p[i].leadingMonomial();
081            if (m != null) {
082                p[j] = p[i];
083                htl[j] = m.getKey();
084                //lbc[j] = m.getValue();
085                j++;
086            }
087        }
088        l = j;
089        ExpVector e;
090        C a;
091        boolean mt = false;
092        GenSolvablePolynomial<C> R = Ap.ring.getZERO().copy();
093        GenSolvablePolynomial<C> Q = null;
094        GenSolvablePolynomial<C> S = Ap.copy();
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                //R = R.sum(a, e);
107                //S = S.subtract(a, e);
108                R.doPutToMap(e, a);
109                S.doRemoveFromMap(e, a);
110                //System.out.println(" S = " + S);
111            } else {
112                e = e.subtract(htl[i]);
113                //logger.info("red div = {}", e);
114                Q = p[i].multiplyLeft(e);
115                C c = Q.leadingBaseCoefficient();
116                ExpVector g = S.leadingExpVector();
117                C ap = a;
118                if (a.remainder(c).isZERO()) { // && !c.isConstant()) {
119                    a = a.divide(c);
120                    S = S.subtractMultiple(a, Q);
121                } else {
122                    R = R.multiplyLeft(c);
123                    S = S.scaleSubtractMultiple(c, a, Q);
124                }
125                ExpVector h = S.leadingExpVector();
126                if (g.equals(h)) { // Ore condition not fulfilled
127                    logger.info("g==h: g = {}, c = {}", g, c);
128                    throw new RuntimeException("g.equals(h): a = " + a + ", ap = " + ap + ", c = " + c);
129                }
130            }
131        }
132        return R;
133    }
134
135
136    /**
137     * Left normalform recursive.
138     * @param Ap recursive polynomial.
139     * @param Pp recursive polynomial list.
140     * @return nf(Ap) with respect to Pp.
141     */
142    @SuppressWarnings({ "unchecked" })
143    public GenSolvablePolynomial<GenPolynomial<C>> leftNormalformRecursive(
144                    List<GenSolvablePolynomial<GenPolynomial<C>>> Pp,
145                    GenSolvablePolynomial<GenPolynomial<C>> Ap) {
146        if (Pp == null || Pp.isEmpty()) {
147            return Ap;
148        }
149        if (Ap == null || Ap.isZERO()) {
150            return Ap;
151        }
152        Map.Entry<ExpVector, GenPolynomial<C>> m;
153        GenSolvablePolynomial<GenPolynomial<C>>[] P = new GenSolvablePolynomial[0];
154        synchronized (Pp) {
155            P = Pp.toArray(P);
156        }
157        int l = P.length;
158        ExpVector[] htl = new ExpVector[l];
159        //GenPolynomial<C>[] lbc = (GenPolynomial<C>[]) new GenPolynomial[l];
160        GenSolvablePolynomial<GenPolynomial<C>>[] p = new GenSolvablePolynomial[l];
161        int i;
162        int j = 0;
163        for (i = 0; i < l; i++) {
164            if (P[i] == null) {
165                continue;
166            }
167            p[i] = P[i];
168            m = p[i].leadingMonomial();
169            if (m != null) {
170                p[j] = p[i];
171                htl[j] = m.getKey();
172                //lbc[j] = m.getValue();
173                j++;
174            }
175        }
176        l = j;
177        ExpVector e, f;
178        GenPolynomial<C> a, b;
179        boolean mt = false;
180        GenSolvablePolynomialRing<GenPolynomial<C>> ring = Ap.ring;
181        final boolean commCoeff = ring.coFac.isCommutative();
182        final SolvableSyzygyAbstract<C> ssy;
183        if (commCoeff) {
184            ssy = null;
185        } else {
186            ssy = new SolvableSyzygySeq<C>(((GenPolynomialRing<C>) ring.coFac).coFac);
187        }
188        GenSolvablePolynomial<GenPolynomial<C>> R = Ap.ring.getZERO().copy();
189        GenSolvablePolynomial<GenPolynomial<C>> Q = null;
190        GenSolvablePolynomial<GenPolynomial<C>> S = Ap.copy();
191        //GenSolvablePolynomial<GenPolynomial<C>> Sp = null;
192        while (S.length() > 0) {
193            m = S.leadingMonomial();
194            e = m.getKey();
195            a = m.getValue();
196            for (i = 0; i < l; i++) {
197                mt = e.multipleOf(htl[i]);
198                if (mt)
199                    break;
200            }
201            if (!mt) {
202                //logger.debug("irred");
203                //R = R.sum(a, e);
204                //S = S.subtract(a, e);
205                R.doPutToMap(e, a);
206                S.doRemoveFromMap(e, a);
207                //System.out.println(" S = " + S);
208            } else {
209                f = e.subtract(htl[i]);
210                if (debug) {
211                    logger.info("red div = {}", f);
212                    //logger.info("red a = {}", a);
213                }
214                Q = p[i].multiplyLeft(f);
215                //if (a.remainder(c).isZERO()) { //c.isUnit() ) {
216                ExpVector g = S.leadingExpVector();
217                GenPolynomial<C> ap = a;
218                if (commCoeff) {
219                    GenPolynomial<C> c = Q.leadingBaseCoefficient();
220                    if (!c.isConstant() && PolyUtil.<C> baseSparsePseudoRemainder(a, c).isZERO()) {
221                        //a = a.divide(c);
222                        b = PolyUtil.<C> basePseudoDivide(a, c);
223                        if (a.equals(b.multiply(c))) {
224                            S = S.subtractMultiple(b, Q);
225                        } else {
226                            R = R.multiplyLeft(c);
227                            S = S.scaleSubtractMultiple(c, a, Q);
228                        }
229                    } else {
230                        R = R.multiplyLeft(c);
231                        S = S.scaleSubtractMultiple(c, a, Q);
232                    }
233                } else { // use Ore condition
234                    GenSolvablePolynomial<C> cs = (GenSolvablePolynomial<C>) Q.leadingBaseCoefficient();
235                    GenSolvablePolynomial<C> as = (GenSolvablePolynomial<C>) a;
236                    GenPolynomial<C>[] ore = ssy.leftOreCond(cs, as);
237                    //System.out.println("cs = " + cs + ", as = " + as);
238                    //System.out.println("ore[0] = " + ore[0] + "\nore[1] = " + ore[1]);
239                    R = R.multiplyLeft(ore[1]);
240                    S = S.scaleSubtractMultiple(ore[1], ore[0], Q);
241                }
242                ExpVector h = S.leadingExpVector();
243                if (g.equals(h)) { // ! Ore cond
244                    logger.info("g==h: g = {}", g);
245                    throw new RuntimeException("g.equals(h): a = " + a + ", ap = " + ap);
246                }
247            }
248        }
249        //System.out.println("Ap = " + Ap + ", R = " + R);
250        return R;
251    }
252
253
254    /**
255     * Left normalform with recording. <b>Note:</b> Only meaningful if all
256     * divisions are exact. Compute first the multiplication factor
257     * <code>mf</code> with <code>(nf,mf) = normalformfactor(Pp,Ap)</code>, then
258     * call this method with <code>normalform(row,Pp,mf*Ap)</code>.
259     * @param row recording matrix, is modified.
260     * @param Pp a polynomial list for reduction.
261     * @param Ap a polynomial.
262     * @return nf(Pp,Ap), the normal form of Ap wrt. Pp.
263     */
264    @SuppressWarnings("unchecked")
265    public GenSolvablePolynomial<C> leftNormalform(List<GenSolvablePolynomial<C>> row,
266                    List<GenSolvablePolynomial<C>> Pp, GenSolvablePolynomial<C> Ap) {
267        if (row == null || Pp == null || Ap == null) {
268            throw new IllegalArgumentException("row, Pp or Ap == null not supported");
269        }
270        if (Pp.isEmpty()) {
271            return Ap;
272        }
273        if (Ap.isZERO()) {
274            return Ap;
275        }
276        GenSolvablePolynomial<C>[] P = new GenSolvablePolynomial[0];
277        synchronized (Pp) {
278            P = Pp.toArray(P);
279        }
280        int l = P.length;
281        ExpVector[] htl = new ExpVector[l];
282        //C[] lbc = (C[]) new GcdRingElem[l];
283        GenSolvablePolynomial<C>[] p = new GenSolvablePolynomial[l];
284        Map.Entry<ExpVector, C> m;
285        int j = 0;
286        int i;
287        for (i = 0; i < l; i++) {
288            p[i] = P[i];
289            m = p[i].leadingMonomial();
290            if (m != null) {
291                p[j] = p[i];
292                htl[j] = m.getKey();
293                //lbc[j] = m.getValue();
294                j++;
295            }
296        }
297        l = j;
298        ExpVector e;
299        C a;
300        boolean mt = false;
301        GenSolvablePolynomial<C> zero = Ap.ring.getZERO();
302        GenSolvablePolynomial<C> R = Ap.ring.getZERO().copy();
303        GenSolvablePolynomial<C> Q = null;
304        GenSolvablePolynomial<C> fac = null;
305        GenSolvablePolynomial<C> S = Ap.copy();
306        while (S.length() > 0) {
307            m = S.leadingMonomial();
308            e = m.getKey();
309            a = m.getValue();
310            for (i = 0; i < l; i++) {
311                mt = e.multipleOf(htl[i]);
312                if (mt)
313                    break;
314            }
315            if (!mt) {
316                //logger.debug("irred");
317                //R = R.sum(a, e);
318                //S = S.subtract(a, e);
319                R.doPutToMap(e, a);
320                S.doRemoveFromMap(e, a);
321                // System.out.println(" S = " + S);
322                //throw new RuntimeException("Syzygy no GB");
323            } else {
324                e = e.subtract(htl[i]);
325                //logger.info("red div = {}", e);
326                Q = p[i].multiplyLeft(e);
327                C c = Q.leadingBaseCoefficient();
328                ExpVector g = S.leadingExpVector();
329                C ap = a;
330                if (a.remainder(c).isZERO()) { //c.isUnit() ) {
331                    a = a.divide(c);
332                    S = S.subtractMultiple(a, Q);
333                    //System.out.print("|");
334                } else {
335                    //System.out.print("*");
336                    R = R.multiplyLeft(c);
337                    S = S.scaleSubtractMultiple(c, a, Q);
338                }
339                ExpVector h = S.leadingExpVector();
340                if (g.equals(h)) { // Ore condition not fulfilled
341                    System.out.println("g = " + g + ", h = " + h);
342                    System.out.println("c*ap = " + c.multiply(ap) + ", ap*c = " + ap.multiply(c));
343                    throw new RuntimeException("g.equals(h): a = " + a + ", ap = " + ap + ", c = " + c);
344                }
345                //Q = p[i].multiply(a, e);
346                //S = S.subtract(Q);
347                fac = row.get(i);
348                if (fac == null) {
349                    fac = (GenSolvablePolynomial<C>) zero.sum(a, e);
350                } else { // doAddTo ??
351                    fac = (GenSolvablePolynomial<C>) fac.sum(a, e);
352                }
353                row.set(i, fac);
354            }
355        }
356        return R;
357    }
358
359
360    /**
361     * Left normalform with factor.
362     * @param Pp polynomial list.
363     * @param Ap polynomial.
364     * @return ( nf(Ap), mf ) with respect to Pp and mf as multiplication factor
365     *         for Ap.
366     */
367    @SuppressWarnings("unchecked")
368    public PseudoReductionEntry<C> leftNormalformFactor(List<GenSolvablePolynomial<C>> Pp,
369                    GenSolvablePolynomial<C> Ap) {
370        if (Ap == null) {
371            return null;
372        }
373        C mfactor = Ap.ring.getONECoefficient();
374        PseudoReductionEntry<C> pf = new PseudoReductionEntry<C>(Ap, mfactor);
375        if (Pp == null || Pp.isEmpty()) {
376            return pf;
377        }
378        if (Ap.isZERO()) {
379            return pf;
380        }
381        Map.Entry<ExpVector, C> m;
382        GenSolvablePolynomial<C>[] P = new GenSolvablePolynomial[0];
383        synchronized (Pp) {
384            P = Pp.toArray(P);
385        }
386        int l = P.length;
387        ExpVector[] htl = new ExpVector[l];
388        //C[] lbc = (C[]) new GcdRingElem[l]; 
389        GenSolvablePolynomial<C>[] p = new GenSolvablePolynomial[l];
390        int i;
391        int j = 0;
392        for (i = 0; i < l; i++) {
393            if (P[i] == null) {
394                continue;
395            }
396            p[i] = P[i];
397            m = p[i].leadingMonomial();
398            if (m != null) {
399                p[j] = p[i];
400                htl[j] = m.getKey();
401                //lbc[j] = m.getValue();
402                j++;
403            }
404        }
405        l = j;
406        ExpVector e;
407        C a;
408        boolean mt = false;
409        GenSolvablePolynomial<C> R = Ap.ring.getZERO().copy();
410        GenSolvablePolynomial<C> Q = null;
411        GenSolvablePolynomial<C> S = Ap.copy();
412        while (S.length() > 0) {
413            m = S.leadingMonomial();
414            e = m.getKey();
415            a = m.getValue();
416            for (i = 0; i < l; i++) {
417                mt = e.multipleOf(htl[i]);
418                if (mt)
419                    break;
420            }
421            if (!mt) {
422                //logger.debug("irred");
423                //R = R.sum(a, e);
424                //S = S.subtract(a, e);
425                R.doPutToMap(e, a);
426                S.doRemoveFromMap(e, a);
427                //System.out.println(" S = " + S);
428            } else {
429                e = e.subtract(htl[i]);
430                //logger.info("red div = {}", e);
431                Q = p[i].multiplyLeft(e);
432                C c = Q.leadingBaseCoefficient();
433                ExpVector g = S.leadingExpVector();
434                C ap = a;
435                if (a.remainder(c).isZERO()) {
436                    a = a.divide(c);
437                    S = S.subtractMultiple(a, Q);
438                } else {
439                    mfactor = c.multiply(mfactor); // left
440                    R = R.multiplyLeft(c);
441                    S = S.scaleSubtractMultiple(c, a, Q);
442                }
443                ExpVector h = S.leadingExpVector();
444                if (g.equals(h)) { // Ore condition not fulfilled
445                    logger.info("g==h: g = {}, c = {}", g, c);
446                    throw new RuntimeException("g==h: a = " + a + ", ap = " + ap);
447                }
448            }
449        }
450        logger.info("multiplicative factor = {}", mfactor);
451        pf = new PseudoReductionEntry<C>(R, mfactor);
452        return pf;
453    }
454
455
456    /**
457     * Right normalform.
458     * @param Ap polynomial.
459     * @param Pp polynomial list.
460     * @return nf(Ap) with respect to Pp.
461     */
462    @SuppressWarnings("unchecked")
463    public GenSolvablePolynomial<C> rightNormalform(List<GenSolvablePolynomial<C>> Pp,
464                    GenSolvablePolynomial<C> Ap) {
465        if (Pp == null || Pp.isEmpty()) {
466            return Ap;
467        }
468        if (Ap == null || Ap.isZERO()) {
469            return Ap;
470        }
471        Map.Entry<ExpVector, C> m;
472        GenSolvablePolynomial<C>[] P = new GenSolvablePolynomial[0];
473        synchronized (Pp) {
474            P = Pp.toArray(P);
475        }
476        int l = P.length;
477        ExpVector[] htl = new ExpVector[l];
478        //C[] lbc = (C[]) new GcdRingElem[l];
479        GenSolvablePolynomial<C>[] p = new GenSolvablePolynomial[l];
480        int i;
481        int j = 0;
482        for (i = 0; i < l; i++) {
483            if (P[i] == null) {
484                continue;
485            }
486            p[i] = P[i];
487            m = p[i].leadingMonomial();
488            if (m != null) {
489                p[j] = p[i];
490                htl[j] = m.getKey();
491                //lbc[j] = m.getValue();
492                j++;
493            }
494        }
495        l = j;
496        ExpVector e;
497        C a;
498        boolean mt = false;
499        GenSolvablePolynomial<C> R = Ap.ring.getZERO().copy();
500        GenSolvablePolynomial<C> Q = null;
501        GenSolvablePolynomial<C> S = Ap.copy();
502        while (S.length() > 0) {
503            m = S.leadingMonomial();
504            e = m.getKey();
505            a = m.getValue();
506            for (i = 0; i < l; i++) {
507                mt = e.multipleOf(htl[i]);
508                if (mt)
509                    break;
510            }
511            if (!mt) {
512                //logger.debug("irred");
513                //R = R.sum(a, e);
514                //S = S.subtract(a, e);
515                R.doPutToMap(e, a);
516                S.doRemoveFromMap(e, a);
517                //System.out.println(" S = " + S);
518            } else {
519                e = e.subtract(htl[i]);
520                //logger.info("red div = {}", e);
521                // need pi * a * e, but only pi * e * a or a * pi * e available
522                Q = p[i].multiply(e);
523                assert Q.multiply(a).equals(Q.multiplyLeft(a));
524                C c = Q.leadingBaseCoefficient();
525                ExpVector g = S.leadingExpVector();
526                C ap = a;
527                if (a.remainder(c).isZERO()) {
528                    a = a.divide(c); // left?
529                    //S = S.subtractMultiple(Q,a);
530                    S = (GenSolvablePolynomial<C>) S.subtract(Q.multiply(a));
531                } else {
532                    R = R.multiply(c);
533                    //S = S.scaleSubtractMultiple(c, Q, a);
534                    S = S.multiply(c);
535                    S = (GenSolvablePolynomial<C>) S.subtract(Q.multiply(a));
536                }
537                ExpVector h = S.leadingExpVector();
538                if (g.equals(h)) { // Ore condition not fulfilled
539                    logger.info("g==h: g = {}, c = {}", g, c);
540                    throw new RuntimeException("g.equals(h): a = " + a + ", ap = " + ap);
541                }
542            }
543        }
544        //System.out.println("R = " + R);
545        return R;
546    }
547
548
549    /**
550     * Right normalform recursive.
551     * @param Ap recursive polynomial.
552     * @param Pp recursive polynomial list.
553     * @return nf(Ap) with respect to Pp. <!--b>Note: not implemented;</b-->
554     */
555    @SuppressWarnings("unchecked")
556    public GenSolvablePolynomial<GenPolynomial<C>> rightNormalformRecursive(
557                    List<GenSolvablePolynomial<GenPolynomial<C>>> Pp,
558                    GenSolvablePolynomial<GenPolynomial<C>> Ap) {
559        if (Pp == null || Ap == null) {
560            throw new IllegalArgumentException("Pp or Ap == null not supported");
561        }
562        //throw new UnsupportedOperationException();
563        if (Pp.isEmpty()) {
564            return Ap;
565        }
566        if (Ap.isZERO()) {
567            return Ap;
568        }
569        Map.Entry<ExpVector, GenPolynomial<C>> m;
570        GenSolvablePolynomial<GenPolynomial<C>>[] P = new GenSolvablePolynomial[0];
571        synchronized (Pp) {
572            P = Pp.toArray(P);
573        }
574        int l = P.length;
575        ExpVector[] htl = new ExpVector[l];
576        //GenPolynomial<C>[] lbc = (GenPolynomial<C>[]) new GenPolynomial[l];
577        GenSolvablePolynomial<GenPolynomial<C>>[] p = new GenSolvablePolynomial[l];
578        int i;
579        int j = 0;
580        for (i = 0; i < l; i++) {
581            if (P[i] == null) {
582                continue;
583            }
584            p[i] = P[i];
585            m = p[i].leadingMonomial();
586            if (m != null) {
587                p[j] = p[i];
588                htl[j] = m.getKey();
589                //lbc[j] = m.getValue();
590                j++;
591            }
592        }
593        l = j;
594        ExpVector e, f;
595        GenPolynomial<C> a, b;
596        boolean mt = false;
597        GenSolvablePolynomialRing<GenPolynomial<C>> ring = Ap.ring;
598        final boolean commCoeff = ring.coFac.isCommutative();
599        final SolvableSyzygyAbstract<C> ssy;
600        if (commCoeff) {
601            ssy = null;
602        } else {
603            ssy = new SolvableSyzygySeq<C>(((GenPolynomialRing<C>) ring.coFac).coFac);
604        }
605        GenSolvablePolynomial<GenPolynomial<C>> R = Ap.ring.getZERO().copy();
606        GenSolvablePolynomial<GenPolynomial<C>> Q = null;
607        GenSolvablePolynomial<GenPolynomial<C>> S = Ap.copy();
608        //GenSolvablePolynomial<GenPolynomial<C>> Sp = null;
609        while (S.length() > 0) {
610            m = S.leadingMonomial();
611            e = m.getKey();
612            a = m.getValue();
613            for (i = 0; i < l; i++) {
614                mt = e.multipleOf(htl[i]);
615                if (mt)
616                    break;
617            }
618            if (!mt) {
619                //logger.debug("irred");
620                //R = R.sum(a, e);
621                //S = S.subtract(a, e);
622                R.doPutToMap(e, a);
623                S.doRemoveFromMap(e, a);
624                //System.out.println(" S = " + S);
625            } else {
626                f = e.subtract(htl[i]);
627                if (debug) {
628                    logger.info("red div = {}", f);
629                    //logger.info("red a = {}", a);
630                }
631                // need pi * a * e, but only pi * e * a or a * pi * e available
632                Q = p[i].multiply(f);
633                assert Q.multiply(a).equals(Q.multiplyLeft(a));
634                ExpVector g = S.leadingExpVector();
635                GenPolynomial<C> ap = a;
636                if (commCoeff) {
637                    GenPolynomial<C> c = Q.leadingBaseCoefficient();
638                    if (!c.isConstant() && PolyUtil.<C> baseSparsePseudoRemainder(a, c).isZERO()) {
639                        //a = a.divide(c);
640                        b = PolyUtil.<C> basePseudoDivide(a, c);
641                        if (a.equals(b.multiply(c))) {
642                            //S = S.subtractMultiple(b, Q);
643                            S = (GenSolvablePolynomial<GenPolynomial<C>>) S.subtract(Q.multiply(b));
644                        } else {
645                            R = R.multiply(c);
646                            //S = S.scaleSubtractMultiple(c, a, Q);
647                            S = S.multiply(c);
648                            S = (GenSolvablePolynomial<GenPolynomial<C>>) S.subtract(Q.multiply(a));
649                        }
650                    } else {
651                        R = R.multiply(c);
652                        //S = S.scaleSubtractMultiple(c, a, Q);
653                        S = S.multiply(c);
654                        S = (GenSolvablePolynomial<GenPolynomial<C>>) S.subtract(Q.multiply(a));
655                    }
656                } else { // use Ore condition
657                    GenSolvablePolynomial<C> cs = (GenSolvablePolynomial<C>) Q.leadingBaseCoefficient();
658                    GenSolvablePolynomial<C> as = (GenSolvablePolynomial<C>) a;
659                    GenPolynomial<C>[] ore = ssy.rightOreCond(cs, as);
660                    //System.out.println("cs = " + cs + ", as = " + as);
661                    //System.out.println("ore[0] = " + ore[0] + "\nore[1] = " + ore[1]);
662                    R = R.multiply(ore[1]);
663                    //S = S.scaleSubtractMultiple(ore[1], ore[0], Q);
664                    S = S.multiply(ore[1]);
665                    S = (GenSolvablePolynomial<GenPolynomial<C>>) S.subtract(Q.multiply(ore[0]));
666                }
667                ExpVector h = S.leadingExpVector();
668                if (g.equals(h)) { // Ore condition not fulfilled
669                    logger.info("not Ore: g==h: g = {}", g);
670                    throw new RuntimeException("g.equals(h): a = " + a + ", ap = " + ap);
671                }
672            }
673        }
674        //System.out.println("Ap = " + Ap + ", R = " + R);
675        return R;
676    }
677
678
679    /**
680     * Right normalform with recording. <b>Note:</b> Only meaningful if all
681     * divisions are exact. Compute first the multiplication factor
682     * <code>mf</code> with <code>(nf, mf) =
683     * normalformfactor(Pp,Ap)</code>, then call this method with
684     * <code>normalform(row,Pp,mf*Ap)</code>.
685     * @param row recording matrix, is modified.
686     * @param Pp a polynomial list for reduction.
687     * @param Ap a polynomial.
688     * @return nf(Pp,Ap), the normal form of Ap wrt. Pp. <!--b>Note: </b> not
689     *         implemented; </b-->
690     */
691    @SuppressWarnings("unchecked")
692    public GenSolvablePolynomial<C> rightNormalform(List<GenSolvablePolynomial<C>> row,
693                    List<GenSolvablePolynomial<C>> Pp, GenSolvablePolynomial<C> Ap) {
694        if (row == null || Pp == null || Ap == null) {
695            throw new IllegalArgumentException("row, Pp or Ap == null not supported");
696        }
697        //throw new UnsupportedOperationException();
698        if (Pp.isEmpty()) {
699            return Ap;
700        }
701        if (Ap.isZERO()) {
702            return Ap;
703        }
704        GenSolvablePolynomial<C>[] P = new GenSolvablePolynomial[0];
705        synchronized (Pp) {
706            P = Pp.toArray(P);
707        }
708        int l = P.length;
709        ExpVector[] htl = new ExpVector[l];
710        //C[] lbc = (C[]) new GcdRingElem[l];
711        GenSolvablePolynomial<C>[] p = new GenSolvablePolynomial[l];
712        Map.Entry<ExpVector, C> m;
713        int j = 0;
714        int i;
715        for (i = 0; i < l; i++) {
716            p[i] = P[i];
717            m = p[i].leadingMonomial();
718            if (m != null) {
719                p[j] = p[i];
720                htl[j] = m.getKey();
721                //lbc[j] = m.getValue();
722                j++;
723            }
724        }
725        l = j;
726        ExpVector e;
727        C a;
728        boolean mt = false;
729        GenSolvablePolynomial<C> zero = Ap.ring.getZERO();
730        GenSolvablePolynomial<C> R = Ap.ring.getZERO().copy();
731        GenSolvablePolynomial<C> Q = null;
732        GenSolvablePolynomial<C> fac = null;
733        GenSolvablePolynomial<C> S = Ap.copy();
734        while (S.length() > 0) {
735            m = S.leadingMonomial();
736            e = m.getKey();
737            a = m.getValue();
738            for (i = 0; i < l; i++) {
739                mt = e.multipleOf(htl[i]);
740                if (mt)
741                    break;
742            }
743            if (!mt) {
744                //logger.debug("irred");
745                //R = R.sum(a, e);
746                //S = S.subtract(a, e);
747                R.doPutToMap(e, a);
748                S.doRemoveFromMap(e, a);
749                // System.out.println(" S = " + S);
750                //throw new RuntimeException("Syzygy no GB");
751            } else {
752                e = e.subtract(htl[i]);
753                //logger.info("red div = {}", e);
754                Q = p[i].multiply(e);
755                assert Q.multiply(a).equals(Q.multiplyLeft(a));
756                C c = Q.leadingBaseCoefficient();
757                ExpVector g = S.leadingExpVector();
758                C ap = a;
759                if (a.remainder(c).isZERO()) { //c.isUnit() ) {
760                    a = a.divide(c);
761                    //S = S.subtractMultiple(a, Q);
762                    S = (GenSolvablePolynomial<C>) S.subtract(Q.multiply(a));
763                    //System.out.print("|");
764                } else {
765                    //System.out.print("*");
766                    R = R.multiply(c);
767                    //S = S.scaleSubtractMultiple(c, a, Q);
768                    S = S.multiply(c);
769                    S = (GenSolvablePolynomial<C>) S.subtract(Q.multiply(a));
770                }
771                ExpVector h = S.leadingExpVector();
772                if (g.equals(h)) { // Ore condition not fulfilled
773                    logger.info("no Ore: g==h: g = {}, c = {}", g, c);
774                    System.out.println("c*ap = " + c.multiply(ap) + ", ap*c = " + ap.multiply(c));
775                    throw new RuntimeException("g.equals(h): a = " + a + ", ap = " + ap + ", c = " + c);
776                }
777                //Q = p[i].multiply(a, e);
778                //S = S.subtract(Q);
779                fac = row.get(i);
780                if (fac == null) {
781                    fac = (GenSolvablePolynomial<C>) zero.sum(a, e);
782                } else { // doAddTo ??
783                    fac = (GenSolvablePolynomial<C>) fac.sum(a, e);
784                }
785                row.set(i, fac);
786            }
787        }
788        return R;
789    }
790
791
792    /**
793     * Right normalform with multiplication factor.
794     * @param Pp polynomial list.
795     * @param Ap polynomial.
796     * @return ( nf(Ap), mf ) with respect to Pp and mf as multiplication factor
797     *         for Ap. <!--b>Note: not implemented; </b-->
798     */
799    @SuppressWarnings("unchecked")
800    public PseudoReductionEntry<C> rightNormalformFactor(List<GenSolvablePolynomial<C>> Pp,
801                    GenSolvablePolynomial<C> Ap) {
802        //throw new UnsupportedOperationException();
803        if (Ap == null) {
804            throw new IllegalArgumentException("Ap == null not supported");
805            //return null;
806        }
807        C mfactor = Ap.ring.getONECoefficient();
808        PseudoReductionEntry<C> pf = new PseudoReductionEntry<C>(Ap, mfactor);
809        if (Pp == null || Pp.isEmpty()) {
810            return pf;
811        }
812        if (Ap.isZERO()) {
813            return pf;
814        }
815        Map.Entry<ExpVector, C> m;
816        GenSolvablePolynomial<C>[] P = new GenSolvablePolynomial[0];
817        synchronized (Pp) {
818            P = Pp.toArray(P);
819        }
820        int l = P.length;
821        ExpVector[] htl = new ExpVector[l];
822        //C[] lbc = (C[]) new GcdRingElem[l];
823        GenSolvablePolynomial<C>[] p = new GenSolvablePolynomial[l];
824        int i;
825        int j = 0;
826        for (i = 0; i < l; i++) {
827            if (P[i] == null) {
828                continue;
829            }
830            p[i] = P[i];
831            m = p[i].leadingMonomial();
832            if (m != null) {
833                p[j] = p[i];
834                htl[j] = m.getKey();
835                //lbc[j] = m.getValue();
836                j++;
837            }
838        }
839        l = j;
840        ExpVector e;
841        C a;
842        boolean mt = false;
843        GenSolvablePolynomial<C> R = Ap.ring.getZERO().copy();
844        GenSolvablePolynomial<C> Q = null;
845        GenSolvablePolynomial<C> S = Ap.copy();
846        while (S.length() > 0) {
847            m = S.leadingMonomial();
848            e = m.getKey();
849            a = m.getValue();
850            for (i = 0; i < l; i++) {
851                mt = e.multipleOf(htl[i]);
852                if (mt)
853                    break;
854            }
855            if (!mt) {
856                //logger.debug("irred");
857                //R = R.sum(a, e);
858                //S = S.subtract(a, e);
859                R.doPutToMap(e, a);
860                S.doRemoveFromMap(e, a);
861                //System.out.println(" S = " + S);
862            } else {
863                e = e.subtract(htl[i]);
864                //logger.info("red div = {}", e);
865                Q = p[i].multiply(e);
866                assert Q.multiply(a).equals(Q.multiplyLeft(a));
867                C c = Q.leadingBaseCoefficient();
868                ExpVector g = S.leadingExpVector();
869                C ap = a;
870                if (a.remainder(c).isZERO()) {
871                    a = a.divide(c);
872                    //S = S.subtractMultiple(a, Q);
873                    S = (GenSolvablePolynomial<C>) S.subtract(Q.multiply(a));
874                } else {
875                    mfactor = mfactor.multiply(c); // right
876                    R = R.multiply(c);
877                    //S = S.scaleSubtractMultiple(c, a, Q);
878                    S = S.multiply(c);
879                    S = (GenSolvablePolynomial<C>) S.subtract(Q.multiply(a));
880                }
881                ExpVector h = S.leadingExpVector();
882                if (g.equals(h)) { // Ore condition not fulfilled
883                    logger.info("no Ore: g==h: g = {}, c = {}", g, c);
884                    throw new RuntimeException("g==h: a = " + a + ", ap = " + ap);
885                }
886            }
887        }
888        logger.info("multiplicative factor = {}", mfactor);
889        pf = new PseudoReductionEntry<C>(R, mfactor);
890        return pf;
891    }
892
893}