001/* 002 * $Id$ 003 */ 004 005package edu.jas.poly; 006 007 008import java.util.Map; 009import java.util.Set; 010import java.util.SortedMap; 011 012import org.apache.logging.log4j.LogManager; 013import org.apache.logging.log4j.Logger; 014 015import edu.jas.structure.NotInvertibleException; 016import edu.jas.structure.RingElem; 017 018 019/** 020 * GenSolvablePolynomial generic solvable polynomials implementing RingElem. 021 * n-variate ordered solvable polynomials over C. Objects of this class are 022 * intended to be immutable. The implementation is based on TreeMap respectively 023 * SortedMap from exponents to coefficients by extension of GenPolybomial. Only 024 * the coefficients are modeled with generic types, the exponents are fixed to 025 * ExpVector with long, int, short entries (@see edu.jas.poly.ExpVector 026 * StorUnit). 027 * @param <C> coefficient type 028 * @author Heinz Kredel 029 */ 030 031public class GenSolvablePolynomial<C extends RingElem<C>> extends GenPolynomial<C> { 032 033 034 //not possible: implements RingElem< GenSolvablePolynomial<C> > { 035 036 037 private static final Logger logger = LogManager.getLogger(GenSolvablePolynomial.class); 038 039 040 //private static final boolean debug = logger.isDebugEnabled(); 041 042 043 /** 044 * The factory for the solvable polynomial ring. Hides super.ring. 045 */ 046 public final GenSolvablePolynomialRing<C> ring; 047 048 049 /** 050 * Constructor for zero GenSolvablePolynomial. 051 * @param r solvable polynomial ring factory. 052 */ 053 public GenSolvablePolynomial(GenSolvablePolynomialRing<C> r) { 054 super(r); 055 ring = r; 056 } 057 058 059 /** 060 * Constructor for GenSolvablePolynomial. 061 * @param r solvable polynomial ring factory. 062 * @param c coefficient. 063 * @param e exponent. 064 */ 065 public GenSolvablePolynomial(GenSolvablePolynomialRing<C> r, C c, ExpVector e) { 066 this(r); 067 if (c != null && !c.isZERO()) { 068 val.put(e, c); 069 } 070 } 071 072 073 /** 074 * Constructor for GenSolvablePolynomial. 075 * @param r solvable polynomial ring factory. 076 * @param c coefficient. 077 */ 078 public GenSolvablePolynomial(GenSolvablePolynomialRing<C> r, C c) { 079 this(r, c, r.evzero); 080 } 081 082 083 /** 084 * Constructor for GenSolvablePolynomial. 085 * @param r solvable polynomial ring factory. 086 * @param v the SortedMap of some other (solvable) polynomial. 087 */ 088 protected GenSolvablePolynomial(GenSolvablePolynomialRing<C> r, SortedMap<ExpVector, C> v) { 089 this(r); 090 if (v.size() > 0) { 091 GenPolynomialRing.creations++; 092 val.putAll(v); // assume val is empty and no zero coefficients in v 093 } 094 } 095 096 097 /** 098 * Get the corresponding element factory. 099 * @return factory for this Element. 100 * @see edu.jas.structure.Element#factory() 101 */ 102 @Override 103 public GenSolvablePolynomialRing<C> factory() { 104 return ring; 105 } 106 107 108 /** 109 * Clone this GenSolvablePolynomial. 110 * @see java.lang.Object#clone() 111 */ 112 @Override 113 public GenSolvablePolynomial<C> copy() { 114 return new GenSolvablePolynomial<C>(ring, this.val); 115 } 116 117 118 /** 119 * Comparison with any other object. 120 * @see java.lang.Object#equals(java.lang.Object) 121 */ 122 @Override 123 public boolean equals(Object B) { 124 if (!(B instanceof GenSolvablePolynomial)) { 125 return false; 126 } 127 return super.equals(B); 128 } 129 130 131 /** 132 * Hash code for this polynomial. 133 * @see java.lang.Object#hashCode() 134 */ 135 @Override 136 public int hashCode() { 137 return super.hashCode(); 138 } 139 140 141 /** 142 * GenSolvablePolynomial multiplication. 143 * @param Bp GenSolvablePolynomial. 144 * @return this*Bp, where * denotes solvable multiplication. 145 */ 146 // cannot @Override 147 @SuppressWarnings("unchecked") 148 public GenSolvablePolynomial<C> multiply(GenSolvablePolynomial<C> Bp) { 149 if (Bp == null || Bp.isZERO()) { 150 return ring.getZERO(); 151 } 152 if (this.isZERO()) { 153 return this; 154 } 155 assert (ring.nvar == Bp.ring.nvar); 156 logger.debug("ring = {}", ring); 157 if (this instanceof RecSolvablePolynomial && Bp instanceof RecSolvablePolynomial) { 158 //throw new RuntimeException("wrong method dispatch in JRE "); 159 logger.info("warn: wrong method dispatch in JRE Rec.multiply(Rec Bp) - trying to fix"); 160 RecSolvablePolynomial T = (RecSolvablePolynomial) this; // no <C> 161 RecSolvablePolynomial Sp = (RecSolvablePolynomial) Bp; 162 return T.multiply(Sp); 163 } 164 if (this instanceof QLRSolvablePolynomial && Bp instanceof QLRSolvablePolynomial) { 165 //throw new RuntimeException("wrong method dispatch in JRE "); 166 logger.info("warn: wrong method dispatch in JRE QLR.multiply(QLR Bp) - trying to fix"); 167 QLRSolvablePolynomial T = (QLRSolvablePolynomial) this; // no <C> 168 QLRSolvablePolynomial Sp = (QLRSolvablePolynomial) Bp; 169 return T.multiply(Sp); 170 } 171 final boolean commute = ring.table.isEmpty(); 172 GenSolvablePolynomial<C> Cp = ring.getZERO().copy(); // needed for doPutToMap and doAddTo 173 ExpVector Z = ring.evzero; 174 175 GenSolvablePolynomial<C> C1 = null; 176 GenSolvablePolynomial<C> C2 = null; 177 Map<ExpVector, C> A = val; 178 Map<ExpVector, C> B = Bp.val; 179 Set<Map.Entry<ExpVector, C>> Bk = B.entrySet(); 180 for (Map.Entry<ExpVector, C> y : A.entrySet()) { 181 C a = y.getValue(); 182 ExpVector e = y.getKey(); 183 logger.debug("e = {}", e); 184 int[] ep = e.dependencyOnVariables(); 185 int el1 = ring.nvar + 1; 186 if (ep.length > 0) { 187 el1 = ep[0]; 188 } 189 int el1s = ring.nvar + 1 - el1; 190 for (Map.Entry<ExpVector, C> x : Bk) { 191 C b = x.getValue(); 192 ExpVector f = x.getKey(); 193 logger.debug("f = {}", f); 194 int[] fp = f.dependencyOnVariables(); 195 int fl1 = 0; 196 if (fp.length > 0) { 197 fl1 = fp[fp.length - 1]; 198 } 199 int fl1s = ring.nvar + 1 - fl1; 200 logger.debug("el1s = {} fl1s = {}", el1s, fl1s); 201 GenSolvablePolynomial<C> Cs = null; 202 if (commute || el1s <= fl1s) { // symmetric 203 ExpVector g = e.sum(f); 204 Cs = ring.valueOf(g); // symmetric! 205 //no: Cs = new GenSolvablePolynomial<C>(ring, one, g); 206 //System.out.println("Cs(sym) = " + Cs + ", g = " + g); 207 } else { // unsymmetric 208 // split e = e1 * e2, f = f1 * f2 209 ExpVector e1 = e.subst(el1, 0); 210 ExpVector e2 = Z.subst(el1, e.getVal(el1)); 211 ExpVector e4; 212 ExpVector f1 = f.subst(fl1, 0); 213 ExpVector f2 = Z.subst(fl1, f.getVal(fl1)); 214 TableRelation<C> rel = ring.table.lookup(e2, f2); 215 //logger.info("relation = {}", rel); 216 Cs = rel.p; // do not clone() 217 if (rel.f != null) { 218 C2 = ring.valueOf(rel.f); 219 Cs = Cs.multiply(C2); 220 if (rel.e == null) { 221 e4 = e2; 222 } else { 223 e4 = e2.subtract(rel.e); 224 } 225 ring.table.update(e4, f2, Cs); 226 } 227 if (rel.e != null) { 228 C1 = ring.valueOf(rel.e); 229 Cs = C1.multiply(Cs); 230 ring.table.update(e2, f2, Cs); 231 } 232 if (!f1.isZERO()) { 233 C2 = ring.valueOf(f1); 234 Cs = Cs.multiply(C2); 235 //ring.table.update(?,f1,Cs) 236 } 237 if (!e1.isZERO()) { 238 C1 = ring.valueOf(e1); 239 Cs = C1.multiply(Cs); 240 //ring.table.update(e1,?,Cs) 241 } 242 } 243 //System.out.println("Cs = " + Cs + ", a = " + a + ", b = " + b); 244 Cs = Cs.multiply(a, b); // now non-symmetric // Cs.multiply(c); is symmetric! 245 Cp.doAddTo(Cs); 246 } 247 } 248 return Cp; 249 } 250 251 252 /** 253 * GenSolvablePolynomial left and right multiplication. Product with two 254 * polynomials. 255 * @param S GenSolvablePolynomial. 256 * @param T GenSolvablePolynomial. 257 * @return S*this*T. 258 */ 259 // new method, @NoOverride 260 public GenSolvablePolynomial<C> multiply(GenSolvablePolynomial<C> S, GenSolvablePolynomial<C> T) { 261 if (S.isZERO() || T.isZERO() || this.isZERO()) { 262 return ring.getZERO(); 263 } 264 if (S.isONE()) { 265 return multiply(T); 266 } 267 if (T.isONE()) { 268 return S.multiply(this); 269 } 270 return S.multiply(this).multiply(T); 271 } 272 273 274 /** 275 * GenSolvablePolynomial multiplication. Product with coefficient ring 276 * element. 277 * @param b coefficient. 278 * @return this*b, where * is coefficient multiplication. 279 */ 280 @Override 281 @SuppressWarnings({ "cast", "unchecked" }) 282 public GenSolvablePolynomial<C> multiply(C b) { 283 GenSolvablePolynomial<C> Cp = ring.getZERO(); 284 if (b == null || b.isZERO()) { 285 return Cp; 286 } 287 if (this instanceof RecSolvablePolynomial && b instanceof GenSolvablePolynomial) { 288 //throw new RuntimeException("wrong method dispatch in JRE "); 289 logger.info("warn: wrong method dispatch in JRE Rec.multiply(b) - trying to fix"); 290 RecSolvablePolynomial T = (RecSolvablePolynomial) this; // no <C> 291 GenSolvablePolynomial Sp = (GenSolvablePolynomial) b; 292 return (GenSolvablePolynomial<C>) T.recMultiply(Sp); 293 } 294 if (this instanceof QLRSolvablePolynomial && b instanceof GenSolvablePolynomial) { 295 //throw new RuntimeException("wrong method dispatch in JRE "); 296 logger.info("warn: wrong method dispatch in JRE QLR.multiply(Bp) - trying to fix"); 297 QLRSolvablePolynomial T = (QLRSolvablePolynomial) this; // no <C> 298 GenSolvablePolynomial Sp = (GenSolvablePolynomial) b; 299 return (GenSolvablePolynomial<C>) T.multiply(Sp); 300 } 301 Cp = Cp.copy(); 302 Map<ExpVector, C> Cm = Cp.val; 303 Map<ExpVector, C> Am = val; 304 for (Map.Entry<ExpVector, C> y : Am.entrySet()) { 305 ExpVector e = y.getKey(); 306 C a = y.getValue(); 307 C c = a.multiply(b); 308 if (!c.isZERO()) { 309 Cm.put(e, c); 310 } 311 } 312 return Cp; 313 } 314 315 316 /** 317 * GenSolvablePolynomial left and right multiplication. Product with 318 * coefficient ring element. 319 * @param b coefficient. 320 * @param c coefficient. 321 * @return b*this*c, where * is coefficient multiplication. 322 */ 323 // new method, @NoOverride 324 @SuppressWarnings({ "cast", "unchecked" }) 325 public GenSolvablePolynomial<C> multiply(C b, C c) { 326 GenSolvablePolynomial<C> Cp = ring.getZERO(); 327 if (b == null || b.isZERO()) { 328 return Cp; 329 } 330 if (c == null || c.isZERO()) { 331 return Cp; 332 } 333 if (this instanceof RecSolvablePolynomial && b instanceof GenSolvablePolynomial 334 && c instanceof GenSolvablePolynomial) { 335 //throw new RuntimeException("wrong method dispatch in JRE "); 336 logger.info("warn: wrong method dispatch in JRE Rec.multiply(b,c) - trying to fix"); 337 RecSolvablePolynomial T = (RecSolvablePolynomial) this; // no <C> 338 GenSolvablePolynomial Bp = (GenSolvablePolynomial) b; 339 GenSolvablePolynomial Dp = (GenSolvablePolynomial) c; 340 return (GenSolvablePolynomial<C>) T.multiply(Bp, Dp); 341 } 342 if (this instanceof QLRSolvablePolynomial && b instanceof GenSolvablePolynomial 343 && c instanceof GenSolvablePolynomial) { 344 //throw new RuntimeException("wrong method dispatch in JRE "); 345 logger.info("warn: wrong method dispatch in JRE QLR.multiply(b,c) - trying to fix"); 346 QLRSolvablePolynomial T = (QLRSolvablePolynomial) this; // no <C> 347 GenSolvablePolynomial Bp = (GenSolvablePolynomial) b; 348 GenSolvablePolynomial Dp = (GenSolvablePolynomial) c; 349 return (GenSolvablePolynomial<C>) T.multiply(Bp, Dp); 350 } 351 Cp = Cp.copy(); 352 Map<ExpVector, C> Cm = Cp.val; 353 Map<ExpVector, C> Am = val; 354 for (Map.Entry<ExpVector, C> y : Am.entrySet()) { 355 ExpVector e = y.getKey(); 356 C a = y.getValue(); 357 C d = b.multiply(a).multiply(c); 358 if (!d.isZERO()) { 359 Cm.put(e, d); 360 } 361 } 362 return Cp; 363 } 364 365 366 /** 367 * GenSolvablePolynomial multiplication. Product with exponent vector. 368 * @param e exponent. 369 * @return this * x<sup>e</sup>, where * denotes solvable multiplication. 370 */ 371 @Override 372 public GenSolvablePolynomial<C> multiply(ExpVector e) { 373 if (e == null || e.isZERO()) { 374 return this; 375 } 376 C b = ring.getONECoefficient(); 377 return multiply(b, e); 378 } 379 380 381 /** 382 * GenSolvablePolynomial left and right multiplication. Product with 383 * exponent vector. 384 * @param e exponent. 385 * @param f exponent. 386 * @return x<sup>e</sup> * this * x<sup>f</sup>, where * denotes solvable 387 * multiplication. 388 */ 389 // new method, @NoOverride 390 public GenSolvablePolynomial<C> multiply(ExpVector e, ExpVector f) { 391 if (e == null || e.isZERO()) { 392 return this; 393 } 394 if (f == null || f.isZERO()) { 395 return this; 396 } 397 C b = ring.getONECoefficient(); 398 return multiply(b, e, b, f); 399 } 400 401 402 /** 403 * GenSolvablePolynomial multiplication. Product with ring element and 404 * exponent vector. 405 * @param b coefficient. 406 * @param e exponent. 407 * @return this * b x<sup>e</sup>, where * denotes solvable multiplication. 408 */ 409 @Override 410 public GenSolvablePolynomial<C> multiply(C b, ExpVector e) { 411 if (b == null || b.isZERO()) { 412 return ring.getZERO(); 413 } 414 GenSolvablePolynomial<C> Cp = ring.valueOf(b, e); //new GenSolvablePolynomial<C>(ring, b, e); 415 return multiply(Cp); 416 } 417 418 419 /** 420 * GenSolvablePolynomial left and right multiplication. Product with ring 421 * element and exponent vector. 422 * @param b coefficient. 423 * @param e exponent. 424 * @param c coefficient. 425 * @param f exponent. 426 * @return b x<sup>e</sup> * this * c x<sup>f</sup>, where * denotes 427 * solvable multiplication. 428 */ 429 // new method, @NoOverride 430 public GenSolvablePolynomial<C> multiply(C b, ExpVector e, C c, ExpVector f) { 431 if (b == null || b.isZERO()) { 432 return ring.getZERO(); 433 } 434 if (c == null || c.isZERO()) { 435 return ring.getZERO(); 436 } 437 GenSolvablePolynomial<C> Cp = ring.valueOf(b, e); //new GenSolvablePolynomial<C>(ring, b, e); 438 GenSolvablePolynomial<C> Dp = ring.valueOf(c, f); //new GenSolvablePolynomial<C>(ring, c, f); 439 return multiply(Cp, Dp); 440 } 441 442 443 /** 444 * GenSolvablePolynomial multiplication. Left product with ring element and 445 * exponent vector. 446 * @param b coefficient. 447 * @param e exponent. 448 * @return b x<sup>e</sup> * this, where * denotes solvable multiplication. 449 */ 450 public GenSolvablePolynomial<C> multiplyLeft(C b, ExpVector e) { 451 if (b == null || b.isZERO()) { 452 return ring.getZERO(); 453 } 454 GenSolvablePolynomial<C> Cp = ring.valueOf(b, e); 455 return Cp.multiply(this); 456 } 457 458 459 /** 460 * GenSolvablePolynomial multiplication. Left product with exponent vector. 461 * @param e exponent. 462 * @return x<sup>e</sup> * this, where * denotes solvable multiplication. 463 */ 464 public GenSolvablePolynomial<C> multiplyLeft(ExpVector e) { 465 if (e == null || e.isZERO()) { 466 return this; 467 } 468 C b = ring.getONECoefficient(); 469 return multiplyLeft(b, e); 470 } 471 472 473 /** 474 * GenSolvablePolynomial multiplication. Left product with coefficient ring 475 * element. 476 * @param b coefficient. 477 * @return b*this, where * is coefficient multiplication. 478 */ 479 @Override 480 public GenSolvablePolynomial<C> multiplyLeft(C b) { 481 GenSolvablePolynomial<C> Cp = ring.getZERO(); 482 if (b == null || b.isZERO()) { 483 return Cp; 484 } 485 Cp = Cp.copy(); 486 Map<ExpVector, C> Cm = Cp.val; //getMap(); 487 Map<ExpVector, C> Am = val; 488 for (Map.Entry<ExpVector, C> y : Am.entrySet()) { 489 ExpVector e = y.getKey(); 490 C a = y.getValue(); 491 C c = b.multiply(a); 492 if (!c.isZERO()) { 493 Cm.put(e, c); 494 } 495 } 496 return Cp; 497 } 498 499 500 /** 501 * GenSolvablePolynomial multiplication. Left product with 'monomial'. 502 * @param m 'monomial'. 503 * @return m * this, where * denotes solvable multiplication. 504 */ 505 // new method, @NoOverride 506 public GenSolvablePolynomial<C> multiplyLeft(Map.Entry<ExpVector, C> m) { 507 if (m == null) { 508 return ring.getZERO(); 509 } 510 return multiplyLeft(m.getValue(), m.getKey()); 511 } 512 513 514 /** 515 * GenSolvablePolynomial multiplication. Product with 'monomial'. 516 * @param m 'monomial'. 517 * @return this * m, where * denotes solvable multiplication. 518 */ 519 @Override 520 public GenSolvablePolynomial<C> multiply(Map.Entry<ExpVector, C> m) { 521 if (m == null) { 522 return ring.getZERO(); 523 } 524 return multiply(m.getValue(), m.getKey()); 525 } 526 527 528 /** 529 * GenSolvablePolynomial subtract a multiple. 530 * @param a coefficient. 531 * @param S GenSolvablePolynomial. 532 * @return this - a * S. 533 */ 534 public GenSolvablePolynomial<C> subtractMultiple(C a, GenSolvablePolynomial<C> S) { 535 if (a == null || a.isZERO()) { 536 return this; 537 } 538 if (S == null || S.isZERO()) { 539 return this; 540 } 541 if (this.isZERO()) { 542 return S.multiplyLeft(a.negate()); 543 } 544 assert (ring.nvar == S.ring.nvar); 545 GenSolvablePolynomial<C> n = this.copy(); 546 SortedMap<ExpVector, C> nv = n.val; 547 SortedMap<ExpVector, C> sv = S.val; 548 for (Map.Entry<ExpVector, C> me : sv.entrySet()) { 549 ExpVector f = me.getKey(); 550 C y = me.getValue(); // assert y != null 551 y = a.multiply(y); 552 C x = nv.get(f); 553 if (x != null) { 554 x = x.subtract(y); 555 if (!x.isZERO()) { 556 nv.put(f, x); 557 } else { 558 nv.remove(f); 559 } 560 } else if (!y.isZERO()) { 561 nv.put(f, y.negate()); 562 } 563 } 564 return n; 565 } 566 567 568 /** 569 * GenSolvablePolynomial subtract a multiple. 570 * @param a coefficient. 571 * @param e exponent. 572 * @param S GenSolvablePolynomial. 573 * @return this - a * x<sup>e</sup> * S. 574 */ 575 public GenSolvablePolynomial<C> subtractMultiple(C a, ExpVector e, GenSolvablePolynomial<C> S) { 576 if (a == null || a.isZERO()) { 577 return this; 578 } 579 if (S == null || S.isZERO()) { 580 return this; 581 } 582 if (this.isZERO()) { 583 return S.multiplyLeft(a.negate(), e); 584 } 585 assert (ring.nvar == S.ring.nvar); 586 GenSolvablePolynomial<C> n = this.copy(); 587 SortedMap<ExpVector, C> nv = n.val; 588 GenSolvablePolynomial<C> s = S.multiplyLeft(e); 589 SortedMap<ExpVector, C> sv = s.val; 590 for (Map.Entry<ExpVector, C> me : sv.entrySet()) { 591 ExpVector f = me.getKey(); 592 //f = e.sum(f); 593 C y = me.getValue(); // assert y != null 594 y = a.multiply(y); 595 C x = nv.get(f); 596 if (x != null) { 597 x = x.subtract(y); 598 if (!x.isZERO()) { 599 nv.put(f, x); 600 } else { 601 nv.remove(f); 602 } 603 } else if (!y.isZERO()) { 604 nv.put(f, y.negate()); 605 } 606 } 607 return n; 608 } 609 610 611 /** 612 * GenSolvablePolynomial scale and subtract a multiple. 613 * @param b scale factor. 614 * @param a coefficient. 615 * @param S GenSolvablePolynomial. 616 * @return b * this - a * S. 617 */ 618 public GenSolvablePolynomial<C> scaleSubtractMultiple(C b, C a, GenSolvablePolynomial<C> S) { 619 if (a == null || S == null) { 620 return this.multiplyLeft(b); 621 } 622 if (a.isZERO() || S.isZERO()) { 623 return this.multiplyLeft(b); 624 } 625 if (this.isZERO() || b == null || b.isZERO()) { 626 return S.multiplyLeft(a.negate()); 627 } 628 if (b.isONE()) { 629 return subtractMultiple(a, S); 630 } 631 assert (ring.nvar == S.ring.nvar); 632 GenSolvablePolynomial<C> n = this.multiplyLeft(b); 633 SortedMap<ExpVector, C> nv = n.val; 634 SortedMap<ExpVector, C> sv = S.val; 635 for (Map.Entry<ExpVector, C> me : sv.entrySet()) { 636 ExpVector f = me.getKey(); 637 //f = e.sum(f); 638 C y = me.getValue(); // assert y != null 639 y = a.multiply(y); // now y can be zero 640 C x = nv.get(f); 641 if (x != null) { 642 x = x.subtract(y); 643 if (!x.isZERO()) { 644 nv.put(f, x); 645 } else { 646 nv.remove(f); 647 } 648 } else if (!y.isZERO()) { 649 nv.put(f, y.negate()); 650 } 651 } 652 return n; 653 } 654 655 656 /** 657 * GenSolvablePolynomial scale and subtract a multiple. 658 * @param b scale factor. 659 * @param a coefficient. 660 * @param e exponent. 661 * @param S GenSolvablePolynomial. 662 * @return b * this - a * x<sup>e</sup> * S. 663 */ 664 public GenSolvablePolynomial<C> scaleSubtractMultiple(C b, C a, ExpVector e, GenSolvablePolynomial<C> S) { 665 if (a == null || S == null) { 666 return this.multiplyLeft(b); 667 } 668 if (a.isZERO() || S.isZERO()) { 669 return this.multiplyLeft(b); 670 } 671 if (this.isZERO() || b == null || b.isZERO()) { 672 return S.multiplyLeft(a.negate(), e); 673 } 674 if (b.isONE()) { 675 return subtractMultiple(a, e, S); 676 } 677 assert (ring.nvar == S.ring.nvar); 678 GenSolvablePolynomial<C> n = this.multiplyLeft(b); 679 SortedMap<ExpVector, C> nv = n.val; 680 GenSolvablePolynomial<C> s = S.multiplyLeft(e); 681 SortedMap<ExpVector, C> sv = s.val; 682 for (Map.Entry<ExpVector, C> me : sv.entrySet()) { 683 ExpVector f = me.getKey(); 684 //f = e.sum(f); 685 C y = me.getValue(); // assert y != null 686 y = a.multiply(y); // now y can be zero 687 C x = nv.get(f); 688 if (x != null) { 689 x = x.subtract(y); 690 if (!x.isZERO()) { 691 nv.put(f, x); 692 } else { 693 nv.remove(f); 694 } 695 } else if (!y.isZERO()) { 696 nv.put(f, y.negate()); 697 } 698 } 699 return n; 700 } 701 702 703 /** 704 * GenSolvablePolynomial scale and subtract a multiple. 705 * @param b scale factor. 706 * @param g scale exponent. 707 * @param a coefficient. 708 * @param e exponent. 709 * @param S GenSolvablePolynomial. 710 * @return a * x<sup>g</sup> * this - a * x<sup>e</sup> * S. 711 */ 712 public GenSolvablePolynomial<C> scaleSubtractMultiple(C b, ExpVector g, C a, ExpVector e, 713 GenSolvablePolynomial<C> S) { 714 if (a == null || S == null) { 715 return this.multiplyLeft(b, g); 716 } 717 if (a.isZERO() || S.isZERO()) { 718 return this.multiplyLeft(b, g); 719 } 720 if (this.isZERO() || b == null || b.isZERO()) { 721 return S.multiplyLeft(a.negate(), e); 722 } 723 if (b.isONE() && g.isZERO()) { 724 return subtractMultiple(a, e, S); 725 } 726 assert (ring.nvar == S.ring.nvar); 727 GenSolvablePolynomial<C> n = this.multiplyLeft(b, g); 728 SortedMap<ExpVector, C> nv = n.val; 729 GenSolvablePolynomial<C> s = S.multiplyLeft(e); 730 SortedMap<ExpVector, C> sv = s.val; 731 for (Map.Entry<ExpVector, C> me : sv.entrySet()) { 732 ExpVector f = me.getKey(); 733 //f = e.sum(f); 734 C y = me.getValue(); // assert y != null 735 y = a.multiply(y); // y can be zero now 736 C x = nv.get(f); 737 if (x != null) { 738 x = x.subtract(y); 739 if (!x.isZERO()) { 740 nv.put(f, x); 741 } else { 742 nv.remove(f); 743 } 744 } else if (!y.isZERO()) { 745 nv.put(f, y.negate()); 746 } 747 } 748 return n; 749 } 750 751 752 /** 753 * GenSolvablePolynomial left monic, i.e. leadingCoefficient == 1. If 754 * leadingCoefficient is not invertible returns this abs value. 755 * @return ldcf(this)**(-1) * this. 756 */ 757 @Override 758 public GenSolvablePolynomial<C> monic() { 759 if (this.isZERO()) { 760 return this; 761 } 762 C lc = leadingBaseCoefficient(); 763 if (!lc.isUnit()) { 764 //System.out.println("lc = "+lc); 765 return this; 766 //return (GenSolvablePolynomial<C>) this.abs(); 767 } 768 C lm = lc.inverse(); 769 return (GenSolvablePolynomial<C>) multiplyLeft(lm); //.abs(); 770 } 771 772 773 /** 774 * GenSolvablePolynomial left monic, i.e. leadingCoefficient == 1. If 775 * leadingCoefficient is not invertible returns this abs value. 776 * @return ldcf(this)**(-1) * this. 777 */ 778 //@Override 779 public GenSolvablePolynomial<C> leftMonic() { 780 return monic(); 781 } 782 783 784 /** 785 * GenSolvablePolynomial right monic, i.e. leadingCoefficient == 1. If 786 * leadingCoefficient is not invertible returns this abs value. 787 * @return this * ldcf(this)**(-1). 788 */ 789 //@Override 790 public GenSolvablePolynomial<C> rightMonic() { 791 if (this.isZERO()) { 792 return this; 793 } 794 C lc = leadingBaseCoefficient(); 795 if (!lc.isUnit()) { 796 //System.out.println("lm = "+lm); 797 return this; 798 //return (GenSolvablePolynomial<C>) this.abs(); 799 } 800 C lm = lc.inverse(); 801 return (GenSolvablePolynomial<C>) multiply(lm); //.abs(); 802 } 803 804 805 /** 806 * GenSolvablePolynomial left division. Fails, if exact division by leading 807 * base coefficient is not possible. Meaningful only for univariate 808 * polynomials over fields, but works in any case. 809 * @param S nonzero GenSolvablePolynomial with invertible leading 810 * coefficient. 811 * @return quotient with this = quotient * S + remainder and deg(remainder) 812 * < deg(S) or remainder = 0. 813 * @see edu.jas.poly.PolyUtil#baseSparsePseudoRemainder(edu.jas.poly.GenPolynomial,edu.jas.poly.GenPolynomial) 814 */ 815 // cannot @Override 816 @SuppressWarnings("unchecked") 817 public GenSolvablePolynomial<C> divide(GenSolvablePolynomial<C> S) { 818 return quotientRemainder(S)[0]; 819 } 820 821 822 /** 823 * GenSolvablePolynomial remainder by left division. Fails, if exact 824 * division by leading base coefficient is not possible. Meaningful only for 825 * univariate polynomials over fields, but works in any case. 826 * @param S nonzero GenSolvablePolynomial with invertible leading 827 * coefficient. 828 * @return remainder with this = quotient * S + remainder and deg(remainder) 829 * < deg(S) or remainder = 0. 830 * @see edu.jas.poly.PolyUtil#baseSparsePseudoRemainder(edu.jas.poly.GenPolynomial,edu.jas.poly.GenPolynomial) 831 */ 832 // cannot @Override 833 @SuppressWarnings("unchecked") 834 public GenSolvablePolynomial<C> remainder(GenSolvablePolynomial<C> S) { 835 return quotientRemainder(S)[1]; 836 } 837 838 839 /** 840 * GenSolvablePolynomial left division with remainder. Fails, if exact 841 * division by leading base coefficient is not possible. Meaningful only for 842 * univariate polynomials over fields, but works in any case. 843 * @param S nonzero GenSolvablePolynomial with invertible leading 844 * coefficient. 845 * @return [ quotient , remainder ] with this = quotient * S + remainder and 846 * deg(remainder) < deg(S) or remainder = 0. 847 * @see edu.jas.poly.PolyUtil#baseSparsePseudoRemainder(edu.jas.poly.GenPolynomial,edu.jas.poly.GenPolynomial) 848 */ 849 // cannot @Override 850 @SuppressWarnings("unchecked") 851 public GenSolvablePolynomial<C>[] quotientRemainder(GenSolvablePolynomial<C> S) { 852 if (S == null || S.isZERO()) { 853 throw new ArithmeticException("division by zero"); 854 } 855 C c = S.leadingBaseCoefficient(); 856 if (!c.isUnit()) { 857 throw new ArithmeticException("lbcf not invertible " + c); 858 } 859 C ci = c.inverse(); 860 assert (ring.nvar == S.ring.nvar); 861 ExpVector e = S.leadingExpVector(); 862 GenSolvablePolynomial<C> h; 863 GenSolvablePolynomial<C> q = ring.getZERO().copy(); 864 GenSolvablePolynomial<C> r = this.copy(); 865 while (!r.isZERO()) { 866 ExpVector f = r.leadingExpVector(); 867 if (f.multipleOf(e)) { 868 C a = r.leadingBaseCoefficient(); 869 //System.out.println("FDQR: f = " + f + ", a = " + a); 870 f = f.subtract(e); 871 //a = ci.multiply(a); // multiplyLeft 872 a = a.multiply(ci); // this is correct! 873 q = (GenSolvablePolynomial<C>) q.sum(a, f); 874 h = S.multiplyLeft(a, f); 875 if (!h.leadingBaseCoefficient().equals(r.leadingBaseCoefficient())) { 876 throw new RuntimeException("something is wrong: r = " + r + ", h = " + h); 877 } 878 r = (GenSolvablePolynomial<C>) r.subtract(h); 879 } else { 880 break; 881 } 882 } 883 //System.out.println("(left)QR: q = " + q + ", r = " + r); 884 GenSolvablePolynomial<C>[] ret = new GenSolvablePolynomial[2]; 885 ret[0] = q; 886 ret[1] = r; 887 return ret; 888 } 889 890 891 /** 892 * GenSolvablePolynomial right division. Fails, if exact division by leading 893 * base coefficient is not possible. Meaningful only for univariate 894 * polynomials over fields, but works in any case. 895 * @param S nonzero GenSolvablePolynomial with invertible leading 896 * coefficient. 897 * @return quotient with this = S * quotient + remainder and deg(remainder) 898 * < deg(S) or remainder = 0. 899 * @see edu.jas.poly.PolyUtil#baseSparsePseudoRemainder(edu.jas.poly.GenPolynomial,edu.jas.poly.GenPolynomial) 900 */ 901 @SuppressWarnings("unchecked") 902 public GenSolvablePolynomial<C> rightDivide(GenSolvablePolynomial<C> S) { 903 return rightQuotientRemainder(S)[0]; 904 } 905 906 907 /** 908 * GenSolvablePolynomial remainder by right division. Fails, if exact 909 * division by leading base coefficient is not possible. Meaningful only for 910 * univariate polynomials over fields, but works in any case. 911 * @param S nonzero GenSolvablePolynomial with invertible leading 912 * coefficient. 913 * @return remainder with this = S * quotient + remainder and deg(remainder) 914 * < deg(S) or remainder = 0. 915 * @see edu.jas.poly.PolyUtil#baseSparsePseudoRemainder(edu.jas.poly.GenPolynomial,edu.jas.poly.GenPolynomial) 916 */ 917 @SuppressWarnings("unchecked") 918 public GenSolvablePolynomial<C> rightRemainder(GenSolvablePolynomial<C> S) { 919 return rightQuotientRemainder(S)[1]; 920 } 921 922 923 /** 924 * GenSolvablePolynomial right division with remainder. Fails, if exact 925 * division by leading base coefficient is not possible. Meaningful only for 926 * univariate polynomials over fields, but works in any case. 927 * @param S nonzero GenSolvablePolynomial with invertible leading 928 * coefficient. 929 * @return [ quotient , remainder ] with this = S * quotient + remainder and 930 * deg(remainder) < deg(S) or remainder = 0. 931 * @see edu.jas.poly.PolyUtil#baseSparsePseudoRemainder(edu.jas.poly.GenPolynomial,edu.jas.poly.GenPolynomial) 932 */ 933 @SuppressWarnings("unchecked") 934 public GenSolvablePolynomial<C>[] rightQuotientRemainder(GenSolvablePolynomial<C> S) { 935 if (S == null || S.isZERO()) { 936 throw new ArithmeticException("division by zero"); 937 } 938 C c = S.leadingBaseCoefficient(); 939 if (!c.isUnit()) { 940 throw new ArithmeticException("lbcf not invertible " + c); 941 } 942 C ci = c.inverse(); 943 assert (ring.nvar == S.ring.nvar); 944 ExpVector e = S.leadingExpVector(); 945 GenSolvablePolynomial<C> h; 946 GenSolvablePolynomial<C> q = ring.getZERO().copy(); 947 GenSolvablePolynomial<C> r = this.copy(); 948 while (!r.isZERO()) { 949 ExpVector f = r.leadingExpVector(); 950 if (f.multipleOf(e)) { 951 C a = r.leadingBaseCoefficient(); 952 //System.out.println("FDQR: f = " + f + ", a = " + a); 953 f = f.subtract(e); 954 //a = a.multiplyLeft(ci); // not existing 955 a = ci.multiply(a); // this is correct! 956 q = (GenSolvablePolynomial<C>) q.sum(a, f); 957 h = S.multiply(a, f); 958 if (!h.leadingBaseCoefficient().equals(r.leadingBaseCoefficient())) { 959 throw new RuntimeException("something is wrong: r = " + r + ", h = " + h); 960 } 961 r = (GenSolvablePolynomial<C>) r.subtract(h); 962 } else { 963 break; 964 } 965 } 966 System.out.println("rightQR: q = " + q + ", r = " + r); 967 GenSolvablePolynomial<C>[] ret = new GenSolvablePolynomial[2]; 968 ret[0] = q; 969 ret[1] = r; 970 return ret; 971 } 972 973 974 /** 975 * RecSolvablePolynomial right coefficients from left coefficients. 976 * <b>Note:</b> R is represented as a polynomial with left coefficients, the 977 * implementation can at the moment not distinguish between left and right 978 * coefficients. 979 * @return R = sum( X<sup>i</sup> b<sub>i</sub> ), with P = 980 * sum(a<sub>i</sub> X<sup>i</sup> ) and eval(sum(X<sup>i</sup> 981 * b<sub>i</sub>)) == sum(a<sub>i</sub> X<sup>i</sup>) 982 */ 983 @SuppressWarnings("unchecked") 984 public GenSolvablePolynomial<C> rightRecursivePolynomial() { 985 if (this.isONE() || this.isZERO()) { 986 return this; 987 } 988 if (!(this instanceof RecSolvablePolynomial)) { 989 return this; 990 } 991 RecSolvablePolynomialRing<C> rfac = (RecSolvablePolynomialRing<C>) ring; 992 if (rfac.coeffTable.isEmpty()) { 993 return this; 994 } 995 RecSolvablePolynomial<C> p = (RecSolvablePolynomial<C>) this; 996 RecSolvablePolynomial<C> R = (RecSolvablePolynomial<C>) p.rightRecursivePolynomial(); 997 return (GenSolvablePolynomial<C>) R; 998 } 999 1000 1001 /** 1002 * Evaluate RecSolvablePolynomial as right coefficients polynomial. 1003 * <b>Note:</b> R is represented as a polynomial with left coefficients, the 1004 * implementation can at the moment not distinguish between left and right 1005 * coefficients. 1006 * @return this as evaluated polynomial R. R = sum( X<sup>i</sup> 1007 * b<sub>i</sub> ), this = sum(a<sub>i</sub> X<sup>i</sup> ) = 1008 * eval(sum(X<sup>i</sup> b<sub>i</sub>)) 1009 */ 1010 @SuppressWarnings("unchecked") 1011 public GenSolvablePolynomial<C> evalAsRightRecursivePolynomial() { 1012 if (this.isONE() || this.isZERO()) { 1013 return this; 1014 } 1015 if (!(this instanceof RecSolvablePolynomial)) { 1016 return this; 1017 } 1018 RecSolvablePolynomialRing<C> rfac = (RecSolvablePolynomialRing<C>) ring; 1019 if (rfac.coeffTable.isEmpty()) { 1020 return this; 1021 } 1022 RecSolvablePolynomial<C> p = (RecSolvablePolynomial<C>) this; 1023 RecSolvablePolynomial<C> R = (RecSolvablePolynomial<C>) p.evalAsRightRecursivePolynomial(); 1024 return (GenSolvablePolynomial<C>) R; 1025 } 1026 1027 1028 /** 1029 * Test RecSolvablePolynomial right coefficients polynomial. <b>Note:</b> R 1030 * is represented as a polynomial with left coefficients, the implementation 1031 * can at the moment not distinguish between left and right coefficients. 1032 * @param R GenSolvablePolynomial with right coefficients. 1033 * @return true, if R is polynomial with right coefficients of this. R = 1034 * sum( X<sup>i</sup> b<sub>i</sub> ), with this = sum(a<sub>i</sub> 1035 * X<sup>i</sup> ) and eval(sum(X<sup>i</sup> b<sub>i</sub>)) == 1036 * sum(a<sub>i</sub> X<sup>i</sup>) 1037 */ 1038 @SuppressWarnings("unchecked") 1039 public boolean isRightRecursivePolynomial(GenSolvablePolynomial<C> R) { 1040 if (this.isZERO()) { 1041 return R.isZERO(); 1042 } 1043 if (this.isONE()) { 1044 return R.isONE(); 1045 } 1046 if (!(this instanceof RecSolvablePolynomial)) { 1047 return !(R instanceof RecSolvablePolynomial); 1048 } 1049 if (!(R instanceof RecSolvablePolynomial)) { 1050 return false; 1051 } 1052 RecSolvablePolynomialRing<C> rfac = (RecSolvablePolynomialRing<C>) ring; 1053 if (rfac.coeffTable.isEmpty()) { 1054 RecSolvablePolynomialRing<C> rf = (RecSolvablePolynomialRing<C>) R.ring; 1055 return rf.coeffTable.isEmpty(); 1056 } 1057 RecSolvablePolynomial<C> p = (RecSolvablePolynomial<C>) this; 1058 RecSolvablePolynomial<C> q = (RecSolvablePolynomial<C>) R; 1059 return p.isRightRecursivePolynomial(q); 1060 } 1061 1062}