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<C> 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<C> 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<C> 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<C> 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<C> 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<C> 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 > 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) < 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}