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