001/* 002 * $Id: GenWordPolynomial.java 4225 2012-09-29 20:27:56Z kredel $ 003 */ 004 005package edu.jas.poly; 006 007 008import java.util.Collections; 009import java.util.Iterator; 010import java.util.Map; 011import java.util.SortedMap; 012import java.util.TreeMap; 013 014import org.apache.log4j.Logger; 015 016import edu.jas.kern.PreemptingException; 017import edu.jas.structure.NotInvertibleException; 018import edu.jas.structure.RingElem; 019import edu.jas.structure.UnaryFunctor; 020 021 022/** 023 * GenWordPolynomial generic polynomials implementing RingElem. Non-commutative 024 * string polynomials over C. Objects of this class are intended to be 025 * immutable. The implementation is based on TreeMap respectively SortedMap from 026 * words to coefficients. Only the coefficients are modeled with generic 027 * types, the "exponents" are fixed to Word. C can also be a non integral domain, 028 * e.g. a ModInteger, i.e. it may contain zero divisors, since multiply() does 029 * check for zeros. 030 * @param <C> coefficient type 031 * @author Heinz Kredel 032 */ 033public final class GenWordPolynomial<C extends RingElem<C>> 034 implements RingElem<GenWordPolynomial<C>>, Iterable<WordMonomial<C>> { 035 036 037 /** 038 * The factory for the polynomial ring. 039 */ 040 public final GenWordPolynomialRing<C> ring; 041 042 043 /** 044 * The data structure for polynomials. 045 */ 046 final SortedMap<Word, C> val; // do not change to TreeMap 047 048 049 private static final Logger logger = Logger.getLogger(GenWordPolynomial.class); 050 051 052 private final boolean debug = logger.isDebugEnabled(); 053 054 055 // protected GenWordPolynomial() { ring = null; val = null; } // don't use 056 057 058 /** 059 * Private constructor for GenWordPolynomial. 060 * @param r polynomial ring factory. 061 * @param t TreeMap with correct ordering. 062 */ 063 private GenWordPolynomial(GenWordPolynomialRing<C> r, TreeMap<Word, C> t) { 064 ring = r; 065 val = t; 066 if (ring.checkPreempt) { 067 if (Thread.currentThread().isInterrupted()) { 068 logger.debug("throw PreemptingException"); 069 throw new PreemptingException(); 070 } 071 } 072 } 073 074 075 /** 076 * Constructor for zero GenWordPolynomial. 077 * @param r polynomial ring factory. 078 */ 079 public GenWordPolynomial(GenWordPolynomialRing<C> r) { 080 this(r, new TreeMap<Word, C>(r.alphabet.getDescendComparator())); 081 } 082 083 084 /** 085 * Constructor for GenWordPolynomial c * x<sup>e</sup>. 086 * @param r polynomial ring factory. 087 * @param c coefficient. 088 * @param e word. 089 */ 090 public GenWordPolynomial(GenWordPolynomialRing<C> r, C c, Word e) { 091 this(r); 092 if (!c.isZERO()) { 093 val.put(e, c); 094 } 095 } 096 097 098 /** 099 * Constructor for GenWordPolynomial c * x<sup>0</sup>. 100 * @param r polynomial ring factory. 101 * @param c coefficient. 102 */ 103 public GenWordPolynomial(GenWordPolynomialRing<C> r, C c) { 104 this(r, c, r.wone); 105 } 106 107 108 /** 109 * Constructor for GenWordPolynomial x<sup>e</sup>. 110 * @param r polynomial ring factory. 111 * @param e word. 112 */ 113 public GenWordPolynomial(GenWordPolynomialRing<C> r, Word e) { 114 this(r, r.coFac.getONE(), e); 115 } 116 117 118 /** 119 * Constructor for GenWordPolynomial. 120 * @param r polynomial ring factory. 121 * @param v the SortedMap of some other polynomial. 122 */ 123 protected GenWordPolynomial(GenWordPolynomialRing<C> r, SortedMap<Word, C> v) { 124 this(r); 125 val.putAll(v); // assume no zero coefficients 126 } 127 128 129 /** 130 * Get the corresponding element factory. 131 * @return factory for this Element. 132 * @see edu.jas.structure.Element#factory() 133 */ 134 public GenWordPolynomialRing<C> factory() { 135 return ring; 136 } 137 138 139 /** 140 * Copy this GenWordPolynomial. 141 * @return copy of this. 142 */ 143 public GenWordPolynomial<C> copy() { 144 return new GenWordPolynomial<C>(ring, this.val); 145 } 146 147 148 /** 149 * Length of GenWordPolynomial. 150 * @return number of coefficients of this GenWordPolynomial. 151 */ 152 public int length() { 153 return val.size(); 154 } 155 156 157 /** 158 * Word to coefficient map of GenWordPolynomial. 159 * @return val as unmodifiable SortedMap. 160 */ 161 public SortedMap<Word, C> getMap() { 162 // return val; 163 return Collections.<Word, C> unmodifiableSortedMap(val); 164 } 165 166 167 /** 168 * Put an Word to coefficient entry into the internal map of this 169 * GenWordPolynomial. <b>Note:</b> Do not use this method unless you are 170 * constructing a new polynomial. this is modified and breaks the 171 * immutability promise of this class. 172 * @param c coefficient. 173 * @param e word. 174 */ 175 public void doPutToMap(Word e, C c) { 176 if (debug) { 177 C a = val.get(e); 178 if (a != null) { 179 logger.error("map entry exists " + e + " to " + a + " new " + c); 180 } 181 } 182 if (!c.isZERO()) { 183 val.put(e, c); 184 } 185 } 186 187 188 /** 189 * Put an a sorted map of words to coefficients into the internal map of 190 * this GenWordPolynomial. <b>Note:</b> Do not use this method unless you 191 * are constructing a new polynomial. this is modified and breaks the 192 * immutability promise of this class. 193 * @param vals sorted map of wordss and coefficients. 194 */ 195 public void doPutToMap(SortedMap<Word, C> vals) { 196 for (Map.Entry<Word, C> me : vals.entrySet()) { 197 Word e = me.getKey(); 198 if (debug) { 199 C a = val.get(e); 200 if (a != null) { 201 logger.error("map entry exists " + e + " to " + a + " new " + me.getValue()); 202 } 203 } 204 C c = me.getValue(); 205 if (!c.isZERO()) { 206 val.put(e, c); 207 } 208 } 209 } 210 211 212 /** 213 * String representation of GenWordPolynomial. 214 * @see java.lang.Object#toString() 215 */ 216 @Override 217 public String toString() { 218 if (isZERO()) { 219 return "0"; 220 } 221 if (isONE()) { 222 return "1"; 223 } 224 StringBuffer s = new StringBuffer(); 225 if (val.size() > 1) { 226 s.append("( "); 227 } 228 boolean parenthesis = false; 229 boolean first = true; 230 for (Map.Entry<Word, C> m : val.entrySet()) { 231 C c = m.getValue(); 232 if (first) { 233 first = false; 234 } else { 235 if (c.signum() < 0) { 236 s.append(" - "); 237 c = c.negate(); 238 } else { 239 s.append(" + "); 240 } 241 } 242 Word e = m.getKey(); 243 if (!c.isONE() || e.isONE()) { 244 if (parenthesis) { 245 s.append("( "); 246 } 247 s.append(c.toString()); 248 if (parenthesis) { 249 s.append(" )"); 250 } 251 if (!e.isONE()) { 252 s.append(" "); 253 } 254 } 255 s.append(e.toString()); 256 } 257 if (val.size() > 1) { 258 s.append(" )"); 259 } 260 return s.toString(); 261 } 262 263 264 /** 265 * Get a scripting compatible string representation. 266 * @return script compatible representation for this Element. 267 * @see edu.jas.structure.Element#toScript() 268 */ 269 //JAVA6only: @Override 270 public String toScript() { 271 if (isZERO()) { 272 return "0"; 273 } 274 if (isONE()) { 275 return "1"; 276 } 277 StringBuffer s = new StringBuffer(); 278 if (val.size() > 1) { 279 s.append("( "); 280 } 281 boolean parenthesis = false; 282 boolean first = true; 283 for (Map.Entry<Word, C> m : val.entrySet()) { 284 C c = m.getValue(); 285 if (first) { 286 first = false; 287 } else { 288 if (c.signum() < 0) { 289 s.append(" - "); 290 c = c.negate(); 291 } else { 292 s.append(" + "); 293 } 294 } 295 Word e = m.getKey(); 296 if (!c.isONE() || e.isONE()) { 297 if (parenthesis) { 298 s.append("( "); 299 } 300 s.append(c.toScript()); 301 if (parenthesis) { 302 s.append(" )"); 303 } 304 if (!e.isONE()) { 305 s.append(" * "); 306 } 307 } 308 s.append(e.toScript()); 309 } 310 if (val.size() > 1) { 311 s.append(" )"); 312 } 313 return s.toString(); 314 } 315 316 317 /** 318 * Get a scripting compatible string representation of the factory. 319 * @return script compatible representation for this ElemFactory. 320 * @see edu.jas.structure.Element#toScriptFactory() 321 */ 322 //JAVA6only: @Override 323 public String toScriptFactory() { 324 // Python case 325 return factory().toScript(); 326 } 327 328 329 /** 330 * Is GenWordPolynomial<C> zero. 331 * @return If this is 0 then true is returned, else false. 332 * @see edu.jas.structure.RingElem#isZERO() 333 */ 334 public boolean isZERO() { 335 return (val.size() == 0); 336 } 337 338 339 /** 340 * Is GenWordPolynomial<C> one. 341 * @return If this is 1 then true is returned, else false. 342 * @see edu.jas.structure.RingElem#isONE() 343 */ 344 public boolean isONE() { 345 if (val.size() != 1) { 346 return false; 347 } 348 C c = val.get(ring.wone); 349 if (c == null) { 350 return false; 351 } 352 return c.isONE(); 353 } 354 355 356 /** 357 * Is GenWordPolynomial<C> a unit. 358 * @return If this is a unit then true is returned, else false. 359 * @see edu.jas.structure.RingElem#isUnit() 360 */ 361 public boolean isUnit() { 362 if (val.size() != 1) { 363 return false; 364 } 365 C c = val.get(ring.wone); 366 if (c == null) { 367 return false; 368 } 369 return c.isUnit(); 370 } 371 372 373 /** 374 * Is GenWordPolynomial<C> a constant. 375 * @return If this is a constant polynomial then true is returned, else 376 * false. 377 */ 378 public boolean isConstant() { 379 if (val.size() != 1) { 380 return false; 381 } 382 C c = val.get(ring.wone); 383 if (c == null) { 384 return false; 385 } 386 return true; 387 } 388 389 390 /** 391 * Is GenWordPolynomial<C> homogeneous. 392 * @return true, if this is homogeneous, else false. 393 */ 394 public boolean isHomogeneous() { 395 if (val.size() <= 1) { 396 return true; 397 } 398 long deg = -1; 399 for (Word e : val.keySet()) { 400 if (deg < 0) { 401 deg = e.degree(); 402 } else if (deg != e.degree()) { 403 return false; 404 } 405 } 406 return true; 407 } 408 409 410 /** 411 * Comparison with any other object. 412 * @see java.lang.Object#equals(java.lang.Object) 413 */ 414 @Override 415 @SuppressWarnings("unchecked") 416 public boolean equals(Object B) { 417 if (!(B instanceof GenWordPolynomial)) { 418 return false; 419 } 420 GenWordPolynomial<C> a = null; 421 try { 422 a = (GenWordPolynomial<C>) B; 423 } catch (ClassCastException ignored) { 424 } 425 if (a == null) { 426 return false; 427 } 428 return this.compareTo(a) == 0; 429 } 430 431 432 /** 433 * Hash code for this polynomial. 434 * @see java.lang.Object#hashCode() 435 */ 436 @Override 437 public int hashCode() { 438 int h; 439 h = (ring.hashCode() << 27); 440 h += val.hashCode(); 441 return h; 442 } 443 444 445 /** 446 * GenWordPolynomial comparison. 447 * @param b GenWordPolynomial. 448 * @return sign(this-b). 449 */ 450 public int compareTo(GenWordPolynomial<C> b) { 451 if (b == null) { 452 return 1; 453 } 454 SortedMap<Word, C> av = this.val; 455 SortedMap<Word, C> bv = b.val; 456 Iterator<Map.Entry<Word, C>> ai = av.entrySet().iterator(); 457 Iterator<Map.Entry<Word, C>> bi = bv.entrySet().iterator(); 458 int s = 0; 459 int c = 0; 460 while (ai.hasNext() && bi.hasNext()) { 461 Map.Entry<Word, C> aie = ai.next(); 462 Map.Entry<Word, C> bie = bi.next(); 463 Word ae = aie.getKey(); 464 Word be = bie.getKey(); 465 s = ae.compareTo(be); 466 //System.out.println("s = " + s + ", " + ae + ", " +be); 467 if (s != 0) { 468 return s; 469 } 470 if (c == 0) { 471 C ac = aie.getValue(); //av.get(ae); 472 C bc = bie.getValue(); //bv.get(be); 473 c = ac.compareTo(bc); 474 } 475 } 476 if (ai.hasNext()) { 477 return 1; 478 } 479 if (bi.hasNext()) { 480 return -1; 481 } 482 // now all keys are equal 483 return c; 484 } 485 486 487 /** 488 * GenWordPolynomial signum. 489 * @return sign(ldcf(this)). 490 */ 491 public int signum() { 492 if (this.isZERO()) { 493 return 0; 494 } 495 Word t = val.firstKey(); 496 C c = val.get(t); 497 return c.signum(); 498 } 499 500 501 /** 502 * Number of variables. 503 * @return ring.alphabet.length(). 504 */ 505 public int numberOfVariables() { 506 return ring.alphabet.length(); 507 } 508 509 510 /** 511 * Leading monomial. 512 * @return first map entry. 513 */ 514 public Map.Entry<Word, C> leadingMonomial() { 515 if (val.size() == 0) 516 return null; 517 Iterator<Map.Entry<Word, C>> ai = val.entrySet().iterator(); 518 return ai.next(); 519 } 520 521 522 /** 523 * Leading word. 524 * @return first highest word. 525 */ 526 public Word leadingWord() { 527 if (val.size() == 0) { 528 return ring.wone; // null? needs changes? 529 } 530 return val.firstKey(); 531 } 532 533 534 /** 535 * Trailing word. 536 * @return last lowest word. 537 */ 538 public Word trailingWord() { 539 if (val.size() == 0) { 540 return ring.wone; // or null ?; 541 } 542 return val.lastKey(); 543 } 544 545 546 /** 547 * Leading base coefficient. 548 * @return first coefficient. 549 */ 550 public C leadingBaseCoefficient() { 551 if (val.size() == 0) { 552 return ring.coFac.getZERO(); 553 } 554 return val.get(val.firstKey()); 555 } 556 557 558 /** 559 * Trailing base coefficient. 560 * @return coefficient of constant term. 561 */ 562 public C trailingBaseCoefficient() { 563 C c = val.get(ring.wone); 564 if (c == null) { 565 return ring.coFac.getZERO(); 566 } 567 return c; 568 } 569 570 571 /** 572 * Coefficient. 573 * @param e word. 574 * @return coefficient for given word. 575 */ 576 public C coefficient(Word e) { 577 C c = val.get(e); 578 if (c == null) { 579 c = ring.coFac.getZERO(); 580 } 581 return c; 582 } 583 584 585 /** 586 * Reductum. 587 * @return this - leading monomial. 588 */ 589 public GenWordPolynomial<C> reductum() { 590 if (val.size() <= 1) { 591 return ring.getZERO(); 592 } 593 Iterator<Word> ai = val.keySet().iterator(); 594 Word lt = ai.next(); 595 lt = ai.next(); // size > 1 596 SortedMap<Word, C> red = val.tailMap(lt); 597 return new GenWordPolynomial<C>(ring, red); 598 } 599 600 601 /** 602 * Maximal degree. 603 * @return maximal degree in any variables. 604 */ 605 public long degree() { 606 if (val.size() == 0) { 607 return 0; // 0 or -1 ?; 608 } 609 long deg = 0; 610 for (Word e : val.keySet()) { 611 long d = e.degree(); 612 if (d > deg) { 613 deg = d; 614 } 615 } 616 return deg; 617 } 618 619 620 /** 621 * GenWordPolynomial maximum norm. 622 * @return ||this||. 623 */ 624 public C maxNorm() { 625 C n = ring.getZEROCoefficient(); 626 for (C c : val.values()) { 627 C x = c.abs(); 628 if (n.compareTo(x) < 0) { 629 n = x; 630 } 631 } 632 return n; 633 } 634 635 636 /** 637 * GenWordPolynomial sum norm. 638 * @return sum of all absolute values of coefficients. 639 */ 640 public C sumNorm() { 641 C n = ring.getZEROCoefficient(); 642 for (C c : val.values()) { 643 C x = c.abs(); 644 n = n.sum(x); 645 } 646 return n; 647 } 648 649 650 /** 651 * GenWordPolynomial summation. 652 * @param S GenWordPolynomial. 653 * @return this+S. 654 */ 655 public GenWordPolynomial<C> sum(GenWordPolynomial<C> S) { 656 if (S == null) { 657 return this; 658 } 659 if (S.isZERO()) { 660 return this; 661 } 662 if (this.isZERO()) { 663 return S; 664 } 665 assert (ring.alphabet == S.ring.alphabet); 666 GenWordPolynomial<C> n = this.copy(); //new GenWordPolynomial<C>(ring, val); 667 SortedMap<Word, C> nv = n.val; 668 SortedMap<Word, C> sv = S.val; 669 for (Map.Entry<Word, C> me : sv.entrySet()) { 670 Word e = me.getKey(); 671 C y = me.getValue(); //sv.get(e); // assert y != null 672 C x = nv.get(e); 673 if (x != null) { 674 x = x.sum(y); 675 if (!x.isZERO()) { 676 nv.put(e, x); 677 } else { 678 nv.remove(e); 679 } 680 } else { 681 nv.put(e, y); 682 } 683 } 684 return n; 685 } 686 687 688 /** 689 * GenWordPolynomial addition. This method is not very efficient, since this 690 * is copied. 691 * @param a coefficient. 692 * @param e word. 693 * @return this + a e. 694 */ 695 public GenWordPolynomial<C> sum(C a, Word e) { 696 if (a == null) { 697 return this; 698 } 699 if (a.isZERO()) { 700 return this; 701 } 702 GenWordPolynomial<C> n = this.copy(); //new GenWordPolynomial<C>(ring, val); 703 SortedMap<Word, C> nv = n.val; 704 C x = nv.get(e); 705 if (x != null) { 706 x = x.sum(a); 707 if (!x.isZERO()) { 708 nv.put(e, x); 709 } else { 710 nv.remove(e); 711 } 712 } else { 713 nv.put(e, a); 714 } 715 return n; 716 } 717 718 719 /** 720 * GenWordPolynomial addition. This method is not very efficient, since this 721 * is copied. 722 * @param a coefficient. 723 * @return this + a x<sup>0</sup>. 724 */ 725 public GenWordPolynomial<C> sum(C a) { 726 return sum(a, ring.wone); 727 } 728 729 730 /** 731 * GenWordPolynomial subtraction. 732 * @param S GenWordPolynomial. 733 * @return this-S. 734 */ 735 public GenWordPolynomial<C> subtract(GenWordPolynomial<C> S) { 736 if (S == null) { 737 return this; 738 } 739 if (S.isZERO()) { 740 return this; 741 } 742 if (this.isZERO()) { 743 return S.negate(); 744 } 745 assert (ring.alphabet == S.ring.alphabet); 746 GenWordPolynomial<C> n = this.copy(); //new GenWordPolynomial<C>(ring, val); 747 SortedMap<Word, C> nv = n.val; 748 SortedMap<Word, C> sv = S.val; 749 for (Map.Entry<Word, C> me : sv.entrySet()) { 750 Word e = me.getKey(); 751 C y = me.getValue(); //sv.get(e); // assert y != null 752 C x = nv.get(e); 753 if (x != null) { 754 x = x.subtract(y); 755 if (!x.isZERO()) { 756 nv.put(e, x); 757 } else { 758 nv.remove(e); 759 } 760 } else { 761 nv.put(e, y.negate()); 762 } 763 } 764 return n; 765 } 766 767 768 /** 769 * GenWordPolynomial subtraction. This method is not very efficient, since 770 * this is copied. 771 * @param a coefficient. 772 * @param e word. 773 * @return this - a e. 774 */ 775 public GenWordPolynomial<C> subtract(C a, Word e) { 776 if (a == null) { 777 return this; 778 } 779 if (a.isZERO()) { 780 return this; 781 } 782 GenWordPolynomial<C> n = this.copy(); //new GenWordPolynomial<C>(ring, val); 783 SortedMap<Word, C> nv = n.val; 784 C x = nv.get(e); 785 if (x != null) { 786 x = x.subtract(a); 787 if (!x.isZERO()) { 788 nv.put(e, x); 789 } else { 790 nv.remove(e); 791 } 792 } else { 793 nv.put(e, a.negate()); 794 } 795 return n; 796 } 797 798 799 /** 800 * GenWordPolynomial subtract. This method is not very efficient, since this 801 * is copied. 802 * @param a coefficient. 803 * @return this + a x<sup>0</sup>. 804 */ 805 public GenWordPolynomial<C> subtract(C a) { 806 return subtract(a, ring.wone); 807 } 808 809 810 /** 811 * GenWordPolynomial negation. 812 * @return -this. 813 */ 814 public GenWordPolynomial<C> negate() { 815 GenWordPolynomial<C> n = ring.getZERO().copy(); 816 SortedMap<Word, C> v = n.val; 817 for (Map.Entry<Word, C> m : val.entrySet()) { 818 C x = m.getValue(); // != null, 0 819 v.put(m.getKey(), x.negate()); 820 } 821 return n; 822 } 823 824 825 /** 826 * GenWordPolynomial absolute value, i.e. leadingCoefficient > 0. 827 * @return abs(this). 828 */ 829 public GenWordPolynomial<C> abs() { 830 if (leadingBaseCoefficient().signum() < 0) { 831 return this.negate(); 832 } 833 return this; 834 } 835 836 837 /** 838 * GenWordPolynomial multiplication. 839 * @param S GenWordPolynomial. 840 * @return this*S. 841 */ 842 public GenWordPolynomial<C> multiply(GenWordPolynomial<C> S) { 843 if (S == null) { 844 return ring.getZERO(); 845 } 846 if (S.isZERO()) { 847 return ring.getZERO(); 848 } 849 if (this.isZERO()) { 850 return this; 851 } 852 assert (ring.alphabet == S.ring.alphabet); 853 GenWordPolynomial<C> p = ring.getZERO().copy(); 854 SortedMap<Word, C> pv = p.val; 855 for (Map.Entry<Word, C> m1 : val.entrySet()) { 856 C c1 = m1.getValue(); 857 Word e1 = m1.getKey(); 858 for (Map.Entry<Word, C> m2 : S.val.entrySet()) { 859 C c2 = m2.getValue(); 860 Word e2 = m2.getKey(); 861 C c = c1.multiply(c2); // check non zero if not domain 862 if (!c.isZERO()) { 863 Word e = e1.multiply(e2); 864 C c0 = pv.get(e); 865 if (c0 == null) { 866 pv.put(e, c); 867 } else { 868 c0 = c0.sum(c); 869 if (!c0.isZERO()) { 870 pv.put(e, c0); 871 } else { 872 pv.remove(e); 873 } 874 } 875 } 876 } 877 } 878 return p; 879 } 880 881 882 /** 883 * GenWordPolynomial left and right multiplication. Product with 884 * two polynomials. 885 * @param S GenWordPolynomial. 886 * @param T GenWordPolynomial. 887 * @return S*this*T. 888 */ 889 public GenWordPolynomial<C> multiply(GenWordPolynomial<C> S, GenWordPolynomial<C> T) { 890 if ( S.isZERO() || T.isZERO() ) { 891 return ring.getZERO(); 892 } 893 if ( S.isONE() ) { 894 return multiply(T); 895 } 896 if ( T.isONE() ) { 897 return S.multiply(this); 898 } 899 return S.multiply(this).multiply(T); 900 } 901 902 903 /** 904 * GenWordPolynomial multiplication. Product with coefficient ring element. 905 * @param s coefficient. 906 * @return this*s. 907 */ 908 public GenWordPolynomial<C> multiply(C s) { 909 if (s == null) { 910 return ring.getZERO(); 911 } 912 if (s.isZERO()) { 913 return ring.getZERO(); 914 } 915 if (this.isZERO()) { 916 return this; 917 } 918 GenWordPolynomial<C> p = ring.getZERO().copy(); 919 SortedMap<Word, C> pv = p.val; 920 for (Map.Entry<Word, C> m1 : val.entrySet()) { 921 C c1 = m1.getValue(); 922 Word e1 = m1.getKey(); 923 C c = c1.multiply(s); // check non zero if not domain 924 if (!c.isZERO()) { 925 pv.put(e1, c); // or m1.setValue( c ) 926 } 927 } 928 return p; 929 } 930 931 932 /** 933 * GenWordPolynomial multiplication. Product with coefficient ring element. 934 * @param s coefficient. 935 * @param t coefficient. 936 * @return s*this*t. 937 */ 938 public GenWordPolynomial<C> multiply(C s, C t) { 939 if (s == null || t == null) { 940 return ring.getZERO(); 941 } 942 if (s.isZERO()||t.isZERO()) { 943 return ring.getZERO(); 944 } 945 if (this.isZERO()) { 946 return this; 947 } 948 GenWordPolynomial<C> p = ring.getZERO().copy(); 949 SortedMap<Word, C> pv = p.val; 950 for (Map.Entry<Word, C> m1 : val.entrySet()) { 951 C c1 = m1.getValue(); 952 Word e = m1.getKey(); 953 C c = s.multiply(c1).multiply(t); // check non zero if not domain 954 if (!c.isZERO()) { 955 pv.put(e, c); // or m1.setValue( c ) 956 } 957 } 958 return p; 959 } 960 961 962 /** 963 * GenWordPolynomial monic, i.e. leadingCoefficient == 1. If 964 * leadingCoefficient is not invertible returns this unmodified. 965 * @return monic(this). 966 */ 967 public GenWordPolynomial<C> monic() { 968 if (this.isZERO()) { 969 return this; 970 } 971 C lc = leadingBaseCoefficient(); 972 if (!lc.isUnit()) { 973 //System.out.println("lc = "+lc); 974 return this; 975 } 976 C lm = lc.inverse(); 977 return multiply(lm); 978 } 979 980 981 /** 982 * GenWordPolynomial multiplication. Product with ring element and word. 983 * @param s coefficient. 984 * @param e left word. 985 * @return this * s e. 986 */ 987 public GenWordPolynomial<C> multiply(C s, Word e) { 988 if (s == null) { 989 return ring.getZERO(); 990 } 991 if (s.isZERO()) { 992 return ring.getZERO(); 993 } 994 if (this.isZERO()) { 995 return this; 996 } 997 GenWordPolynomial<C> p = ring.getZERO().copy(); 998 SortedMap<Word, C> pv = p.val; 999 for (Map.Entry<Word, C> m1 : val.entrySet()) { 1000 C c1 = m1.getValue(); 1001 Word e1 = m1.getKey(); 1002 C c = c1.multiply(s); // check non zero if not domain 1003 if (!c.isZERO()) { 1004 Word e2 = e1.multiply(e); 1005 pv.put(e2, c); 1006 } 1007 } 1008 return p; 1009 } 1010 1011 1012 /** 1013 * GenWordPolynomial left and right multiplication. Product with 1014 * ring element and two words. 1015 * @param e left word. 1016 * @param f right word. 1017 * @return e * this * f. 1018 */ 1019 public GenWordPolynomial<C> multiply(Word e, Word f) { 1020 if (this.isZERO()) { 1021 return this; 1022 } 1023 if (e.isONE()) { 1024 return multiply(f); 1025 } 1026 GenWordPolynomial<C> p = ring.getZERO().copy(); 1027 SortedMap<Word, C> pv = p.val; 1028 for (Map.Entry<Word, C> m1 : val.entrySet()) { 1029 C c = m1.getValue(); 1030 Word e1 = m1.getKey(); 1031 Word e2 = e.multiply(e1.multiply(f)); 1032 pv.put(e2, c); 1033 } 1034 return p; 1035 } 1036 1037 1038 /** 1039 * GenWordPolynomial left and right multiplication. Product with 1040 * ring element and two words. 1041 * @param s coefficient. 1042 * @param e left word. 1043 * @param f right word. 1044 * @return e * this * s * f. 1045 */ 1046 public GenWordPolynomial<C> multiply(C s, Word e, Word f) { 1047 if (s == null) { 1048 return ring.getZERO(); 1049 } 1050 if (s.isZERO()) { 1051 return ring.getZERO(); 1052 } 1053 if (this.isZERO()) { 1054 return this; 1055 } 1056 if (e.isONE()) { 1057 return multiply(s, f); 1058 } 1059 C c = ring.coFac.getONE(); 1060 return multiply(c,e,s,f); // sic, history 1061 } 1062 1063 1064 /** 1065 * GenWordPolynomial left and right multiplication. Product with 1066 * ring element and two words. 1067 * @param s coefficient. 1068 * @param e left word. 1069 * @param t coefficient. 1070 * @param f right word. 1071 * @return s * e * this * t * f. 1072 */ 1073 public GenWordPolynomial<C> multiply(C s, Word e, C t, Word f) { 1074 if (s == null) { 1075 return ring.getZERO(); 1076 } 1077 if (s.isZERO()) { 1078 return ring.getZERO(); 1079 } 1080 if (this.isZERO()) { 1081 return this; 1082 } 1083 GenWordPolynomial<C> p = ring.getZERO().copy(); 1084 SortedMap<Word, C> pv = p.val; 1085 for (Map.Entry<Word, C> m1 : val.entrySet()) { 1086 C c1 = m1.getValue(); 1087 C c = s.multiply(c1).multiply(t); // check non zero if not domain 1088 if (!c.isZERO()) { 1089 Word e1 = m1.getKey(); 1090 Word e2 = e.multiply(e1).multiply(f); 1091 pv.put(e2, c); 1092 } 1093 } 1094 return p; 1095 } 1096 1097 1098 /** 1099 * GenWordPolynomial multiplication. Product with word. 1100 * @param e word (!= null). 1101 * @return this * e. 1102 */ 1103 public GenWordPolynomial<C> multiply(Word e) { 1104 if (this.isZERO()) { 1105 return this; 1106 } 1107 GenWordPolynomial<C> p = ring.getZERO().copy(); 1108 SortedMap<Word, C> pv = p.val; 1109 for (Map.Entry<Word, C> m1 : val.entrySet()) { 1110 C c1 = m1.getValue(); 1111 Word e1 = m1.getKey(); 1112 Word e2 = e1.multiply(e); 1113 pv.put(e2, c1); 1114 } 1115 return p; 1116 } 1117 1118 1119 /** 1120 * GenWordPolynomial multiplication. Product with 'monomial'. 1121 * @param m 'monomial'. 1122 * @return this * m. 1123 */ 1124 public GenWordPolynomial<C> multiply(Map.Entry<Word, C> m) { 1125 if (m == null) { 1126 return ring.getZERO(); 1127 } 1128 return multiply(m.getValue(), m.getKey()); 1129 } 1130 1131 1132 /** 1133 * GenWordPolynomial division. Division by coefficient ring element. Fails, 1134 * if exact division is not possible. 1135 * @param s coefficient. 1136 * @return this/s. 1137 */ 1138 public GenWordPolynomial<C> divide(C s) { 1139 if (s == null || s.isZERO()) { 1140 throw new ArithmeticException(this.getClass().getName() + " division by zero"); 1141 } 1142 if (this.isZERO()) { 1143 return this; 1144 } 1145 //C t = s.inverse(); 1146 //return multiply(t); 1147 GenWordPolynomial<C> p = ring.getZERO().copy(); 1148 SortedMap<Word, C> pv = p.val; 1149 for (Map.Entry<Word, C> m : val.entrySet()) { 1150 Word e = m.getKey(); 1151 C c1 = m.getValue(); 1152 C c = c1.divide(s); 1153 if (debug) { 1154 C x = c1.remainder(s); 1155 if (!x.isZERO()) { 1156 logger.info("divide x = " + x); 1157 throw new ArithmeticException(this.getClass().getName() + " no exact division: " + c1 1158 + "/" + s); 1159 } 1160 } 1161 if (c.isZERO()) { 1162 throw new ArithmeticException(this.getClass().getName() + " no exact division: " + c1 + "/" 1163 + s + ", in " + this); 1164 } 1165 pv.put(e, c); // or m1.setValue( c ) 1166 } 1167 return p; 1168 } 1169 1170 1171 /** 1172 * GenWordPolynomial division with remainder. Fails, if exact division by 1173 * leading base coefficient is not possible. Meaningful only for univariate 1174 * polynomials over fields, but works in any case. 1175 * @param S nonzero GenWordPolynomial with invertible leading coefficient. 1176 * @return [ quotient , remainder ] with this = quotient * S + remainder and 1177 * deg(remainder) < deg(S) or remiander = 0. 1178 * @see edu.jas.poly.PolyUtil#baseSparsePseudoRemainder(edu.jas.poly.GenPolynomial,edu.jas.poly.GenPolynomial). 1179 */ 1180 @SuppressWarnings("unchecked") 1181 public GenWordPolynomial<C>[] quotientRemainder(GenWordPolynomial<C> S) { 1182 if (S == null || S.isZERO()) { 1183 throw new ArithmeticException(this.getClass().getName() + " division by zero"); 1184 } 1185 C c = S.leadingBaseCoefficient(); 1186 if (!c.isUnit()) { 1187 throw new ArithmeticException(this.getClass().getName() + " lbcf not invertible " + c); 1188 } 1189 C ci = c.inverse(); 1190 C one = ring.coFac.getONE(); 1191 assert (ring.alphabet == S.ring.alphabet); 1192 WordFactory.WordComparator cmp = ring.alphabet.getDescendComparator(); 1193 Word e = S.leadingWord(); 1194 GenWordPolynomial<C> h; 1195 GenWordPolynomial<C> q = ring.getZERO().copy(); 1196 GenWordPolynomial<C> r = this.copy(); 1197 while (!r.isZERO()) { 1198 Word f = r.leadingWord(); 1199 if (f.multipleOf(e)) { 1200 C a = r.leadingBaseCoefficient(); 1201 Word[] g = f.divideWord(e); // divide not sufficient 1202 //logger.info("div: f = " + f + ", e = " + e + ", g = " + g[0] + ", " + g[1]); 1203 a = a.multiply(ci); 1204 q = q.sum(a, g[0].multiply(g[1])); 1205 h = S.multiply(a, g[0], one, g[1]); 1206 r = r.subtract(h); 1207 Word fr = r.leadingWord(); 1208 if (cmp.compare(f, fr) > 0) { // non noetherian reduction 1209 throw new RuntimeException("possible infinite loop: f = " + f + ", fr = " + fr); 1210 } 1211 } else { 1212 break; 1213 } 1214 } 1215 GenWordPolynomial<C>[] ret = new GenWordPolynomial[2]; 1216 ret[0] = q; 1217 ret[1] = r; 1218 return ret; 1219 } 1220 1221 1222 /** 1223 * GenWordPolynomial division. Fails, if exact division by leading base 1224 * coefficient is not possible. Meaningful only for univariate polynomials 1225 * over fields, but works in any case. 1226 * @param S nonzero GenWordPolynomial with invertible leading coefficient. 1227 * @return quotient with this = quotient * S + remainder. 1228 * @see edu.jas.poly.PolyUtil#baseSparsePseudoRemainder(edu.jas.poly.GenPolynomial,edu.jas.poly.GenPolynomial). 1229 */ 1230 public GenWordPolynomial<C> divide(GenWordPolynomial<C> S) { 1231 return quotientRemainder(S)[0]; 1232 } 1233 1234 1235 /** 1236 * GenWordPolynomial remainder. Fails, if exact division by leading base 1237 * coefficient is not possible. Meaningful only for univariate polynomials 1238 * over fields, but works in any case. 1239 * @param S nonzero GenWordPolynomial with invertible leading coefficient. 1240 * @return remainder with this = quotient * S + remainder. 1241 * @see edu.jas.poly.PolyUtil#baseSparsePseudoRemainder(edu.jas.poly.GenPolynomial,edu.jas.poly.GenPolynomial). 1242 */ 1243 public GenWordPolynomial<C> remainder(GenWordPolynomial<C> S) { 1244 if (S == null || S.isZERO()) { 1245 throw new ArithmeticException(this.getClass().getName() + " division by zero"); 1246 } 1247 C c = S.leadingBaseCoefficient(); 1248 if (!c.isUnit()) { 1249 throw new ArithmeticException(this.getClass().getName() + " lbc not invertible " + c); 1250 } 1251 C ci = c.inverse(); 1252 C one = ring.coFac.getONE(); 1253 assert (ring.alphabet == S.ring.alphabet); 1254 WordFactory.WordComparator cmp = ring.alphabet.getDescendComparator(); 1255 Word e = S.leadingWord(); 1256 GenWordPolynomial<C> h; 1257 GenWordPolynomial<C> r = this.copy(); 1258 while (!r.isZERO()) { 1259 Word f = r.leadingWord(); 1260 if (f.multipleOf(e)) { 1261 C a = r.leadingBaseCoefficient(); 1262 Word[] g = f.divideWord(e); // divide not sufficient 1263 //logger.info("rem: f = " + f + ", e = " + e + ", g = " + g[0] + ", " + g[1]); 1264 a = a.multiply(ci); 1265 h = S.multiply(a, g[0], one, g[1]); 1266 r = r.subtract(h); 1267 Word fr = r.leadingWord(); 1268 if (cmp.compare(f, fr) > 0) { // non noetherian reduction 1269 throw new RuntimeException("possible infinite loop: f = " + f + ", fr = " + fr); 1270 } 1271 } else { 1272 break; 1273 } 1274 } 1275 return r; 1276 } 1277 1278 1279 /** 1280 * GenWordPolynomial greatest common divisor. Only for univariate 1281 * polynomials over fields. 1282 * @param S GenWordPolynomial. 1283 * @return gcd(this,S). 1284 */ 1285 public GenWordPolynomial<C> gcd(GenWordPolynomial<C> S) { 1286 if (S == null || S.isZERO()) { 1287 return this; 1288 } 1289 if (this.isZERO()) { 1290 return S; 1291 } 1292 if (ring.alphabet.length() != 1) { 1293 throw new IllegalArgumentException("no univariate polynomial " + ring); 1294 } 1295 GenWordPolynomial<C> x; 1296 GenWordPolynomial<C> q = this; 1297 GenWordPolynomial<C> r = S; 1298 while (!r.isZERO()) { 1299 x = q.remainder(r); 1300 q = r; 1301 r = x; 1302 } 1303 return q.monic(); // normalize 1304 } 1305 1306 1307 /** 1308 * GenWordPolynomial extended greatest comon divisor. Only for univariate 1309 * polynomials over fields. 1310 * @param S GenWordPolynomial. 1311 * @return [ gcd(this,S), a, b ] with a*this + b*S = gcd(this,S). 1312 */ 1313 @SuppressWarnings("unchecked") 1314 public GenWordPolynomial<C>[] egcd(GenWordPolynomial<C> S) { 1315 GenWordPolynomial<C>[] ret = new GenWordPolynomial[3]; 1316 ret[0] = null; 1317 ret[1] = null; 1318 ret[2] = null; 1319 if (S == null || S.isZERO()) { 1320 ret[0] = this; 1321 ret[1] = this.ring.getONE(); 1322 ret[2] = this.ring.getZERO(); 1323 return ret; 1324 } 1325 if (this.isZERO()) { 1326 ret[0] = S; 1327 ret[1] = this.ring.getZERO(); 1328 ret[2] = this.ring.getONE(); 1329 return ret; 1330 } 1331 if (ring.alphabet.length() != 1) { 1332 throw new IllegalArgumentException("no univariate polynomial " + ring); 1333 } 1334 if (this.isConstant() && S.isConstant()) { 1335 C t = this.leadingBaseCoefficient(); 1336 C s = S.leadingBaseCoefficient(); 1337 C[] gg = t.egcd(s); 1338 //System.out.println("coeff gcd = " + Arrays.toString(gg)); 1339 GenWordPolynomial<C> z = this.ring.getZERO(); 1340 ret[0] = z.sum(gg[0]); 1341 ret[1] = z.sum(gg[1]); 1342 ret[2] = z.sum(gg[2]); 1343 return ret; 1344 } 1345 GenWordPolynomial<C>[] qr; 1346 GenWordPolynomial<C> q = this; 1347 GenWordPolynomial<C> r = S; 1348 GenWordPolynomial<C> c1 = ring.getONE().copy(); 1349 GenWordPolynomial<C> d1 = ring.getZERO().copy(); 1350 GenWordPolynomial<C> c2 = ring.getZERO().copy(); 1351 GenWordPolynomial<C> d2 = ring.getONE().copy(); 1352 GenWordPolynomial<C> x1; 1353 GenWordPolynomial<C> x2; 1354 while (!r.isZERO()) { 1355 qr = q.quotientRemainder(r); 1356 q = qr[0]; 1357 x1 = c1.subtract(q.multiply(d1)); 1358 x2 = c2.subtract(q.multiply(d2)); 1359 c1 = d1; 1360 c2 = d2; 1361 d1 = x1; 1362 d2 = x2; 1363 q = r; 1364 r = qr[1]; 1365 } 1366 // normalize ldcf(q) to 1, i.e. make monic 1367 C g = q.leadingBaseCoefficient(); 1368 if (g.isUnit()) { 1369 C h = g.inverse(); 1370 q = q.multiply(h); 1371 c1 = c1.multiply(h); 1372 c2 = c2.multiply(h); 1373 } 1374 //assert ( ((c1.multiply(this)).sum( c2.multiply(S)).equals(q) )); 1375 ret[0] = q; 1376 ret[1] = c1; 1377 ret[2] = c2; 1378 return ret; 1379 } 1380 1381 1382 /** 1383 * GenWordPolynomial half extended greatest comon divisor. Only for 1384 * univariate polynomials over fields. 1385 * @param S GenWordPolynomial. 1386 * @return [ gcd(this,S), a ] with a*this + b*S = gcd(this,S). 1387 */ 1388 @SuppressWarnings("unchecked") 1389 public GenWordPolynomial<C>[] hegcd(GenWordPolynomial<C> S) { 1390 GenWordPolynomial<C>[] ret = new GenWordPolynomial[2]; 1391 ret[0] = null; 1392 ret[1] = null; 1393 if (S == null || S.isZERO()) { 1394 ret[0] = this; 1395 ret[1] = this.ring.getONE(); 1396 return ret; 1397 } 1398 if (this.isZERO()) { 1399 ret[0] = S; 1400 return ret; 1401 } 1402 if (ring.alphabet.length() != 1) { 1403 throw new IllegalArgumentException("no univariate polynomial " + ring); 1404 } 1405 GenWordPolynomial<C>[] qr; 1406 GenWordPolynomial<C> q = this; 1407 GenWordPolynomial<C> r = S; 1408 GenWordPolynomial<C> c1 = ring.getONE().copy(); 1409 GenWordPolynomial<C> d1 = ring.getZERO().copy(); 1410 GenWordPolynomial<C> x1; 1411 while (!r.isZERO()) { 1412 qr = q.quotientRemainder(r); 1413 q = qr[0]; 1414 x1 = c1.subtract(q.multiply(d1)); 1415 c1 = d1; 1416 d1 = x1; 1417 q = r; 1418 r = qr[1]; 1419 } 1420 // normalize ldcf(q) to 1, i.e. make monic 1421 C g = q.leadingBaseCoefficient(); 1422 if (g.isUnit()) { 1423 C h = g.inverse(); 1424 q = q.multiply(h); 1425 c1 = c1.multiply(h); 1426 } 1427 //assert ( ((c1.multiply(this)).remainder(S).equals(q) )); 1428 ret[0] = q; 1429 ret[1] = c1; 1430 return ret; 1431 } 1432 1433 1434 /** 1435 * GenWordPolynomial inverse. Required by RingElem. Throws not invertible 1436 * exception. 1437 */ 1438 public GenWordPolynomial<C> inverse() { 1439 if (isUnit()) { // only possible if ldbcf is unit 1440 C c = leadingBaseCoefficient().inverse(); 1441 return ring.getONE().multiply(c); 1442 } 1443 throw new NotInvertibleException("element not invertible " + this + " :: " + ring); 1444 } 1445 1446 1447 /** 1448 * GenWordPolynomial modular inverse. Only for univariate polynomials over 1449 * fields. 1450 * @param m GenWordPolynomial. 1451 * @return a with with a*this = 1 mod m. 1452 */ 1453 public GenWordPolynomial<C> modInverse(GenWordPolynomial<C> m) { 1454 if (this.isZERO()) { 1455 throw new NotInvertibleException("zero is not invertible"); 1456 } 1457 GenWordPolynomial<C>[] hegcd = this.hegcd(m); 1458 GenWordPolynomial<C> a = hegcd[0]; 1459 if (!a.isUnit()) { // gcd != 1 1460 throw new NotInvertibleException("element not invertible, gcd != 1"); 1461 } 1462 GenWordPolynomial<C> b = hegcd[1]; 1463 if (b.isZERO()) { // when m divides this, e.g. m.isUnit() 1464 throw new NotInvertibleException("element not invertible, divisible by modul"); 1465 } 1466 return b; 1467 } 1468 1469 1470 /** 1471 * Iterator over coefficients. 1472 * @return val.values().iterator(). 1473 */ 1474 public Iterator<C> coefficientIterator() { 1475 return val.values().iterator(); 1476 } 1477 1478 1479 /** 1480 * Iterator over words. 1481 * @return val.keySet().iterator(). 1482 */ 1483 public Iterator<Word> wordIterator() { 1484 return val.keySet().iterator(); 1485 } 1486 1487 1488 /** 1489 * Iterator over monomials. 1490 * @return a PolyIterator. 1491 */ 1492 public Iterator<WordMonomial<C>> iterator() { 1493 return new WordPolyIterator<C>(val); 1494 } 1495 1496 1497 /** 1498 * Map a unary function to the coefficients. 1499 * @param f evaluation functor. 1500 * @return new polynomial with coefficients f(this(e)). 1501 */ 1502 public GenWordPolynomial<C> map(final UnaryFunctor<? super C, C> f) { 1503 GenWordPolynomial<C> n = ring.getZERO().copy(); 1504 SortedMap<Word, C> nv = n.val; 1505 for (WordMonomial<C> m : this) { 1506 //logger.info("m = " + m); 1507 C c = f.eval(m.c); 1508 if (c != null && !c.isZERO()) { 1509 nv.put(m.e, c); 1510 } 1511 } 1512 return n; 1513 } 1514 1515}