001/*
002 * $Id: RecSolvablePolynomial.java 5226 2015-04-19 10:16:29Z kredel $
003 */
004
005package edu.jas.poly;
006
007
008import java.util.Map;
009import java.util.Set;
010import java.util.SortedMap;
011
012import org.apache.log4j.Logger;
013
014import edu.jas.structure.RingElem;
015
016
017/**
018 * RecSolvablePolynomial generic recursive solvable polynomials implementing
019 * RingElem. n-variate ordered solvable polynomials over solvable polynomial
020 * coefficients. Objects of this class are intended to be immutable. The
021 * implementation is based on TreeMap respectively SortedMap from exponents to
022 * coefficients by extension of GenPolynomial.
023 * @param <C> coefficient type
024 * @author Heinz Kredel
025 */
026
027public class RecSolvablePolynomial<C extends RingElem<C>> extends GenSolvablePolynomial<GenPolynomial<C>> {
028
029
030    /**
031     * The factory for the recursive solvable polynomial ring. Hides super.ring.
032     */
033    public final RecSolvablePolynomialRing<C> ring;
034
035
036    private static final Logger logger = Logger.getLogger(RecSolvablePolynomial.class);
037
038
039    private final boolean debug = logger.isDebugEnabled();
040
041
042    /**
043     * Constructor for zero RecSolvablePolynomial.
044     * @param r solvable polynomial ring factory.
045     */
046    public RecSolvablePolynomial(RecSolvablePolynomialRing<C> r) {
047        super(r);
048        ring = r;
049    }
050
051
052    /**
053     * Constructor for RecSolvablePolynomial.
054     * @param r solvable polynomial ring factory.
055     * @param e exponent.
056     */
057    public RecSolvablePolynomial(RecSolvablePolynomialRing<C> r, ExpVector e) {
058        this(r);
059        val.put(e, ring.getONECoefficient());
060    }
061
062
063    /**
064     * Constructor for RecSolvablePolynomial.
065     * @param r solvable polynomial ring factory.
066     * @param c coefficient polynomial.
067     * @param e exponent.
068     */
069    public RecSolvablePolynomial(RecSolvablePolynomialRing<C> r, GenPolynomial<C> c, ExpVector e) {
070        this(r);
071        if (c != null && !c.isZERO()) {
072            val.put(e, c);
073        }
074    }
075
076
077    /**
078     * Constructor for RecSolvablePolynomial.
079     * @param r solvable polynomial ring factory.
080     * @param c coefficient polynomial.
081     */
082    public RecSolvablePolynomial(RecSolvablePolynomialRing<C> r, GenPolynomial<C> c) {
083        this(r, c, r.evzero);
084    }
085
086
087    /**
088     * Constructor for RecSolvablePolynomial.
089     * @param r solvable polynomial ring factory.
090     * @param S solvable polynomial.
091     */
092    public RecSolvablePolynomial(RecSolvablePolynomialRing<C> r, GenSolvablePolynomial<GenPolynomial<C>> S) {
093        this(r, S.val);
094    }
095
096
097    /**
098     * Constructor for RecSolvablePolynomial.
099     * @param r solvable polynomial ring factory.
100     * @param v the SortedMap of some other (solvable) polynomial.
101     */
102    protected RecSolvablePolynomial(RecSolvablePolynomialRing<C> r, SortedMap<ExpVector, GenPolynomial<C>> v) {
103        this(r);
104        val.putAll(v); // assume no zero coefficients
105    }
106
107
108    /**
109     * Get the corresponding element factory.
110     * @return factory for this Element.
111     * @see edu.jas.structure.Element#factory()
112     */
113    @Override
114    public RecSolvablePolynomialRing<C> factory() {
115        return ring;
116    }
117
118
119    /**
120     * Clone this RecSolvablePolynomial.
121     * @see java.lang.Object#clone()
122     */
123    @Override
124    public RecSolvablePolynomial<C> copy() {
125        return new RecSolvablePolynomial<C>(ring, this.val);
126    }
127
128
129    /**
130     * Comparison with any other object.
131     * @see java.lang.Object#equals(java.lang.Object)
132     */
133    @Override
134    public boolean equals(Object B) {
135        if (!(B instanceof RecSolvablePolynomial)) {
136            return false;
137        }
138        return super.equals(B);
139    }
140
141
142    /**
143     * RecSolvablePolynomial multiplication.
144     * @param Bp RecSolvablePolynomial.
145     * @return this*Bp, where * denotes solvable multiplication.
146     */
147    // cannot @Override, @NoOverride
148    public RecSolvablePolynomial<C> multiply(RecSolvablePolynomial<C> Bp) {
149        if (Bp == null || Bp.isZERO()) {
150            return ring.getZERO();
151        }
152        if (this.isZERO()) {
153            return this;
154        }
155        assert (ring.nvar == Bp.ring.nvar);
156        if (debug) {
157            logger.info("ring = " + ring.toScript());
158        }
159        final boolean commute = ring.table.isEmpty();
160        final boolean commuteCoeff = ring.coeffTable.isEmpty();
161        GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) ring.coFac;
162        RecSolvablePolynomial<C> Dp = ring.getZERO().copy();
163        //RecSolvablePolynomial<C> zero = ring.getZERO(); //.copy(); not needed
164        ExpVector Z = ring.evzero;
165        ExpVector Zc = cfac.evzero;
166        GenPolynomial<C> one = ring.getONECoefficient();
167
168        RecSolvablePolynomial<C> C1 = null;
169        RecSolvablePolynomial<C> C2 = null;
170        Map<ExpVector, GenPolynomial<C>> A = val;
171        Map<ExpVector, GenPolynomial<C>> B = Bp.val;
172        Set<Map.Entry<ExpVector, GenPolynomial<C>>> Bk = B.entrySet();
173        if (debug)
174            logger.info("input A = " + this);
175        for (Map.Entry<ExpVector, GenPolynomial<C>> y : A.entrySet()) {
176            GenPolynomial<C> a = y.getValue();
177            ExpVector e = y.getKey();
178            if (debug)
179                logger.info("e = " + e + ", a = " + a);
180            int[] ep = e.dependencyOnVariables();
181            int el1 = ring.nvar + 1;
182            if (ep.length > 0) {
183                el1 = ep[0];
184            }
185            //int el1s = ring.nvar + 1 - el1;
186            if (debug)
187                logger.info("input B = " + Bp);
188            for (Map.Entry<ExpVector, GenPolynomial<C>> x : Bk) {
189                GenPolynomial<C> b = x.getValue();
190                ExpVector f = x.getKey();
191                if (debug)
192                    logger.info("f = " + f + ", b = " + b);
193                int[] fp = f.dependencyOnVariables();
194                int fl1 = 0;
195                if (fp.length > 0) {
196                    fl1 = fp[fp.length - 1];
197                }
198                int fl1s = ring.nvar + 1 - fl1;
199                // polynomial coefficient multiplication e*b = P_eb, for a*((e*b)*f)
200                RecSolvablePolynomial<C> Cps = ring.getZERO().copy();
201                RecSolvablePolynomial<C> Cs = null;
202                if (commuteCoeff || b.isConstant() || e.isZERO()) { // symmetric
203                    //Cps = new RecSolvablePolynomial<C>(ring, b, e);
204                    //Cps = (RecSolvablePolynomial<C>) zero.sum(b, e);
205                    Cps.doAddTo(b, e);
206                    if (debug)
207                        logger.info("symmetric coeff, e*b: b = " + b + ", e = " + e);
208                } else { // unsymmetric
209                    if (debug)
210                        logger.info("unsymmetric coeff, e*b: b = " + b + ", e = " + e);
211                    for (Map.Entry<ExpVector, C> z : b.val.entrySet()) {
212                        C c = z.getValue();
213                        GenPolynomial<C> cc = b.ring.valueOf(c); // getONE().multiply(c);
214                        ExpVector g = z.getKey();
215                        if (debug)
216                            logger.info("g = " + g + ", c = " + c);
217                        int[] gp = g.dependencyOnVariables();
218                        int gl1 = 0;
219                        if (gp.length > 0) {
220                            gl1 = gp[gp.length - 1];
221                        }
222                        int gl1s = b.ring.nvar + 1 - gl1;
223                        if (debug) {
224                            logger.info("gl1s = " + gl1s);
225                        }
226                        // split e = e1 * e2, g = g2 * g1 (= g1 * g2)
227                        ExpVector e1 = e;
228                        ExpVector e2 = Z;
229                        if (!e.isZERO()) {
230                            e1 = e.subst(el1, 0);
231                            e2 = Z.subst(el1, e.getVal(el1));
232                        }
233                        ExpVector e4;
234                        ExpVector g1 = g;
235                        ExpVector g2 = Zc;
236                        if (!g.isZERO()) {
237                            g1 = g.subst(gl1, 0);
238                            g2 = Zc.subst(gl1, g.getVal(gl1));
239                        }
240                        if (debug) {
241                            logger.info("coeff, e1 = " + e1 + ", e2 = " + e2 + ", Cps = " + Cps);
242                            logger.info("coeff, g1 = " + g1 + ", g2 = " + g2);
243                        }
244                        TableRelation<GenPolynomial<C>> crel = ring.coeffTable.lookup(e2, g2);
245                        if (debug)
246                            logger.info("coeff, crel = " + crel.p);
247                        //logger.info("coeff, e  = " + e + " g, = " + g + ", crel = " + crel);
248                        Cs = new RecSolvablePolynomial<C>(ring, crel.p);
249                        // rest of multiplication and update relations
250                        if (crel.f != null) { // process remaining right power
251                            GenPolynomial<C> c2 = b.ring.valueOf(crel.f); //getONE().multiply(crel.f);
252                            C2 = new RecSolvablePolynomial<C>(ring, c2, Z);
253                            Cs = Cs.multiply(C2);
254                            if (crel.e == null) {
255                                e4 = e2;
256                            } else {
257                                e4 = e2.subtract(crel.e);
258                            }
259                            ring.coeffTable.update(e4, g2, Cs);
260                        }
261                        if (crel.e != null) { // process remaining left power
262                            C1 = new RecSolvablePolynomial<C>(ring, one, crel.e);
263                            Cs = C1.multiply(Cs);
264                            ring.coeffTable.update(e2, g2, Cs);
265                        }
266                        if (!g1.isZERO()) { // process remaining right part
267                            GenPolynomial<C> c2 = b.ring.valueOf(g1); //getONE().multiply(g1);
268                            C2 = new RecSolvablePolynomial<C>(ring, c2, Z);
269                            Cs = Cs.multiply(C2);
270                        }
271                        if (!e1.isZERO()) { // process remaining left part
272                            C1 = new RecSolvablePolynomial<C>(ring, one, e1);
273                            Cs = C1.multiply(Cs);
274                        }
275                        //System.out.println("e1*Cs*g1 = " + Cs);
276                        Cs = Cs.multiplyLeft(cc); // assume c, coeff(cc) commutes with Cs
277                        //Cps = (RecSolvablePolynomial<C>) Cps.sum(Cs);
278                        Cps.doAddTo(Cs);
279                    } // end b loop 
280                    if (debug)
281                        logger.info("coeff, Cs = " + Cs + ", Cps = " + Cps);
282                }
283                if (debug)
284                    logger.info("coeff-poly: Cps = " + Cps);
285                // polynomial multiplication P_eb*f, for a*(P_eb*f)
286                RecSolvablePolynomial<C> Dps = ring.getZERO().copy();
287                RecSolvablePolynomial<C> Ds = null;
288                RecSolvablePolynomial<C> D1, D2;
289                if (commute || Cps.isConstant() || f.isZERO()) { // symmetric
290                    if (debug)
291                        logger.info("symmetric poly, P_eb*f: Cps = " + Cps + ", f = " + f);
292                    ExpVector g = e.sum(f);
293                    if (Cps.isConstant()) {
294                        Ds = new RecSolvablePolynomial<C>(ring, Cps.leadingBaseCoefficient(), g); // symmetric!
295                    } else {
296                        Ds = shift(Cps, f); // symmetric
297                    }
298                } else { // eventually unsymmetric
299                    if (debug)
300                        logger.info("unsymmetric poly, P_eb*f: Cps = " + Cps + ", f = " + f);
301                    for (Map.Entry<ExpVector, GenPolynomial<C>> z : Cps.val.entrySet()) {
302                        // split g = g1 * g2, f = f1 * f2
303                        GenPolynomial<C> c = z.getValue();
304                        ExpVector g = z.getKey();
305                        if (debug)
306                            logger.info("g = " + g + ", c = " + c);
307                        int[] gp = g.dependencyOnVariables();
308                        int gl1 = ring.nvar + 1;
309                        if (gp.length > 0) {
310                            gl1 = gp[0];
311                        }
312                        int gl1s = ring.nvar + 1 - gl1;
313                        if (gl1s <= fl1s) { // symmetric
314                            ExpVector h = g.sum(f);
315                            if (debug)
316                                logger.info("disjoint poly: g = " + g + ", f = " + f + ", h = " + h);
317                            Ds = ring.valueOf(h); // symmetric! //(RecSolvablePolynomial<C>) zero.sum(one, h); 
318                        } else {
319                            ExpVector g1 = g.subst(gl1, 0);
320                            ExpVector g2 = Z.subst(gl1, g.getVal(gl1)); // bug el1, gl1
321                            ExpVector g4;
322                            ExpVector f1 = f.subst(fl1, 0);
323                            ExpVector f2 = Z.subst(fl1, f.getVal(fl1));
324                            if (debug) {
325                                logger.info("poly, g1 = " + g1 + ", f1 = " + f1 + ", Dps = " + Dps);
326                                logger.info("poly, g2 = " + g2 + ", f2 = " + f2);
327                            }
328                            TableRelation<GenPolynomial<C>> rel = ring.table.lookup(g2, f2);
329                            if (debug)
330                                logger.info("poly, g  = " + g + ", f  = " + f + ", rel = " + rel);
331                            Ds = new RecSolvablePolynomial<C>(ring, rel.p); //ring.copy(rel.p);
332                            if (rel.f != null) {
333                                D2 = ring.valueOf(rel.f); //new RecSolvablePolynomial<C>(ring, one, rel.f);
334                                Ds = Ds.multiply(D2);
335                                if (rel.e == null) {
336                                    g4 = g2;
337                                } else {
338                                    g4 = g2.subtract(rel.e);
339                                }
340                                ring.table.update(g4, f2, Ds);
341                            }
342                            if (rel.e != null) {
343                                D1 = ring.valueOf(rel.e); // new RecSolvablePolynomial<C>(ring, one, rel.e);
344                                Ds = D1.multiply(Ds);
345                                ring.table.update(g2, f2, Ds);
346                            }
347                            if (!f1.isZERO()) {
348                                D2 = ring.valueOf(f1); //new RecSolvablePolynomial<C>(ring, one, f1);
349                                Ds = Ds.multiply(D2);
350                                //ring.table.update(?,f1,Ds)
351                            }
352                            if (!g1.isZERO()) {
353                                D1 = ring.valueOf(g1); //new RecSolvablePolynomial<C>(ring, one, g1);
354                                Ds = D1.multiply(Ds);
355                                //ring.table.update(e1,?,Ds)
356                            }
357                        }
358                        Ds = Ds.multiplyLeft(c); // assume c commutes with Cs
359                        //Dps = (RecSolvablePolynomial<C>) Dps.sum(Ds);
360                        Dps.doAddTo(Ds);
361                    } // end Dps loop
362                    Ds = Dps;
363                }
364                if (debug) {
365                    logger.info("recursion+: Ds = " + Ds + ", a = " + a);
366                }
367                // polynomial coefficient multiplication a*(P_eb*f) = a*Ds
368                Ds = Ds.multiplyLeft(a); // multiply(a,b); // non-symmetric 
369                if (debug)
370                    logger.info("recursion-: Ds = " + Ds);
371                //Dp = (RecSolvablePolynomial<C>) Dp.sum(Ds);
372                Dp.doAddTo(Ds);
373                if (debug)
374                    logger.info("end B loop: Dp = " + Dp);
375            } // end B loop
376            if (debug)
377                logger.info("end A loop: Dp = " + Dp);
378        } // end A loop
379        return Dp;
380    }
381
382
383    /**
384     * RecSolvablePolynomial left and right multiplication. Product with two
385     * polynomials.
386     * @param S RecSolvablePolynomial.
387     * @param T RecSolvablePolynomial.
388     * @return S*this*T.
389     */
390    // cannot @Override, @NoOverride
391    public RecSolvablePolynomial<C> multiply(RecSolvablePolynomial<C> S, RecSolvablePolynomial<C> T) {
392        if (S.isZERO() || T.isZERO() || this.isZERO()) {
393            return ring.getZERO();
394        }
395        if (S.isONE()) {
396            return multiply(T);
397        }
398        if (T.isONE()) {
399            return S.multiply(this);
400        }
401        return S.multiply(this).multiply(T);
402    }
403
404
405    /**
406     * RecSolvablePolynomial multiplication. Product with coefficient ring
407     * element.
408     * @param b coefficient polynomial.
409     * @return this*b, where * is coefficient multiplication.
410     */
411    //todo @Override, @NoOverride
412    //public RecSolvablePolynomial<C> multiply(GenPolynomial<C> b) {
413    //public GenSolvablePolynomial<GenPolynomial<C>> multiply(GenPolynomial<C> b) {
414    public RecSolvablePolynomial<C> recMultiply(GenPolynomial<C> b) {
415        RecSolvablePolynomial<C> Cp = ring.getZERO().copy();
416        if (b == null || b.isZERO()) {
417            return Cp;
418        }
419        Cp = new RecSolvablePolynomial<C>(ring, b, ring.evzero);
420        return multiply(Cp);
421        // wrong:
422        // Map<ExpVector, GenPolynomial<C>> Cm = Cp.val; //getMap();
423        // Map<ExpVector, GenPolynomial<C>> Am = val;
424        // for (Map.Entry<ExpVector, GenPolynomial<C>> y : Am.entrySet()) {
425        //     ExpVector e = y.getKey();
426        //     GenPolynomial<C> a = y.getValue();
427        //     GenPolynomial<C> c = a.multiply(b);
428        //     if (!c.isZERO()) {
429        //         Cm.put(e, c);
430        //     }
431        // }
432        // return Cp;
433    }
434
435
436    /**
437     * RecSolvablePolynomial left and right multiplication. Product with
438     * coefficient ring element.
439     * @param b coefficient polynomial.
440     * @param c coefficient polynomial.
441     * @return b*this*c, where * is coefficient multiplication.
442     */
443    @Override
444    public RecSolvablePolynomial<C> multiply(GenPolynomial<C> b, GenPolynomial<C> c) {
445        RecSolvablePolynomial<C> Cp = ring.getZERO().copy();
446        if (b == null || b.isZERO()) {
447            return Cp;
448        }
449        if (c == null || c.isZERO()) {
450            return Cp;
451        }
452        RecSolvablePolynomial<C> Cb = ring.valueOf(b); //new RecSolvablePolynomial<C>(ring, b, ring.evzero);
453        RecSolvablePolynomial<C> Cc = ring.valueOf(c); //new RecSolvablePolynomial<C>(ring, c, ring.evzero);
454        return Cb.multiply(this).multiply(Cc);
455        // wrong:
456        // Map<ExpVector, GenPolynomial<C>> Cm = Cp.val; //getMap();
457        // Map<ExpVector, GenPolynomial<C>> Am = val;
458        // for (Map.Entry<ExpVector, GenPolynomial<C>> y : Am.entrySet()) {
459        //     ExpVector e = y.getKey();
460        //     GenPolynomial<C> a = y.getValue();
461        //     GenPolynomial<C> d = b.multiply(a).multiply(c);
462        //     if (!d.isZERO()) {
463        //         Cm.put(e, d);
464        //     }
465        // }
466        // return Cp;
467    }
468
469
470    /*
471     * RecSolvablePolynomial multiplication. Product with coefficient ring
472     * element.
473     * @param b coefficient of coefficient.
474     * @return this*b, where * is coefficient multiplication.
475     */
476    //@Override not possible, @NoOverride
477    //public RecSolvablePolynomial<C> multiply(C b) { ... }
478
479
480    /**
481     * RecSolvablePolynomial multiplication. Product with exponent vector.
482     * @param e exponent.
483     * @return this * x<sup>e</sup>, where * denotes solvable multiplication.
484     */
485    @Override
486    public RecSolvablePolynomial<C> multiply(ExpVector e) {
487        if (e == null || e.isZERO()) {
488            return this;
489        }
490        GenPolynomial<C> b = ring.getONECoefficient();
491        return multiply(b, e);
492    }
493
494
495    /**
496     * RecSolvablePolynomial left and right multiplication. Product with
497     * exponent vector.
498     * @param e exponent.
499     * @param f exponent.
500     * @return x<sup>e</sup> * this * x<sup>f</sup>, where * denotes solvable
501     *         multiplication.
502     */
503    @Override
504    public RecSolvablePolynomial<C> multiply(ExpVector e, ExpVector f) {
505        if (e == null || e.isZERO()) {
506            return this;
507        }
508        if (f == null || f.isZERO()) {
509            return this;
510        }
511        GenPolynomial<C> b = ring.getONECoefficient();
512        return multiply(b, e, b, f);
513    }
514
515
516    /**
517     * RecSolvablePolynomial multiplication. Product with ring element and
518     * exponent vector.
519     * @param b coefficient polynomial.
520     * @param e exponent.
521     * @return this * b x<sup>e</sup>, where * denotes solvable multiplication.
522     */
523    @Override
524    public RecSolvablePolynomial<C> multiply(GenPolynomial<C> b, ExpVector e) {
525        if (b == null || b.isZERO()) {
526            return ring.getZERO();
527        }
528        RecSolvablePolynomial<C> Cp = ring.valueOf(b, e); //new RecSolvablePolynomial<C>(ring, b, e);
529        return multiply(Cp);
530    }
531
532
533    /**
534     * RecSolvablePolynomial left and right multiplication. Product with ring
535     * element and exponent vector.
536     * @param b coefficient polynomial.
537     * @param e exponent.
538     * @param c coefficient polynomial.
539     * @param f exponent.
540     * @return b x<sup>e</sup> * this * c x<sup>f</sup>, where * denotes
541     *         solvable multiplication.
542     */
543    @Override
544    public RecSolvablePolynomial<C> multiply(GenPolynomial<C> b, ExpVector e, GenPolynomial<C> c, ExpVector f) {
545        if (b == null || b.isZERO()) {
546            return ring.getZERO();
547        }
548        if (c == null || c.isZERO()) {
549            return ring.getZERO();
550        }
551        RecSolvablePolynomial<C> Cp = ring.valueOf(b, e); //new RecSolvablePolynomial<C>(ring, b, e);
552        RecSolvablePolynomial<C> Dp = ring.valueOf(c, f); //new RecSolvablePolynomial<C>(ring, c, f);
553        return multiply(Cp, Dp);
554    }
555
556
557    /**
558     * RecSolvablePolynomial multiplication. Left product with ring element and
559     * exponent vector.
560     * @param b coefficient polynomial.
561     * @param e exponent.
562     * @return b x<sup>e</sup> * this, where * denotes solvable multiplication.
563     */
564    @Override
565    public RecSolvablePolynomial<C> multiplyLeft(GenPolynomial<C> b, ExpVector e) {
566        if (b == null || b.isZERO()) {
567            return ring.getZERO();
568        }
569        RecSolvablePolynomial<C> Cp = ring.valueOf(b, e); //new RecSolvablePolynomial<C>(ring, b, e);
570        return Cp.multiply(this);
571    }
572
573
574    /**
575     * RecSolvablePolynomial multiplication. Left product with exponent vector.
576     * @param e exponent.
577     * @return x<sup>e</sup> * this, where * denotes solvable multiplication.
578     */
579    @Override
580    public RecSolvablePolynomial<C> multiplyLeft(ExpVector e) {
581        if (e == null || e.isZERO()) {
582            return this;
583        }
584        //GenPolynomial<C> b = ring.getONECoefficient();
585        RecSolvablePolynomial<C> Cp = ring.valueOf(e); // new RecSolvablePolynomial<C>(ring, b, e);
586        return Cp.multiply(this);
587    }
588
589
590    /**
591     * RecSolvablePolynomial multiplication. Left product with coefficient ring
592     * element.
593     * @param b coefficient polynomial.
594     * @return b*this, where * is coefficient multiplication.
595     */
596    @Override
597    public RecSolvablePolynomial<C> multiplyLeft(GenPolynomial<C> b) {
598        RecSolvablePolynomial<C> Cp = ring.getZERO().copy();
599        if (b == null || b.isZERO()) {
600            return Cp;
601        }
602        GenSolvablePolynomial<C> bb = null;
603        if (b instanceof GenSolvablePolynomial) {
604            //throw new RuntimeException("wrong method dispatch in JRE ");
605            logger.debug("warn: wrong method dispatch in JRE multiply(b) - trying to fix");
606            bb = (GenSolvablePolynomial<C>) b;
607        }
608        Map<ExpVector, GenPolynomial<C>> Cm = Cp.val; //getMap();
609        Map<ExpVector, GenPolynomial<C>> Am = val;
610        GenPolynomial<C> c;
611        for (Map.Entry<ExpVector, GenPolynomial<C>> y : Am.entrySet()) {
612            ExpVector e = y.getKey();
613            GenPolynomial<C> a = y.getValue();
614            if (bb != null) {
615                GenSolvablePolynomial<C> aa = (GenSolvablePolynomial<C>) a;
616                c = bb.multiply(aa);
617            } else {
618                c = b.multiply(a);
619            }
620            if (!c.isZERO()) {
621                Cm.put(e, c);
622            }
623        }
624        return Cp;
625    }
626
627
628    /**
629     * RecSolvablePolynomial multiplication. Left product with 'monomial'.
630     * @param m 'monomial'.
631     * @return m * this, where * denotes solvable multiplication.
632     */
633    @Override
634    public RecSolvablePolynomial<C> multiplyLeft(Map.Entry<ExpVector, GenPolynomial<C>> m) {
635        if (m == null) {
636            return ring.getZERO();
637        }
638        return multiplyLeft(m.getValue(), m.getKey());
639    }
640
641
642    /**
643     * RecSolvablePolynomial multiplication. Product with 'monomial'.
644     * @param m 'monomial'.
645     * @return this * m, where * denotes solvable multiplication.
646     */
647    @Override
648    public RecSolvablePolynomial<C> multiply(Map.Entry<ExpVector, GenPolynomial<C>> m) {
649        if (m == null) {
650            return ring.getZERO();
651        }
652        return multiply(m.getValue(), m.getKey());
653    }
654
655
656    /**
657     * RecSolvablePolynomial multiplication. Commutative product with exponent
658     * vector.
659     * @param B solvable polynomial.
660     * @param f exponent vector.
661     * @return B*f, where * is commutative multiplication.
662     */
663    protected RecSolvablePolynomial<C> shift(RecSolvablePolynomial<C> B, ExpVector f) {
664        RecSolvablePolynomial<C> C = ring.getZERO().copy();
665        if (B == null || B.isZERO()) {
666            return C;
667        }
668        if (f == null || f.isZERO()) {
669            return B;
670        }
671        Map<ExpVector, GenPolynomial<C>> Cm = C.val;
672        Map<ExpVector, GenPolynomial<C>> Bm = B.val;
673        for (Map.Entry<ExpVector, GenPolynomial<C>> y : Bm.entrySet()) {
674            ExpVector e = y.getKey();
675            GenPolynomial<C> a = y.getValue();
676            ExpVector d = e.sum(f);
677            if (!a.isZERO()) {
678                Cm.put(d, a);
679            }
680        }
681        return C;
682    }
683
684
685    /**
686     * RecSolvablePolynomial right coefficients from left coefficients.
687     * <b>Note:</b> R is represented as a polynomial with left coefficients, the
688     * implementation can at the moment not distinguish between left and right
689     * coefficients.
690     * @return R = sum( X<sup>i</sup> b<sub>i</sub> ), with this =
691     *         sum(a<sub>i</sub> X<sup>i</sup> ) and eval(sum(X<sup>i</sup>
692     *         b<sub>i</sub>)) == sum(a<sub>i</sub> X<sup>i</sup>)
693     */
694    @SuppressWarnings("cast")
695    @Override
696    public GenSolvablePolynomial<GenPolynomial<C>> rightRecursivePolynomial() {
697        if (this.isONE() || this.isZERO()) {
698            return this;
699        }
700        if (!(this instanceof RecSolvablePolynomial)) {
701            return this;
702        }
703        RecSolvablePolynomialRing<C> rfac = (RecSolvablePolynomialRing<C>) ring;
704        if (rfac.coeffTable.isEmpty()) {
705            return this;
706        }
707        GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) rfac.coFac;
708        GenPolynomial<C> one = cfac.getONE();
709        RecSolvablePolynomial<C> onep = rfac.getONE();
710        ExpVector zero = rfac.evzero;
711        RecSolvablePolynomial<C> R = rfac.getZERO();
712        RecSolvablePolynomial<C> r;
713        RecSolvablePolynomial<C> p = (RecSolvablePolynomial<C>) this;
714        while (!p.isZERO()) {
715            ExpVector f = p.leadingExpVector();
716            GenPolynomial<C> a = p.leadingBaseCoefficient();
717            //r = h.multiply(a); // wrong method dispatch // right: f*a
718            r = onep.multiply(one, f, a, zero); // right: (1 f) * 1 * (a zero)
719            //System.out.println("a,f = " + a + ", " + f); // + ", h.ring = " + h.ring.toScript());
720            //System.out.println("f*a = " + r); // + ", r.ring = " + r.ring.toScript());
721            p = (RecSolvablePolynomial<C>) p.subtract(r);
722            R = (RecSolvablePolynomial<C>) R.sum(a, f);
723        }
724        return R;
725    }
726
727
728    /**
729     * Evaluate RecSolvablePolynomial as right coefficients polynomial.
730     * <b>Note:</b> R is represented as a polynomial with left coefficients, the
731     * implementation can at the moment not distinguish between left and right
732     * coefficients.
733     * @return this as evaluated polynomial R. R = sum( X<sup>i</sup>
734     *         b<sub>i</sub> ), this = sum(a<sub>i</sub> X<sup>i</sup> ) =
735     *         eval(sum(X<sup>i</sup> b<sub>i</sub>))
736     */
737    @SuppressWarnings("cast")
738    @Override
739    public GenSolvablePolynomial<GenPolynomial<C>> evalAsRightRecursivePolynomial() {
740        if (this.isONE() || this.isZERO()) {
741            return this;
742        }
743        if (!(this instanceof RecSolvablePolynomial)) {
744            return this;
745        }
746        RecSolvablePolynomialRing<C> rfac = (RecSolvablePolynomialRing<C>) ring;
747        if (rfac.coeffTable.isEmpty()) {
748            return this;
749        }
750        GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) rfac.coFac;
751        GenPolynomial<C> one = cfac.getONE();
752        RecSolvablePolynomial<C> onep = rfac.getONE();
753        ExpVector zero = rfac.evzero;
754        RecSolvablePolynomial<C> q = rfac.getZERO();
755        RecSolvablePolynomial<C> s;
756        RecSolvablePolynomial<C> r = (RecSolvablePolynomial<C>) this;
757        for (Map.Entry<ExpVector, GenPolynomial<C>> y : r.getMap().entrySet()) {
758            ExpVector f = y.getKey();
759            GenPolynomial<C> a = y.getValue();
760            // f.multiply(a); // wrong method dispatch // right: f*a
761            // onep.multiply(f).multiply(a) // should do now
762            s = onep.multiply(one, f, a, zero); // right: (1 f) * 1 * (a zero)
763            q = (RecSolvablePolynomial<C>) q.sum(s);
764        }
765        return q;
766    }
767
768
769    /**
770     * Test RecSolvablePolynomial right coefficients polynomial. <b>Note:</b> R
771     * is represented as a polynomial with left coefficients, the implementation
772     * can at the moment not distinguish between left and right coefficients.
773     * @param R GenSolvablePolynomial with right coefficients.
774     * @return true, if R is polynomial with right coefficients of this. R =
775     *         sum( X<sup>i</sup> b<sub>i</sub> ), with this = sum(a<sub>i</sub>
776     *         X<sup>i</sup> ) and eval(sum(X<sup>i</sup> b<sub>i</sub>)) ==
777     *         sum(a<sub>i</sub> X<sup>i</sup>)
778     */
779    @SuppressWarnings("cast")
780    @Override
781    public boolean isRightRecursivePolynomial(GenSolvablePolynomial<GenPolynomial<C>> R) {
782        if (this.isZERO()) {
783            return R.isZERO();
784        }
785        if (this.isONE()) {
786            return R.isONE();
787        }
788        if (!(this instanceof RecSolvablePolynomial)) {
789            return !(R instanceof RecSolvablePolynomial);
790        }
791        if (!(R instanceof RecSolvablePolynomial)) {
792            return false;
793        }
794        RecSolvablePolynomialRing<C> rfac = (RecSolvablePolynomialRing<C>) ring;
795        if (rfac.coeffTable.isEmpty()) {
796            RecSolvablePolynomialRing<C> rf = (RecSolvablePolynomialRing<C>) R.ring;
797            return rf.coeffTable.isEmpty();
798        }
799        RecSolvablePolynomial<C> p = (RecSolvablePolynomial<C>) this;
800        RecSolvablePolynomial<C> q = (RecSolvablePolynomial<C>) R.evalAsRightRecursivePolynomial();
801        p = (RecSolvablePolynomial<C>) PolyUtil.<C> monic(p);
802        q = (RecSolvablePolynomial<C>) PolyUtil.<C> monic(q);
803        return p.equals(q);
804    }
805
806}