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