Source code

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