001/*
002 * $Id$
003 */
004
005package edu.jas.poly;
006
007
008import java.io.IOException;
009import java.lang.reflect.InvocationTargetException;
010import java.lang.reflect.Method;
011import java.util.ArrayList;
012import java.util.Collections;
013import java.util.Iterator;
014import java.util.List;
015import java.util.Map;
016import java.util.SortedMap;
017import java.util.Spliterator;
018import java.util.TreeMap;
019import java.util.function.Function;
020import java.util.regex.Pattern;
021import java.util.stream.Collectors;
022import java.util.stream.Stream;
023
024import org.apache.logging.log4j.LogManager;
025import org.apache.logging.log4j.Logger;
026
027import edu.jas.kern.PreemptingException;
028import edu.jas.kern.PrettyPrint;
029import edu.jas.structure.NotInvertibleException;
030import edu.jas.structure.RingElem;
031import edu.jas.structure.StarRingElem;
032import edu.jas.structure.UnaryFunctor;
033import edu.jas.util.MapEntry;
034
035
036/**
037 * GenPolynomial generic polynomials implementing RingElem. n-variate ordered
038 * polynomials over coefficients C. The variables commute with each other and
039 * with the coefficients. For non-commutative coefficients some care is taken to
040 * respect the multiplication order.
041 *
042 * Objects of this class are intended to be immutable. The implementation is
043 * based on TreeMap respectively SortedMap from exponents to coefficients. Only
044 * the coefficients are modeled with generic types, the exponents are fixed to
045 * ExpVector with long entries (@see edu.jas.poly.ExpVector StorUnit). C can
046 * also be a non integral domain, e.g. a ModInteger, i.e. it may contain zero
047 * divisors, since multiply() does check for zeros. <b>Note:</b> multiply() now
048 * checks for wrong method dispatch for GenSolvablePolynomial.
049 * @param <C> coefficient type
050 * @author Heinz Kredel
051 */
052public class GenPolynomial<C extends RingElem<C>>
053                implements RingElem<GenPolynomial<C>>, /* not yet Polynomial<C> */
054                Iterable<Monomial<C>> {
055
056
057    /**
058     * The factory for the polynomial ring.
059     */
060    public final GenPolynomialRing<C> ring;
061
062
063    /**
064     * The data structure for polynomials.
065     */
066    protected final SortedMap<ExpVector, C> val; // do not change to TreeMap
067
068
069    /**
070     * Stored hash code.
071     */
072    transient protected int hash = -1;
073
074
075    /**
076     * Stored bitLength.
077     */
078    transient protected long blen = -1;
079
080
081    private static final Logger logger = LogManager.getLogger(GenPolynomial.class);
082
083
084    private static final boolean debug = logger.isDebugEnabled();
085
086
087    // protected GenPolynomial() { ring = null; val = null; } // don't use
088
089
090    /**
091     * Private constructor for GenPolynomial.
092     * @param r polynomial ring factory.
093     * @param t TreeMap with correct ordering.
094     */
095    private GenPolynomial(GenPolynomialRing<C> r, TreeMap<ExpVector, C> t) {
096        ring = r;
097        val = t;
098        if (ring.checkPreempt) {
099            if (Thread.currentThread().isInterrupted()) {
100                logger.debug("throw PreemptingException");
101                throw new PreemptingException();
102            }
103        }
104    }
105
106
107    /**
108     * Constructor for zero GenPolynomial.
109     * @param r polynomial ring factory.
110     */
111    public GenPolynomial(GenPolynomialRing<C> r) {
112        this(r, new TreeMap<ExpVector, C>(r.tord.getDescendComparator()));
113    }
114
115
116    /**
117     * Constructor for GenPolynomial c * x<sup>e</sup>.
118     * @param r polynomial ring factory.
119     * @param c coefficient.
120     * @param e exponent.
121     */
122    public GenPolynomial(GenPolynomialRing<C> r, C c, ExpVector e) {
123        this(r);
124        if (!c.isZERO()) {
125            val.put(e, c);
126        }
127    }
128
129
130    /**
131     * Constructor for GenPolynomial c * x<sup>0</sup>.
132     * @param r polynomial ring factory.
133     * @param c coefficient.
134     */
135    public GenPolynomial(GenPolynomialRing<C> r, C c) {
136        this(r, c, r.evzero);
137    }
138
139
140    /**
141     * Constructor for GenPolynomial x<sup>e</sup>.
142     * @param r polynomial ring factory.
143     * @param e exponent.
144     */
145    public GenPolynomial(GenPolynomialRing<C> r, ExpVector e) {
146        this(r, r.coFac.getONE(), e);
147    }
148
149
150    /**
151     * Constructor for GenPolynomial.
152     * @param r polynomial ring factory.
153     * @param v the SortedMap of some other polynomial.
154     */
155    protected GenPolynomial(GenPolynomialRing<C> r, SortedMap<ExpVector, C> v) {
156        this(r);
157        if (v.size() > 0) {
158            GenPolynomialRing.creations++;
159            val.putAll(v); // assume no zero coefficients and val is empty
160            assert !val.values().contains(r.coFac.getZERO()) : "illegal coefficient zero: " + v;
161        }
162    }
163
164
165    /**
166     * Constructor for GenPolynomial.
167     * @param r polynomial ring factory.
168     * @param v some Map from ExpVector to coefficients.
169     */
170    protected GenPolynomial(GenPolynomialRing<C> r, Map<ExpVector, C> v) {
171        this(r);
172        if (v.size() > 0) {
173            GenPolynomialRing.creations++;
174            val.putAll(v); // assume no zero coefficients and val is empty
175            assert !val.values().contains(r.coFac.getZERO()) : "illegal coefficient zero: " + v;
176        }
177    }
178
179
180    /**
181     * Get the corresponding element factory.
182     * @return factory for this Element.
183     * @see edu.jas.structure.Element#factory()
184     */
185    public GenPolynomialRing<C> factory() {
186        return ring;
187    }
188
189
190    /**
191     * Copy this GenPolynomial.
192     * @return copy of this.
193     */
194    public GenPolynomial<C> copy() {
195        return new GenPolynomial<C>(ring, this.val);
196    }
197
198
199    /**
200     * Length of GenPolynomial.
201     * @return number of coefficients of this GenPolynomial.
202     */
203    public int length() {
204        return val.size();
205    }
206
207
208    /**
209     * ExpVector to coefficient map of GenPolynomial.
210     * @return val as unmodifiable SortedMap.
211     */
212    public SortedMap<ExpVector, C> getMap() {
213        // return val;
214        return Collections.<ExpVector, C> unmodifiableSortedMap(val);
215    }
216
217
218    /**
219     * Put an ExpVector to coefficient entry into the internal map of this
220     * GenPolynomial. <b>Note:</b> Do not use this method unless you are
221     * constructing a new polynomial. this is modified and breaks the
222     * immutability promise of this class.
223     * @param c coefficient.
224     * @param e exponent.
225     */
226    public void doPutToMap(ExpVector e, C c) {
227        if (debug) {
228            C a = val.get(e);
229            if (a != null) {
230                logger.error("map entry exists {} to {} new {}", e, a, c);
231            }
232            hash = -1;
233            blen = -1;
234        }
235        if (!c.isZERO()) {
236            val.put(e, c);
237        }
238    }
239
240
241    /**
242     * Remove an ExpVector to coefficient entry from the internal map of this
243     * GenPolynomial. <b>Note:</b> Do not use this method unless you are
244     * constructing a new polynomial. this is modified and breaks the
245     * immutability promise of this class.
246     * @param e exponent.
247     * @param c expected coefficient, null for ignore.
248     */
249    public void doRemoveFromMap(ExpVector e, C c) {
250        C b = val.remove(e);
251        if (true) { //||debug
252            hash = -1;
253            blen = -1;
254            if (c == null) { // ignore b
255                return;
256            }
257            if (!c.equals(b)) {
258                logger.error("map entry wrong {} to {} old {}", e, c, b);
259                throw new RuntimeException("c != b");
260            }
261        }
262    }
263
264
265    /**
266     * Put an a sorted map of exponents to coefficients into the internal map of
267     * this GenPolynomial. <b>Note:</b> Do not use this method unless you are
268     * constructing a new polynomial. this is modified and breaks the
269     * immutability promise of this class.
270     * @param vals sorted map of exponents and coefficients.
271     */
272    public void doPutToMap(SortedMap<ExpVector, C> vals) {
273        for (Map.Entry<ExpVector, C> me : vals.entrySet()) {
274            ExpVector e = me.getKey();
275            if (debug) {
276                C a = val.get(e);
277                if (a != null) {
278                    logger.error("map entry exists {} to {} new {}", e, a, me.getValue());
279                }
280                hash = -1;
281                blen = -1;
282            }
283            C c = me.getValue();
284            if (!c.isZERO()) {
285                val.put(e, c);
286            }
287        }
288    }
289
290
291    /**
292     * String representation of GenPolynomial.
293     * @see java.lang.Object#toString()
294     */
295    @Override
296    public String toString() {
297        if (ring.vars != null) {
298            return toString(ring.vars);
299        }
300        StringBuffer s = new StringBuffer();
301        s.append(this.getClass().getSimpleName() + ":");
302        s.append(ring.coFac.getClass().getSimpleName());
303        if (ring.coFac.characteristic().signum() != 0) {
304            s.append("(" + ring.coFac.characteristic() + ")");
305        }
306        s.append("[ ");
307        boolean first = true;
308        for (Map.Entry<ExpVector, C> m : val.entrySet()) {
309            if (first) {
310                first = false;
311            } else {
312                s.append(", ");
313            }
314            s.append(m.getValue().toString());
315            s.append(" ");
316            s.append(m.getKey().toString());
317        }
318        s.append(" ] "); // no not use: ring.toString() );
319        return s.toString();
320    }
321
322
323    /**
324     * String representation of GenPolynomial.
325     * @param v names for variables.
326     * @see java.lang.Object#toString()
327     */
328    public String toString(String[] v) {
329        StringBuffer s = new StringBuffer();
330        if (PrettyPrint.isTrue()) {
331            if (val.isEmpty()) {
332                s.append("0");
333            } else {
334                // s.append( "( " );
335                boolean first = true;
336                for (Map.Entry<ExpVector, C> m : val.entrySet()) {
337                    C c = m.getValue();
338                    if (first) {
339                        first = false;
340                    } else {
341                        if (c.signum() < 0) {
342                            s.append(" - ");
343                            c = c.negate();
344                        } else {
345                            s.append(" + ");
346                        }
347                    }
348                    ExpVector e = m.getKey();
349                    if (!c.isONE() || e.isZERO()) {
350                        String cs = c.toString();
351                        //if (c instanceof GenPolynomial || c instanceof AlgebraicNumber) {
352                        if (cs.indexOf("-") >= 0 || cs.indexOf("+") >= 0) {
353                            s.append("( ");
354                            s.append(cs);
355                            s.append(" )");
356                        } else {
357                            s.append(cs);
358                        }
359                        s.append(" ");
360                    }
361                    if (e != null && v != null) {
362                        s.append(e.toString(v));
363                    } else {
364                        s.append(e);
365                    }
366                }
367                //s.append(" )");
368            }
369        } else {
370            s.append(this.getClass().getSimpleName() + "[ ");
371            if (val.isEmpty()) {
372                s.append("0");
373            } else {
374                boolean first = true;
375                for (Map.Entry<ExpVector, C> m : val.entrySet()) {
376                    C c = m.getValue();
377                    if (first) {
378                        first = false;
379                    } else {
380                        if (c.signum() < 0) {
381                            s.append(" - ");
382                            c = c.negate();
383                        } else {
384                            s.append(" + ");
385                        }
386                    }
387                    ExpVector e = m.getKey();
388                    if (!c.isONE() || e.isZERO()) {
389                        s.append(c.toString());
390                        s.append(" ");
391                    }
392                    s.append(e.toString(v));
393                }
394            }
395            s.append(" ] "); // no not use: ring.toString() );
396        }
397        return s.toString();
398    }
399
400
401    /**
402     * Get a scripting compatible string representation.
403     * @return script compatible representation for this Element.
404     * @see edu.jas.structure.Element#toScript()
405     */
406    @Override
407    public String toScript() {
408        // Python case
409        if (isZERO()) {
410            return "0";
411        }
412        StringBuffer s = new StringBuffer();
413        if (val.size() > 1) {
414            s.append("( ");
415        }
416        String[] v = ring.vars;
417        if (v == null) {
418            v = GenPolynomialRing.newVars("x", ring.nvar);
419        }
420        Pattern klammern = Pattern.compile("\\s*\\(.+\\)\\s*");
421        boolean first = true;
422        for (Map.Entry<ExpVector, C> m : val.entrySet()) {
423            C c = m.getValue();
424            if (first) {
425                first = false;
426            } else {
427                if (c.signum() < 0) {
428                    s.append(" - ");
429                    c = c.negate();
430                } else {
431                    s.append(" + ");
432                }
433            }
434            ExpVector e = m.getKey();
435            String cs = c.toScript();
436            boolean parenthesis = (cs.indexOf("-") >= 0 || cs.indexOf("+") >= 0)
437                            && !klammern.matcher(cs).matches();
438            if (!c.isONE() || e.isZERO()) {
439                if (parenthesis) {
440                    s.append("( ");
441                }
442                s.append(cs);
443                if (parenthesis) {
444                    s.append(" )");
445                }
446                if (!e.isZERO()) {
447                    s.append(" * ");
448                }
449            }
450            s.append(e.toScript(v));
451        }
452        if (val.size() > 1) {
453            s.append(" )");
454        }
455        return s.toString();
456    }
457
458
459    /**
460     * Get a scripting compatible string representation of the factory.
461     * @return script compatible representation for this ElemFactory.
462     * @see edu.jas.structure.Element#toScriptFactory()
463     */
464    @Override
465    public String toScriptFactory() {
466        // Python case
467        return factory().toScript();
468    }
469
470
471    /**
472     * Is GenPolynomial&lt;C&gt; zero.
473     * @return If this is 0 then true is returned, else false.
474     * @see edu.jas.structure.RingElem#isZERO()
475     */
476    public boolean isZERO() {
477        return val.isEmpty();
478    }
479
480
481    /**
482     * Is GenPolynomial&lt;C&gt; one.
483     * @return If this is 1 then true is returned, else false.
484     * @see edu.jas.structure.RingElem#isONE()
485     */
486    public boolean isONE() {
487        if (val.size() != 1) {
488            return false;
489        }
490        C c = val.get(ring.evzero);
491        if (c == null) {
492            return false;
493        }
494        return c.isONE();
495    }
496
497
498    /**
499     * Is GenPolynomial&lt;C&gt; a unit.
500     * @return If this is a unit then true is returned, else false.
501     * @see edu.jas.structure.RingElem#isUnit()
502     */
503    public boolean isUnit() {
504        if (val.size() != 1) {
505            return false;
506        }
507        C c = val.get(ring.evzero);
508        if (c == null) {
509            return false;
510        }
511        return c.isUnit();
512    }
513
514
515    /**
516     * Is GenPolynomial&lt;C&gt; a constant.
517     * @return If this is a constant polynomial then true is returned, else
518     *         false.
519     */
520    public boolean isConstant() {
521        if (val.size() != 1) {
522            return false;
523        }
524        C c = val.get(ring.evzero);
525        if (c == null) {
526            return false;
527        }
528        return true;
529    }
530
531
532    /**
533     * Is GenPolynomial&lt;C&gt; homogeneous.
534     * @return true, if this is homogeneous, else false.
535     */
536    public boolean isHomogeneous() {
537        if (val.size() <= 1) {
538            return true;
539        }
540        long deg = -1;
541        for (ExpVector e : val.keySet()) {
542            if (deg < 0) {
543                deg = e.totalDeg();
544            } else if (deg != e.totalDeg()) {
545                return false;
546            }
547        }
548        return true;
549    }
550
551
552    /**
553     * Comparison with any other object.
554     * @see java.lang.Object#equals(java.lang.Object)
555     */
556    @Override
557    @SuppressWarnings("unchecked")
558    public boolean equals(Object B) {
559        if (B == null) {
560            return false;
561        }
562        if (!(B instanceof GenPolynomial)) {
563            return false;
564        }
565        GenPolynomial<C> a = (GenPolynomial<C>) B;
566        return this.compareTo(a) == 0;
567    }
568
569
570    /**
571     * Hash code for this polynomial.
572     * @see java.lang.Object#hashCode()
573     */
574    @Override
575    public int hashCode() {
576        int h = hash;
577        if (h == -1) {
578            //not in sync with equals(): h = (ring.hashCode() << 27);
579            h = val.hashCode();
580            hash = h;
581            //System.out.println("GenPolynomial.hashCode: " + h);
582        }
583        return h;
584    }
585
586
587    /**
588     * GenPolynomial comparison.
589     * @param b GenPolynomial.
590     * @return sign(this-b).
591     */
592    public int compareTo(GenPolynomial<C> b) {
593        if (b == null) {
594            return 1;
595        }
596        SortedMap<ExpVector, C> av = this.val;
597        SortedMap<ExpVector, C> bv = b.val;
598        Iterator<Map.Entry<ExpVector, C>> ai = av.entrySet().iterator();
599        Iterator<Map.Entry<ExpVector, C>> bi = bv.entrySet().iterator();
600        int s = 0;
601        int c = 0;
602        while (ai.hasNext() && bi.hasNext()) {
603            Map.Entry<ExpVector, C> aie = ai.next();
604            Map.Entry<ExpVector, C> bie = bi.next();
605            ExpVector ae = aie.getKey();
606            ExpVector be = bie.getKey();
607            s = ae.compareTo(be);
608            if (s != 0) {
609                //System.out.println("s = " + s + ", " + ring.toScript(ae) + ", " + ring.toScript(be));
610                return s;
611            }
612            if (c == 0) {
613                C ac = aie.getValue(); //av.get(ae);
614                C bc = bie.getValue(); //bv.get(be);
615                c = ac.compareTo(bc);
616            }
617        }
618        if (ai.hasNext()) {
619            //System.out.println("ai = " + ai);
620            return 1;
621        }
622        if (bi.hasNext()) {
623            //System.out.println("bi = " + bi);
624            return -1;
625        }
626        //if (c != 0) {
627        //System.out.println("c = " + c);
628        //}
629        // now all keys are equal
630        return c;
631    }
632
633
634    /**
635     * GenPolynomial signum.
636     * @return sign(ldcf(this)).
637     */
638    public int signum() {
639        if (this.isZERO()) {
640            return 0;
641        }
642        ExpVector t = val.firstKey();
643        C c = val.get(t);
644        return c.signum();
645    }
646
647
648    /**
649     * Number of variables.
650     * @return ring.nvar.
651     */
652    public int numberOfVariables() {
653        return ring.nvar;
654    }
655
656
657    /**
658     * Leading monomial.
659     * @return first map entry.
660     */
661    public Map.Entry<ExpVector, C> leadingMonomial() {
662        if (val.isEmpty()) {
663            return null;
664        }
665        //Iterator<Map.Entry<ExpVector, C>> ai = val.entrySet().iterator();
666        //return ai.next();
667        ExpVector e = val.firstKey();
668        return new MapEntry<ExpVector, C>(e, val.get(e));
669    }
670
671
672    /**
673     * Leading exponent vector.
674     * @return first exponent.
675     */
676    public ExpVector leadingExpVector() {
677        if (val.isEmpty()) {
678            return null; // ring.evzero? needs many changes 
679        }
680        return val.firstKey();
681    }
682
683
684    /**
685     * Trailing exponent vector.
686     * @return last exponent.
687     */
688    public ExpVector trailingExpVector() {
689        if (val.isEmpty()) {
690            return null; //ring.evzero; // or null ?;
691        }
692        return val.lastKey();
693    }
694
695
696    /**
697     * Leading base coefficient.
698     * @return first coefficient.
699     */
700    public C leadingBaseCoefficient() {
701        if (val.isEmpty()) {
702            return ring.coFac.getZERO();
703        }
704        return val.get(val.firstKey());
705    }
706
707
708    /**
709     * Trailing base coefficient.
710     * @return coefficient of constant term.
711     */
712    public C trailingBaseCoefficient() {
713        C c = val.get(ring.evzero);
714        if (c == null) {
715            return ring.coFac.getZERO();
716        }
717        return c;
718    }
719
720
721    /**
722     * Coefficient.
723     * @param e exponent.
724     * @return coefficient for given exponent.
725     */
726    public C coefficient(ExpVector e) {
727        C c = val.get(e);
728        if (c == null) {
729            c = ring.coFac.getZERO();
730        }
731        return c;
732    }
733
734
735    /**
736     * Reductum.
737     * @return this - leading monomial.
738     */
739    public GenPolynomial<C> reductum() {
740        if (val.size() <= 1) {
741            return ring.getZERO();
742        }
743        Iterator<ExpVector> ai = val.keySet().iterator();
744        ExpVector lt = ai.next();
745        lt = ai.next(); // size > 1
746        SortedMap<ExpVector, C> red = val.tailMap(lt);
747        GenPolynomial<C> r = ring.getZERO().copy();
748        r.doPutToMap(red); //  new GenPolynomial<C>(ring, red);
749        return r;
750    }
751
752
753    /**
754     * Degree in variable i.
755     * @return maximal degree in the variable i.
756     */
757    public long degree(int i) {
758        if (val.isEmpty()) {
759            return -1L; // 0 or -1 ?;
760        }
761        int j;
762        if (i >= 0) {
763            j = ring.nvar - 1 - i;
764        } else { // python like -1 means main variable
765            j = ring.nvar + i;
766        }
767        long deg = 0;
768        if (j < 0) {
769            return deg;
770        }
771        for (ExpVector e : val.keySet()) {
772            long d = e.getVal(j);
773            if (d > deg) {
774                deg = d;
775            }
776        }
777        return deg;
778    }
779
780
781    /**
782     * Maximal degree.
783     * @return maximal degree in any variables.
784     */
785    public long degree() {
786        if (val.isEmpty()) {
787            return -1L; // 0 or -1 ?;
788        }
789        long deg = 0;
790        for (ExpVector e : val.keySet()) {
791            long d = e.maxDeg();
792            if (d > deg) {
793                deg = d;
794            }
795        }
796        return deg;
797    }
798
799
800    /**
801     * Minimal degree. <b>Author:</b> Youssef Elbarbary
802     * @return minimal degree in any variables.
803     */
804    public long degreeMin() {
805        if (val.isEmpty()) {
806            return -1L; // 0 or -1 ?;
807        }
808        long deg = Long.MAX_VALUE;
809        for (ExpVector e : val.keySet()) {
810            long d = e.minDeg();
811            if (d < deg) {
812                deg = d;
813            }
814        }
815        return deg;
816    }
817
818
819    /**
820     * Total degree.
821     * @return total degree in any variables.
822     */
823    public long totalDegree() {
824        if (val.isEmpty()) {
825            return -1L; // 0 or -1 ?;
826        }
827        long deg = 0;
828        for (ExpVector e : val.keySet()) {
829            long d = e.totalDeg();
830            if (d > deg) {
831                deg = d;
832            }
833        }
834        return deg;
835    }
836
837
838    /**
839     * Weight degree.
840     * @return weight degree in all variables.
841     */
842    public long weightDegree() {
843        long[][] w = ring.tord.getWeight();
844        if (w == null || w.length == 0) {
845            return totalDegree(); // assume weight 1 
846        }
847        if (val.isEmpty()) {
848            return -1L; // 0 or -1 ?;
849        }
850        long deg = 0;
851        for (ExpVector e : val.keySet()) {
852            long d = e.weightDeg(w);
853            if (d > deg) {
854                deg = d;
855            }
856        }
857        return deg;
858    }
859
860
861    /**
862     * Leading weight polynomial.
863     * @return polynomial with terms of maximal weight degree.
864     */
865    public GenPolynomial<C> leadingWeightPolynomial() {
866        if (val.isEmpty()) {
867            return ring.getZERO();
868        }
869        long[][] w = ring.tord.getWeight();
870        long maxw = weightDegree();
871        GenPolynomial<C> wp = ring.getZERO().copy();
872        for (Map.Entry<ExpVector, C> m : val.entrySet()) {
873            ExpVector e = m.getKey();
874            long d = e.weightDeg(w);
875            if (d >= maxw) {
876                wp.val.put(e, m.getValue());
877            }
878        }
879        return wp;
880    }
881
882
883    /**
884     * Leading facet normal polynomial.
885     * @param u leading exponent vector.
886     * @param uv exponent vector of facet normal.
887     * @return polynomial with terms of facet normal.
888     */
889    public GenPolynomial<C> leadingFacetPolynomial(ExpVector u, ExpVector uv) {
890        if (val.isEmpty()) {
891            return ring.getZERO();
892        }
893        long[] normal = uv.getVal();
894        GenPolynomial<C> fp = ring.getZERO().copy();
895        for (Map.Entry<ExpVector, C> m : val.entrySet()) {
896            ExpVector e = m.getKey();
897            if (u.equals(e)) {
898                fp.val.put(e, m.getValue());
899            } else {
900                ExpVector v = u.subtract(e);
901                if (v.compareTo(uv) == 0) { // || v.negate().compareTo(uv) == 0
902                    fp.val.put(e, m.getValue());
903                } else { // check for v parallel to uv
904                    long ab = v.weightDeg(normal); //scalarProduct(v, uv);
905                    long a = v.weightDeg(v.getVal()); //scalarProduct(v, v);
906                    long b = uv.weightDeg(normal); //scalarProduct(uv, uv);
907                    if (ab * ab == a * b) { // cos == 1
908                        fp.val.put(e, m.getValue());
909                        if (logger.isInfoEnabled()) {
910                            logger.info("ab = {}, a = {}, b = {}, u = {}, e = {}, v = {}", ab, a, b, u, e, v);
911                        }
912                    }
913                }
914            }
915        }
916        return fp;
917    }
918
919
920    /**
921     * Is GenPolynomial&lt;C&gt; homogeneous with respect to a weight.
922     * @return true, if this is weight homogeneous, else false.
923     */
924    public boolean isWeightHomogeneous() {
925        if (val.size() <= 1) {
926            return true;
927        }
928        long[][] w = ring.tord.getWeight();
929        if (w == null || w.length == 0) {
930            return isHomogeneous(); // assume weights = 1
931        }
932        long deg = -1;
933        for (ExpVector e : val.keySet()) {
934            if (deg < 0) {
935                deg = e.weightDeg(w);
936            } else if (deg != e.weightDeg(w)) {
937                return false;
938            }
939        }
940        return true;
941    }
942
943
944    /**
945     * Maximal degree vector.
946     * @return maximal degree vector of all variables.
947     */
948    public ExpVector degreeVector() {
949        if (val.isEmpty()) {
950            return null; //deg;
951        }
952        ExpVector deg = ring.evzero;
953        for (ExpVector e : val.keySet()) {
954            deg = deg.lcm(e);
955        }
956        return deg;
957    }
958
959
960    /**
961     * Delta of exponent vectors.
962     * @return list of u-v, where u = lt() and v != u in this.
963     */
964    public List<ExpVector> deltaExpVectors() {
965        List<ExpVector> de = new ArrayList<ExpVector>(val.size());
966        if (val.isEmpty()) {
967            return de;
968        }
969        ExpVector u = null;
970        for (ExpVector e : val.keySet()) {
971            if (u == null) {
972                u = e;
973            } else {
974                ExpVector v = u.subtract(e);
975                de.add(v);
976            }
977        }
978        return de;
979    }
980
981
982    /**
983     * Delta of exponent vectors.
984     * @param u marked ExpVector in this.expVectors
985     * @return list of u-v, where v != u in this.expVectors.
986     */
987    public List<ExpVector> deltaExpVectors(ExpVector u) {
988        List<ExpVector> de = new ArrayList<ExpVector>(val.size());
989        if (val.isEmpty()) {
990            return de;
991        }
992        for (ExpVector e : val.keySet()) {
993            ExpVector v = u.subtract(e);
994            if (v.isZERO()) {
995                continue;
996            }
997            de.add(v);
998        }
999        return de;
1000    }
1001
1002
1003    /**
1004     * GenPolynomial maximum norm.
1005     * @return ||this|| the maximum of all absolute values of coefficients.
1006     */
1007    public C maxNorm() {
1008        C n = ring.getZEROCoefficient();
1009        for (C c : val.values()) {
1010            C x = c.abs();
1011            if (n.compareTo(x) < 0) {
1012                n = x;
1013            }
1014        }
1015        return n;
1016    }
1017
1018
1019    /**
1020     * GenPolynomial sum norm.
1021     * @return sum of all absolute values of coefficients.
1022     */
1023    public C sumNorm() {
1024        C n = ring.getZEROCoefficient();
1025        for (C c : val.values()) {
1026            C x = c.abs();
1027            n = n.sum(x);
1028        }
1029        return n;
1030    }
1031
1032
1033    /**
1034     * GenPolynomial square norm.
1035     * @return the sum all squared values of coefficients.
1036     */
1037    public C squareNorm() {
1038        C n = ring.getZEROCoefficient();
1039        for (C c : val.values()) {
1040            C x = c.abs();
1041            x = x.multiply(x);
1042            n = n.sum(x);
1043        }
1044        return n;
1045    }
1046
1047
1048    /**
1049     * GenPolynomial summation.
1050     * @param S GenPolynomial.
1051     * @return this+S.
1052     */
1053    //public <T extends GenPolynomial<C>> T sum(T /*GenPolynomial<C>*/ S) {
1054    public GenPolynomial<C> sum(GenPolynomial<C> S) {
1055        if (S == null || S.isZERO()) {
1056            return this;
1057        }
1058        if (this.isZERO()) {
1059            return S;
1060        }
1061        if (this.length() < (3 * S.length()) / 5) {
1062            return S.sum(this); // performance
1063        }
1064        assert (ring.nvar == S.ring.nvar);
1065        GenPolynomial<C> n = this.copy();
1066        SortedMap<ExpVector, C> nv = n.val;
1067        SortedMap<ExpVector, C> sv = S.val;
1068        for (Map.Entry<ExpVector, C> me : sv.entrySet()) {
1069            ExpVector e = me.getKey();
1070            C y = me.getValue(); // assert y != null
1071            C x = nv.get(e);
1072            if (x != null) {
1073                x = x.sum(y);
1074                if (!x.isZERO()) {
1075                    nv.put(e, x);
1076                } else {
1077                    nv.remove(e);
1078                }
1079            } else {
1080                nv.put(e, y);
1081            }
1082        }
1083        return n;
1084    }
1085
1086
1087    /**
1088     * GenPolynomial addition. This method is not very efficient, since this is
1089     * copied.
1090     * @param a coefficient.
1091     * @param e exponent.
1092     * @return this + a x<sup>e</sup>.
1093     */
1094    public GenPolynomial<C> sum(C a, ExpVector e) {
1095        if (a == null) {
1096            return this;
1097        }
1098        if (a.isZERO()) {
1099            return this;
1100        }
1101        GenPolynomial<C> n = this.copy();
1102        SortedMap<ExpVector, C> nv = n.val;
1103        //if ( nv.size() == 0 ) { nv.put(e,a); return n; }
1104        C x = nv.get(e);
1105        if (x != null) {
1106            x = x.sum(a);
1107            if (!x.isZERO()) {
1108                nv.put(e, x);
1109            } else {
1110                nv.remove(e);
1111            }
1112        } else {
1113            nv.put(e, a);
1114        }
1115        return n;
1116    }
1117
1118
1119    /**
1120     * GenPolynomial addition. This method is not very efficient, since this is
1121     * copied.
1122     * @param m monomial.
1123     * @return this + m.
1124     */
1125    public GenPolynomial<C> sum(Monomial<C> m) {
1126        return sum(m.coefficient(), m.exponent());
1127    }
1128
1129
1130    /**
1131     * GenPolynomial addition. This method is not very efficient, since this is
1132     * copied.
1133     * @param a coefficient.
1134     * @return this + a x<sup>0</sup>.
1135     */
1136    public GenPolynomial<C> sum(C a) {
1137        return sum(a, ring.evzero);
1138    }
1139
1140
1141    /**
1142     * GenPolynomial destructive summation.
1143     * @param S GenPolynomial.
1144     */
1145    public void doAddTo(GenPolynomial<C> S) {
1146        if (S == null || S.isZERO()) {
1147            return;
1148        }
1149        if (this.isZERO()) {
1150            this.val.putAll(S.val);
1151            return;
1152        }
1153        assert (ring.nvar == S.ring.nvar);
1154        SortedMap<ExpVector, C> nv = this.val;
1155        SortedMap<ExpVector, C> sv = S.val;
1156        for (Map.Entry<ExpVector, C> me : sv.entrySet()) {
1157            ExpVector e = me.getKey();
1158            C y = me.getValue(); // assert y != null
1159            C x = nv.get(e);
1160            if (x != null) {
1161                x = x.sum(y);
1162                if (!x.isZERO()) {
1163                    nv.put(e, x);
1164                } else {
1165                    nv.remove(e);
1166                }
1167            } else {
1168                nv.put(e, y);
1169            }
1170        }
1171        return;
1172    }
1173
1174
1175    /**
1176     * GenPolynomial destructive summation.
1177     * @param a coefficient.
1178     * @param e exponent.
1179     */
1180    public void doAddTo(C a, ExpVector e) {
1181        if (a == null || a.isZERO()) {
1182            return;
1183        }
1184        SortedMap<ExpVector, C> nv = this.val;
1185        C x = nv.get(e);
1186        if (x != null) {
1187            x = x.sum(a);
1188            if (!x.isZERO()) {
1189                nv.put(e, x);
1190            } else {
1191                nv.remove(e);
1192            }
1193        } else {
1194            nv.put(e, a);
1195        }
1196        return;
1197    }
1198
1199
1200    /**
1201     * GenPolynomial destructive summation.
1202     * @param a coefficient.
1203     */
1204    public void doAddTo(C a) {
1205        doAddTo(a, ring.evzero);
1206    }
1207
1208
1209    /**
1210     * GenPolynomial subtraction.
1211     * @param S GenPolynomial.
1212     * @return this-S.
1213     */
1214    public GenPolynomial<C> subtract(GenPolynomial<C> S) {
1215        if (S == null) {
1216            return this;
1217        }
1218        if (S.isZERO()) {
1219            return this;
1220        }
1221        if (this.isZERO()) {
1222            return S.negate();
1223        }
1224        assert (ring.nvar == S.ring.nvar);
1225        GenPolynomial<C> n = this.copy();
1226        SortedMap<ExpVector, C> nv = n.val;
1227        SortedMap<ExpVector, C> sv = S.val;
1228        for (Map.Entry<ExpVector, C> me : sv.entrySet()) {
1229            ExpVector e = me.getKey();
1230            C y = me.getValue(); // assert y != null
1231            C x = nv.get(e);
1232            if (x != null) {
1233                x = x.subtract(y);
1234                if (!x.isZERO()) {
1235                    nv.put(e, x);
1236                } else {
1237                    nv.remove(e);
1238                }
1239            } else {
1240                nv.put(e, y.negate());
1241            }
1242        }
1243        return n;
1244    }
1245
1246
1247    /**
1248     * GenPolynomial subtraction. This method is not very efficient, since this
1249     * is copied.
1250     * @param a coefficient.
1251     * @param e exponent.
1252     * @return this - a x<sup>e</sup>.
1253     */
1254    public GenPolynomial<C> subtract(C a, ExpVector e) {
1255        if (a == null || a.isZERO()) {
1256            return this;
1257        }
1258        GenPolynomial<C> n = this.copy();
1259        SortedMap<ExpVector, C> nv = n.val;
1260        C x = nv.get(e);
1261        if (x != null) {
1262            x = x.subtract(a);
1263            if (!x.isZERO()) {
1264                nv.put(e, x);
1265            } else {
1266                nv.remove(e);
1267            }
1268        } else {
1269            nv.put(e, a.negate());
1270        }
1271        return n;
1272    }
1273
1274
1275    /**
1276     * GenPolynomial subtraction. This method is not very efficient, since this
1277     * is copied.
1278     * @param m monomial.
1279     * @return this - m.
1280     */
1281    public GenPolynomial<C> subtract(Monomial<C> m) {
1282        return subtract(m.coefficient(), m.exponent());
1283    }
1284
1285
1286    /**
1287     * GenPolynomial subtract. This method is not very efficient, since this is
1288     * copied.
1289     * @param a coefficient.
1290     * @return this + a x<sup>0</sup>.
1291     */
1292    public GenPolynomial<C> subtract(C a) {
1293        return subtract(a, ring.evzero);
1294    }
1295
1296
1297    /**
1298     * GenPolynomial subtract a multiple.
1299     * @param a coefficient.
1300     * @param S GenPolynomial.
1301     * @return this - a S.
1302     */
1303    public GenPolynomial<C> subtractMultiple(C a, GenPolynomial<C> S) {
1304        if (a == null || a.isZERO()) {
1305            return this;
1306        }
1307        if (S == null || S.isZERO()) {
1308            return this;
1309        }
1310        if (this.isZERO()) {
1311            return S.multiply(a.negate());
1312        }
1313        assert (ring.nvar == S.ring.nvar);
1314        GenPolynomial<C> n = this.copy();
1315        SortedMap<ExpVector, C> nv = n.val;
1316        SortedMap<ExpVector, C> sv = S.val;
1317        for (Map.Entry<ExpVector, C> me : sv.entrySet()) {
1318            ExpVector f = me.getKey();
1319            C y = me.getValue(); // assert y != null
1320            y = a.multiply(y);
1321            C x = nv.get(f);
1322            if (x != null) {
1323                x = x.subtract(y);
1324                if (!x.isZERO()) {
1325                    nv.put(f, x);
1326                } else {
1327                    nv.remove(f);
1328                }
1329            } else if (!y.isZERO()) {
1330                nv.put(f, y.negate());
1331            }
1332        }
1333        return n;
1334    }
1335
1336
1337    /**
1338     * GenPolynomial subtract a multiple.
1339     * @param a coefficient.
1340     * @param e exponent.
1341     * @param S GenPolynomial.
1342     * @return this - a x<sup>e</sup> S.
1343     */
1344    public GenPolynomial<C> subtractMultiple(C a, ExpVector e, GenPolynomial<C> S) {
1345        if (a == null || a.isZERO()) {
1346            return this;
1347        }
1348        if (S == null || S.isZERO()) {
1349            return this;
1350        }
1351        if (this.isZERO()) {
1352            return S.multiply(a.negate(), e);
1353        }
1354        assert (ring.nvar == S.ring.nvar);
1355        GenPolynomial<C> n = this.copy();
1356        SortedMap<ExpVector, C> nv = n.val;
1357        SortedMap<ExpVector, C> sv = S.val;
1358        for (Map.Entry<ExpVector, C> me : sv.entrySet()) {
1359            ExpVector f = me.getKey();
1360            f = e.sum(f);
1361            C y = me.getValue(); // assert y != null
1362            y = a.multiply(y);
1363            C x = nv.get(f);
1364            if (x != null) {
1365                x = x.subtract(y);
1366                if (!x.isZERO()) {
1367                    nv.put(f, x);
1368                } else {
1369                    nv.remove(f);
1370                }
1371            } else if (!y.isZERO()) {
1372                nv.put(f, y.negate());
1373            }
1374        }
1375        return n;
1376    }
1377
1378
1379    /**
1380     * GenPolynomial scale and subtract a multiple.
1381     * @param b scale factor.
1382     * @param a coefficient.
1383     * @param S GenPolynomial.
1384     * @return this * b - a S.
1385     */
1386    public GenPolynomial<C> scaleSubtractMultiple(C b, C a, GenPolynomial<C> S) {
1387        if (a == null || S == null) {
1388            return this.multiply(b);
1389        }
1390        if (a.isZERO() || S.isZERO()) {
1391            return this.multiply(b);
1392        }
1393        if (this.isZERO() || b == null || b.isZERO()) {
1394            return S.multiply(a.negate()); //left?
1395        }
1396        if (b.isONE()) {
1397            return subtractMultiple(a, S);
1398        }
1399        assert (ring.nvar == S.ring.nvar);
1400        GenPolynomial<C> n = this.multiply(b);
1401        SortedMap<ExpVector, C> nv = n.val;
1402        SortedMap<ExpVector, C> sv = S.val;
1403        for (Map.Entry<ExpVector, C> me : sv.entrySet()) {
1404            ExpVector f = me.getKey();
1405            //f = e.sum(f);
1406            C y = me.getValue(); // assert y != null
1407            y = a.multiply(y); // now y can be zero
1408            C x = nv.get(f);
1409            if (x != null) {
1410                x = x.subtract(y);
1411                if (!x.isZERO()) {
1412                    nv.put(f, x);
1413                } else {
1414                    nv.remove(f);
1415                }
1416            } else if (!y.isZERO()) {
1417                nv.put(f, y.negate());
1418            }
1419        }
1420        return n;
1421    }
1422
1423
1424    /**
1425     * GenPolynomial scale and subtract a multiple.
1426     * @param b scale factor.
1427     * @param a coefficient.
1428     * @param e exponent.
1429     * @param S GenPolynomial.
1430     * @return this * b - a x<sup>e</sup> S.
1431     */
1432    public GenPolynomial<C> scaleSubtractMultiple(C b, C a, ExpVector e, GenPolynomial<C> S) {
1433        if (a == null || S == null) {
1434            return this.multiply(b);
1435        }
1436        if (a.isZERO() || S.isZERO()) {
1437            return this.multiply(b);
1438        }
1439        if (this.isZERO() || b == null || b.isZERO()) {
1440            return S.multiply(a.negate(), e);
1441        }
1442        if (b.isONE()) {
1443            return subtractMultiple(a, e, S);
1444        }
1445        assert (ring.nvar == S.ring.nvar);
1446        GenPolynomial<C> n = this.multiply(b);
1447        SortedMap<ExpVector, C> nv = n.val;
1448        SortedMap<ExpVector, C> sv = S.val;
1449        for (Map.Entry<ExpVector, C> me : sv.entrySet()) {
1450            ExpVector f = me.getKey();
1451            f = e.sum(f);
1452            C y = me.getValue(); // assert y != null
1453            y = a.multiply(y); // now y can be zero
1454            C x = nv.get(f);
1455            if (x != null) {
1456                x = x.subtract(y);
1457                if (!x.isZERO()) {
1458                    nv.put(f, x);
1459                } else {
1460                    nv.remove(f);
1461                }
1462            } else if (!y.isZERO()) {
1463                nv.put(f, y.negate());
1464            }
1465        }
1466        return n;
1467    }
1468
1469
1470    /**
1471     * GenPolynomial scale and subtract a multiple.
1472     * @param b scale factor.
1473     * @param g scale exponent.
1474     * @param a coefficient.
1475     * @param e exponent.
1476     * @param S GenPolynomial.
1477     * @return this * a x<sup>g</sup> - a x<sup>e</sup> S.
1478     */
1479    public GenPolynomial<C> scaleSubtractMultiple(C b, ExpVector g, C a, ExpVector e, GenPolynomial<C> S) {
1480        if (a == null || S == null) {
1481            return this.multiply(b, g);
1482        }
1483        if (a.isZERO() || S.isZERO()) {
1484            return this.multiply(b, g);
1485        }
1486        if (this.isZERO() || b == null || b.isZERO()) {
1487            return S.multiply(a.negate(), e);
1488        }
1489        if (b.isONE() && g.isZERO()) {
1490            return subtractMultiple(a, e, S);
1491        }
1492        assert (ring.nvar == S.ring.nvar);
1493        GenPolynomial<C> n = this.multiply(b, g);
1494        SortedMap<ExpVector, C> nv = n.val;
1495        SortedMap<ExpVector, C> sv = S.val;
1496        for (Map.Entry<ExpVector, C> me : sv.entrySet()) {
1497            ExpVector f = me.getKey();
1498            f = e.sum(f);
1499            C y = me.getValue(); // assert y != null
1500            y = a.multiply(y); // y can be zero now
1501            C x = nv.get(f);
1502            if (x != null) {
1503                x = x.subtract(y);
1504                if (!x.isZERO()) {
1505                    nv.put(f, x);
1506                } else {
1507                    nv.remove(f);
1508                }
1509            } else if (!y.isZERO()) {
1510                nv.put(f, y.negate());
1511            }
1512        }
1513        return n;
1514    }
1515
1516
1517    /**
1518     * GenPolynomial negation, alternative implementation.
1519     * @return -this.
1520     */
1521    public GenPolynomial<C> negateAlt() {
1522        GenPolynomial<C> n = ring.getZERO().copy();
1523        SortedMap<ExpVector, C> v = n.val;
1524        for (Map.Entry<ExpVector, C> m : val.entrySet()) {
1525            C x = m.getValue(); // != null, 0
1526            v.put(m.getKey(), x.negate());
1527        }
1528        return n;
1529    }
1530
1531
1532    /**
1533     * GenPolynomial negation.
1534     * @return -this.
1535     */
1536    public GenPolynomial<C> negate() {
1537        GenPolynomial<C> n = this.copy();
1538        SortedMap<ExpVector, C> v = n.val;
1539        for (Map.Entry<ExpVector, C> m : v.entrySet()) {
1540            C x = m.getValue(); // != null, 0
1541            m.setValue(x.negate()); // okay
1542        }
1543        return n;
1544    }
1545
1546
1547    /**
1548     * GenPolynomial absolute value, i.e. leadingCoefficient &gt; 0.
1549     * @return abs(this).
1550     */
1551    public GenPolynomial<C> abs() {
1552        if (leadingBaseCoefficient().signum() < 0) {
1553            return this.negate();
1554        }
1555        return this;
1556    }
1557
1558
1559    /**
1560     * GenPolynomial multiplication.
1561     * @param S GenPolynomial.
1562     * @return this*S.
1563     */
1564    public GenPolynomial<C> multiply(GenPolynomial<C> S) {
1565        if (S == null) {
1566            return ring.getZERO();
1567        }
1568        if (S.isZERO()) {
1569            return ring.getZERO();
1570        }
1571        if (this.isZERO()) {
1572            return this;
1573        }
1574        assert (ring.nvar == S.ring.nvar);
1575        if (this instanceof GenSolvablePolynomial && S instanceof GenSolvablePolynomial) {
1576            //throw new RuntimeException("wrong method dispatch in JRE ");
1577            logger.debug("warn: wrong method dispatch in JRE multiply(S) - trying to fix");
1578            GenSolvablePolynomial<C> T = (GenSolvablePolynomial<C>) this;
1579            GenSolvablePolynomial<C> Sp = (GenSolvablePolynomial<C>) S;
1580            return T.multiply(Sp);
1581        }
1582        GenPolynomial<C> p = ring.getZERO().copy();
1583        SortedMap<ExpVector, C> pv = p.val;
1584        for (Map.Entry<ExpVector, C> m1 : val.entrySet()) {
1585            C c1 = m1.getValue();
1586            ExpVector e1 = m1.getKey();
1587            for (Map.Entry<ExpVector, C> m2 : S.val.entrySet()) {
1588                C c2 = m2.getValue();
1589                ExpVector e2 = m2.getKey();
1590                C c = c1.multiply(c2); // check non zero if not domain
1591                if (!c.isZERO()) {
1592                    ExpVector e = e1.sum(e2);
1593                    C c0 = pv.get(e);
1594                    if (c0 == null) {
1595                        pv.put(e, c);
1596                    } else {
1597                        c0 = c0.sum(c);
1598                        if (!c0.isZERO()) {
1599                            pv.put(e, c0);
1600                        } else {
1601                            pv.remove(e);
1602                        }
1603                    }
1604                }
1605            }
1606        }
1607        return p;
1608    }
1609
1610
1611    /**
1612     * GenPolynomial multiplication. Product with coefficient ring element.
1613     * @param s coefficient.
1614     * @return this*s.
1615     */
1616    public GenPolynomial<C> multiply(C s) {
1617        if (s == null || s.isZERO()) {
1618            return ring.getZERO();
1619        }
1620        if (this.isZERO()) {
1621            return this;
1622        }
1623        if (this instanceof GenSolvablePolynomial) {
1624            //throw new RuntimeException("wrong method dispatch in JRE ");
1625            logger.debug("warn: wrong method dispatch in JRE multiply(s) - trying to fix");
1626            GenSolvablePolynomial<C> T = (GenSolvablePolynomial<C>) this;
1627            return T.multiply(s);
1628        }
1629        GenPolynomial<C> p = ring.getZERO().copy();
1630        SortedMap<ExpVector, C> pv = p.val;
1631        for (Map.Entry<ExpVector, C> m : val.entrySet()) {
1632            C a = m.getValue();
1633            ExpVector e = m.getKey();
1634            C c = a.multiply(s); // check non zero if not domain
1635            if (!c.isZERO()) {
1636                pv.put(e, c); // not m1.setValue( c )
1637            }
1638        }
1639        return p;
1640    }
1641
1642
1643    /**
1644     * GenPolynomial left multiplication. Left product with coefficient ring
1645     * element.
1646     * @param s coefficient.
1647     * @return s*this.
1648     */
1649    public GenPolynomial<C> multiplyLeft(C s) {
1650        if (s == null || s.isZERO()) {
1651            return ring.getZERO();
1652        }
1653        if (this.isZERO()) {
1654            return this;
1655        }
1656        if (this instanceof GenSolvablePolynomial) {
1657            //throw new RuntimeException("wrong method dispatch in JRE ");
1658            logger.debug("warn: wrong method dispatch in JRE multiply(s) - trying to fix");
1659            GenSolvablePolynomial<C> T = (GenSolvablePolynomial<C>) this;
1660            return T.multiplyLeft(s);
1661        }
1662        GenPolynomial<C> p = ring.getZERO().copy();
1663        SortedMap<ExpVector, C> pv = p.val;
1664        for (Map.Entry<ExpVector, C> m : val.entrySet()) {
1665            C a = m.getValue();
1666            ExpVector e = m.getKey();
1667            C c = s.multiply(a);
1668            if (!c.isZERO()) {
1669                pv.put(e, c);
1670            }
1671        }
1672        return p;
1673    }
1674
1675
1676    /**
1677     * GenPolynomial monic, i.e. leadingCoefficient == 1. If leadingCoefficient
1678     * is not invertible returns this unmodified.
1679     * @return monic(this).
1680     */
1681    public GenPolynomial<C> monic() {
1682        if (this.isZERO()) {
1683            return this;
1684        }
1685        C lc = leadingBaseCoefficient();
1686        if (!lc.isUnit()) {
1687            //System.out.println("lc = "+lc);
1688            return this;
1689        }
1690        C lm = lc.inverse();
1691        return multiplyLeft(lm);
1692    }
1693
1694
1695    /**
1696     * GenPolynomial monic, i.e. leadingCoefficient == 1. If leadingCoefficient
1697     * is not invertible returns this unmodified.
1698     * @return monic(this).
1699     */
1700    public GenPolynomial<C> monicRight() {
1701        if (this.isZERO()) {
1702            return this;
1703        }
1704        C lc = leadingBaseCoefficient();
1705        if (!lc.isUnit()) {
1706            //System.out.println("lc = "+lc);
1707            return this;
1708        }
1709        C lm = lc.inverse();
1710        return multiply(lm);
1711    }
1712
1713
1714    /**
1715     * GenPolynomial multiplication. Product with ring element and exponent
1716     * vector.
1717     * @param s coefficient.
1718     * @param e exponent.
1719     * @return this * s x<sup>e</sup>.
1720     */
1721    public GenPolynomial<C> multiply(C s, ExpVector e) {
1722        if (s == null) {
1723            return ring.getZERO();
1724        }
1725        if (s.isZERO()) {
1726            return ring.getZERO();
1727        }
1728        if (this.isZERO()) {
1729            return this;
1730        }
1731        if (e == null) { // exp vector of zero polynomial
1732            return ring.getZERO();
1733        }
1734        if (this instanceof GenSolvablePolynomial) {
1735            //throw new RuntimeException("wrong method dispatch in JRE ");
1736            logger.debug("warn: wrong method dispatch in JRE multiply(s,e) - trying to fix");
1737            GenSolvablePolynomial<C> T = (GenSolvablePolynomial<C>) this;
1738            return T.multiply(s, e);
1739        }
1740        GenPolynomial<C> p = ring.getZERO().copy();
1741        SortedMap<ExpVector, C> pv = p.val;
1742        for (Map.Entry<ExpVector, C> m1 : val.entrySet()) {
1743            C c1 = m1.getValue();
1744            ExpVector e1 = m1.getKey();
1745            C c = c1.multiply(s); // check non zero if not domain
1746            if (!c.isZERO()) {
1747                ExpVector e2 = e1.sum(e);
1748                pv.put(e2, c);
1749            }
1750        }
1751        return p;
1752    }
1753
1754
1755    /**
1756     * GenPolynomial multiplication. Product with exponent vector.
1757     * @param e exponent (!= null).
1758     * @return this * x<sup>e</sup>.
1759     */
1760    public GenPolynomial<C> multiply(ExpVector e) {
1761        if (e == null) { // exp vector of zero polynomial
1762            return ring.getZERO();
1763        }
1764        // assert e != null. This is seldom allowed.
1765        if (this.isZERO()) {
1766            return this;
1767        }
1768        if (this instanceof GenSolvablePolynomial) {
1769            //throw new RuntimeException("wrong method dispatch in JRE ");
1770            logger.debug("warn: wrong method dispatch in JRE multiply(e) - trying to fix");
1771            GenSolvablePolynomial<C> T = (GenSolvablePolynomial<C>) this;
1772            return T.multiply(e);
1773        }
1774        GenPolynomial<C> p = ring.getZERO().copy();
1775        SortedMap<ExpVector, C> pv = p.val;
1776        for (Map.Entry<ExpVector, C> m1 : val.entrySet()) {
1777            C c1 = m1.getValue();
1778            ExpVector e1 = m1.getKey();
1779            ExpVector e2 = e1.sum(e);
1780            pv.put(e2, c1);
1781        }
1782        return p;
1783    }
1784
1785
1786    /**
1787     * GenPolynomial multiplication. Product with 'monomial'.
1788     * @param m 'monomial'.
1789     * @return this * m.
1790     */
1791    public GenPolynomial<C> multiply(Map.Entry<ExpVector, C> m) {
1792        if (m == null) {
1793            return ring.getZERO();
1794        }
1795        return multiply(m.getValue(), m.getKey());
1796    }
1797
1798
1799    /**
1800     * GenPolynomial division. Division by coefficient ring element. Fails, if
1801     * exact division is not possible.
1802     * @param s coefficient.
1803     * @return s**(-1) * this.
1804     */
1805    public GenPolynomial<C> divide(C s) {
1806        if (s == null || s.isZERO()) {
1807            throw new ArithmeticException("division by zero");
1808        }
1809        if (this.isZERO()) {
1810            return this;
1811        }
1812        //C t = s.inverse();
1813        //return multiply(t);
1814        GenPolynomial<C> p = ring.getZERO().copy();
1815        SortedMap<ExpVector, C> pv = p.val;
1816        for (Map.Entry<ExpVector, C> m : val.entrySet()) {
1817            ExpVector e = m.getKey();
1818            C c1 = m.getValue();
1819            C c = c1.divide(s);
1820            if (debug) {
1821                C x = c1.remainder(s);
1822                if (!x.isZERO()) {
1823                    logger.info("divide x = {}", x);
1824                    throw new ArithmeticException("no exact division: " + c1 + "/" + s);
1825                }
1826            }
1827            if (c.isZERO()) {
1828                throw new ArithmeticException("no exact division: " + c1 + "/" + s + ", in " + this);
1829            }
1830            pv.put(e, c); // not m1.setValue( c )
1831        }
1832        return p;
1833    }
1834
1835
1836    /**
1837     * GenPolynomial right division. Right division by coefficient ring element.
1838     * Fails, if exact division is not possible.
1839     * @param s coefficient.
1840     * @return this * s**(-1).
1841     */
1842    public GenPolynomial<C> rightDivideCoeff(C s) {
1843        if (s == null || s.isZERO()) {
1844            throw new ArithmeticException("division by zero");
1845        }
1846        if (this.isZERO()) {
1847            return this;
1848        }
1849        //C t = s.inverse();
1850        //return multiply(t);
1851        GenPolynomial<C> p = ring.getZERO().copy();
1852        SortedMap<ExpVector, C> pv = p.val;
1853        for (Map.Entry<ExpVector, C> m : val.entrySet()) {
1854            ExpVector e = m.getKey();
1855            C c1 = m.getValue();
1856            C c = c1.rightDivide(s);
1857            if (debug) {
1858                C x = c1.rightRemainder(s);
1859                if (!x.isZERO()) {
1860                    logger.info("divide x = {}", x);
1861                    throw new ArithmeticException("no exact division: " + c1 + "/" + s);
1862                }
1863            }
1864            if (c.isZERO()) {
1865                throw new ArithmeticException("no exact division: " + c1 + "/" + s + ", in " + this);
1866            }
1867            pv.put(e, c); // not m1.setValue( c )
1868        }
1869        return p;
1870    }
1871
1872
1873    /**
1874     * GenPolynomial left division. Left division by coefficient ring element.
1875     * Fails, if exact division is not possible.
1876     * @param s coefficient.
1877     * @return s**(-1) * this.
1878     */
1879    public GenPolynomial<C> leftDivideCoeff(C s) {
1880        if (s == null || s.isZERO()) {
1881            throw new ArithmeticException("division by zero");
1882        }
1883        if (this.isZERO()) {
1884            return this;
1885        }
1886        //C t = s.inverse();
1887        //return multiply(t);
1888        GenPolynomial<C> p = ring.getZERO().copy();
1889        SortedMap<ExpVector, C> pv = p.val;
1890        for (Map.Entry<ExpVector, C> m : val.entrySet()) {
1891            ExpVector e = m.getKey();
1892            C c1 = m.getValue();
1893            C c = c1.leftDivide(s);
1894            if (debug) {
1895                C x = c1.leftRemainder(s);
1896                if (!x.isZERO()) {
1897                    logger.info("divide x = {}", x);
1898                    throw new ArithmeticException("no exact division: " + c1 + "/" + s);
1899                }
1900            }
1901            if (c.isZERO()) {
1902                throw new ArithmeticException("no exact division: " + c1 + "/" + s + ", in " + this);
1903            }
1904            pv.put(e, c); // not m1.setValue( c )
1905        }
1906        return p;
1907    }
1908
1909
1910    /**
1911     * GenPolynomial coefficient primitive part. Division by
1912     * gcd of coefficients.
1913     * @return this/gcd(coeff(this)).
1914     */
1915    public GenPolynomial<C> coeffPrimitivePart() {
1916        if (this.isZERO() || this.isONE()) {
1917            return this;
1918        }
1919        C s = ring.coFac.getZERO();
1920        for (C c : val.values()) {
1921            s = s.gcd(c);
1922        }
1923        return divide(s).abs();
1924    }
1925
1926
1927    /**
1928     * GenPolynomial division with remainder. Fails, if exact division by
1929     * leading base coefficient is not possible. Meaningful only for univariate
1930     * polynomials over fields, but works in any case.
1931     * @param S nonzero GenPolynomial with invertible leading coefficient.
1932     * @return [ quotient , remainder ] with this = quotient * S + remainder and
1933     *         deg(remainder) &lt; deg(S) or remainder = 0.
1934     * @see edu.jas.poly.PolyUtil#baseSparsePseudoRemainder(edu.jas.poly.GenPolynomial,edu.jas.poly.GenPolynomial)
1935     */
1936    @SuppressWarnings("unchecked")
1937    public GenPolynomial<C>[] quotientRemainder(GenPolynomial<C> S) {
1938        if (S == null || S.isZERO()) {
1939            throw new ArithmeticException("division by zero");
1940        }
1941        C c = S.leadingBaseCoefficient();
1942        if (!c.isUnit()) {
1943            throw new ArithmeticException("lbcf not invertible " + c);
1944        }
1945        C ci = c.inverse();
1946        assert (ring.nvar == S.ring.nvar);
1947        ExpVector e = S.leadingExpVector();
1948        GenPolynomial<C> h;
1949        GenPolynomial<C> q = ring.getZERO().copy();
1950        GenPolynomial<C> r = this.copy();
1951        while (!r.isZERO()) {
1952            ExpVector f = r.leadingExpVector();
1953            if (f.multipleOf(e)) {
1954                C a = r.leadingBaseCoefficient();
1955                ExpVector g = f.subtract(e);
1956                a = a.multiply(ci);
1957                q = q.sum(a, g);
1958                h = S.multiply(a, g);
1959                r = r.subtract(h);
1960                assert (!f.equals(r.leadingExpVector())) : "leadingExpVector not descending: " + f;
1961            } else {
1962                break;
1963            }
1964        }
1965        GenPolynomial<C>[] ret = new GenPolynomial[2];
1966        ret[0] = q;
1967        ret[1] = r;
1968        return ret;
1969    }
1970
1971
1972    /**
1973     * GenPolynomial division. Fails, if exact division by leading base
1974     * coefficient is not possible. Meaningful only for univariate polynomials
1975     * over fields, but works in any case.
1976     * @param S nonzero GenPolynomial with invertible leading coefficient.
1977     * @return quotient with this = quotient * S + remainder.
1978     * @see edu.jas.poly.PolyUtil#baseSparsePseudoRemainder(edu.jas.poly.GenPolynomial,edu.jas.poly.GenPolynomial)
1979     */
1980    public GenPolynomial<C> divide(GenPolynomial<C> S) {
1981        if (this instanceof GenSolvablePolynomial || S instanceof GenSolvablePolynomial) {
1982            //throw new RuntimeException("wrong method dispatch in JRE ");
1983            //logger.debug("warn: wrong method dispatch in JRE multiply(S) - trying to fix");
1984            GenSolvablePolynomial<C> T = (GenSolvablePolynomial<C>) this;
1985            GenSolvablePolynomial<C> Sp = (GenSolvablePolynomial<C>) S;
1986            return T.quotientRemainder(Sp)[0];
1987        }
1988        return quotientRemainder(S)[0];
1989    }
1990
1991
1992    /**
1993     * GenPolynomial remainder. Fails, if exact division by leading base
1994     * coefficient is not possible. Meaningful only for univariate polynomials
1995     * over fields, but works in any case.
1996     * @param S nonzero GenPolynomial with invertible leading coefficient.
1997     * @return remainder with this = quotient * S + remainder.
1998     * @see edu.jas.poly.PolyUtil#baseSparsePseudoRemainder(edu.jas.poly.GenPolynomial,edu.jas.poly.GenPolynomial)
1999     */
2000    public GenPolynomial<C> remainder(GenPolynomial<C> S) {
2001        if (this instanceof GenSolvablePolynomial || S instanceof GenSolvablePolynomial) {
2002            //throw new RuntimeException("wrong method dispatch in JRE ");
2003            //logger.debug("warn: wrong method dispatch in JRE multiply(S) - trying to fix");
2004            GenSolvablePolynomial<C> T = (GenSolvablePolynomial<C>) this;
2005            GenSolvablePolynomial<C> Sp = (GenSolvablePolynomial<C>) S;
2006            return T.quotientRemainder(Sp)[1];
2007        }
2008        if (S == null || S.isZERO()) {
2009            throw new ArithmeticException("division by zero");
2010        }
2011        C c = S.leadingBaseCoefficient();
2012        if (!c.isUnit()) {
2013            throw new ArithmeticException("lbc not invertible " + c);
2014        }
2015        C ci = c.inverse();
2016        assert (ring.nvar == S.ring.nvar);
2017        ExpVector e = S.leadingExpVector();
2018        GenPolynomial<C> h;
2019        GenPolynomial<C> r = this.copy();
2020        while (!r.isZERO()) {
2021            ExpVector f = r.leadingExpVector();
2022            if (f.multipleOf(e)) {
2023                C a = r.leadingBaseCoefficient();
2024                ExpVector g = f.subtract(e);
2025                //logger.info("red div = {}", e);
2026                a = a.multiply(ci);
2027                h = S.multiply(a, g);
2028                r = r.subtract(h);
2029                assert (!f.equals(r.leadingExpVector())) : "leadingExpVector not descending: " + f;
2030            } else {
2031                break;
2032            }
2033        }
2034        return r;
2035    }
2036
2037
2038    /**
2039     * GenPolynomial greatest common divisor. Only for univariate polynomials
2040     * over fields.
2041     * @param S GenPolynomial.
2042     * @return gcd(this,S).
2043     */
2044    public GenPolynomial<C> gcd(GenPolynomial<C> S) {
2045        if (S == null || S.isZERO()) {
2046            return this;
2047        }
2048        if (this.isZERO()) {
2049            return S;
2050        }
2051        if (ring.nvar != 1) {
2052            throw new IllegalArgumentException("not univariate polynomials" + ring);
2053        }
2054        GenPolynomial<C> x;
2055        GenPolynomial<C> q = this;
2056        GenPolynomial<C> r = S;
2057        while (!r.isZERO()) {
2058            x = q.remainder(r);
2059            q = r;
2060            r = x;
2061        }
2062        return q.monic(); // normalize
2063    }
2064
2065
2066    /**
2067     * GenPolynomial extended greatest common divisor. Only for univariate
2068     * polynomials over fields.
2069     * @param S GenPolynomial.
2070     * @return [ gcd(this,S), a, b ] with a*this + b*S = gcd(this,S).
2071     */
2072    @SuppressWarnings("unchecked")
2073    public GenPolynomial<C>[] egcd(GenPolynomial<C> S) {
2074        GenPolynomial<C>[] ret = new GenPolynomial[3];
2075        ret[0] = null;
2076        ret[1] = null;
2077        ret[2] = null;
2078        if (S == null || S.isZERO()) {
2079            ret[0] = this;
2080            ret[1] = this.ring.getONE();
2081            ret[2] = this.ring.getZERO();
2082            return ret;
2083        }
2084        if (this.isZERO()) {
2085            ret[0] = S;
2086            ret[1] = this.ring.getZERO();
2087            ret[2] = this.ring.getONE();
2088            return ret;
2089        }
2090        if (ring.nvar != 1) {
2091            throw new IllegalArgumentException(
2092                            this.getClass().getName() + " not univariate polynomials" + ring);
2093        }
2094        if (this.isConstant() && S.isConstant()) {
2095            C t = this.leadingBaseCoefficient();
2096            C s = S.leadingBaseCoefficient();
2097            C[] gg = t.egcd(s);
2098            //System.out.println("coeff gcd = " + Arrays.toString(gg));
2099            GenPolynomial<C> z = this.ring.getZERO();
2100            ret[0] = z.sum(gg[0]);
2101            ret[1] = z.sum(gg[1]);
2102            ret[2] = z.sum(gg[2]);
2103            return ret;
2104        }
2105        GenPolynomial<C>[] qr;
2106        GenPolynomial<C> q = this;
2107        GenPolynomial<C> r = S;
2108        GenPolynomial<C> c1 = ring.getONE().copy();
2109        GenPolynomial<C> d1 = ring.getZERO().copy();
2110        GenPolynomial<C> c2 = ring.getZERO().copy();
2111        GenPolynomial<C> d2 = ring.getONE().copy();
2112        GenPolynomial<C> x1;
2113        GenPolynomial<C> x2;
2114        while (!r.isZERO()) {
2115            qr = q.quotientRemainder(r);
2116            q = qr[0];
2117            x1 = c1.subtract(q.multiply(d1));
2118            x2 = c2.subtract(q.multiply(d2));
2119            c1 = d1;
2120            c2 = d2;
2121            d1 = x1;
2122            d2 = x2;
2123            q = r;
2124            r = qr[1];
2125        }
2126        // normalize ldcf(q) to 1, i.e. make monic
2127        C g = q.leadingBaseCoefficient();
2128        if (g.isUnit()) {
2129            C h = g.inverse();
2130            q = q.multiplyLeft(h);
2131            c1 = c1.multiplyLeft(h);
2132            c2 = c2.multiplyLeft(h);
2133        }
2134        //assert ( ((c1.multiply(this)).sum( c2.multiply(S)).equals(q) )); 
2135        ret[0] = q;
2136        ret[1] = c1;
2137        ret[2] = c2;
2138        return ret;
2139    }
2140
2141
2142    /**
2143     * GenPolynomial half extended greatest common divisor. Only for univariate
2144     * polynomials over fields.
2145     * @param S GenPolynomial.
2146     * @return [ gcd(this,S), a ] with a*this + b*S = gcd(this,S).
2147     */
2148    @SuppressWarnings("unchecked")
2149    public GenPolynomial<C>[] hegcd(GenPolynomial<C> S) {
2150        GenPolynomial<C>[] ret = new GenPolynomial[2];
2151        ret[0] = null;
2152        ret[1] = null;
2153        if (S == null || S.isZERO()) {
2154            ret[0] = this;
2155            ret[1] = this.ring.getONE();
2156            return ret;
2157        }
2158        if (this.isZERO()) {
2159            ret[0] = S;
2160            return ret;
2161        }
2162        if (ring.nvar != 1) {
2163            throw new IllegalArgumentException(
2164                            this.getClass().getName() + " not univariate polynomials" + ring);
2165        }
2166        GenPolynomial<C>[] qr;
2167        GenPolynomial<C> q = this;
2168        GenPolynomial<C> r = S;
2169        GenPolynomial<C> c1 = ring.getONE().copy();
2170        GenPolynomial<C> d1 = ring.getZERO().copy();
2171        GenPolynomial<C> x1;
2172        while (!r.isZERO()) {
2173            qr = q.quotientRemainder(r);
2174            q = qr[0];
2175            x1 = c1.subtract(q.multiply(d1));
2176            c1 = d1;
2177            d1 = x1;
2178            q = r;
2179            r = qr[1];
2180        }
2181        // normalize ldcf(q) to 1, i.e. make monic
2182        C g = q.leadingBaseCoefficient();
2183        if (g.isUnit()) {
2184            C h = g.inverse();
2185            q = q.multiplyLeft(h);
2186            c1 = c1.multiplyLeft(h);
2187        }
2188        //assert ( ((c1.multiply(this)).remainder(S).equals(q) )); 
2189        ret[0] = q;
2190        ret[1] = c1;
2191        return ret;
2192    }
2193
2194
2195    /**
2196     * GenPolynomial inverse. Required by RingElem. Throws not invertible
2197     * exception.
2198     */
2199    public GenPolynomial<C> inverse() {
2200        if (isUnit()) { // only possible if ldbcf is unit
2201            C c = leadingBaseCoefficient().inverse();
2202            return ring.getONE().multiply(c);
2203        }
2204        throw new NotInvertibleException("element not invertible " + this + " :: " + ring);
2205    }
2206
2207
2208    /**
2209     * GenPolynomial modular inverse. Only for univariate polynomials over
2210     * fields.
2211     * @param m GenPolynomial.
2212     * @return a with with a*this = 1 mod m.
2213     */
2214    public GenPolynomial<C> modInverse(GenPolynomial<C> m) {
2215        if (this.isZERO()) {
2216            throw new NotInvertibleException("zero is not invertible");
2217        }
2218        GenPolynomial<C>[] hegcd = this.hegcd(m);
2219        GenPolynomial<C> a = hegcd[0];
2220        if (!a.isUnit()) { // gcd != 1
2221            throw new AlgebraicNotInvertibleException("element not invertible, gcd != 1", m, a, m.divide(a));
2222        }
2223        GenPolynomial<C> b = hegcd[1];
2224        if (b.isZERO()) { // when m divides this, e.g. m.isUnit()
2225            throw new NotInvertibleException("element not invertible, divisible by modul");
2226        }
2227        return b;
2228    }
2229
2230
2231    /**
2232     * GenPolynomial greatest common divisor. Only for univariate polynomials
2233     * over fields.
2234     * @param S GenPolynomial.
2235     * @return right gcd(this,S).
2236     */
2237    public GenPolynomial<C> rightGcd(GenPolynomial<C> S) {
2238        if (S == null || S.isZERO()) {
2239            return this;
2240        }
2241        if (this.isZERO()) {
2242            return S;
2243        }
2244        if (ring.nvar != 1) {
2245            throw new IllegalArgumentException("not univariate polynomials" + ring);
2246        }
2247        GenPolynomial<C> x;
2248        GenPolynomial<C> q = this;
2249        GenPolynomial<C> r = S;
2250        while (!r.isZERO()) {
2251            x = q.rightRemainder(r);
2252            q = r;
2253            r = x;
2254        }
2255        return q.monicRight(); // normalize
2256    }
2257
2258
2259    /**
2260     * Extend variables. Used e.g. in module embedding. Extend all ExpVectors by
2261     * i elements and multiply by x_j^k.
2262     * @param pfac extended polynomial ring factory (by i variables).
2263     * @param j index of variable to be used for multiplication.
2264     * @param k exponent for x_j.
2265     * @return extended polynomial.
2266     */
2267    public GenPolynomial<C> extend(GenPolynomialRing<C> pfac, int j, long k) {
2268        if (ring.equals(pfac)) { // nothing to do
2269            return this;
2270        }
2271        GenPolynomial<C> Cp = pfac.getZERO().copy();
2272        if (this.isZERO()) {
2273            return Cp;
2274        }
2275        int i = pfac.nvar - ring.nvar;
2276        Map<ExpVector, C> C = Cp.val; //getMap();
2277        Map<ExpVector, C> A = val;
2278        for (Map.Entry<ExpVector, C> y : A.entrySet()) {
2279            ExpVector e = y.getKey();
2280            C a = y.getValue();
2281            ExpVector f = e.extend(i, j, k);
2282            C.put(f, a);
2283        }
2284        return Cp;
2285    }
2286
2287
2288    /**
2289     * Extend lower variables. Used e.g. in module embedding. Extend all
2290     * ExpVectors by i lower elements and multiply by x_j^k.
2291     * @param pfac extended polynomial ring factory (by i variables).
2292     * @param j index of variable to be used for multiplication.
2293     * @param k exponent for x_j.
2294     * @return extended polynomial.
2295     */
2296    public GenPolynomial<C> extendLower(GenPolynomialRing<C> pfac, int j, long k) {
2297        if (ring.equals(pfac)) { // nothing to do
2298            return this;
2299        }
2300        GenPolynomial<C> Cp = pfac.getZERO().copy();
2301        if (this.isZERO()) {
2302            return Cp;
2303        }
2304        int i = pfac.nvar - ring.nvar;
2305        Map<ExpVector, C> C = Cp.val; //getMap();
2306        Map<ExpVector, C> A = val;
2307        for (Map.Entry<ExpVector, C> y : A.entrySet()) {
2308            ExpVector e = y.getKey();
2309            C a = y.getValue();
2310            ExpVector f = e.extendLower(i, j, k);
2311            C.put(f, a);
2312        }
2313        return Cp;
2314    }
2315
2316
2317    /**
2318     * Contract variables. Used e.g. in module embedding. Remove i elements of
2319     * each ExpVector.
2320     * @param pfac contracted polynomial ring factory (by i variables).
2321     * @return Map of exponents and contracted polynomials. <b>Note:</b> could
2322     *         return SortedMap
2323     */
2324    public Map<ExpVector, GenPolynomial<C>> contract(GenPolynomialRing<C> pfac) {
2325        GenPolynomial<C> zero = pfac.getZERO(); //not pfac.coFac;
2326        TermOrder t = new TermOrder(TermOrder.INVLEX);
2327        Map<ExpVector, GenPolynomial<C>> B = new TreeMap<ExpVector, GenPolynomial<C>>(
2328                        t.getAscendComparator());
2329        if (this.isZERO()) {
2330            return B;
2331        }
2332        int i = ring.nvar - pfac.nvar;
2333        Map<ExpVector, C> A = val;
2334        for (Map.Entry<ExpVector, C> y : A.entrySet()) {
2335            ExpVector e = y.getKey();
2336            C a = y.getValue();
2337            ExpVector f = e.contract(0, i);
2338            ExpVector g = e.contract(i, e.length() - i);
2339            GenPolynomial<C> p = B.get(f);
2340            if (p == null) {
2341                p = zero;
2342            }
2343            p = p.sum(a, g);
2344            B.put(f, p);
2345        }
2346        return B;
2347    }
2348
2349
2350    /**
2351     * Contract variables to coefficient polynomial. Remove i elements of each
2352     * ExpVector, removed elements must be zero.
2353     * @param pfac contracted polynomial ring factory (by i variables).
2354     * @return contracted coefficient polynomial.
2355     */
2356    public GenPolynomial<C> contractCoeff(GenPolynomialRing<C> pfac) {
2357        Map<ExpVector, GenPolynomial<C>> ms = contract(pfac);
2358        GenPolynomial<C> c = pfac.getZERO();
2359        for (Map.Entry<ExpVector, GenPolynomial<C>> m : ms.entrySet()) {
2360            if (m.getKey().isZERO()) {
2361                c = m.getValue();
2362            } else {
2363                throw new RuntimeException("wrong coefficient contraction " + m + ", pol =  " + c);
2364            }
2365        }
2366        return c;
2367    }
2368
2369
2370    /**
2371     * Extend univariate to multivariate polynomial. This is an univariate
2372     * polynomial in variable i of the polynomial ring, it is extended to the
2373     * given polynomial ring.
2374     * @param pfac extended polynomial ring factory.
2375     * @param i index of the variable of this polynomial in pfac.
2376     * @return extended multivariate polynomial.
2377     */
2378    public GenPolynomial<C> extendUnivariate(GenPolynomialRing<C> pfac, int i) {
2379        if (i < 0 || pfac.nvar < i) {
2380            throw new IllegalArgumentException("index " + i + "out of range " + pfac.nvar);
2381        }
2382        if (ring.nvar != 1) {
2383            throw new IllegalArgumentException("polynomial not univariate " + ring.nvar);
2384        }
2385        if (this.isONE()) {
2386            return pfac.getONE();
2387        }
2388        int j = pfac.nvar - 1 - i;
2389        GenPolynomial<C> Cp = pfac.getZERO().copy();
2390        if (this.isZERO()) {
2391            return Cp;
2392        }
2393        Map<ExpVector, C> C = Cp.val; //getMap();
2394        Map<ExpVector, C> A = val;
2395        for (Map.Entry<ExpVector, C> y : A.entrySet()) {
2396            ExpVector e = y.getKey();
2397            long n = e.getVal(0);
2398            C a = y.getValue();
2399            ExpVector f = ExpVector.create(pfac.nvar, j, n);
2400            C.put(f, a); // assert not contained
2401        }
2402        return Cp;
2403    }
2404
2405
2406    /**
2407     * Make homogeneous.
2408     * @param pfac extended polynomial ring factory (by 1 variable).
2409     * @return homogeneous polynomial.
2410     */
2411    public GenPolynomial<C> homogenize(GenPolynomialRing<C> pfac) {
2412        if (ring.equals(pfac)) { // not implemented
2413            throw new UnsupportedOperationException("case with same ring not implemented");
2414        }
2415        GenPolynomial<C> Cp = pfac.getZERO().copy();
2416        if (this.isZERO()) {
2417            return Cp;
2418        }
2419        long deg = totalDegree();
2420        //int i = pfac.nvar - ring.nvar;
2421        Map<ExpVector, C> C = Cp.val; //getMap();
2422        Map<ExpVector, C> A = val;
2423        for (Map.Entry<ExpVector, C> y : A.entrySet()) {
2424            ExpVector e = y.getKey();
2425            C a = y.getValue();
2426            long d = deg - e.totalDeg();
2427            ExpVector f = e.extend(1, 0, d);
2428            C.put(f, a);
2429        }
2430        return Cp;
2431    }
2432
2433
2434    /**
2435     * Dehomogenize.
2436     * @param pfac contracted polynomial ring factory (by 1 variable).
2437     * @return in homogeneous polynomial.
2438     */
2439    public GenPolynomial<C> deHomogenize(GenPolynomialRing<C> pfac) {
2440        if (ring.equals(pfac)) { // not implemented
2441            throw new UnsupportedOperationException("case with same ring not implemented");
2442        }
2443        GenPolynomial<C> Cp = pfac.getZERO().copy();
2444        if (this.isZERO()) {
2445            return Cp;
2446        }
2447        Map<ExpVector, C> C = Cp.val; //getMap();
2448        Map<ExpVector, C> A = val;
2449        for (Map.Entry<ExpVector, C> y : A.entrySet()) {
2450            ExpVector e = y.getKey();
2451            C a = y.getValue();
2452            ExpVector f = e.contract(1, pfac.nvar);
2453            C.put(f, a);
2454        }
2455        return Cp;
2456    }
2457
2458
2459    /**
2460     * Reverse variables. Used e.g. in opposite rings.
2461     * @return polynomial with reversed variables.
2462     */
2463    public GenPolynomial<C> reverse(GenPolynomialRing<C> oring) {
2464        GenPolynomial<C> Cp = oring.getZERO().copy();
2465        if (this.isZERO()) {
2466            return Cp;
2467        }
2468        int k = -1;
2469        if (oring.tord.getEvord2() != 0 && oring.partial) {
2470            k = oring.tord.getSplit();
2471        }
2472
2473        Map<ExpVector, C> C = Cp.val; //getMap();
2474        Map<ExpVector, C> A = val;
2475        ExpVector f;
2476        for (Map.Entry<ExpVector, C> y : A.entrySet()) {
2477            ExpVector e = y.getKey();
2478            if (k >= 0) {
2479                f = e.reverse(k);
2480            } else {
2481                f = e.reverse();
2482            }
2483            C a = y.getValue();
2484            C.put(f, a);
2485        }
2486        if (oring.coFac.isCommutative()) {
2487            return Cp;
2488        }
2489        if (oring.coFac.getONE() instanceof StarRingElem) {
2490            Cp = PolyUtil.<C> conjugateCoeff(Cp);
2491        }
2492        // other coFac ignore
2493        return Cp;
2494    }
2495
2496
2497    /**
2498     * GenPolynomial inflate. Only for univariate polynomials over fields.
2499     * @param e exponent.
2500     * @return this(x**e)
2501     */
2502    public GenPolynomial<C> inflate(long e) {
2503        if (e == 1) {
2504            return this;
2505        }
2506        if (this.isZERO()) {
2507            return this;
2508        }
2509        if (ring.nvar != 1) {
2510            throw new IllegalArgumentException(
2511                            this.getClass().getName() + " not univariate polynomial" + ring);
2512        }
2513        GenPolynomial<C> Cp = ring.getZERO().copy();
2514        Map<ExpVector, C> C = Cp.val; //getMap();
2515        Map<ExpVector, C> A = val;
2516        ExpVector f;
2517        for (Map.Entry<ExpVector, C> y : A.entrySet()) {
2518            ExpVector g = y.getKey();
2519            f = g.scalarMultiply(e);
2520            C a = y.getValue();
2521            C.put(f, a);
2522        }
2523        return Cp;
2524    }
2525
2526
2527    /**
2528     * Iterator over coefficients.
2529     * @return val.values().iterator().
2530     */
2531    public Iterator<C> coefficientIterator() {
2532        return val.values().iterator();
2533    }
2534
2535
2536    /**
2537     * Iterator over exponents.
2538     * @return val.keySet().iterator().
2539     */
2540    public Iterator<ExpVector> exponentIterator() {
2541        return val.keySet().iterator();
2542    }
2543
2544
2545    /**
2546     * Iterator over monomials.
2547     * @return a PolyIterator.
2548     */
2549    public Iterator<Monomial<C>> iterator() {
2550        return new PolyIterator<C>(val);
2551    }
2552
2553
2554    /**
2555     * Spliterator over monomials.
2556     * @return a PolySpliterator.
2557     */
2558    public Spliterator<Monomial<C>> spliterator() {
2559        return new PolySpliterator<C>(val);
2560    }
2561
2562
2563    /**
2564     * Map a unary function to the coefficients.
2565     * @param f evaluation functor.
2566     * @return new polynomial with coefficients f(this.coefficients).
2567     */
2568    public GenPolynomial<C> map(final UnaryFunctor<? super C, C> f) {
2569        GenPolynomial<C> n = ring.getZERO().copy();
2570        SortedMap<ExpVector, C> nv = n.val;
2571        for (Map.Entry<ExpVector, C> m : this.val.entrySet()) {
2572            //logger.info("m = {}", m);
2573            C c = f.eval(m.getValue());
2574            if (c != null && !c.isZERO()) {
2575                nv.put(m.getKey(), c);
2576            }
2577        }
2578        return n;
2579    }
2580
2581
2582    /*
2583     * Map a unary function to the coefficients.
2584     * @param f evaluation functor.
2585     * @return new polynomial with coefficients f(this.coefficients).
2586     */
2587    GenPolynomial<C> mapWrong(final UnaryFunctor<? super C, C> f) {
2588        GenPolynomial<C> n = this.copy();
2589        SortedMap<ExpVector, C> nv = n.val;
2590        for (Map.Entry<ExpVector, C> m : nv.entrySet()) {
2591            //logger.info("m = {}", m);
2592            C c = f.eval(m.getValue());
2593            if (c != null && !c.isZERO()) {
2594                m.setValue(c); // not okay
2595            } else {
2596                // not possible nv.remove(m.getKey());
2597            }
2598        }
2599        return n;
2600    }
2601
2602
2603    /**
2604     * Map a function to the polynomial stream entries.
2605     * @param f evaluation functor.
2606     * @return new polynomial with f(this.entries).
2607     */
2608    public GenPolynomial<C> mapOnStream(
2609                    final Function<? super Map.Entry<ExpVector, C>, ? extends Map.Entry<ExpVector, C>> f) {
2610        return mapOnStream(f, false);
2611    }
2612
2613
2614    /**
2615     * Map a function to the polynomial stream entries.
2616     * @param f evaluation functor.
2617     * @return new polynomial with f(this.entries).
2618     */
2619    public GenPolynomial<C> mapOnStream(
2620                    final Function<? super Map.Entry<ExpVector, C>, ? extends Map.Entry<ExpVector, C>> f,
2621                    boolean parallel) {
2622        Stream<Map.Entry<ExpVector, C>> st;
2623        if (parallel) {
2624            st = val.entrySet().parallelStream();
2625        } else {
2626            st = val.entrySet().stream();
2627        }
2628        Map<ExpVector, C> m = st.map(f).filter(me -> !me.getValue().isZERO())
2629                        .collect(Collectors.toMap(me -> me.getKey(), me -> me.getValue()));
2630        //Stream<Map.Entry<ExpVector,C>> stp = st.map(f);
2631        //Stream<Map.Entry<ExpVector,C>> stf = stp.filter(me -> !me.getValue().isZERO());
2632        //Map<ExpVector,C> m = stf.collect(Collectors.toMap(me -> me.getKey(), me -> me.getValue()));
2633        return new GenPolynomial<C>(ring, m);
2634    }
2635
2636
2637    /**
2638     * Returns the number of bits in the representation of this polynomial.
2639     * @return number of bits in the representation of this polynomial,
2640     *         including sign bits.
2641     */
2642    public long bitLength() {
2643        if (blen < 0L) {
2644            long n = 0L;
2645            for (Monomial<C> m : this) {
2646                n += m.e.bitLength();
2647                //n += m.c.bitLength(); // todo add bitLength to Element
2648                try { // hack
2649                    Method method = m.c.getClass().getMethod("bitLength", (Class<?>[]) null);
2650                    n += (Long) method.invoke(m.c, (Object[]) null);
2651                } catch (NoSuchMethodException e) {
2652                    logger.error("Exception, class: {}", m.c.getClass());
2653                    throw new RuntimeException(e);
2654                } catch (IllegalAccessException e) {
2655                    logger.error("Exception, class: {}", m.c.getClass());
2656                    throw new RuntimeException(e);
2657                } catch (InvocationTargetException e) {
2658                    logger.error("Exception, class: {}", m.c.getClass());
2659                    throw new RuntimeException(e);
2660                }
2661            }
2662            blen = n;
2663            //System.out.println("bitLength(poly) = " + blen);
2664        }
2665        return blen;
2666    }
2667
2668    //private void writeObject(java.io.ObjectOutputStream out) throws IOException {
2669    //    out.defaultWriteObject();
2670    //}
2671
2672
2673    private void readObject(java.io.ObjectInputStream in) throws IOException, ClassNotFoundException {
2674        in.defaultReadObject();
2675        blen = -1;
2676        hash = -1;
2677    }
2678}