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