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