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