001/* 002 * $Id: FDUtil.java 5267 2015-07-27 17:57:50Z kredel $ 003 */ 004 005package edu.jas.fd; 006 007 008import java.util.ArrayList; 009import java.util.Collection; 010import java.util.List; 011import java.util.Map; 012 013import org.apache.log4j.Logger; 014 015import edu.jas.gbufd.SolvableQuotient; 016import edu.jas.gbufd.SolvableQuotientRing; 017import edu.jas.poly.ExpVector; 018import edu.jas.poly.GenPolynomial; 019import edu.jas.poly.GenPolynomialRing; 020import edu.jas.poly.GenSolvablePolynomial; 021import edu.jas.poly.GenSolvablePolynomialRing; 022import edu.jas.poly.PolyUtil; 023import edu.jas.poly.RecSolvablePolynomial; 024import edu.jas.poly.RecSolvablePolynomialRing; 025import edu.jas.structure.GcdRingElem; 026import edu.jas.structure.RingElem; 027import edu.jas.structure.RingFactory; 028 029 030/** 031 * Factorization domain utilities, for example recursive pseudo remainder. 032 * @author Heinz Kredel 033 */ 034 035public class FDUtil { 036 037 038 private static final Logger logger = Logger.getLogger(FDUtil.class); 039 040 041 private static boolean debug = logger.isDebugEnabled(); 042 043 044 /** 045 * GenSolvablePolynomial sparse pseudo remainder for univariate polynomials. 046 * @param <C> coefficient type. 047 * @param P GenSolvablePolynomial. 048 * @param S nonzero GenSolvablePolynomial. 049 * @return remainder with ore(ldcf(S)<sup>m'</sup>) P = quotient * S + 050 * remainder. m' ≤ deg(P)-deg(S) 051 * @see edu.jas.poly.GenPolynomial#remainder(edu.jas.poly.GenPolynomial). 052 */ 053 public static <C extends GcdRingElem<C>> GenSolvablePolynomial<C> leftBaseSparsePseudoRemainder( 054 GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) { 055 if (S == null || S.isZERO()) { 056 throw new ArithmeticException(P.toString() + " division by zero " + S); 057 } 058 if (P.isZERO()) { 059 return P; 060 } 061 if (S.isConstant()) { 062 return P.ring.getZERO(); 063 } 064 if (P instanceof RecSolvablePolynomial) { 065 RecSolvablePolynomial<C> Pr = (RecSolvablePolynomial) P; 066 if (!Pr.ring.coeffTable.isEmpty()) { 067 throw new UnsupportedOperationException( 068 "RecSolvablePolynomial with twisted coeffs not supported"); 069 } 070 } 071 GreatestCommonDivisorAbstract<C> fd = new GreatestCommonDivisorSimple<C>(P.ring.coFac); 072 ExpVector e = S.leadingExpVector(); 073 GenSolvablePolynomial<C> h; 074 GenSolvablePolynomial<C> r = P; 075 while (!r.isZERO()) { 076 ExpVector f = r.leadingExpVector(); 077 if (f.multipleOf(e)) { 078 C a = r.leadingBaseCoefficient(); 079 f = f.subtract(e); 080 h = S.multiplyLeft(f); // coeff a 081 C c = h.leadingBaseCoefficient(); 082 // need ga, gc: ga a = gc c 083 C[] oc = fd.leftOreCond(a, c); 084 C ga = oc[0]; 085 C gc = oc[1]; 086 r = r.multiplyLeft(ga); // coeff ga a, exp f 087 h = h.multiplyLeft(gc); // coeff gc c, exp f 088 r = (GenSolvablePolynomial<C>) r.subtract(h); 089 } else { 090 break; 091 } 092 } 093 return r; 094 } 095 096 097 /** 098 * GenSolvablePolynomial sparse right pseudo remainder for univariate 099 * polynomials. 100 * @param <C> coefficient type. 101 * @param P GenSolvablePolynomial. 102 * @param S nonzero GenSolvablePolynomial. 103 * @return remainder with P ore(ldcf(S)<sup>m'</sup>) = S * quotient + 104 * remainder. m' ≤ deg(P)-deg(S) 105 * @see edu.jas.poly.GenPolynomial#remainder(edu.jas.poly.GenPolynomial). 106 */ 107 public static <C extends GcdRingElem<C>> GenSolvablePolynomial<C> rightBaseSparsePseudoRemainder( 108 GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) { 109 if (S == null || S.isZERO()) { 110 throw new ArithmeticException(P.toString() + " division by zero " + S); 111 } 112 if (P.isZERO()) { 113 return P; 114 } 115 if (S.isConstant()) { 116 return P.ring.getZERO(); 117 } 118 if (P instanceof RecSolvablePolynomial) { 119 RecSolvablePolynomial<C> Pr = (RecSolvablePolynomial) P; 120 if (!Pr.ring.coeffTable.isEmpty()) { 121 throw new UnsupportedOperationException( 122 "RecSolvablePolynomial with twisted coeffs not supported"); 123 } 124 } 125 GreatestCommonDivisorAbstract<C> fd = new GreatestCommonDivisorSimple<C>(P.ring.coFac); 126 ExpVector e = S.leadingExpVector(); 127 GenSolvablePolynomial<C> h; 128 GenSolvablePolynomial<C> r = P; 129 while (!r.isZERO()) { 130 ExpVector f = r.leadingExpVector(); 131 if (f.multipleOf(e)) { 132 f = f.subtract(e); 133 h = S.multiply(f); // coeff a 134 C a = r.leadingBaseCoefficient(); 135 C c = h.leadingBaseCoefficient(); 136 // need ga, gc: ga a = gc c 137 C[] oc = fd.rightOreCond(a, c); 138 C ga = oc[0]; 139 C gc = oc[1]; 140 r = r.multiply(ga); // coeff a c, exp f 141 h = h.multiply(gc); // coeff a c, exp f 142 r = (GenSolvablePolynomial<C>) r.subtract(h); 143 } else { 144 break; 145 } 146 } 147 return r; 148 } 149 150 151 /** 152 * GenSolvablePolynomial sparse pseudo quotient for univariate polynomials 153 * or exact division. 154 * @param <C> coefficient type. 155 * @param P GenSolvablePolynomial. 156 * @param S nonzero GenSolvablePolynomial. 157 * @return quotient with ldcf(S)<sup>m'</sup> P = quotient * S + remainder. 158 * m' ≤ deg(P)-deg(S) 159 * @see edu.jas.poly.GenPolynomial#divide(edu.jas.poly.GenPolynomial). 160 */ 161 public static <C extends GcdRingElem<C>> GenSolvablePolynomial<C> leftBasePseudoQuotient( 162 GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) { 163 return leftBasePseudoQuotientRemainder(P, S)[0]; 164 } 165 166 167 /** 168 * GenSolvablePolynomial sparse pseudo quotient and remainder for univariate 169 * polynomials or exact division. 170 * @param <C> coefficient type. 171 * @param P GenSolvablePolynomial. 172 * @param S nonzero GenSolvablePolynomial. 173 * @return [ quotient, remainder ] with ldcf(S)<sup>m'</sup> P = quotient * 174 * S + remainder. m' ≤ deg(P)-deg(S) 175 * @see edu.jas.poly.GenPolynomial#divide(edu.jas.poly.GenPolynomial). 176 */ 177 @SuppressWarnings("unchecked") 178 public static <C extends GcdRingElem<C>> GenSolvablePolynomial<C>[] leftBasePseudoQuotientRemainder( 179 GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) { 180 if (S == null || S.isZERO()) { 181 throw new ArithmeticException(P.toString() + " division by zero " + S); 182 } 183 //if (S.ring.nvar != 1) { // ok if exact division 184 // throw new RuntimeException("univariate polynomials only"); 185 //} 186 GenSolvablePolynomial<C>[] ret = new GenSolvablePolynomial[2]; 187 ret[0] = null; 188 ret[1] = null; 189 if (P.isZERO() || S.isONE()) { 190 ret[0] = P; 191 ret[1] = S.ring.getZERO(); 192 return ret; 193 } 194 if (P instanceof RecSolvablePolynomial) { 195 RecSolvablePolynomial<C> Pr = (RecSolvablePolynomial) P; 196 if (!Pr.ring.coeffTable.isEmpty()) { 197 throw new UnsupportedOperationException( 198 "RecSolvablePolynomial with twisted coeffs not supported"); 199 } 200 } 201 GreatestCommonDivisorAbstract<C> fd = new GreatestCommonDivisorSimple<C>(P.ring.coFac); 202 ExpVector e = S.leadingExpVector(); 203 GenSolvablePolynomial<C> h; 204 GenSolvablePolynomial<C> r = P; 205 GenSolvablePolynomial<C> q = S.ring.getZERO().copy(); 206 while (!r.isZERO()) { 207 ExpVector f = r.leadingExpVector(); 208 if (f.multipleOf(e)) { 209 C a = r.leadingBaseCoefficient(); 210 f = f.subtract(e); 211 h = S.multiplyLeft(f); // coeff a 212 C c = h.leadingBaseCoefficient(); 213 // need ga, gc: ga a = gc c 214 C[] oc = fd.leftOreCond(a, c); 215 C ga = oc[0]; 216 C gc = oc[1]; 217 r = r.multiplyLeft(ga); // coeff ga a, exp f 218 h = h.multiplyLeft(gc); // coeff gc c, exp f 219 q = q.multiplyLeft(ga); // c 220 q = (GenSolvablePolynomial<C>) q.sum(gc, f); // a 221 r = (GenSolvablePolynomial<C>) r.subtract(h); 222 } else { 223 break; 224 } 225 } 226 ret[0] = q; 227 ret[1] = r; 228 return ret; 229 } 230 231 232 /** 233 * GenSolvablePolynomial sparse pseudo remainder for recursive solvable 234 * polynomials. 235 * @param <C> coefficient type. 236 * @param P recursive GenSolvablePolynomial. 237 * @param S nonzero recursive GenSolvablePolynomial. 238 * @return remainder with ore(ldcf(S)<sup>m'</sup>) P = quotient * S + 239 * remainder. 240 * @see edu.jas.poly.PolyUtil#recursiveSparsePseudoRemainder(edu.jas.poly.GenPolynomial,edu.jas.poly.GenPolynomial) 241 * . 242 */ 243 public static <C extends GcdRingElem<C>> GenSolvablePolynomial<GenPolynomial<C>> recursiveSparsePseudoRemainder( 244 GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<GenPolynomial<C>> S) { 245 if (S == null || S.isZERO()) { 246 throw new ArithmeticException(P + " division by zero " + S); 247 } 248 if (P == null || P.isZERO()) { 249 return P; 250 } 251 //if (S.isConstant()) { 252 // return P.ring.getZERO(); 253 //} 254 GenPolynomialRing<C> cofac = (GenPolynomialRing) P.ring.coFac; 255 GreatestCommonDivisorAbstract<C> fd = new GreatestCommonDivisorSimple<C>(cofac.coFac); 256 257 ExpVector e = S.leadingExpVector(); 258 GenSolvablePolynomial<GenPolynomial<C>> h; 259 GenSolvablePolynomial<GenPolynomial<C>> r = P; 260 while (!r.isZERO()) { 261 ExpVector f = r.leadingExpVector(); 262 if (f.multipleOf(e)) { 263 GenSolvablePolynomial<C> a = (GenSolvablePolynomial<C>) r.leadingBaseCoefficient(); 264 f = f.subtract(e); 265 h = S.multiplyLeft(f); // coeff c, exp (f-e) e 266 //wrong: h = S.multiply(f); // coeff c, exp e (f-e) 267 GenSolvablePolynomial<C> d = (GenSolvablePolynomial<C>) h.leadingBaseCoefficient(); 268 GenSolvablePolynomial<C>[] oc = fd.leftOreCond(a, d); 269 GenPolynomial<C> ga = oc[0]; 270 GenPolynomial<C> gd = oc[1]; 271 // ga a = gd d 272 r = r.multiplyLeft(ga); // coeff ga a, exp f 273 h = h.multiplyLeft(gd); // coeff gd d, exp f 274 //if (!r.leadingBaseCoefficient().equals(h.leadingBaseCoefficient())) { 275 //System.out.println("OreCond: a = " + a + ", d = " + d); 276 //System.out.println("OreCond: ga = " + ga + ", gd = " + gd); 277 // throw new RuntimeException("should not happen: lc(r) = " + r.leadingBaseCoefficient() 278 // + ", lc(h) = " + h.leadingBaseCoefficient()); 279 //} 280 r = (GenSolvablePolynomial<GenPolynomial<C>>) r.subtract(h); 281 //System.out.println("recRem: lm(r) = " + r.leadingMonomial()); 282 } else { 283 break; 284 } 285 } 286 return r; 287 } 288 289 290 /** 291 * Is recursive GenSolvablePolynomial pseudo quotient and remainder. For 292 * recursive polynomials. 293 * @param <C> coefficient type. 294 * @param P recursive GenSolvablePolynomial. 295 * @param S nonzero recursive GenSolvablePolynomial. 296 * @return true, if P ~= q * S + r, else false. 297 * @see edu.jas.poly.GenPolynomial#remainder(edu.jas.poly.GenPolynomial). 298 * <b>Note:</b> not always meaningful and working 299 */ 300 public static <C extends GcdRingElem<C>> boolean isRecursivePseudoQuotientRemainder( 301 GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<GenPolynomial<C>> S, 302 GenSolvablePolynomial<GenPolynomial<C>> q, GenSolvablePolynomial<GenPolynomial<C>> r) { 303 GenSolvablePolynomial<GenPolynomial<C>> rhs = (GenSolvablePolynomial<GenPolynomial<C>>) q.multiply(S) 304 .sum(r); 305 GenSolvablePolynomial<GenPolynomial<C>> lhs = P; 306 GenPolynomial<C> ldcf = S.leadingBaseCoefficient(); 307 long d = P.degree(0) - S.degree(0) + 1; 308 d = (d > 0 ? d : -d + 2); 309 for (long i = 0; i <= d; i++) { 310 //System.out.println("lhs = " + lhs); 311 //System.out.println("rhs = " + rhs); 312 //System.out.println("lhs-rhs = " + lhs.subtract(rhs)); 313 if (lhs.equals(rhs)) { 314 return true; 315 } 316 lhs = lhs.multiply(ldcf); 317 } 318 GenSolvablePolynomial<GenPolynomial<C>> Pp = P; 319 rhs = q.multiply(S); 320 //System.out.println("rhs,2 = " + rhs); 321 for (long i = 0; i <= d; i++) { 322 lhs = (GenSolvablePolynomial<GenPolynomial<C>>) Pp.subtract(r); 323 //System.out.println("lhs-rhs = " + lhs.subtract(rhs)); 324 if (lhs.equals(rhs)) { 325 //System.out.println("lhs,2 = " + lhs); 326 return true; 327 } 328 Pp = Pp.multiply(ldcf); 329 } 330 GenPolynomialRing<C> cofac = (GenPolynomialRing) P.ring.coFac; 331 GreatestCommonDivisorAbstract<C> fd = new GreatestCommonDivisorSimple<C>(cofac.coFac); 332 GenSolvablePolynomial<C> a = (GenSolvablePolynomial<C>) P.leadingBaseCoefficient(); 333 rhs = (GenSolvablePolynomial<GenPolynomial<C>>) q.multiply(S).sum(r); 334 GenSolvablePolynomial<C> b = (GenSolvablePolynomial<C>) rhs.leadingBaseCoefficient(); 335 GenSolvablePolynomial<C>[] oc = fd.leftOreCond(a, b); 336 GenPolynomial<C> ga = oc[0]; 337 GenPolynomial<C> gb = oc[1]; 338 //System.out.println("FDQR: OreCond: a = " + a + ", b = " + b); 339 //System.out.println("FDQR: OreCond: ga = " + ga + ", gb = " + gb); 340 // ga a = gd d 341 GenSolvablePolynomial<GenPolynomial<C>> Pa = P.multiplyLeft(ga); // coeff ga a 342 GenSolvablePolynomial<GenPolynomial<C>> Rb = rhs.multiplyLeft(gb); // coeff gb b 343 GenSolvablePolynomial<GenPolynomial<C>> D = (GenSolvablePolynomial<GenPolynomial<C>>) Pa.subtract(Rb); 344 if (D.isZERO()) { 345 return true; 346 } 347 if (debug) { 348 logger.info("not QR: D = " + D); 349 } 350 //System.out.println("FDQR: Pa = " + Pa); 351 //System.out.println("FDQR: Rb = " + Rb); 352 //System.out.println("FDQR: Pa-Rb = " + D); 353 return false; 354 } 355 356 357 /** 358 * GenSolvablePolynomial recursive pseudo quotient for recursive 359 * polynomials. 360 * @param <C> coefficient type. 361 * @param P recursive GenSolvablePolynomial. 362 * @param S nonzero recursive GenSolvablePolynomial. 363 * @return quotient with ore(ldcf(S)<sup>m'</sup>) P = quotient * S + 364 * remainder. 365 * @see edu.jas.poly.GenPolynomial#remainder(edu.jas.poly.GenPolynomial). 366 */ 367 public static <C extends GcdRingElem<C>> GenSolvablePolynomial<GenPolynomial<C>> recursivePseudoQuotient( 368 GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<GenPolynomial<C>> S) { 369 return recursivePseudoQuotientRemainder(P, S)[0]; 370 } 371 372 373 /** 374 * GenSolvablePolynomial recursive pseudo quotient and remainder for 375 * recursive polynomials. 376 * @param <C> coefficient type. 377 * @param P recursive GenSolvablePolynomial. 378 * @param S nonzero recursive GenSolvablePolynomial. 379 * @return [ quotient, remainder ] with ore(ldcf(S)<sup>m'</sup>) P = 380 * quotient * S + remainder. 381 * @see edu.jas.poly.GenPolynomial#remainder(edu.jas.poly.GenPolynomial). 382 */ 383 public static <C extends GcdRingElem<C>> GenSolvablePolynomial<GenPolynomial<C>>[] recursivePseudoQuotientRemainder( 384 GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<GenPolynomial<C>> S) { 385 if (S == null || S.isZERO()) { 386 throw new ArithmeticException(P + " division by zero " + S); 387 } 388 //if (S.ring.nvar != 1) { // ok if exact division 389 // throw new RuntimeException("univariate polynomials only"); 390 //} 391 GenSolvablePolynomial<GenPolynomial<C>>[] ret = new GenSolvablePolynomial[2]; 392 if (P == null || P.isZERO()) { 393 ret[0] = S.ring.getZERO(); 394 ret[1] = S.ring.getZERO(); 395 return ret; 396 } 397 if (S.isONE()) { 398 ret[0] = P; 399 ret[1] = S.ring.getZERO(); 400 return ret; 401 } 402 GenPolynomialRing<C> cofac = (GenPolynomialRing) P.ring.coFac; 403 GreatestCommonDivisorAbstract<C> fd = new GreatestCommonDivisorSimple<C>(cofac.coFac); 404 405 ExpVector e = S.leadingExpVector(); 406 GenSolvablePolynomial<GenPolynomial<C>> h; 407 GenSolvablePolynomial<GenPolynomial<C>> r = P; 408 GenSolvablePolynomial<GenPolynomial<C>> q = S.ring.getZERO().copy(); 409 while (!r.isZERO()) { 410 ExpVector f = r.leadingExpVector(); 411 if (f.multipleOf(e)) { 412 f = f.subtract(e); 413 h = S.multiplyLeft(f); // coeff c, exp (f/e) e 414 GenSolvablePolynomial<C> a = (GenSolvablePolynomial<C>) r.leadingBaseCoefficient(); 415 GenSolvablePolynomial<C> d = (GenSolvablePolynomial<C>) h.leadingBaseCoefficient(); 416 GenSolvablePolynomial<C>[] oc = fd.leftOreCond(a, d); 417 GenPolynomial<C> ga = oc[0]; // d 418 GenPolynomial<C> gd = oc[1]; // a 419 // ga a = gd d 420 r = r.multiplyLeft(ga); // coeff ga a, exp f 421 h = h.multiplyLeft(gd); // coeff gd d, exp f 422 q = q.multiplyLeft(ga); // d 423 q = (GenSolvablePolynomial<GenPolynomial<C>>) q.sum(gd, f); // a 424 r = (GenSolvablePolynomial<GenPolynomial<C>>) r.subtract(h); 425 } else { 426 break; 427 } 428 } 429 ret[0] = q; 430 ret[1] = r; 431 return ret; 432 } 433 434 435 /** 436 * Is recursive GenSolvablePolynomial right pseudo quotient and remainder. 437 * For recursive polynomials. 438 * @param <C> coefficient type. 439 * @param P recursive GenSolvablePolynomial. 440 * @param S nonzero recursive GenSolvablePolynomial. 441 * @return true, if P ~= S * q + r, else false. 442 * @see edu.jas.poly.GenPolynomial#remainder(edu.jas.poly.GenPolynomial). 443 * <b>Note:</b> not always meaningful and working 444 */ 445 public static <C extends GcdRingElem<C>> boolean isRecursiveRightPseudoQuotientRemainder( 446 GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<GenPolynomial<C>> S, 447 GenSolvablePolynomial<GenPolynomial<C>> q, GenSolvablePolynomial<GenPolynomial<C>> r) { 448 GenSolvablePolynomial<GenPolynomial<C>> rhs = (GenSolvablePolynomial<GenPolynomial<C>>) S.multiply(q) 449 .sum(r); 450 GenSolvablePolynomial<GenPolynomial<C>> lhs = P; 451 GenPolynomial<C> ldcf = S.leadingBaseCoefficient(); 452 long d = P.degree(0) - S.degree(0) + 1; 453 d = (d > 0 ? d : -d + 2); 454 for (long i = 0; i <= d; i++) { 455 //System.out.println("lhs = " + lhs); 456 //System.out.println("rhs = " + rhs); 457 //System.out.println("lhs-rhs = " + lhs.subtract(rhs)); 458 if (lhs.equals(rhs)) { 459 return true; 460 } 461 lhs = lhs.multiply(ldcf); // side? 462 } 463 GenSolvablePolynomial<GenPolynomial<C>> Pp = P; 464 rhs = S.multiply(q); 465 //System.out.println("rhs,2 = " + rhs); 466 for (long i = 0; i <= d; i++) { 467 lhs = (GenSolvablePolynomial<GenPolynomial<C>>) Pp.subtract(r); 468 //System.out.println("lhs-rhs = " + lhs.subtract(rhs)); 469 if (lhs.equals(rhs)) { 470 //System.out.println("lhs,2 = " + lhs); 471 return true; 472 } 473 Pp = Pp.multiply(ldcf); // side? 474 } 475 GenPolynomialRing<C> cofac = (GenPolynomialRing) P.ring.coFac; 476 GreatestCommonDivisorAbstract<C> fd = new GreatestCommonDivisorSimple<C>(cofac.coFac); 477 478 GenSolvablePolynomial<GenPolynomial<C>> pr = P.rightRecursivePolynomial(); 479 GenSolvablePolynomial<C> a = (GenSolvablePolynomial<C>) pr.leadingBaseCoefficient(); 480 481 rhs = (GenSolvablePolynomial<GenPolynomial<C>>) S.multiply(q).sum(r); 482 GenSolvablePolynomial<GenPolynomial<C>> rr = rhs.rightRecursivePolynomial(); 483 GenSolvablePolynomial<C> b = (GenSolvablePolynomial<C>) rr.leadingBaseCoefficient(); 484 485 GenSolvablePolynomial<C>[] oc = fd.rightOreCond(a, b); 486 GenPolynomial<C> ga = oc[0]; 487 GenPolynomial<C> gb = oc[1]; 488 //System.out.println("FDQR: OreCond: a = " + a + ", b = " + b); 489 //System.out.println("FDQR: OreCond: ga = " + ga + ", gb = " + gb); 490 // a ga = d gd 491 GenSolvablePolynomial<GenPolynomial<C>> Pa = FDUtil.<C> multiplyRightRecursivePolynomial(pr, ga); // coeff a ga 492 GenSolvablePolynomial<GenPolynomial<C>> Rb = FDUtil.<C> multiplyRightRecursivePolynomial(rr, gb); // coeff b gb 493 //System.out.println("right(P) = " + pr + ", P = " + P); 494 //System.out.println("right(rhs)= " + rr + ", rhs = " + rhs); 495 //System.out.println("Pa = " + Pa + ", ga = " + ga); 496 //System.out.println("Rb = " + Rb + ", gb = " + gb); 497 GenSolvablePolynomial<GenPolynomial<C>> D = (GenSolvablePolynomial<GenPolynomial<C>>) Pa.subtract(Rb); 498 if (D.isZERO()) { 499 return true; 500 } 501 if (true) { 502 System.out.println("Pa = " + Pa); 503 System.out.println("Rb = " + Rb); 504 logger.info("not right QR: Pa-Rb = " + D); 505 } 506 return false; 507 } 508 509 510 /** 511 * GenSolvablePolynomial recursive right pseudo quotient for recursive 512 * polynomials. 513 * @param <C> coefficient type. 514 * @param P recursive GenSolvablePolynomial. 515 * @param S nonzero recursive GenSolvablePolynomial. 516 * @return quotient with P ore(ldcf(S)<sup>m'</sup>) = S * quotient + 517 * remainder. 518 * @see edu.jas.poly.GenPolynomial#remainder(edu.jas.poly.GenPolynomial). 519 */ 520 public static <C extends GcdRingElem<C>> GenSolvablePolynomial<GenPolynomial<C>> recursiveRightPseudoQuotient( 521 GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<GenPolynomial<C>> S) { 522 return recursiveRightPseudoQuotientRemainder(P, S)[0]; 523 } 524 525 526 /** 527 * GenSolvablePolynomial right sparse pseudo remainder for recursive 528 * solvable polynomials. <b>Note:</b> uses right multiplication of P by 529 * ldcf(S), not always applicable. 530 * @param <C> coefficient type. 531 * @param P recursive GenSolvablePolynomial. 532 * @param S nonzero recursive GenSolvablePolynomial. 533 * @return remainder with P ldcf(S)<sup>m'</sup> = quotient * S + remainder. 534 * @see edu.jas.poly.PolyUtil#recursiveSparsePseudoRemainder(edu.jas.poly.GenPolynomial,edu.jas.poly.GenPolynomial) 535 * . 536 */ 537 public static <C extends GcdRingElem<C>> GenSolvablePolynomial<GenPolynomial<C>> recursiveRightSparsePseudoRemainder( 538 GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<GenPolynomial<C>> S) { 539 return recursiveRightPseudoQuotientRemainder(P, S)[1]; 540 } 541 542 543 /** 544 * GenSolvablePolynomial right sparse pseudo remainder for recursive 545 * solvable polynomials. <b>Note:</b> uses right multiplication of P by 546 * ldcf(S), not always applicable. 547 * @param <C> coefficient type. 548 * @param P recursive GenSolvablePolynomial. 549 * @param S nonzero recursive GenSolvablePolynomial. 550 * @return remainder with P ore(ldcf(S)<sup>m'</sup>) = quotient * S + 551 * remainder. 552 * @see edu.jas.poly.PolyUtil#recursiveSparsePseudoRemainder(edu.jas.poly.GenPolynomial,edu.jas.poly.GenPolynomial) 553 * . 554 */ 555 public static <C extends RingElem<C>> GenSolvablePolynomial<GenPolynomial<C>> recursiveRightSparsePseudoRemainderOld( 556 GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<GenPolynomial<C>> S) { 557 if (S == null || S.isZERO()) { 558 throw new ArithmeticException(P + " division by zero " + S); 559 } 560 if (P == null || P.isZERO()) { 561 return P; 562 } 563 if (S.isConstant()) { 564 return P.ring.getZERO(); 565 } 566 //GenPolynomial<C> c = S.leadingBaseCoefficient(); 567 ExpVector e = S.leadingExpVector(); 568 GenSolvablePolynomial<GenPolynomial<C>> h; 569 GenSolvablePolynomial<GenPolynomial<C>> r = P; 570 while (!r.isZERO()) { 571 ExpVector f = r.leadingExpVector(); 572 if (f.multipleOf(e)) { 573 f = f.subtract(e); 574 575 h = S.multiply(f); // coeff c, exp (f-e) e 576 GenPolynomial<C> d = h.leadingBaseCoefficient(); 577 GenPolynomial<C> a = r.leadingBaseCoefficient(); 578 579 r = r.multiply(d); // coeff a d, exp f 580 h = h.multiply(a); // coeff a d, exp f 581 582 //if (!r.leadingBaseCoefficient().equals(h.leadingBaseCoefficient())) { 583 // throw new RuntimeException("should not happen: lc(r) = " + r.leadingBaseCoefficient() 584 // + ", lc(h) = " + h.leadingBaseCoefficient()); 585 //} 586 r = (GenSolvablePolynomial<GenPolynomial<C>>) r.subtract(h); 587 } else { 588 break; 589 } 590 } 591 return r; 592 } 593 594 595 /** 596 * GenSolvablePolynomial right sparse pseudo quotient and remainder for 597 * recursive solvable polynomials. <b>Note:</b> uses right multiplication of 598 * P by ldcf(S), not always applicable. 599 * @param <C> coefficient type. 600 * @param P recursive GenSolvablePolynomial. 601 * @param S nonzero recursive GenSolvablePolynomial. 602 * @return remainder with P ore(ldcf(S)<sup>m'</sup>) = S * quotient + 603 * remainder. 604 * @see edu.jas.poly.PolyUtil#recursiveSparsePseudoRemainder(edu.jas.poly.GenPolynomial,edu.jas.poly.GenPolynomial) 605 * . 606 */ 607 public static <C extends GcdRingElem<C>> GenSolvablePolynomial<GenPolynomial<C>>[] recursiveRightPseudoQuotientRemainder( 608 GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<GenPolynomial<C>> S) { 609 if (S == null || S.isZERO()) { 610 throw new ArithmeticException(P + " division by zero " + S); 611 } 612 GenSolvablePolynomial<GenPolynomial<C>>[] ret = new GenSolvablePolynomial[2]; 613 if (P == null || P.isZERO()) { 614 ret[0] = S.ring.getZERO(); 615 ret[1] = S.ring.getZERO(); 616 return ret; 617 } 618 if (S.isONE()) { 619 ret[0] = P; 620 ret[1] = S.ring.getZERO(); 621 return ret; 622 } 623 //if (S.isConstant()) { 624 // ret[0] = P.ring.getZERO(); 625 // ret[1] = S.ring.getZERO(); 626 // return ret; 627 //} 628 GenPolynomialRing<C> cofac = (GenPolynomialRing) P.ring.coFac; 629 GreatestCommonDivisorAbstract<C> fd = new GreatestCommonDivisorSimple<C>(cofac.coFac); 630 631 ExpVector e = S.leadingExpVector(); 632 GenSolvablePolynomial<GenPolynomial<C>> h, q, hr, rr; 633 GenSolvablePolynomial<GenPolynomial<C>> r = P; 634 GenSolvablePolynomial<GenPolynomial<C>> qr = S.ring.getZERO().copy(); 635 while (!r.isZERO()) { 636 ExpVector f = r.leadingExpVector(); 637 if (f.multipleOf(e)) { 638 f = f.subtract(e); 639 h = S.multiply(f); // coeff c, exp e (f/e) 640 hr = h.rightRecursivePolynomial(); 641 rr = r.rightRecursivePolynomial(); 642 GenSolvablePolynomial<C> a = (GenSolvablePolynomial<C>) rr.leadingBaseCoefficient(); 643 GenSolvablePolynomial<C> d = (GenSolvablePolynomial<C>) hr.leadingBaseCoefficient(); 644 GenSolvablePolynomial<C>[] oc = fd.rightOreCond(a, d); 645 GenPolynomial<C> ga = oc[0]; // d 646 GenPolynomial<C> gd = oc[1]; // a 647 //System.out.println("OreCond: a = " + a + ", d = " + d); 648 //System.out.println("OreCond: ga = " + ga + ", gd = " + gd); 649 // a ga = d gd 650 rr = FDUtil.<C> multiplyRightRecursivePolynomial(rr, ga); // exp f, coeff a ga, 651 hr = FDUtil.<C> multiplyRightRecursivePolynomial(hr, gd); // exp f, coeff d gd 652 h = hr.evalAsRightRecursivePolynomial(); 653 r = rr.evalAsRightRecursivePolynomial(); 654 //if (!r.leadingBaseCoefficient().equals(h.leadingBaseCoefficient())) { 655 // throw new RuntimeException("can not happen: lc(r) = " + r.leadingBaseCoefficient() 656 // + ", lc(h) = " + h.leadingBaseCoefficient()); 657 //} 658 r = (GenSolvablePolynomial<GenPolynomial<C>>) r.subtract(h); 659 qr = FDUtil.<C> multiplyRightRecursivePolynomial(qr, ga); // d 660 qr = (GenSolvablePolynomial<GenPolynomial<C>>) qr.sum(gd, f); // a // same for right coefficients 661 //System.out.println("r = " + r + ", qr = " + qr); 662 } else { 663 break; 664 } 665 } 666 q = qr.evalAsRightRecursivePolynomial(); 667 ret[0] = q; 668 ret[1] = r; 669 return ret; 670 } 671 672 673 /** 674 * GenSolvablePolynomial recursive quotient for recursive polynomials and 675 * exact division by coefficient ring element. 676 * @param <C> coefficient type. 677 * @param P recursive GenSolvablePolynomial. 678 * @param s GenSolvablePolynomial. 679 * @return this/s. 680 */ 681 public static <C extends GcdRingElem<C>> GenSolvablePolynomial<GenPolynomial<C>> recursiveDivideRightEval( 682 GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<C> s) { 683 if (s.isONE()) { 684 return P; 685 } 686 GenSolvablePolynomial<GenPolynomial<C>> Pr = P.rightRecursivePolynomial(); 687 GenSolvablePolynomial<GenPolynomial<C>> Qr = FDUtil.<C> recursiveDivide(Pr, s); 688 GenSolvablePolynomial<GenPolynomial<C>> Q = Qr.evalAsRightRecursivePolynomial(); 689 if (debug) { 690 if (!Q.multiply(s).equals(P)) { 691 System.out.println("rDivREval: P = " + P + ", right(P) = " + Pr); 692 System.out.println("rDivREval: Q = " + Q + ", right(Q) = " + Qr); 693 System.out.println("rDivREval: Q*s = " + Q.multiply(s) + ", s = " + s); 694 //System.out.println("rDivREval: P.ring == Q.ring: " + P.ring.equals(Q.ring) ); 695 throw new RuntimeException("rDivREval: Q*s != P"); 696 } 697 } 698 return Q; 699 } 700 701 702 /** 703 * GenSolvablePolynomial recursive quotient for recursive polynomials and 704 * exact division by coefficient ring element. 705 * @param <C> coefficient type. 706 * @param P recursive GenSolvablePolynomial. 707 * @param s GenSolvablePolynomial. 708 * @return this/s. 709 */ 710 public static <C extends GcdRingElem<C>> GenSolvablePolynomial<GenPolynomial<C>> recursiveDivide( 711 GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<C> s) { 712 if (s == null || s.isZERO()) { 713 throw new ArithmeticException("division by zero " + P + ", " + s); 714 } 715 if (P.isZERO()) { 716 return P; 717 } 718 if (s.isONE()) { 719 return P; 720 } 721 GenSolvablePolynomial<GenPolynomial<C>> p = P.ring.getZERO().copy(); 722 for (Map.Entry<ExpVector, GenPolynomial<C>> m1 : P.getMap().entrySet()) { 723 GenSolvablePolynomial<C> c1 = (GenSolvablePolynomial<C>) m1.getValue(); 724 ExpVector e1 = m1.getKey(); 725 //GenSolvablePolynomial<C> c = FDUtil.<C> basePseudoQuotient(c1, s); 726 GenSolvablePolynomial<C>[] QR = FDUtil.<C> leftBasePseudoQuotientRemainder(c1, s); 727 GenSolvablePolynomial<C> c = QR[0]; 728 if (debug) { 729 if (!QR[1].isZERO()) { 730 System.out.println("rDiv, P = " + P); 731 System.out.println("rDiv, c1 = " + c1); 732 System.out.println("rDiv, s = " + s); 733 System.out.println("rDiv, c = " + c + ", r = " + QR[1]); 734 System.out.println("rDiv, c*s = " + c.multiply(s)); 735 System.out.println("rDiv, s*c = " + s.multiply(c)); 736 throw new RuntimeException("something is wrong: rem = " + QR[1]); 737 } 738 } 739 if (!c.isZERO()) { 740 //pv.put(e1, c); 741 p.doPutToMap(e1, c); 742 } else { 743 System.out.println("rDiv, P = " + P); 744 System.out.println("rDiv, c1 = " + c1); 745 System.out.println("rDiv, s = " + s); 746 System.out.println("rDiv, c = " + c); 747 throw new RuntimeException("something is wrong: c is zero"); 748 } 749 } 750 return p; 751 } 752 753 754 /** 755 * GenSolvablePolynomial recursive right quotient for recursive polynomials 756 * and partial right exact division by coefficient ring element. 757 * @param <C> coefficient type. 758 * @param P recursive GenSolvablePolynomial. 759 * @param s GenSolvablePolynomial. 760 * @return this/s. 761 */ 762 public static <C extends GcdRingElem<C>> GenSolvablePolynomial<GenPolynomial<C>> recursiveDivideRightPolynomial( 763 GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<C> s) { 764 if (s == null || s.isZERO()) { 765 throw new ArithmeticException("division by zero " + P + ", " + s); 766 } 767 if (P.isZERO()) { 768 return P; 769 } 770 if (s.isONE()) { 771 return P; 772 } 773 GenSolvablePolynomial<GenPolynomial<C>> p = P.ring.getZERO().copy(); 774 GenSolvablePolynomial<GenPolynomial<C>> Pr = P.rightRecursivePolynomial(); 775 logger.info("P = " + P + ", right(P) = " + Pr + ", left(s) = " + s); 776 for (Map.Entry<ExpVector, GenPolynomial<C>> m1 : Pr.getMap().entrySet()) { 777 GenSolvablePolynomial<C> c1 = (GenSolvablePolynomial<C>) m1.getValue(); 778 ExpVector e1 = m1.getKey(); 779 //GenSolvablePolynomial<C> c = FDUtil.<C> basePseudoQuotient(c1, s); 780 GenSolvablePolynomial<C> c = FDUtil.<C> divideRightPolynomial(c1, s); 781 //GenSolvablePolynomial<C>[] QR = FDUtil.<C> basePseudoQuotientRemainder(c1, s); 782 if (!c.isZERO()) { 783 //pv.put(e1, c); 784 p.doPutToMap(e1, c); 785 } 786 } 787 GenSolvablePolynomial<GenPolynomial<C>> pl = p.evalAsRightRecursivePolynomial(); 788 logger.info("pl = " + pl + ", p = " + p); 789 return pl; 790 } 791 792 793 /** 794 * GenSolvablePolynomial right quotient for polynomials and partial right 795 * exact division by coefficient ring element. 796 * @param <C> coefficient type. 797 * @param P GenSolvablePolynomial. 798 * @param s GenSolvablePolynomial, constant wrt. the main variable. 799 * @return this/s. 800 */ 801 public static <C extends GcdRingElem<C>> GenSolvablePolynomial<C> divideRightPolynomial( 802 GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> s) { 803 if (s == null || s.isZERO()) { 804 throw new ArithmeticException("division by zero " + P + ", " + s); 805 } 806 if (P.isZERO()) { 807 return P; 808 } 809 if (s.isONE()) { 810 return P; 811 } 812 GenSolvablePolynomialRing<C> pfac = P.ring; 813 GenSolvablePolynomial<C> q; 814 if (pfac.nvar <= 1) { 815 GenSolvablePolynomial<C>[] QR1; 816 QR1 = FDUtil.<C> leftBasePseudoQuotientRemainder(P, s); 817 q = QR1[0]; 818 if (debug) { 819 if (!QR1[1].isZERO()) { 820 System.out.println("rDivPol, P = " + P); 821 System.out.println("rDivPol, s = " + s); 822 throw new RuntimeException("non zero remainder, q = " + q + ", r = " + QR1[1]); 823 } 824 } 825 return q; 826 } 827 GenSolvablePolynomialRing<GenPolynomial<C>> rfac = pfac.recursive(1); 828 GenSolvablePolynomial<GenPolynomial<C>> pr, sr, qr, rr; 829 GenSolvablePolynomial<GenPolynomial<C>>[] QR; 830 pr = (GenSolvablePolynomial<GenPolynomial<C>>) PolyUtil.<C> recursive(rfac, P); 831 sr = (GenSolvablePolynomial<GenPolynomial<C>>) PolyUtil.<C> recursive(rfac, s); 832 //qr = FDUtil.<C> recursiveDivideRightPolynomial(pr,sc); 833 QR = FDUtil.<C> recursiveRightPseudoQuotientRemainder(pr, sr); 834 //QR = FDUtil.<C> recursivePseudoQuotientRemainder(pr,sr); 835 qr = QR[0]; 836 rr = QR[1]; 837 if (debug) { 838 if (!rr.isZERO()) { 839 System.out.println("rDivPol, pr = " + pr); 840 System.out.println("rDivPol, sr = " + sr); 841 throw new RuntimeException("non zero remainder, q = " + qr + ", r = " + rr); 842 } 843 } 844 q = (GenSolvablePolynomial<C>) PolyUtil.<C> distribute(pfac, qr); 845 return q; 846 } 847 848 849 /** 850 * GenSolvablePolynomial recursive quotient for recursive polynomials and 851 * partial right exact division by coefficient ring element. 852 * @param <C> coefficient type. 853 * @param P recursive GenSolvablePolynomial. 854 * @param s GenSolvablePolynomial. 855 * @return this/s. 856 */ 857 public static <C extends GcdRingElem<C>> GenSolvablePolynomial<GenPolynomial<C>> recursiveRightDivide( 858 GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<C> s) { 859 if (s == null || s.isZERO()) { 860 throw new ArithmeticException("division by zero " + P + ", " + s); 861 } 862 if (P.isZERO()) { 863 return P; 864 } 865 if (s.isONE()) { 866 return P; 867 } 868 if (!(P instanceof RecSolvablePolynomial)) { 869 //return FDUtil.<C> recursiveDivide(P,s); 870 } 871 RecSolvablePolynomialRing<C> rfac = (RecSolvablePolynomialRing<C>) P.ring; 872 if (rfac.coeffTable.isEmpty()) { 873 //return FDUtil.<C> recursiveDivide(P,s); 874 } 875 //GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) rfac.coFac; 876 //GenPolynomial<C> one = cfac.getONE(); 877 RecSolvablePolynomial<C> onep = rfac.getONE(); 878 ExpVector zero = rfac.evzero; 879 RecSolvablePolynomial<C> q = rfac.getZERO(); 880 RecSolvablePolynomial<C> r; 881 RecSolvablePolynomial<C> p = (RecSolvablePolynomial<C>) P; 882 //System.out.println("recRightDivide: p = " + p + ", s = " + s); 883 while (!p.isZERO()) { 884 ExpVector f = p.leadingExpVector(); 885 GenSolvablePolynomial<C> a = (GenSolvablePolynomial<C>) p.leadingBaseCoefficient(); 886 //GenSolvablePolynomial<C> c = FDUtil.<C> basePseudoQuotient(a, s); 887 GenSolvablePolynomial<C>[] QR = FDUtil.<C> leftBasePseudoQuotientRemainder(a, s); 888 //GenSolvablePolynomial<C> c = (GenSolvablePolynomial<C>) a.divide(s); 889 //System.out.println("content QR[1] = " + QR[1]); 890 if (debug) { 891 if (!QR[1].isZERO() || !a.remainder(s).isZERO()) { 892 logger.info("no exact division, rem = " + a.remainder(s) + ", r =" + QR[1]); 893 throw new RuntimeException("no exact division: r = " + QR[1]); 894 } 895 } 896 GenSolvablePolynomial<C> c = QR[0]; 897 // c * s = a 898 if (c.isZERO()) { 899 System.out.println("rDiv, P = " + P); 900 System.out.println("rDiv, a = " + a); 901 System.out.println("rDiv, s = " + s); 902 System.out.println("rDiv, c = " + c); 903 throw new RuntimeException("something is wrong: c is zero"); 904 } 905 //System.out.println("recRightDivide: a = " + a + ", c = " + c + ", f = " + f); 906 r = onep.multiply(c, f, s, zero); // right: (c f) * 1 * (s zero) 907 //System.out.println("recRightDivide: r = " + r); 908 p = (RecSolvablePolynomial<C>) p.subtract(r); 909 q = (RecSolvablePolynomial<C>) q.sum(c, f); 910 } 911 return q; 912 } 913 914 915 /* 916 * RecSolvablePolynomial right coefficients from left coefficients. 917 * <b>Note:</b> R is represented as a polynomial with left coefficients, the 918 * implementation can at the moment not distinguish between left and right 919 * coefficients. 920 * @param <C> coefficient type. 921 * @param P GenSolvablePolynomial. 922 * @return R = sum( X<sup>i</sup> b<sub>i</sub> ), with P = 923 * sum(a<sub>i</sub> X<sup>i</sup> ) and eval(sum(X<sup>i</sup> 924 * b<sub>i</sub>)) == sum(a<sub>i</sub> X<sup>i</sup>) 925 926 public static <C extends RingElem<C>> GenSolvablePolynomial<GenPolynomial<C>> rightRecursivePolynomial( 927 GenSolvablePolynomial<GenPolynomial<C>> P) { 928 if (P == null || P.isZERO()) { 929 return P; 930 } 931 if (!(P instanceof RecSolvablePolynomial)) { 932 return P; 933 } 934 RecSolvablePolynomialRing<C> rfac = (RecSolvablePolynomialRing<C>) P.ring; 935 if (rfac.coeffTable.isEmpty()) { 936 return P; 937 } 938 GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) rfac.coFac; 939 GenPolynomial<C> one = cfac.getONE(); 940 RecSolvablePolynomial<C> onep = rfac.getONE(); 941 ExpVector zero = rfac.evzero; 942 RecSolvablePolynomial<C> R = rfac.getZERO(); 943 RecSolvablePolynomial<C> r; 944 RecSolvablePolynomial<C> p = (RecSolvablePolynomial<C>) P; 945 while (!p.isZERO()) { 946 ExpVector f = p.leadingExpVector(); 947 GenPolynomial<C> a = p.leadingBaseCoefficient(); 948 //r = h.multiply(a); // wrong method dispatch // right: f*a 949 r = onep.multiply(one, f, a, zero); // right: (1 f) * 1 * (a zero) 950 //System.out.println("a,f = " + a + ", " + f); // + ", h.ring = " + h.ring.toScript()); 951 //System.out.println("f*a = " + r); // + ", r.ring = " + r.ring.toScript()); 952 p = (RecSolvablePolynomial<C>) p.subtract(r); 953 R = (RecSolvablePolynomial<C>) R.sum(a, f); 954 } 955 return R; 956 } 957 */ 958 959 /* 960 * Evaluate RecSolvablePolynomial as right coefficients polynomial. 961 * <b>Note:</b> R is represented as a polynomial with left coefficients, the 962 * implementation can at the moment not distinguish between left and right 963 * coefficients. 964 * @param <C> coefficient type. 965 * @param R GenSolvablePolynomial with right coefficients. 966 * @return P as evaluated polynomial R. R = sum( X<sup>i</sup> b<sub>i</sub> 967 * ), P = sum(a<sub>i</sub> X<sup>i</sup> ) = eval(sum(X<sup>i</sup> 968 * b<sub>i</sub>)) 969 970 public static <C extends RingElem<C>> GenSolvablePolynomial<GenPolynomial<C>> evalAsRightRecursivePolynomial( 971 GenSolvablePolynomial<GenPolynomial<C>> R) { 972 if (R == null || R.isZERO()) { 973 return R; 974 } 975 if (!(R instanceof RecSolvablePolynomial)) { 976 return R; 977 } 978 RecSolvablePolynomialRing<C> rfac = (RecSolvablePolynomialRing<C>) R.ring; 979 if (rfac.coeffTable.isEmpty()) { 980 return R; 981 } 982 GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) rfac.coFac; 983 GenPolynomial<C> one = cfac.getONE(); 984 RecSolvablePolynomial<C> onep = rfac.getONE(); 985 ExpVector zero = rfac.evzero; 986 RecSolvablePolynomial<C> q = rfac.getZERO(); 987 RecSolvablePolynomial<C> s; 988 RecSolvablePolynomial<C> r = (RecSolvablePolynomial<C>) R; 989 for (Map.Entry<ExpVector, GenPolynomial<C>> y : r.getMap().entrySet()) { 990 ExpVector f = y.getKey(); 991 GenPolynomial<C> a = y.getValue(); 992 // f.multiply(a); // wrong method dispatch // right: f*a 993 // onep.multiply(f).multiply(a) // should do now 994 s = onep.multiply(one, f, a, zero); // right: (1 f) * 1 * (a zero) 995 q = (RecSolvablePolynomial<C>) q.sum(s); 996 } 997 return q; 998 } 999 */ 1000 1001 /* 1002 * Test RecSolvablePolynomial right coefficients polynomial. <b>Note:</b> R 1003 * is represented as a polynomial with left coefficients, the implementation 1004 * can at the moment not distinguish between left and right coefficients. 1005 * @param <C> coefficient type. 1006 * @param P GenSolvablePolynomial with left coefficients. 1007 * @param R GenSolvablePolynomial with right coefficients. 1008 * @return true, if R is polynomial with right coefficients of P. R = sum( 1009 * X<sup>i</sup> b<sub>i</sub> ), with P = sum(a<sub>i</sub> 1010 * X<sup>i</sup> ) and eval(sum(X<sup>i</sup> b<sub>i</sub>)) == 1011 * sum(a<sub>i</sub> X<sup>i</sup>) 1012 1013 public static <C extends RingElem<C>> boolean isRightRecursivePolynomial( 1014 GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<GenPolynomial<C>> R) { 1015 if (P == null) { 1016 return R == null; 1017 } 1018 if (P.isZERO()) { 1019 return R.isZERO(); 1020 } 1021 if (!(P instanceof RecSolvablePolynomial)) { 1022 return !(R instanceof RecSolvablePolynomial); 1023 } 1024 if (!(R instanceof RecSolvablePolynomial)) { 1025 return false; 1026 } 1027 RecSolvablePolynomialRing<C> rfac = (RecSolvablePolynomialRing<C>) P.ring; 1028 if (rfac.coeffTable.isEmpty()) { 1029 RecSolvablePolynomialRing<C> rf = (RecSolvablePolynomialRing<C>) R.ring; 1030 return rf.coeffTable.isEmpty(); 1031 } 1032 RecSolvablePolynomial<C> p = (RecSolvablePolynomial<C>) P; 1033 RecSolvablePolynomial<C> q = (RecSolvablePolynomial<C>) R.evalAsRightRecursivePolynomial(); 1034 p = (RecSolvablePolynomial<C>) PolyUtil.<C> monic(p); 1035 q = (RecSolvablePolynomial<C>) PolyUtil.<C> monic(q); 1036 return p.equals(q); 1037 } 1038 */ 1039 1040 /** 1041 * RecSolvablePolynomial right coefficients multiply. <b>Note:</b> R is 1042 * represented as a polynomial with left coefficients, the implementation 1043 * can at the moment not distinguish between left and right coefficients. 1044 * @param <C> coefficient type. 1045 * @param P GenSolvablePolynomial with right coefficients. 1046 * @param b coefficient. 1047 * @return R = P * b 1048 */ 1049 public static <C extends RingElem<C>> GenSolvablePolynomial<GenPolynomial<C>> multiplyRightRecursivePolynomial( 1050 GenSolvablePolynomial<GenPolynomial<C>> P, GenPolynomial<C> b) { 1051 if (P == null || P.isZERO()) { 1052 return P; 1053 } 1054 GenSolvablePolynomial<GenPolynomial<C>> Cp = P.ring.getZERO().copy(); 1055 if (b == null || b.isZERO()) { 1056 return Cp; 1057 } 1058 //Map<ExpVector, GenPolynomial<C>> Cm = Cp.val; //getMap(); 1059 Map<ExpVector, GenPolynomial<C>> Am = P.getMap(); //val; 1060 for (Map.Entry<ExpVector, GenPolynomial<C>> y : Am.entrySet()) { 1061 ExpVector e = y.getKey(); 1062 GenPolynomial<C> a = y.getValue(); 1063 GenPolynomial<C> c = a.multiply(b); 1064 if (!c.isZERO()) { 1065 //Cm.put(e, c); 1066 Cp.doPutToMap(e, c); 1067 } 1068 } 1069 return Cp; 1070 } 1071 1072 1073 /** 1074 * Integral solvable polynomial from solvable rational function 1075 * coefficients. Represent as polynomial with integral solvable polynomial 1076 * coefficients by multiplication with the lcm(??) of the numerators of the 1077 * rational function coefficients. 1078 * @param fac result polynomial factory. 1079 * @param A polynomial with solvable rational function coefficients to be 1080 * converted. 1081 * @return polynomial with integral solvable polynomial coefficients. 1082 */ 1083 public static <C extends GcdRingElem<C>> GenSolvablePolynomial<GenPolynomial<C>> integralFromQuotientCoefficients( 1084 GenSolvablePolynomialRing<GenPolynomial<C>> fac, 1085 GenSolvablePolynomial<SolvableQuotient<C>> A) { 1086 GenSolvablePolynomial<GenPolynomial<C>> B = fac.getZERO().copy(); 1087 if (A == null || A.isZERO()) { 1088 return B; 1089 } 1090 GenSolvablePolynomial<C> c = null; 1091 GenSolvablePolynomial<C> d; 1092 GenSolvablePolynomial<C> x; 1093 GenSolvablePolynomial<C> z; 1094 GenPolynomialRing<C> cofac = (GenPolynomialRing) fac.coFac; 1095 GreatestCommonDivisorAbstract<C> fd = new GreatestCommonDivisorPrimitive<C>(cofac.coFac); 1096 int s = 0; 1097 // lcm/ore of denominators ?? 1098 Map<ExpVector, SolvableQuotient<C>> Am = A.getMap(); 1099 for (SolvableQuotient<C> y : Am.values()) { 1100 x = y.den; 1101 // c = lcm(c,x) 1102 if (c == null) { 1103 c = x; 1104 s = x.signum(); 1105 } else { 1106 d = fd.leftGcd(c, x); 1107 z = (GenSolvablePolynomial<C>) x.divide(d); // ?? 1108 c = z.multiply(c); // ?? multiplyLeft 1109 } 1110 } 1111 if (s < 0) { 1112 c = (GenSolvablePolynomial<C>) c.negate(); 1113 } 1114 for (Map.Entry<ExpVector, SolvableQuotient<C>> y : Am.entrySet()) { 1115 ExpVector e = y.getKey(); 1116 SolvableQuotient<C> a = y.getValue(); 1117 // p = n*(c/d) 1118 GenPolynomial<C> b = c.divide(a.den); 1119 GenPolynomial<C> p = a.num.multiply(b); 1120 //B = B.sum( p, e ); // inefficient 1121 B.doPutToMap(e, p); 1122 } 1123 return B; 1124 } 1125 1126 1127 /** 1128 * Integral solvable polynomial from solvable rational function 1129 * coefficients. Represent as polynomial with integral solvable polynomial 1130 * coefficients by multiplication with the lcm(??) of the numerators of the 1131 * solvable rational function coefficients. 1132 * @param fac result polynomial factory. 1133 * @param L list of polynomials with solvable rational function coefficients 1134 * to be converted. 1135 * @return list of polynomials with integral solvable polynomial 1136 * coefficients. 1137 */ 1138 public static <C extends GcdRingElem<C>> List<GenSolvablePolynomial<GenPolynomial<C>>> integralFromQuotientCoefficients( 1139 GenSolvablePolynomialRing<GenPolynomial<C>> fac, 1140 Collection<GenSolvablePolynomial<SolvableQuotient<C>>> L) { 1141 if (L == null) { 1142 return null; 1143 } 1144 List<GenSolvablePolynomial<GenPolynomial<C>>> list = new ArrayList<GenSolvablePolynomial<GenPolynomial<C>>>( 1145 L.size()); 1146 for (GenSolvablePolynomial<SolvableQuotient<C>> p : L) { 1147 list.add(integralFromQuotientCoefficients(fac, p)); 1148 } 1149 return list; 1150 } 1151 1152 1153 /** 1154 * Solvable rational function from integral solvable polynomial 1155 * coefficients. Represent as polynomial with type SolvableQuotient<C> 1156 * coefficients. 1157 * @param fac result polynomial factory. 1158 * @param A polynomial with integral solvable polynomial coefficients to be 1159 * converted. 1160 * @return polynomial with type SolvableQuotient<C> coefficients. 1161 */ 1162 public static <C extends GcdRingElem<C>> GenSolvablePolynomial<SolvableQuotient<C>> quotientFromIntegralCoefficients( 1163 GenSolvablePolynomialRing<SolvableQuotient<C>> fac, 1164 GenSolvablePolynomial<GenPolynomial<C>> A) { 1165 GenSolvablePolynomial<SolvableQuotient<C>> B = fac.getZERO().copy(); 1166 if (A == null || A.isZERO()) { 1167 return B; 1168 } 1169 RingFactory<SolvableQuotient<C>> cfac = fac.coFac; 1170 SolvableQuotientRing<C> qfac = (SolvableQuotientRing<C>) cfac; 1171 for (Map.Entry<ExpVector, GenPolynomial<C>> y : A.getMap().entrySet()) { 1172 ExpVector e = y.getKey(); 1173 GenSolvablePolynomial<C> a = (GenSolvablePolynomial<C>) y.getValue(); 1174 SolvableQuotient<C> p = new SolvableQuotient<C>(qfac, a); // can not be zero 1175 if (!p.isZERO()) { 1176 //B = B.sum( p, e ); // inefficient 1177 B.doPutToMap(e, p); 1178 } 1179 } 1180 return B; 1181 } 1182 1183 1184 /** 1185 * Solvable rational function from integral solvable polynomial 1186 * coefficients. Represent as polynomial with type SolvableQuotient<C> 1187 * coefficients. 1188 * @param fac result polynomial factory. 1189 * @param L list of polynomials with integral solvable polynomial 1190 * coefficients to be converted. 1191 * @return list of polynomials with type SolvableQuotient<C> coefficients. 1192 */ 1193 public static <C extends GcdRingElem<C>> List<GenSolvablePolynomial<SolvableQuotient<C>>> quotientFromIntegralCoefficients( 1194 GenSolvablePolynomialRing<SolvableQuotient<C>> fac, 1195 Collection<GenSolvablePolynomial<GenPolynomial<C>>> L) { 1196 if (L == null) { 1197 return null; 1198 } 1199 List<GenSolvablePolynomial<SolvableQuotient<C>>> list = new ArrayList<GenSolvablePolynomial<SolvableQuotient<C>>>( 1200 L.size()); 1201 for (GenSolvablePolynomial<GenPolynomial<C>> p : L) { 1202 list.add(quotientFromIntegralCoefficients(fac, p)); 1203 } 1204 return list; 1205 } 1206 1207}