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.GcdRingElem; 016import edu.jas.structure.QuotPair; 017import edu.jas.structure.RingFactory; 018 019 020/** 021 * QLRSolvablePolynomial generic recursive solvable polynomials implementing 022 * RingElem. n-variate ordered solvable polynomials over solvable quotient, 023 * local and local-residue coefficients. Objects of this class are intended to 024 * be immutable. The implementation is based on TreeMap respectively SortedMap 025 * from exponents to coefficients by extension of GenPolynomial. 026 * @param <C> polynomial coefficient type 027 * @param <D> quotient coefficient type 028 * @author Heinz Kredel 029 */ 030 031public class QLRSolvablePolynomial<C extends GcdRingElem<C> & QuotPair<GenPolynomial<D>>, D extends GcdRingElem<D>> 032 extends GenSolvablePolynomial<C> { 033 034 035 private static final Logger logger = LogManager.getLogger(QLRSolvablePolynomial.class); 036 037 038 private static final boolean debug = logger.isDebugEnabled(); 039 040 041 /** 042 * The factory for the recursive solvable polynomial ring. Hides super.ring. 043 */ 044 public final QLRSolvablePolynomialRing<C, D> ring; 045 046 047 /** 048 * Constructor for zero QLRSolvablePolynomial. 049 * @param r solvable polynomial ring factory. 050 */ 051 public QLRSolvablePolynomial(QLRSolvablePolynomialRing<C, D> r) { 052 super(r); 053 ring = r; 054 } 055 056 057 /** 058 * Constructor for QLRSolvablePolynomial. 059 * @param r solvable polynomial ring factory. 060 * @param c coefficient polynomial. 061 * @param e exponent. 062 */ 063 public QLRSolvablePolynomial(QLRSolvablePolynomialRing<C, D> r, C c, ExpVector e) { 064 this(r); 065 if (c != null && !c.isZERO()) { 066 val.put(e, c); 067 } 068 } 069 070 071 /** 072 * Constructor for QLRSolvablePolynomial. 073 * @param r solvable polynomial ring factory. 074 * @param c coefficient polynomial. 075 */ 076 public QLRSolvablePolynomial(QLRSolvablePolynomialRing<C, D> r, C c) { 077 this(r, c, r.evzero); 078 } 079 080 081 /** 082 * Constructor for QLRSolvablePolynomial. 083 * @param r solvable polynomial ring factory. 084 * @param S solvable polynomial. 085 */ 086 public QLRSolvablePolynomial(QLRSolvablePolynomialRing<C, D> r, GenSolvablePolynomial<C> S) { 087 this(r, S.getMap()); 088 } 089 090 091 /** 092 * Constructor for QLRSolvablePolynomial. 093 * @param r solvable polynomial ring factory. 094 * @param v the SortedMap of some other (solvable) polynomial. 095 */ 096 protected QLRSolvablePolynomial(QLRSolvablePolynomialRing<C, D> r, SortedMap<ExpVector, C> v) { 097 this(r); 098 val.putAll(v); // assume no zero coefficients 099 } 100 101 102 /** 103 * Get the corresponding element factory. 104 * @return factory for this Element. 105 * @see edu.jas.structure.Element#factory() 106 */ 107 @Override 108 public QLRSolvablePolynomialRing<C, D> factory() { 109 return ring; 110 } 111 112 113 /** 114 * Clone this QLRSolvablePolynomial. 115 * @see java.lang.Object#clone() 116 */ 117 @Override 118 public QLRSolvablePolynomial<C, D> copy() { 119 return new QLRSolvablePolynomial<C, D>(ring, this.val); 120 } 121 122 123 /** 124 * Comparison with any other object. 125 * @see java.lang.Object#equals(java.lang.Object) 126 */ 127 @Override 128 public boolean equals(Object B) { 129 if (!(B instanceof QLRSolvablePolynomial)) { 130 return false; 131 } 132 return super.equals(B); 133 } 134 135 136 /** 137 * Hash code for this polynomial. 138 * @see java.lang.Object#hashCode() 139 */ 140 @Override 141 public int hashCode() { 142 return super.hashCode(); 143 } 144 145 146 /** 147 * QLRSolvablePolynomial multiplication. 148 * @param Bp QLRSolvablePolynomial. 149 * @return this*Bp, where * denotes solvable multiplication. 150 */ 151 // not @Override 152 @SuppressWarnings("unchecked") 153 public QLRSolvablePolynomial<C, D> multiply(QLRSolvablePolynomial<C, D> Bp) { 154 if (Bp == null || Bp.isZERO()) { 155 return ring.getZERO(); 156 } 157 if (this.isZERO()) { 158 return this; 159 } 160 if (Bp.isONE()) { 161 return this; 162 } 163 if (this.isONE()) { 164 return Bp; 165 } 166 assert (ring.nvar == Bp.ring.nvar); 167 if (debug) { 168 logger.debug("ring = {}", ring); 169 } 170 //System.out.println("this = " + this + ", Bp = " + Bp); 171 ExpVector Z = ring.evzero; 172 QLRSolvablePolynomial<C, D> Dp = ring.getZERO().copy(); 173 QLRSolvablePolynomial<C, D> zero = ring.getZERO().copy(); 174 C one = ring.getONECoefficient(); 175 176 Map<ExpVector, C> A = val; 177 Map<ExpVector, C> B = Bp.val; 178 Set<Map.Entry<ExpVector, C>> Bk = B.entrySet(); 179 for (Map.Entry<ExpVector, C> y : A.entrySet()) { 180 C a = y.getValue(); 181 ExpVector e = y.getKey(); 182 if (debug) 183 logger.info("e = {}, a = {}", e, a); 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 if (debug) 194 logger.info("f = {}, b = {}", f, b); 195 int[] fp = f.dependencyOnVariables(); 196 int fl1 = 0; 197 if (fp.length > 0) { 198 fl1 = fp[fp.length - 1]; 199 } 200 int fl1s = ring.nvar + 1 - fl1; 201 // polynomial with coefficient multiplication 202 QLRSolvablePolynomial<C, D> Cps = ring.getZERO().copy(); 203 //QLRSolvablePolynomial<C, D> Cs; 204 QLRSolvablePolynomial<C, D> qp; 205 if (ring.polCoeff.isCommutative() || b.isConstant() || e.isZERO()) { // symmetric 206 Cps = new QLRSolvablePolynomial<C, D>(ring, b, e); 207 if (debug) 208 logger.info("symmetric coeff: b = {}, e = {}", b, e); 209 } else { // unsymmetric 210 if (debug) 211 logger.info("unsymmetric coeff: b = {}, e = {}", b, e); 212 // compute e * b as ( e * 1/b.den ) * b.num 213 if (b.denominator().isONE()) { // recursion base 214 // recursive polynomial coefficient multiplication : e * b.num 215 RecSolvablePolynomial<D> rsp1 = new RecSolvablePolynomial<D>(ring.polCoeff, e); 216 RecSolvablePolynomial<D> rsp2 = new RecSolvablePolynomial<D>(ring.polCoeff, 217 b.numerator()); 218 RecSolvablePolynomial<D> rsp3 = rsp1.multiply(rsp2); 219 QLRSolvablePolynomial<C, D> rsp = ring.fromPolyCoefficients(rsp3); 220 Cps = rsp; 221 } else { // b.denominator() != 1 222 if (debug) 223 logger.info("coeff-num: Cps = {}, num = {}, den = {}", Cps, b.numerator(), 224 b.denominator()); 225 RingFactory<C> bfq = (RingFactory<C>) b.factory(); 226 Cps = new QLRSolvablePolynomial<C, D>(ring, bfq.getONE(), e); 227 228 // coefficient multiplication with 1/den: 229 QLRSolvablePolynomial<C, D> qv = Cps; 230 //C qden = new C(b.denominator().factory(), b.denominator()); // den/1 231 C qden = ring.qpfac.create(b.denominator()); // den/1 232 //System.out.println("qv = " + qv + ", den = " + den); 233 // recursion with den==1: 234 QLRSolvablePolynomial<C, D> v = qv.multiply(qden); 235 QLRSolvablePolynomial<C, D> vl = qv.multiplyLeft(qden); 236 //System.out.println("v = " + v + ", vl = " + vl + ", qden = " + qden); 237 QLRSolvablePolynomial<C, D> vr = (QLRSolvablePolynomial<C, D>) v.subtract(vl); 238 //C qdeni = new C(b.factory(), b.factory().getONE().numerator(), b.denominator()); 239 C qdeni = ring.qpfac.create(ring.qpfac.pairFactory().getONE(), b.denominator()); // 1/den 240 //System.out.println("vr = " + vr + ", qdeni = " + qdeni); 241 // recursion with smaller head term: 242 if (qv.leadingExpVector().equals(vr.leadingExpVector())) { 243 throw new IllegalArgumentException("qv !> vr: qv = " + qv + ", vr = " + vr); 244 } 245 QLRSolvablePolynomial<C, D> rq = vr.multiply(qdeni); 246 qp = (QLRSolvablePolynomial<C, D>) qv.subtract(rq); 247 qp = qp.multiplyLeft(qdeni); 248 //System.out.println("qp_i = " + qp); 249 Cps = qp; 250 251 if (!b.numerator().isONE()) { 252 //C qnum = new C(b.denominator().factory(), b.numerator()); // num/1 253 C qnum = ring.qpfac.create(b.numerator()); // num/1 254 // recursion with den == 1: 255 Cps = Cps.multiply(qnum); 256 } 257 } 258 } // end coeff 259 if (debug) 260 logger.info("coeff-den: Cps = {}", Cps); 261 // polynomial multiplication 262 QLRSolvablePolynomial<C, D> Dps = ring.getZERO().copy(); 263 QLRSolvablePolynomial<C, D> Ds = null; 264 QLRSolvablePolynomial<C, D> D1, D2; 265 if (ring.isCommutative() || Cps.isConstant() || f.isZERO()) { // symmetric 266 if (debug) 267 logger.info("symmetric poly: b = {}, e = {}", b, e); 268 if (Cps.isConstant()) { 269 ExpVector g = e.sum(f); 270 Ds = new QLRSolvablePolynomial<C, D>(ring, Cps.leadingBaseCoefficient(), g); // symmetric! 271 } else { 272 Ds = Cps.shift(f); // symmetric 273 } 274 } else { // eventually unsymmetric 275 if (debug) 276 logger.info("unsymmetric poly: Cps = {}, f = {}", Cps, f); 277 for (Map.Entry<ExpVector, C> z : Cps.val.entrySet()) { 278 // split g = g1 * g2, f = f1 * f2 279 C c = z.getValue(); 280 ExpVector g = z.getKey(); 281 if (debug) 282 logger.info("g = {}, c = {}", g, c); 283 int[] gp = g.dependencyOnVariables(); 284 int gl1 = ring.nvar + 1; 285 if (gp.length > 0) { 286 gl1 = gp[0]; 287 } 288 int gl1s = ring.nvar + 1 - gl1; 289 if (gl1s <= fl1s) { // symmetric 290 ExpVector h = g.sum(f); 291 if (debug) 292 logger.info("disjoint poly: g = {}, f = {}, h = {}", g, f, h); 293 Ds = (QLRSolvablePolynomial<C, D>) zero.sum(one, h); // symmetric! 294 } else { 295 ExpVector g1 = g.subst(gl1, 0); 296 ExpVector g2 = Z.subst(gl1, g.getVal(gl1)); // bug el1, gl1 297 ExpVector g4; 298 ExpVector f1 = f.subst(fl1, 0); 299 ExpVector f2 = Z.subst(fl1, f.getVal(fl1)); 300 if (debug) { 301 logger.info("poly, g1 = {}, f1 = {}, Dps = {}", g1, f1, Dps); 302 logger.info("poly, g2 = {}, f2 = {}", g2, f2); 303 } 304 TableRelation<C> rel = ring.table.lookup(g2, f2); 305 if (debug) 306 logger.info("poly, g = {}, f = {}, rel = {}", g, f, rel); 307 Ds = new QLRSolvablePolynomial<C, D>(ring, rel.p); //ring.copy(rel.p); 308 if (rel.f != null) { 309 D2 = new QLRSolvablePolynomial<C, D>(ring, one, rel.f); 310 Ds = Ds.multiply(D2); 311 if (rel.e == null) { 312 g4 = g2; 313 } else { 314 g4 = g2.subtract(rel.e); 315 } 316 ring.table.update(g4, f2, Ds); 317 } 318 if (rel.e != null) { 319 D1 = new QLRSolvablePolynomial<C, D>(ring, one, rel.e); 320 Ds = D1.multiply(Ds); 321 ring.table.update(g2, f2, Ds); 322 } 323 if (!f1.isZERO()) { 324 D2 = new QLRSolvablePolynomial<C, D>(ring, one, f1); 325 Ds = Ds.multiply(D2); 326 //ring.table.update(?,f1,Ds) 327 } 328 if (!g1.isZERO()) { 329 D1 = new QLRSolvablePolynomial<C, D>(ring, one, g1); 330 Ds = D1.multiply(Ds); 331 //ring.table.update(e1,?,Ds) 332 } 333 } 334 Ds = Ds.multiplyLeft(c); // c * Ds 335 //Dps = (QLRSolvablePolynomial<C, D>) Dps.sum(Ds); 336 Dps.doAddTo(Ds); 337 } // end Dps loop 338 Ds = Dps; 339 } 340 Ds = Ds.multiplyLeft(a); // multiply(a,b); // non-symmetric 341 if (debug) 342 logger.debug("Ds = {}", Ds); 343 //Dp = (QLRSolvablePolynomial<C, D>) Dp.sum(Ds); 344 Dp.doAddTo(Ds); 345 } // end B loop 346 } // end A loop 347 //System.out.println("this * Bp = " + Dp); 348 return Dp; 349 } 350 351 352 /** 353 * QLRSolvablePolynomial left and right multiplication. Product with two 354 * polynomials. 355 * @param S QLRSolvablePolynomial. 356 * @param T QLRSolvablePolynomial. 357 * @return S*this*T. 358 */ 359 // not @Override 360 public QLRSolvablePolynomial<C, D> multiply(QLRSolvablePolynomial<C, D> S, 361 QLRSolvablePolynomial<C, D> T) { 362 if (S.isZERO() || T.isZERO() || this.isZERO()) { 363 return ring.getZERO(); 364 } 365 if (S.isONE()) { 366 return multiply(T); 367 } 368 if (T.isONE()) { 369 return S.multiply(this); 370 } 371 return S.multiply(this).multiply(T); 372 } 373 374 375 /** 376 * QLRSolvablePolynomial multiplication. Product with coefficient ring 377 * element. 378 * @param b solvable coefficient. 379 * @return this*b, where * is coefficient multiplication. 380 */ 381 @Override 382 public QLRSolvablePolynomial<C, D> multiply(C b) { 383 QLRSolvablePolynomial<C, D> Cp = ring.getZERO().copy(); 384 if (b == null || b.isZERO()) { 385 return Cp; 386 } 387 if (b.isONE()) { 388 return this; 389 } 390 Cp = new QLRSolvablePolynomial<C, D>(ring, b, ring.evzero); 391 return multiply(Cp); 392 } 393 394 395 /** 396 * QLRSolvablePolynomial left and right multiplication. Product with 397 * coefficient ring element. 398 * @param b coefficient polynomial. 399 * @param c coefficient polynomial. 400 * @return b*this*c, where * is coefficient multiplication. 401 */ 402 @Override 403 public QLRSolvablePolynomial<C, D> multiply(C b, C c) { 404 QLRSolvablePolynomial<C, D> Cp = ring.getZERO().copy(); 405 if (b == null || b.isZERO()) { 406 return Cp; 407 } 408 if (c == null || c.isZERO()) { 409 return Cp; 410 } 411 if (b.isONE() && c.isONE()) { 412 return this; 413 } 414 Cp = new QLRSolvablePolynomial<C, D>(ring, b, ring.evzero); 415 QLRSolvablePolynomial<C, D> Dp = new QLRSolvablePolynomial<C, D>(ring, c, ring.evzero); 416 return multiply(Cp, Dp); 417 } 418 419 420 /** 421 * QLRSolvablePolynomial multiplication. Product with exponent vector. 422 * @param e exponent. 423 * @return this * x<sup>e</sup>, where * denotes solvable multiplication. 424 */ 425 @Override 426 public QLRSolvablePolynomial<C, D> multiply(ExpVector e) { 427 if (e == null || e.isZERO()) { 428 return this; 429 } 430 C b = ring.getONECoefficient(); 431 return multiply(b, e); 432 } 433 434 435 /** 436 * QLRSolvablePolynomial left and right multiplication. Product with 437 * exponent vector. 438 * @param e exponent. 439 * @param f exponent. 440 * @return x<sup>e</sup> * this * x<sup>f</sup>, where * denotes solvable 441 * multiplication. 442 */ 443 @Override 444 public QLRSolvablePolynomial<C, D> multiply(ExpVector e, ExpVector f) { 445 if (e == null || e.isZERO()) { 446 return this; 447 } 448 if (f == null || f.isZERO()) { 449 return this; 450 } 451 C b = ring.getONECoefficient(); 452 return multiply(b, e, b, f); 453 } 454 455 456 /** 457 * QLRSolvablePolynomial multiplication. Product with ring element and 458 * exponent vector. 459 * @param b coefficient polynomial. 460 * @param e exponent. 461 * @return this * b x<sup>e</sup>, where * denotes solvable multiplication. 462 */ 463 @Override 464 public QLRSolvablePolynomial<C, D> multiply(C b, ExpVector e) { 465 if (b == null || b.isZERO()) { 466 return ring.getZERO(); 467 } 468 if (b.isONE() && e.isZERO()) { 469 return this; 470 } 471 QLRSolvablePolynomial<C, D> Cp = new QLRSolvablePolynomial<C, D>(ring, b, e); 472 return multiply(Cp); 473 } 474 475 476 /** 477 * QLRSolvablePolynomial left and right multiplication. Product with ring 478 * element and exponent vector. 479 * @param b coefficient polynomial. 480 * @param e exponent. 481 * @param c coefficient polynomial. 482 * @param f exponent. 483 * @return b x<sup>e</sup> * this * c x<sup>f</sup>, where * denotes 484 * solvable multiplication. 485 */ 486 @Override 487 public QLRSolvablePolynomial<C, D> multiply(C b, ExpVector e, C c, ExpVector f) { 488 if (b == null || b.isZERO()) { 489 return ring.getZERO(); 490 } 491 if (c == null || c.isZERO()) { 492 return ring.getZERO(); 493 } 494 if (b.isONE() && e.isZERO() && c.isONE() && f.isZERO()) { 495 return this; 496 } 497 QLRSolvablePolynomial<C, D> Cp = new QLRSolvablePolynomial<C, D>(ring, b, e); 498 QLRSolvablePolynomial<C, D> Dp = new QLRSolvablePolynomial<C, D>(ring, c, f); 499 return multiply(Cp, Dp); 500 } 501 502 503 /** 504 * QLRSolvablePolynomial multiplication. Left product with ring element and 505 * exponent vector. 506 * @param b coefficient polynomial. 507 * @param e exponent. 508 * @return b x<sup>e</sup> * this, where * denotes solvable multiplication. 509 */ 510 @Override 511 public QLRSolvablePolynomial<C, D> multiplyLeft(C b, ExpVector e) { 512 if (b == null || b.isZERO()) { 513 return ring.getZERO(); 514 } 515 QLRSolvablePolynomial<C, D> Cp = new QLRSolvablePolynomial<C, D>(ring, b, e); 516 return Cp.multiply(this); 517 } 518 519 520 /** 521 * QLRSolvablePolynomial multiplication. Left product with exponent vector. 522 * @param e exponent. 523 * @return x<sup>e</sup> * this, where * denotes solvable multiplication. 524 */ 525 @Override 526 public QLRSolvablePolynomial<C, D> multiplyLeft(ExpVector e) { 527 if (e == null || e.isZERO()) { 528 return this; 529 } 530 C b = ring.getONECoefficient(); 531 QLRSolvablePolynomial<C, D> Cp = new QLRSolvablePolynomial<C, D>(ring, b, e); 532 return Cp.multiply(this); 533 } 534 535 536 /** 537 * QLRSolvablePolynomial multiplication. Left product with coefficient ring 538 * element. 539 * @param b coefficient polynomial. 540 * @return b*this, where * is coefficient multiplication. 541 */ 542 @Override 543 public QLRSolvablePolynomial<C, D> multiplyLeft(C b) { 544 QLRSolvablePolynomial<C, D> Cp = ring.getZERO().copy(); 545 if (b == null || b.isZERO()) { 546 return Cp; 547 } 548 Map<ExpVector, C> Cm = Cp.val; //getMap(); 549 Map<ExpVector, C> Am = val; 550 C c; 551 for (Map.Entry<ExpVector, C> y : Am.entrySet()) { 552 ExpVector e = y.getKey(); 553 C a = y.getValue(); 554 c = b.multiply(a); 555 if (!c.isZERO()) { 556 Cm.put(e, c); 557 } 558 } 559 return Cp; 560 } 561 562 563 /** 564 * QLRSolvablePolynomial multiplication. Left product with 'monomial'. 565 * @param m 'monomial'. 566 * @return m * this, where * denotes solvable multiplication. 567 */ 568 @Override 569 public QLRSolvablePolynomial<C, D> multiplyLeft(Map.Entry<ExpVector, C> m) { 570 if (m == null) { 571 return ring.getZERO(); 572 } 573 return multiplyLeft(m.getValue(), m.getKey()); 574 } 575 576 577 /** 578 * QLRSolvablePolynomial multiplication. Product with 'monomial'. 579 * @param m 'monomial'. 580 * @return this * m, where * denotes solvable multiplication. 581 */ 582 @Override 583 public QLRSolvablePolynomial<C, D> multiply(Map.Entry<ExpVector, C> m) { 584 if (m == null) { 585 return ring.getZERO(); 586 } 587 return multiply(m.getValue(), m.getKey()); 588 } 589 590 591 /** 592 * QLRSolvablePolynomial multiplication with exponent vector. 593 * @param f exponent vector. 594 * @return B*f, where * is commutative multiplication. 595 */ 596 protected QLRSolvablePolynomial<C, D> shift(ExpVector f) { 597 QLRSolvablePolynomial<C, D> C = ring.getZERO().copy(); 598 if (this.isZERO()) { 599 return C; 600 } 601 if (f == null || f.isZERO()) { 602 return this; 603 } 604 Map<ExpVector, C> Cm = C.val; 605 Map<ExpVector, C> Bm = this.val; 606 for (Map.Entry<ExpVector, C> y : Bm.entrySet()) { 607 ExpVector e = y.getKey(); 608 C a = y.getValue(); 609 ExpVector d = e.sum(f); 610 if (!a.isZERO()) { 611 Cm.put(d, a); 612 } 613 } 614 return C; 615 } 616 617}