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