001/* 002 * $Id: RecSolvablePolynomial.java 5226 2015-04-19 10:16:29Z kredel $ 003 */ 004 005package edu.jas.poly; 006 007 008import java.util.Map; 009import java.util.Set; 010import java.util.SortedMap; 011 012import org.apache.log4j.Logger; 013 014import edu.jas.structure.RingElem; 015 016 017/** 018 * RecSolvablePolynomial generic recursive solvable polynomials implementing 019 * RingElem. n-variate ordered solvable polynomials over solvable polynomial 020 * coefficients. Objects of this class are intended to be immutable. The 021 * implementation is based on TreeMap respectively SortedMap from exponents to 022 * coefficients by extension of GenPolynomial. 023 * @param <C> coefficient type 024 * @author Heinz Kredel 025 */ 026 027public class RecSolvablePolynomial<C extends RingElem<C>> extends GenSolvablePolynomial<GenPolynomial<C>> { 028 029 030 /** 031 * The factory for the recursive solvable polynomial ring. Hides super.ring. 032 */ 033 public final RecSolvablePolynomialRing<C> ring; 034 035 036 private static final Logger logger = Logger.getLogger(RecSolvablePolynomial.class); 037 038 039 private final boolean debug = logger.isDebugEnabled(); 040 041 042 /** 043 * Constructor for zero RecSolvablePolynomial. 044 * @param r solvable polynomial ring factory. 045 */ 046 public RecSolvablePolynomial(RecSolvablePolynomialRing<C> r) { 047 super(r); 048 ring = r; 049 } 050 051 052 /** 053 * Constructor for RecSolvablePolynomial. 054 * @param r solvable polynomial ring factory. 055 * @param e exponent. 056 */ 057 public RecSolvablePolynomial(RecSolvablePolynomialRing<C> r, ExpVector e) { 058 this(r); 059 val.put(e, ring.getONECoefficient()); 060 } 061 062 063 /** 064 * Constructor for RecSolvablePolynomial. 065 * @param r solvable polynomial ring factory. 066 * @param c coefficient polynomial. 067 * @param e exponent. 068 */ 069 public RecSolvablePolynomial(RecSolvablePolynomialRing<C> r, GenPolynomial<C> c, ExpVector e) { 070 this(r); 071 if (c != null && !c.isZERO()) { 072 val.put(e, c); 073 } 074 } 075 076 077 /** 078 * Constructor for RecSolvablePolynomial. 079 * @param r solvable polynomial ring factory. 080 * @param c coefficient polynomial. 081 */ 082 public RecSolvablePolynomial(RecSolvablePolynomialRing<C> r, GenPolynomial<C> c) { 083 this(r, c, r.evzero); 084 } 085 086 087 /** 088 * Constructor for RecSolvablePolynomial. 089 * @param r solvable polynomial ring factory. 090 * @param S solvable polynomial. 091 */ 092 public RecSolvablePolynomial(RecSolvablePolynomialRing<C> r, GenSolvablePolynomial<GenPolynomial<C>> S) { 093 this(r, S.val); 094 } 095 096 097 /** 098 * Constructor for RecSolvablePolynomial. 099 * @param r solvable polynomial ring factory. 100 * @param v the SortedMap of some other (solvable) polynomial. 101 */ 102 protected RecSolvablePolynomial(RecSolvablePolynomialRing<C> r, SortedMap<ExpVector, GenPolynomial<C>> v) { 103 this(r); 104 val.putAll(v); // assume no zero coefficients 105 } 106 107 108 /** 109 * Get the corresponding element factory. 110 * @return factory for this Element. 111 * @see edu.jas.structure.Element#factory() 112 */ 113 @Override 114 public RecSolvablePolynomialRing<C> factory() { 115 return ring; 116 } 117 118 119 /** 120 * Clone this RecSolvablePolynomial. 121 * @see java.lang.Object#clone() 122 */ 123 @Override 124 public RecSolvablePolynomial<C> copy() { 125 return new RecSolvablePolynomial<C>(ring, this.val); 126 } 127 128 129 /** 130 * Comparison with any other object. 131 * @see java.lang.Object#equals(java.lang.Object) 132 */ 133 @Override 134 public boolean equals(Object B) { 135 if (!(B instanceof RecSolvablePolynomial)) { 136 return false; 137 } 138 return super.equals(B); 139 } 140 141 142 /** 143 * RecSolvablePolynomial multiplication. 144 * @param Bp RecSolvablePolynomial. 145 * @return this*Bp, where * denotes solvable multiplication. 146 */ 147 // cannot @Override, @NoOverride 148 public RecSolvablePolynomial<C> multiply(RecSolvablePolynomial<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 if (debug) { 157 logger.info("ring = " + ring.toScript()); 158 } 159 final boolean commute = ring.table.isEmpty(); 160 final boolean commuteCoeff = ring.coeffTable.isEmpty(); 161 GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) ring.coFac; 162 RecSolvablePolynomial<C> Dp = ring.getZERO().copy(); 163 //RecSolvablePolynomial<C> zero = ring.getZERO(); //.copy(); not needed 164 ExpVector Z = ring.evzero; 165 ExpVector Zc = cfac.evzero; 166 GenPolynomial<C> one = ring.getONECoefficient(); 167 168 RecSolvablePolynomial<C> C1 = null; 169 RecSolvablePolynomial<C> C2 = null; 170 Map<ExpVector, GenPolynomial<C>> A = val; 171 Map<ExpVector, GenPolynomial<C>> B = Bp.val; 172 Set<Map.Entry<ExpVector, GenPolynomial<C>>> Bk = B.entrySet(); 173 if (debug) 174 logger.info("input A = " + this); 175 for (Map.Entry<ExpVector, GenPolynomial<C>> y : A.entrySet()) { 176 GenPolynomial<C> a = y.getValue(); 177 ExpVector e = y.getKey(); 178 if (debug) 179 logger.info("e = " + e + ", a = " + a); 180 int[] ep = e.dependencyOnVariables(); 181 int el1 = ring.nvar + 1; 182 if (ep.length > 0) { 183 el1 = ep[0]; 184 } 185 //int el1s = ring.nvar + 1 - el1; 186 if (debug) 187 logger.info("input B = " + Bp); 188 for (Map.Entry<ExpVector, GenPolynomial<C>> x : Bk) { 189 GenPolynomial<C> b = x.getValue(); 190 ExpVector f = x.getKey(); 191 if (debug) 192 logger.info("f = " + f + ", b = " + b); 193 int[] fp = f.dependencyOnVariables(); 194 int fl1 = 0; 195 if (fp.length > 0) { 196 fl1 = fp[fp.length - 1]; 197 } 198 int fl1s = ring.nvar + 1 - fl1; 199 // polynomial coefficient multiplication e*b = P_eb, for a*((e*b)*f) 200 RecSolvablePolynomial<C> Cps = ring.getZERO().copy(); 201 RecSolvablePolynomial<C> Cs = null; 202 if (commuteCoeff || b.isConstant() || e.isZERO()) { // symmetric 203 //Cps = new RecSolvablePolynomial<C>(ring, b, e); 204 //Cps = (RecSolvablePolynomial<C>) zero.sum(b, e); 205 Cps.doAddTo(b, e); 206 if (debug) 207 logger.info("symmetric coeff, e*b: b = " + b + ", e = " + e); 208 } else { // unsymmetric 209 if (debug) 210 logger.info("unsymmetric coeff, e*b: b = " + b + ", e = " + e); 211 for (Map.Entry<ExpVector, C> z : b.val.entrySet()) { 212 C c = z.getValue(); 213 GenPolynomial<C> cc = b.ring.valueOf(c); // getONE().multiply(c); 214 ExpVector g = z.getKey(); 215 if (debug) 216 logger.info("g = " + g + ", c = " + c); 217 int[] gp = g.dependencyOnVariables(); 218 int gl1 = 0; 219 if (gp.length > 0) { 220 gl1 = gp[gp.length - 1]; 221 } 222 int gl1s = b.ring.nvar + 1 - gl1; 223 if (debug) { 224 logger.info("gl1s = " + gl1s); 225 } 226 // split e = e1 * e2, g = g2 * g1 (= g1 * g2) 227 ExpVector e1 = e; 228 ExpVector e2 = Z; 229 if (!e.isZERO()) { 230 e1 = e.subst(el1, 0); 231 e2 = Z.subst(el1, e.getVal(el1)); 232 } 233 ExpVector e4; 234 ExpVector g1 = g; 235 ExpVector g2 = Zc; 236 if (!g.isZERO()) { 237 g1 = g.subst(gl1, 0); 238 g2 = Zc.subst(gl1, g.getVal(gl1)); 239 } 240 if (debug) { 241 logger.info("coeff, e1 = " + e1 + ", e2 = " + e2 + ", Cps = " + Cps); 242 logger.info("coeff, g1 = " + g1 + ", g2 = " + g2); 243 } 244 TableRelation<GenPolynomial<C>> crel = ring.coeffTable.lookup(e2, g2); 245 if (debug) 246 logger.info("coeff, crel = " + crel.p); 247 //logger.info("coeff, e = " + e + " g, = " + g + ", crel = " + crel); 248 Cs = new RecSolvablePolynomial<C>(ring, crel.p); 249 // rest of multiplication and update relations 250 if (crel.f != null) { // process remaining right power 251 GenPolynomial<C> c2 = b.ring.valueOf(crel.f); //getONE().multiply(crel.f); 252 C2 = new RecSolvablePolynomial<C>(ring, c2, Z); 253 Cs = Cs.multiply(C2); 254 if (crel.e == null) { 255 e4 = e2; 256 } else { 257 e4 = e2.subtract(crel.e); 258 } 259 ring.coeffTable.update(e4, g2, Cs); 260 } 261 if (crel.e != null) { // process remaining left power 262 C1 = new RecSolvablePolynomial<C>(ring, one, crel.e); 263 Cs = C1.multiply(Cs); 264 ring.coeffTable.update(e2, g2, Cs); 265 } 266 if (!g1.isZERO()) { // process remaining right part 267 GenPolynomial<C> c2 = b.ring.valueOf(g1); //getONE().multiply(g1); 268 C2 = new RecSolvablePolynomial<C>(ring, c2, Z); 269 Cs = Cs.multiply(C2); 270 } 271 if (!e1.isZERO()) { // process remaining left part 272 C1 = new RecSolvablePolynomial<C>(ring, one, e1); 273 Cs = C1.multiply(Cs); 274 } 275 //System.out.println("e1*Cs*g1 = " + Cs); 276 Cs = Cs.multiplyLeft(cc); // assume c, coeff(cc) commutes with Cs 277 //Cps = (RecSolvablePolynomial<C>) Cps.sum(Cs); 278 Cps.doAddTo(Cs); 279 } // end b loop 280 if (debug) 281 logger.info("coeff, Cs = " + Cs + ", Cps = " + Cps); 282 } 283 if (debug) 284 logger.info("coeff-poly: Cps = " + Cps); 285 // polynomial multiplication P_eb*f, for a*(P_eb*f) 286 RecSolvablePolynomial<C> Dps = ring.getZERO().copy(); 287 RecSolvablePolynomial<C> Ds = null; 288 RecSolvablePolynomial<C> D1, D2; 289 if (commute || Cps.isConstant() || f.isZERO()) { // symmetric 290 if (debug) 291 logger.info("symmetric poly, P_eb*f: Cps = " + Cps + ", f = " + f); 292 ExpVector g = e.sum(f); 293 if (Cps.isConstant()) { 294 Ds = new RecSolvablePolynomial<C>(ring, Cps.leadingBaseCoefficient(), g); // symmetric! 295 } else { 296 Ds = shift(Cps, f); // symmetric 297 } 298 } else { // eventually unsymmetric 299 if (debug) 300 logger.info("unsymmetric poly, P_eb*f: Cps = " + Cps + ", f = " + f); 301 for (Map.Entry<ExpVector, GenPolynomial<C>> z : Cps.val.entrySet()) { 302 // split g = g1 * g2, f = f1 * f2 303 GenPolynomial<C> c = z.getValue(); 304 ExpVector g = z.getKey(); 305 if (debug) 306 logger.info("g = " + g + ", c = " + c); 307 int[] gp = g.dependencyOnVariables(); 308 int gl1 = ring.nvar + 1; 309 if (gp.length > 0) { 310 gl1 = gp[0]; 311 } 312 int gl1s = ring.nvar + 1 - gl1; 313 if (gl1s <= fl1s) { // symmetric 314 ExpVector h = g.sum(f); 315 if (debug) 316 logger.info("disjoint poly: g = " + g + ", f = " + f + ", h = " + h); 317 Ds = ring.valueOf(h); // symmetric! //(RecSolvablePolynomial<C>) zero.sum(one, h); 318 } else { 319 ExpVector g1 = g.subst(gl1, 0); 320 ExpVector g2 = Z.subst(gl1, g.getVal(gl1)); // bug el1, gl1 321 ExpVector g4; 322 ExpVector f1 = f.subst(fl1, 0); 323 ExpVector f2 = Z.subst(fl1, f.getVal(fl1)); 324 if (debug) { 325 logger.info("poly, g1 = " + g1 + ", f1 = " + f1 + ", Dps = " + Dps); 326 logger.info("poly, g2 = " + g2 + ", f2 = " + f2); 327 } 328 TableRelation<GenPolynomial<C>> rel = ring.table.lookup(g2, f2); 329 if (debug) 330 logger.info("poly, g = " + g + ", f = " + f + ", rel = " + rel); 331 Ds = new RecSolvablePolynomial<C>(ring, rel.p); //ring.copy(rel.p); 332 if (rel.f != null) { 333 D2 = ring.valueOf(rel.f); //new RecSolvablePolynomial<C>(ring, one, rel.f); 334 Ds = Ds.multiply(D2); 335 if (rel.e == null) { 336 g4 = g2; 337 } else { 338 g4 = g2.subtract(rel.e); 339 } 340 ring.table.update(g4, f2, Ds); 341 } 342 if (rel.e != null) { 343 D1 = ring.valueOf(rel.e); // new RecSolvablePolynomial<C>(ring, one, rel.e); 344 Ds = D1.multiply(Ds); 345 ring.table.update(g2, f2, Ds); 346 } 347 if (!f1.isZERO()) { 348 D2 = ring.valueOf(f1); //new RecSolvablePolynomial<C>(ring, one, f1); 349 Ds = Ds.multiply(D2); 350 //ring.table.update(?,f1,Ds) 351 } 352 if (!g1.isZERO()) { 353 D1 = ring.valueOf(g1); //new RecSolvablePolynomial<C>(ring, one, g1); 354 Ds = D1.multiply(Ds); 355 //ring.table.update(e1,?,Ds) 356 } 357 } 358 Ds = Ds.multiplyLeft(c); // assume c commutes with Cs 359 //Dps = (RecSolvablePolynomial<C>) Dps.sum(Ds); 360 Dps.doAddTo(Ds); 361 } // end Dps loop 362 Ds = Dps; 363 } 364 if (debug) { 365 logger.info("recursion+: Ds = " + Ds + ", a = " + a); 366 } 367 // polynomial coefficient multiplication a*(P_eb*f) = a*Ds 368 Ds = Ds.multiplyLeft(a); // multiply(a,b); // non-symmetric 369 if (debug) 370 logger.info("recursion-: Ds = " + Ds); 371 //Dp = (RecSolvablePolynomial<C>) Dp.sum(Ds); 372 Dp.doAddTo(Ds); 373 if (debug) 374 logger.info("end B loop: Dp = " + Dp); 375 } // end B loop 376 if (debug) 377 logger.info("end A loop: Dp = " + Dp); 378 } // end A loop 379 return Dp; 380 } 381 382 383 /** 384 * RecSolvablePolynomial left and right multiplication. Product with two 385 * polynomials. 386 * @param S RecSolvablePolynomial. 387 * @param T RecSolvablePolynomial. 388 * @return S*this*T. 389 */ 390 // cannot @Override, @NoOverride 391 public RecSolvablePolynomial<C> multiply(RecSolvablePolynomial<C> S, RecSolvablePolynomial<C> T) { 392 if (S.isZERO() || T.isZERO() || this.isZERO()) { 393 return ring.getZERO(); 394 } 395 if (S.isONE()) { 396 return multiply(T); 397 } 398 if (T.isONE()) { 399 return S.multiply(this); 400 } 401 return S.multiply(this).multiply(T); 402 } 403 404 405 /** 406 * RecSolvablePolynomial multiplication. Product with coefficient ring 407 * element. 408 * @param b coefficient polynomial. 409 * @return this*b, where * is coefficient multiplication. 410 */ 411 //todo @Override, @NoOverride 412 //public RecSolvablePolynomial<C> multiply(GenPolynomial<C> b) { 413 //public GenSolvablePolynomial<GenPolynomial<C>> multiply(GenPolynomial<C> b) { 414 public RecSolvablePolynomial<C> recMultiply(GenPolynomial<C> b) { 415 RecSolvablePolynomial<C> Cp = ring.getZERO().copy(); 416 if (b == null || b.isZERO()) { 417 return Cp; 418 } 419 Cp = new RecSolvablePolynomial<C>(ring, b, ring.evzero); 420 return multiply(Cp); 421 // wrong: 422 // Map<ExpVector, GenPolynomial<C>> Cm = Cp.val; //getMap(); 423 // Map<ExpVector, GenPolynomial<C>> Am = val; 424 // for (Map.Entry<ExpVector, GenPolynomial<C>> y : Am.entrySet()) { 425 // ExpVector e = y.getKey(); 426 // GenPolynomial<C> a = y.getValue(); 427 // GenPolynomial<C> c = a.multiply(b); 428 // if (!c.isZERO()) { 429 // Cm.put(e, c); 430 // } 431 // } 432 // return Cp; 433 } 434 435 436 /** 437 * RecSolvablePolynomial left and right multiplication. Product with 438 * coefficient ring element. 439 * @param b coefficient polynomial. 440 * @param c coefficient polynomial. 441 * @return b*this*c, where * is coefficient multiplication. 442 */ 443 @Override 444 public RecSolvablePolynomial<C> multiply(GenPolynomial<C> b, GenPolynomial<C> c) { 445 RecSolvablePolynomial<C> Cp = ring.getZERO().copy(); 446 if (b == null || b.isZERO()) { 447 return Cp; 448 } 449 if (c == null || c.isZERO()) { 450 return Cp; 451 } 452 RecSolvablePolynomial<C> Cb = ring.valueOf(b); //new RecSolvablePolynomial<C>(ring, b, ring.evzero); 453 RecSolvablePolynomial<C> Cc = ring.valueOf(c); //new RecSolvablePolynomial<C>(ring, c, ring.evzero); 454 return Cb.multiply(this).multiply(Cc); 455 // wrong: 456 // Map<ExpVector, GenPolynomial<C>> Cm = Cp.val; //getMap(); 457 // Map<ExpVector, GenPolynomial<C>> Am = val; 458 // for (Map.Entry<ExpVector, GenPolynomial<C>> y : Am.entrySet()) { 459 // ExpVector e = y.getKey(); 460 // GenPolynomial<C> a = y.getValue(); 461 // GenPolynomial<C> d = b.multiply(a).multiply(c); 462 // if (!d.isZERO()) { 463 // Cm.put(e, d); 464 // } 465 // } 466 // return Cp; 467 } 468 469 470 /* 471 * RecSolvablePolynomial multiplication. Product with coefficient ring 472 * element. 473 * @param b coefficient of coefficient. 474 * @return this*b, where * is coefficient multiplication. 475 */ 476 //@Override not possible, @NoOverride 477 //public RecSolvablePolynomial<C> multiply(C b) { ... } 478 479 480 /** 481 * RecSolvablePolynomial multiplication. Product with exponent vector. 482 * @param e exponent. 483 * @return this * x<sup>e</sup>, where * denotes solvable multiplication. 484 */ 485 @Override 486 public RecSolvablePolynomial<C> multiply(ExpVector e) { 487 if (e == null || e.isZERO()) { 488 return this; 489 } 490 GenPolynomial<C> b = ring.getONECoefficient(); 491 return multiply(b, e); 492 } 493 494 495 /** 496 * RecSolvablePolynomial left and right multiplication. Product with 497 * exponent vector. 498 * @param e exponent. 499 * @param f exponent. 500 * @return x<sup>e</sup> * this * x<sup>f</sup>, where * denotes solvable 501 * multiplication. 502 */ 503 @Override 504 public RecSolvablePolynomial<C> multiply(ExpVector e, ExpVector f) { 505 if (e == null || e.isZERO()) { 506 return this; 507 } 508 if (f == null || f.isZERO()) { 509 return this; 510 } 511 GenPolynomial<C> b = ring.getONECoefficient(); 512 return multiply(b, e, b, f); 513 } 514 515 516 /** 517 * RecSolvablePolynomial multiplication. Product with ring element and 518 * exponent vector. 519 * @param b coefficient polynomial. 520 * @param e exponent. 521 * @return this * b x<sup>e</sup>, where * denotes solvable multiplication. 522 */ 523 @Override 524 public RecSolvablePolynomial<C> multiply(GenPolynomial<C> b, ExpVector e) { 525 if (b == null || b.isZERO()) { 526 return ring.getZERO(); 527 } 528 RecSolvablePolynomial<C> Cp = ring.valueOf(b, e); //new RecSolvablePolynomial<C>(ring, b, e); 529 return multiply(Cp); 530 } 531 532 533 /** 534 * RecSolvablePolynomial left and right multiplication. Product with ring 535 * element and exponent vector. 536 * @param b coefficient polynomial. 537 * @param e exponent. 538 * @param c coefficient polynomial. 539 * @param f exponent. 540 * @return b x<sup>e</sup> * this * c x<sup>f</sup>, where * denotes 541 * solvable multiplication. 542 */ 543 @Override 544 public RecSolvablePolynomial<C> multiply(GenPolynomial<C> b, ExpVector e, GenPolynomial<C> c, ExpVector f) { 545 if (b == null || b.isZERO()) { 546 return ring.getZERO(); 547 } 548 if (c == null || c.isZERO()) { 549 return ring.getZERO(); 550 } 551 RecSolvablePolynomial<C> Cp = ring.valueOf(b, e); //new RecSolvablePolynomial<C>(ring, b, e); 552 RecSolvablePolynomial<C> Dp = ring.valueOf(c, f); //new RecSolvablePolynomial<C>(ring, c, f); 553 return multiply(Cp, Dp); 554 } 555 556 557 /** 558 * RecSolvablePolynomial multiplication. Left product with ring element and 559 * exponent vector. 560 * @param b coefficient polynomial. 561 * @param e exponent. 562 * @return b x<sup>e</sup> * this, where * denotes solvable multiplication. 563 */ 564 @Override 565 public RecSolvablePolynomial<C> multiplyLeft(GenPolynomial<C> b, ExpVector e) { 566 if (b == null || b.isZERO()) { 567 return ring.getZERO(); 568 } 569 RecSolvablePolynomial<C> Cp = ring.valueOf(b, e); //new RecSolvablePolynomial<C>(ring, b, e); 570 return Cp.multiply(this); 571 } 572 573 574 /** 575 * RecSolvablePolynomial multiplication. Left product with exponent vector. 576 * @param e exponent. 577 * @return x<sup>e</sup> * this, where * denotes solvable multiplication. 578 */ 579 @Override 580 public RecSolvablePolynomial<C> multiplyLeft(ExpVector e) { 581 if (e == null || e.isZERO()) { 582 return this; 583 } 584 //GenPolynomial<C> b = ring.getONECoefficient(); 585 RecSolvablePolynomial<C> Cp = ring.valueOf(e); // new RecSolvablePolynomial<C>(ring, b, e); 586 return Cp.multiply(this); 587 } 588 589 590 /** 591 * RecSolvablePolynomial multiplication. Left product with coefficient ring 592 * element. 593 * @param b coefficient polynomial. 594 * @return b*this, where * is coefficient multiplication. 595 */ 596 @Override 597 public RecSolvablePolynomial<C> multiplyLeft(GenPolynomial<C> b) { 598 RecSolvablePolynomial<C> Cp = ring.getZERO().copy(); 599 if (b == null || b.isZERO()) { 600 return Cp; 601 } 602 GenSolvablePolynomial<C> bb = null; 603 if (b instanceof GenSolvablePolynomial) { 604 //throw new RuntimeException("wrong method dispatch in JRE "); 605 logger.debug("warn: wrong method dispatch in JRE multiply(b) - trying to fix"); 606 bb = (GenSolvablePolynomial<C>) b; 607 } 608 Map<ExpVector, GenPolynomial<C>> Cm = Cp.val; //getMap(); 609 Map<ExpVector, GenPolynomial<C>> Am = val; 610 GenPolynomial<C> c; 611 for (Map.Entry<ExpVector, GenPolynomial<C>> y : Am.entrySet()) { 612 ExpVector e = y.getKey(); 613 GenPolynomial<C> a = y.getValue(); 614 if (bb != null) { 615 GenSolvablePolynomial<C> aa = (GenSolvablePolynomial<C>) a; 616 c = bb.multiply(aa); 617 } else { 618 c = b.multiply(a); 619 } 620 if (!c.isZERO()) { 621 Cm.put(e, c); 622 } 623 } 624 return Cp; 625 } 626 627 628 /** 629 * RecSolvablePolynomial multiplication. Left product with 'monomial'. 630 * @param m 'monomial'. 631 * @return m * this, where * denotes solvable multiplication. 632 */ 633 @Override 634 public RecSolvablePolynomial<C> multiplyLeft(Map.Entry<ExpVector, GenPolynomial<C>> m) { 635 if (m == null) { 636 return ring.getZERO(); 637 } 638 return multiplyLeft(m.getValue(), m.getKey()); 639 } 640 641 642 /** 643 * RecSolvablePolynomial multiplication. Product with 'monomial'. 644 * @param m 'monomial'. 645 * @return this * m, where * denotes solvable multiplication. 646 */ 647 @Override 648 public RecSolvablePolynomial<C> multiply(Map.Entry<ExpVector, GenPolynomial<C>> m) { 649 if (m == null) { 650 return ring.getZERO(); 651 } 652 return multiply(m.getValue(), m.getKey()); 653 } 654 655 656 /** 657 * RecSolvablePolynomial multiplication. Commutative product with exponent 658 * vector. 659 * @param B solvable polynomial. 660 * @param f exponent vector. 661 * @return B*f, where * is commutative multiplication. 662 */ 663 protected RecSolvablePolynomial<C> shift(RecSolvablePolynomial<C> B, ExpVector f) { 664 RecSolvablePolynomial<C> C = ring.getZERO().copy(); 665 if (B == null || B.isZERO()) { 666 return C; 667 } 668 if (f == null || f.isZERO()) { 669 return B; 670 } 671 Map<ExpVector, GenPolynomial<C>> Cm = C.val; 672 Map<ExpVector, GenPolynomial<C>> Bm = B.val; 673 for (Map.Entry<ExpVector, GenPolynomial<C>> y : Bm.entrySet()) { 674 ExpVector e = y.getKey(); 675 GenPolynomial<C> a = y.getValue(); 676 ExpVector d = e.sum(f); 677 if (!a.isZERO()) { 678 Cm.put(d, a); 679 } 680 } 681 return C; 682 } 683 684 685 /** 686 * RecSolvablePolynomial right coefficients from left coefficients. 687 * <b>Note:</b> R is represented as a polynomial with left coefficients, the 688 * implementation can at the moment not distinguish between left and right 689 * coefficients. 690 * @return R = sum( X<sup>i</sup> b<sub>i</sub> ), with this = 691 * sum(a<sub>i</sub> X<sup>i</sup> ) and eval(sum(X<sup>i</sup> 692 * b<sub>i</sub>)) == sum(a<sub>i</sub> X<sup>i</sup>) 693 */ 694 @SuppressWarnings("cast") 695 @Override 696 public GenSolvablePolynomial<GenPolynomial<C>> rightRecursivePolynomial() { 697 if (this.isONE() || this.isZERO()) { 698 return this; 699 } 700 if (!(this instanceof RecSolvablePolynomial)) { 701 return this; 702 } 703 RecSolvablePolynomialRing<C> rfac = (RecSolvablePolynomialRing<C>) ring; 704 if (rfac.coeffTable.isEmpty()) { 705 return this; 706 } 707 GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) rfac.coFac; 708 GenPolynomial<C> one = cfac.getONE(); 709 RecSolvablePolynomial<C> onep = rfac.getONE(); 710 ExpVector zero = rfac.evzero; 711 RecSolvablePolynomial<C> R = rfac.getZERO(); 712 RecSolvablePolynomial<C> r; 713 RecSolvablePolynomial<C> p = (RecSolvablePolynomial<C>) this; 714 while (!p.isZERO()) { 715 ExpVector f = p.leadingExpVector(); 716 GenPolynomial<C> a = p.leadingBaseCoefficient(); 717 //r = h.multiply(a); // wrong method dispatch // right: f*a 718 r = onep.multiply(one, f, a, zero); // right: (1 f) * 1 * (a zero) 719 //System.out.println("a,f = " + a + ", " + f); // + ", h.ring = " + h.ring.toScript()); 720 //System.out.println("f*a = " + r); // + ", r.ring = " + r.ring.toScript()); 721 p = (RecSolvablePolynomial<C>) p.subtract(r); 722 R = (RecSolvablePolynomial<C>) R.sum(a, f); 723 } 724 return R; 725 } 726 727 728 /** 729 * Evaluate RecSolvablePolynomial as right coefficients polynomial. 730 * <b>Note:</b> R is represented as a polynomial with left coefficients, the 731 * implementation can at the moment not distinguish between left and right 732 * coefficients. 733 * @return this as evaluated polynomial R. R = sum( X<sup>i</sup> 734 * b<sub>i</sub> ), this = sum(a<sub>i</sub> X<sup>i</sup> ) = 735 * eval(sum(X<sup>i</sup> b<sub>i</sub>)) 736 */ 737 @SuppressWarnings("cast") 738 @Override 739 public GenSolvablePolynomial<GenPolynomial<C>> evalAsRightRecursivePolynomial() { 740 if (this.isONE() || this.isZERO()) { 741 return this; 742 } 743 if (!(this instanceof RecSolvablePolynomial)) { 744 return this; 745 } 746 RecSolvablePolynomialRing<C> rfac = (RecSolvablePolynomialRing<C>) ring; 747 if (rfac.coeffTable.isEmpty()) { 748 return this; 749 } 750 GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) rfac.coFac; 751 GenPolynomial<C> one = cfac.getONE(); 752 RecSolvablePolynomial<C> onep = rfac.getONE(); 753 ExpVector zero = rfac.evzero; 754 RecSolvablePolynomial<C> q = rfac.getZERO(); 755 RecSolvablePolynomial<C> s; 756 RecSolvablePolynomial<C> r = (RecSolvablePolynomial<C>) this; 757 for (Map.Entry<ExpVector, GenPolynomial<C>> y : r.getMap().entrySet()) { 758 ExpVector f = y.getKey(); 759 GenPolynomial<C> a = y.getValue(); 760 // f.multiply(a); // wrong method dispatch // right: f*a 761 // onep.multiply(f).multiply(a) // should do now 762 s = onep.multiply(one, f, a, zero); // right: (1 f) * 1 * (a zero) 763 q = (RecSolvablePolynomial<C>) q.sum(s); 764 } 765 return q; 766 } 767 768 769 /** 770 * Test RecSolvablePolynomial right coefficients polynomial. <b>Note:</b> R 771 * is represented as a polynomial with left coefficients, the implementation 772 * can at the moment not distinguish between left and right coefficients. 773 * @param R GenSolvablePolynomial with right coefficients. 774 * @return true, if R is polynomial with right coefficients of this. R = 775 * sum( X<sup>i</sup> b<sub>i</sub> ), with this = sum(a<sub>i</sub> 776 * X<sup>i</sup> ) and eval(sum(X<sup>i</sup> b<sub>i</sub>)) == 777 * sum(a<sub>i</sub> X<sup>i</sup>) 778 */ 779 @SuppressWarnings("cast") 780 @Override 781 public boolean isRightRecursivePolynomial(GenSolvablePolynomial<GenPolynomial<C>> R) { 782 if (this.isZERO()) { 783 return R.isZERO(); 784 } 785 if (this.isONE()) { 786 return R.isONE(); 787 } 788 if (!(this instanceof RecSolvablePolynomial)) { 789 return !(R instanceof RecSolvablePolynomial); 790 } 791 if (!(R instanceof RecSolvablePolynomial)) { 792 return false; 793 } 794 RecSolvablePolynomialRing<C> rfac = (RecSolvablePolynomialRing<C>) ring; 795 if (rfac.coeffTable.isEmpty()) { 796 RecSolvablePolynomialRing<C> rf = (RecSolvablePolynomialRing<C>) R.ring; 797 return rf.coeffTable.isEmpty(); 798 } 799 RecSolvablePolynomial<C> p = (RecSolvablePolynomial<C>) this; 800 RecSolvablePolynomial<C> q = (RecSolvablePolynomial<C>) R.evalAsRightRecursivePolynomial(); 801 p = (RecSolvablePolynomial<C>) PolyUtil.<C> monic(p); 802 q = (RecSolvablePolynomial<C>) PolyUtil.<C> monic(q); 803 return p.equals(q); 804 } 805 806}