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