001/* 002 * $Id$ 003 */ 004 005package edu.jas.fd; 006 007 008import java.util.ArrayList; 009import java.util.Arrays; 010import java.util.List; 011 012import org.apache.logging.log4j.LogManager; 013import org.apache.logging.log4j.Logger; 014 015import edu.jas.gbufd.SolvableSyzygyAbstract; 016import edu.jas.gbufd.SolvableSyzygySeq; 017import edu.jas.poly.GenPolynomial; 018import edu.jas.poly.GenSolvablePolynomial; 019import edu.jas.poly.GenSolvablePolynomialRing; 020import edu.jas.poly.PolyUtil; 021import edu.jas.poly.RecSolvablePolynomial; 022import edu.jas.poly.RecSolvablePolynomialRing; 023import edu.jas.structure.GcdRingElem; 024import edu.jas.structure.RingFactory; 025import edu.jas.structure.StarRingElem; 026import edu.jas.ufd.GCDFactory; 027 028 029/** 030 * (Non-unique) factorization domain greatest common divisor common algorithms. 031 * @param <C> coefficient type 032 * @author Heinz Kredel 033 */ 034 035public abstract class GreatestCommonDivisorAbstract<C extends GcdRingElem<C>> 036 implements GreatestCommonDivisor<C> { 037 038 039 private static final Logger logger = LogManager.getLogger(GreatestCommonDivisorAbstract.class); 040 041 042 private static final boolean debug = logger.isDebugEnabled(); 043 044 045 /** 046 * Engine for syzygy computation, mainly for Ore conditions. 047 */ 048 final SolvableSyzygyAbstract<C> syz; 049 050 051 /** 052 * Coefficient ring. 053 */ 054 final RingFactory<C> coFac; 055 056 057 /* 058 * Engine for commutative gcd computation. 059 */ 060 //edu.jas.ufd.GreatestCommonDivisorAbstract<C> cgcd; 061 062 063 /** 064 * Constructor. 065 * @param cf coefficient ring. 066 */ 067 public GreatestCommonDivisorAbstract(RingFactory<C> cf) { 068 this(cf, new SolvableSyzygySeq<C>(cf)); 069 } 070 071 072 /** 073 * Constructor. 074 * @param cf coefficient ring. 075 * @param s algorithm for SolvableSyzygy computation. 076 */ 077 public GreatestCommonDivisorAbstract(RingFactory<C> cf, SolvableSyzygyAbstract<C> s) { 078 coFac = cf; 079 syz = s; 080 //cgcd = GCDFactory.<C> getImplementation(pfac.coFac); 081 } 082 083 084 /** 085 * Get the String representation. 086 * @see java.lang.Object#toString() 087 */ 088 @Override 089 public String toString() { 090 return getClass().getName(); 091 } 092 093 094 /** 095 * GenSolvablePolynomial base coefficient content. 096 * @param P GenSolvablePolynomial. 097 * @return cont(P) with pp(P)*cont(P) = P. 098 */ 099 public C leftBaseContent(GenSolvablePolynomial<C> P) { 100 if (P == null) { 101 throw new IllegalArgumentException("P == null"); 102 } 103 if (P.isZERO()) { 104 return P.ring.getZEROCoefficient(); 105 } 106 if (P.ring.coFac.isField()) { // so to make monic 107 return P.leadingBaseCoefficient(); 108 } 109 C d = null; 110 for (C c : P.getMap().values()) { 111 if (d == null) { 112 d = c; 113 } else { 114 d = d.leftGcd(c); 115 } 116 if (d.isONE()) { 117 return d; 118 } 119 } 120 if (d.signum() < 0) { 121 d = d.negate(); 122 } 123 return d; 124 } 125 126 127 /** 128 * GenSolvablePolynomial right base coefficient content. 129 * @param P GenSolvablePolynomial. 130 * @return cont(P) with cont(P)*pp(P) = P. 131 */ 132 public C rightBaseContent(GenSolvablePolynomial<C> P) { 133 if (P == null) { 134 throw new IllegalArgumentException("P == null"); 135 } 136 if (P.isZERO()) { 137 return P.ring.getZEROCoefficient(); 138 } 139 if (P.ring.coFac.isField()) { // so to make monic 140 return P.leadingBaseCoefficient(); // todo check move to right 141 } 142 C d = null; 143 for (C c : P.getMap().values()) { 144 if (d == null) { 145 d = c; 146 } else { 147 d = d.rightGcd(c); // DONE does now exist 148 } 149 if (d.isONE()) { 150 return d; 151 } 152 } 153 if (d.signum() < 0) { 154 d = d.negate(); 155 } 156 return d; 157 } 158 159 160 /** 161 * GenSolvablePolynomial base coefficient primitive part. 162 * @param P GenSolvablePolynomial. 163 * @return pp(P) with pp(P)*cont(P) = P. 164 */ 165 public GenSolvablePolynomial<C> leftBasePrimitivePart(GenSolvablePolynomial<C> P) { 166 if (P == null) { 167 throw new IllegalArgumentException("P == null"); 168 } 169 if (P.isZERO()) { 170 return P; 171 } 172 C d = leftBaseContent(P); 173 if (d.isONE()) { 174 return P; 175 } 176 if (P.ring.coFac.isField()) { // make monic 177 return P.multiplyLeft(d.inverse()); // avoid the divisions 178 //return P.multiply( d.inverse() ); // avoid the divisions 179 } 180 //GenSolvablePolynomial<C> pp = (GenSolvablePolynomial<C>) P.rightDivideCoeff(d); // rightDivide TODO/done 181 GenSolvablePolynomial<C> pp = (GenSolvablePolynomial<C>) P.leftDivideCoeff(d); // TODO 182 if (debug) { 183 GenSolvablePolynomial<C> p = pp.multiplyLeft(d); 184 if (!p.equals(P)) { 185 throw new ArithmeticException("pp(p)*cont(p) != p: "); 186 } 187 } 188 return pp; 189 } 190 191 192 /** 193 * GenSolvablePolynomial right base coefficient primitive part. 194 * @param P GenSolvablePolynomial. 195 * @return pp(P) with cont(P)*pp(P) = P. 196 */ 197 public GenSolvablePolynomial<C> rightBasePrimitivePart(GenSolvablePolynomial<C> P) { 198 if (P == null) { 199 throw new IllegalArgumentException("P == null"); 200 } 201 if (P.isZERO()) { 202 return P; 203 } 204 C d = rightBaseContent(P); 205 if (d.isONE()) { 206 return P; 207 } 208 if (P.ring.coFac.isField()) { // make monic 209 return P.multiply(d.inverse()); // avoid the divisions 210 } 211 GenSolvablePolynomial<C> pp = (GenSolvablePolynomial<C>) P.rightDivideCoeff(d); // leftDivide TODO/done 212 if (debug) { 213 GenSolvablePolynomial<C> p = pp.multiplyLeft(d); 214 if (!p.equals(P)) { 215 throw new ArithmeticException("pp(p)*cont(p) != p: "); 216 } 217 } 218 return pp; 219 } 220 221 222 /** 223 * Univariate GenSolvablePolynomial greatest common divisor. Uses sparse 224 * pseudoRemainder for remainder. 225 * @param P univariate GenSolvablePolynomial. 226 * @param S univariate GenSolvablePolynomial. 227 * @return gcd(P,S) with P = P'*gcd(P,S) and S = S'*gcd(P,S). 228 */ 229 public abstract GenSolvablePolynomial<C> leftBaseGcd(GenSolvablePolynomial<C> P, 230 GenSolvablePolynomial<C> S); 231 232 233 /** 234 * Univariate GenSolvablePolynomial right greatest common divisor. Uses 235 * sparse pseudoRemainder for remainder. 236 * @param P univariate GenSolvablePolynomial. 237 * @param S univariate GenSolvablePolynomial. 238 * @return gcd(P,S) with P = gcd(P,S)*P' and S = gcd(P,S)*S'. 239 */ 240 public abstract GenSolvablePolynomial<C> rightBaseGcd(GenSolvablePolynomial<C> P, 241 GenSolvablePolynomial<C> S); 242 243 244 /** 245 * GenSolvablePolynomial commuting recursive content. 246 * @param P recursive GenSolvablePolynomial with commuting main and 247 * coefficient variables. 248 * @return cont(P) with cont(P)*pp(P) = pp(P)*cont(P). 249 */ 250 public GenSolvablePolynomial<C> recursiveContent(GenSolvablePolynomial<GenPolynomial<C>> P) { 251 if (P == null) { 252 throw new IllegalArgumentException("P == null"); 253 } 254 if (P instanceof RecSolvablePolynomial) { 255 RecSolvablePolynomialRing<C> rfac = (RecSolvablePolynomialRing<C>) P.ring; 256 if (!rfac.coeffTable.isEmpty()) { 257 throw new UnsupportedOperationException("RecSolvablePolynomial with non empty coeffTable"); 258 } 259 } 260 if (P.isZERO()) { 261 return (GenSolvablePolynomial<C>) P.ring.getZEROCoefficient(); 262 } 263 if (P.leadingBaseCoefficient().isONE()) { 264 return (GenSolvablePolynomial<C>) P.ring.getONECoefficient(); 265 } 266 GenSolvablePolynomial<C> d = null; 267 for (GenPolynomial<C> cp : P.getMap().values()) { 268 GenSolvablePolynomial<C> c = (GenSolvablePolynomial<C>) cp; 269 if (d == null) { 270 d = c; 271 } else { 272 ///d = leftGcd(d, c); // go to recursion 273 d = rightGcd(d, c); // go to recursion 274 } 275 if (d.isONE()) { 276 return d; 277 } 278 } 279 return (GenSolvablePolynomial<C>) d.abs(); 280 } 281 282 283 /** 284 * GenSolvablePolynomial left recursive content. 285 * @param P recursive GenSolvablePolynomial. 286 * @return cont(P) with cont(P)*pp(P) = P. 287 */ 288 public GenSolvablePolynomial<C> leftRecursiveContent(GenSolvablePolynomial<GenPolynomial<C>> P) { 289 if (P == null) { 290 throw new IllegalArgumentException("P != null"); 291 } 292 if (P.isZERO()) { 293 return (GenSolvablePolynomial<C>) P.ring.getZEROCoefficient(); 294 } 295 if (P.leadingBaseCoefficient().isONE()) { 296 return (GenSolvablePolynomial<C>) P.ring.getONECoefficient(); 297 } 298 GenSolvablePolynomial<C> d = null, cs = null; 299 GenSolvablePolynomial<GenPolynomial<C>> Pr = P; //FDUtil.<C> rightRecursivePolynomial(P); 300 logger.info("recCont: P = {}, left(P) = {}", P, Pr); 301 for (GenPolynomial<C> c : Pr.getMap().values()) { 302 cs = (GenSolvablePolynomial<C>) c; 303 if (d == null) { 304 d = cs; 305 } else { 306 d = leftGcd(d, cs); // go to recursion 307 logger.info("recCont: cs = {}, d = {}", cs, d); 308 } 309 if (d.isONE()) { 310 return d; 311 } 312 } 313 return (GenSolvablePolynomial<C>) d.abs(); 314 } 315 316 317 /** 318 * GenSolvablePolynomial right recursive content. 319 * @param P recursive GenSolvablePolynomial. 320 * @return cont(P) with pp(P)*cont(P) = P. 321 */ 322 public GenSolvablePolynomial<C> rightRecursiveContent(GenSolvablePolynomial<GenPolynomial<C>> P) { 323 if (P == null) { 324 throw new IllegalArgumentException("P != null"); 325 } 326 if (P.isZERO()) { 327 return (GenSolvablePolynomial<C>) P.ring.getZEROCoefficient(); 328 } 329 if (P.leadingBaseCoefficient().isONE()) { 330 return (GenSolvablePolynomial<C>) P.ring.getONECoefficient(); 331 } 332 GenSolvablePolynomial<C> d = null, cs = null, x; 333 GenSolvablePolynomial<GenPolynomial<C>> Pr = P.rightRecursivePolynomial(); 334 logger.warn("RI-recCont: P = {}, right(P) = {}", P, Pr); 335 for (GenPolynomial<C> c : Pr.getMap().values()) { 336 cs = (GenSolvablePolynomial<C>) c; 337 if (d == null) { 338 d = cs; 339 } else { 340 x = d; 341 d = leftGcd(d, cs); // go to recursion, P = P'*gcd(P,S) 342 ///d = rightGcd(d, cs); // go to recursion, P = gcd(P,S)*P' 343 logger.info("RI-recCont: d = {}, cs = {}, d = {}", x, cs, d); 344 } 345 if (d.isONE()) { 346 return d; 347 } 348 } 349 return (GenSolvablePolynomial<C>) d.abs();// todo: eval right ? 350 } 351 352 353 /** 354 * GenSolvablePolynomial left recursive primitive part. 355 * @param P recursive GenSolvablePolynomial. 356 * @return pp(P) with cont(P)*pp(P) = P. 357 */ 358 public GenSolvablePolynomial<GenPolynomial<C>> leftRecursivePrimitivePart( 359 GenSolvablePolynomial<GenPolynomial<C>> P) { 360 if (P == null) { 361 throw new IllegalArgumentException("P == null"); 362 } 363 if (P.isZERO()) { 364 return P; 365 } 366 GenSolvablePolynomial<C> d = leftRecursiveContent(P); 367 if (d.isONE()) { 368 return P; 369 } 370 GenSolvablePolynomial<GenPolynomial<C>> pp; 371 //pp = FDUtil.<C> recursiveRightDivide(P, d); 372 pp = FDUtil.<C> recursiveLeftDivide(P, d); 373 if (debug) { // not checkable 374 if (!P.equals(pp.multiplyLeft(d))) { 375 System.out.println("ppart, P = " + P); 376 System.out.println("ppart, cont(P) = " + d); 377 System.out.println("ppart, pp(P) = " + pp); 378 System.out.println("ppart, pp(P)c(P) = " + pp.multiplyLeft(d)); 379 throw new RuntimeException("primitivePart: P != cont(P)*pp(P)"); 380 } 381 } 382 return pp; 383 } 384 385 386 /** 387 * GenSolvablePolynomial right recursive primitive part. 388 * @param P recursive GenSolvablePolynomial. 389 * @return pp(P) with pp(P)*cont(P) = P. 390 */ 391 public GenSolvablePolynomial<GenPolynomial<C>> rightRecursivePrimitivePart( 392 GenSolvablePolynomial<GenPolynomial<C>> P) { 393 if (P == null) { 394 throw new IllegalArgumentException("P == null"); 395 } 396 if (P.isZERO()) { 397 return P; 398 } 399 GenSolvablePolynomial<C> d = rightRecursiveContent(P); 400 if (d.isONE()) { 401 return P; 402 } 403 GenSolvablePolynomial<GenPolynomial<C>> pp; 404 pp = FDUtil.<C> recursiveRightDivide(P, d); //RightEval 405 if (debug) { // not checkable 406 if (!P.equals(pp.multiply(d))) { 407 System.out.println("RI-ppart, P = " + P); 408 System.out.println("RI-ppart, cont(P) = " + d); 409 System.out.println("RI-ppart, pp(P) = " + pp); 410 System.out.println("RI-ppart, pp(P)c(P) = " + pp.multiply(d)); 411 throw new RuntimeException("RI-primitivePart: P != pp(P)*cont(P)"); 412 } 413 } 414 return pp; 415 } 416 417 418 /** 419 * GenSolvablePolynomial base recursive content. 420 * @param P recursive GenSolvablePolynomial. 421 * @return baseCont(P) with pp(P)*cont(P) = P. 422 */ 423 public C baseRecursiveContent(GenSolvablePolynomial<GenPolynomial<C>> P) { 424 if (P == null) { 425 throw new IllegalArgumentException("P == null"); 426 } 427 if (P.isZERO()) { 428 GenSolvablePolynomialRing<C> cf = (GenSolvablePolynomialRing<C>) P.ring.coFac; 429 return cf.coFac.getZERO(); 430 } 431 C d = null; 432 for (GenPolynomial<C> cp : P.getMap().values()) { 433 GenSolvablePolynomial<C> c = (GenSolvablePolynomial<C>) cp; 434 C cc = leftBaseContent(c); 435 if (d == null) { 436 d = cc; 437 } else { 438 d = gcd(d, cc); 439 } 440 if (d.isONE()) { 441 return d; 442 } 443 } 444 return d.abs(); 445 } 446 447 448 /** 449 * GenSolvablePolynomial base recursive primitive part. 450 * @param P recursive GenSolvablePolynomial. 451 * @return basePP(P) with pp(P)*cont(P) = P. 452 */ 453 public GenSolvablePolynomial<GenPolynomial<C>> baseRecursivePrimitivePart( 454 GenSolvablePolynomial<GenPolynomial<C>> P) { 455 if (P == null) { 456 throw new IllegalArgumentException("P == null"); 457 } 458 if (P.isZERO()) { 459 return P; 460 } 461 C d = baseRecursiveContent(P); 462 if (d.isONE()) { 463 return P; 464 } 465 GenSolvablePolynomial<GenPolynomial<C>> pp = (GenSolvablePolynomial<GenPolynomial<C>>) PolyUtil 466 .<C> baseRecursiveDivide(P, d); 467 return pp; 468 } 469 470 471 /** 472 * GenSolvablePolynomial left recursive greatest common divisor. Uses 473 * pseudoRemainder for remainder. 474 * @param P recursive GenSolvablePolynomial. 475 * @param S recursive GenSolvablePolynomial. 476 * @return gcd(P,S) with P = P'*gcd(P,S)*p and S = S'*gcd(P,S)*s, where 477 * deg_main(p) = deg_main(s) == 0. 478 */ 479 @SuppressWarnings("unchecked") 480 public GenSolvablePolynomial<GenPolynomial<C>> leftRecursiveGcd(GenSolvablePolynomial<GenPolynomial<C>> P, 481 GenSolvablePolynomial<GenPolynomial<C>> S) { 482 if (S == null || S.isZERO()) { 483 return P; 484 } 485 if (P == null || P.isZERO()) { 486 return S; 487 } 488 if (P.ring.nvar == 1) { 489 return leftRecursiveUnivariateGcd(P, S); 490 } 491 // distributed polynomials gcd 492 GenSolvablePolynomialRing<GenPolynomial<C>> rfac = P.ring; 493 GenSolvablePolynomialRing<C> dfac; 494 if (rfac instanceof RecSolvablePolynomialRing) { 495 RecSolvablePolynomialRing<C> rf = (RecSolvablePolynomialRing<C>) rfac; 496 dfac = RecSolvablePolynomialRing.<C> distribute(rf); 497 } else { 498 GenSolvablePolynomialRing<C> df = (GenSolvablePolynomialRing) rfac; 499 dfac = df.distribute(); 500 } 501 GenSolvablePolynomial<C> Pd = (GenSolvablePolynomial<C>) PolyUtil.<C> distribute(dfac, P); 502 GenSolvablePolynomial<C> Sd = (GenSolvablePolynomial<C>) PolyUtil.<C> distribute(dfac, S); 503 // left gcd 504 GenSolvablePolynomial<C> Dd = leftGcd(Pd, Sd); 505 // convert back to recursive 506 GenSolvablePolynomial<GenPolynomial<C>> C = (GenSolvablePolynomial<GenPolynomial<C>>) PolyUtil 507 .<C> recursive(rfac, Dd); 508 return C; 509 } 510 511 512 /** 513 * GenSolvablePolynomial right recursive greatest common divisor. Uses 514 * pseudoRemainder for remainder. 515 * @param P recursive GenSolvablePolynomial. 516 * @param S recursive GenSolvablePolynomial. 517 * @return gcd(P,S) with P = p*gcd(P,S)*P' and S = s*gcd(P,S)*S', where 518 * deg_main(p) = deg_main(s) == 0. 519 */ 520 @SuppressWarnings("unchecked") 521 public GenSolvablePolynomial<GenPolynomial<C>> rightRecursiveGcd( 522 GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<GenPolynomial<C>> S) { 523 if (S == null || S.isZERO()) { 524 return P; 525 } 526 if (P == null || P.isZERO()) { 527 return S; 528 } 529 if (P.ring.nvar == 1) { 530 return rightRecursiveUnivariateGcd(P, S); 531 } 532 // distributed polynomials gcd 533 GenSolvablePolynomialRing<GenPolynomial<C>> rfac = P.ring; 534 GenSolvablePolynomialRing<C> dfac; 535 if (rfac instanceof RecSolvablePolynomialRing) { 536 RecSolvablePolynomialRing<C> rf = (RecSolvablePolynomialRing<C>) rfac; 537 dfac = RecSolvablePolynomialRing.<C> distribute(rf); 538 } else { 539 GenSolvablePolynomialRing<C> df = (GenSolvablePolynomialRing) rfac; 540 dfac = df.distribute(); 541 } 542 GenSolvablePolynomial<C> Pd = (GenSolvablePolynomial<C>) PolyUtil.<C> distribute(dfac, P); 543 GenSolvablePolynomial<C> Sd = (GenSolvablePolynomial<C>) PolyUtil.<C> distribute(dfac, S); 544 GenSolvablePolynomial<C> Dd = rightGcd(Pd, Sd); 545 // convert to recursive 546 GenSolvablePolynomial<GenPolynomial<C>> C = (GenSolvablePolynomial<GenPolynomial<C>>) PolyUtil 547 .<C> recursive(rfac, Dd); 548 return C; 549 } 550 551 552 /** 553 * Univariate GenSolvablePolynomial recursive greatest common divisor. Uses 554 * pseudoRemainder for remainder. 555 * @param P univariate recursive GenSolvablePolynomial. 556 * @param S univariate recursive GenSolvablePolynomial. 557 * @return gcd(P,S) with P = P'*gcd(P,S)*p and S = S'*gcd(P,S)*s, where 558 * deg_main(p) = deg_main(s) == 0. 559 */ 560 public abstract GenSolvablePolynomial<GenPolynomial<C>> leftRecursiveUnivariateGcd( 561 GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<GenPolynomial<C>> S); 562 563 564 /** 565 * Univariate GenSolvablePolynomial right recursive greatest common divisor. 566 * Uses pseudoRemainder for remainder. 567 * @param P univariate recursive GenSolvablePolynomial. 568 * @param S univariate recursive GenSolvablePolynomial. 569 * @return gcd(P,S) with P = p*gcd(P,S)*P' and S = s*gcd(P,S)*S', where 570 * deg_main(p) = deg_main(s) == 0. 571 */ 572 public abstract GenSolvablePolynomial<GenPolynomial<C>> rightRecursiveUnivariateGcd( 573 GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<GenPolynomial<C>> S); 574 575 576 /** 577 * GenSolvablePolynomial left content. 578 * @param P GenSolvablePolynomial. 579 * @return cont(P) with cont(P)*pp(P) = P. 580 */ 581 public GenSolvablePolynomial<C> leftContent(GenSolvablePolynomial<C> P) { 582 if (P == null) { 583 throw new IllegalArgumentException("P == null"); 584 } 585 GenSolvablePolynomialRing<C> pfac = P.ring; 586 if (pfac.nvar <= 1) { 587 // baseContent not possible by return type 588 throw new IllegalArgumentException("use baseContent() for univariate polynomials"); 589 } 590 GenSolvablePolynomialRing<GenPolynomial<C>> rfac // = (RecSolvablePolynomialRing<C>) 591 = pfac.recursive(1); 592 593 GenSolvablePolynomial<GenPolynomial<C>> Pr = (RecSolvablePolynomial<C>) PolyUtil.<C> recursive(rfac, 594 P); 595 GenSolvablePolynomial<C> D = leftRecursiveContent(Pr); 596 return D; 597 } 598 599 600 /** 601 * GenSolvablePolynomial left primitive part. 602 * @param P GenSolvablePolynomial. 603 * @return pp(P) with cont(P)*pp(P) = P. 604 */ 605 public GenSolvablePolynomial<C> leftPrimitivePart(GenSolvablePolynomial<C> P) { 606 if (P == null) { 607 throw new IllegalArgumentException("P == null"); 608 } 609 if (P.isZERO()) { 610 return P; 611 } 612 GenSolvablePolynomialRing<C> pfac = P.ring; 613 if (pfac.nvar <= 1) { 614 return leftBasePrimitivePart(P); 615 } 616 GenSolvablePolynomialRing<GenPolynomial<C>> rfac = /*(RecSolvablePolynomialRing<C>)*/pfac 617 .recursive(1); 618 619 GenSolvablePolynomial<GenPolynomial<C>> Pr = (RecSolvablePolynomial<C>) PolyUtil.<C> recursive(rfac, 620 P); 621 GenSolvablePolynomial<GenPolynomial<C>> PP = leftRecursivePrimitivePart(Pr); 622 623 GenSolvablePolynomial<C> D = (GenSolvablePolynomial<C>) PolyUtil.<C> distribute(pfac, PP); 624 return D; 625 } 626 627 628 /** 629 * GenSolvablePolynomial right content. 630 * @param P GenSolvablePolynomial. 631 * @return cont(P) with pp(P)*cont(P) = P. 632 */ 633 public GenSolvablePolynomial<C> rightContent(GenSolvablePolynomial<C> P) { 634 if (P == null) { 635 throw new IllegalArgumentException("P == null"); 636 } 637 GenSolvablePolynomialRing<C> pfac = P.ring; 638 if (pfac.nvar <= 1) { 639 // baseContent not possible by return type 640 throw new IllegalArgumentException("use baseContent() for univariate polynomials"); 641 } 642 GenSolvablePolynomialRing<GenPolynomial<C>> rfac // = (RecSolvablePolynomialRing<C>) 643 = pfac.recursive(1); 644 645 GenSolvablePolynomial<GenPolynomial<C>> Pr = (RecSolvablePolynomial<C>) PolyUtil.<C> recursive(rfac, 646 P); 647 GenSolvablePolynomial<C> D = rightRecursiveContent(Pr); 648 return D; 649 } 650 651 652 /** 653 * GenSolvablePolynomial right primitive part. 654 * @param P GenSolvablePolynomial. 655 * @return pp(P) with pp(P)*cont(P) = P. 656 */ 657 public GenSolvablePolynomial<C> rightPrimitivePart(GenSolvablePolynomial<C> P) { 658 if (P == null) { 659 throw new IllegalArgumentException("P == null"); 660 } 661 if (P.isZERO()) { 662 return P; 663 } 664 GenSolvablePolynomialRing<C> pfac = P.ring; 665 if (pfac.nvar <= 1) { 666 return rightBasePrimitivePart(P); 667 } 668 GenSolvablePolynomialRing<GenPolynomial<C>> rfac = /*(RecSolvablePolynomialRing<C>)*/pfac 669 .recursive(1); 670 671 GenSolvablePolynomial<GenPolynomial<C>> Pr = (RecSolvablePolynomial<C>) PolyUtil.<C> recursive(rfac, 672 P); 673 GenSolvablePolynomial<GenPolynomial<C>> PP = rightRecursivePrimitivePart(Pr); 674 675 GenSolvablePolynomial<C> D = (GenSolvablePolynomial<C>) PolyUtil.<C> distribute(pfac, PP); 676 return D; 677 } 678 679 680 /** 681 * GenSolvablePolynomial division. Indirection to GenSolvablePolynomial 682 * method. 683 * @param a GenSolvablePolynomial. 684 * @param b coefficient. 685 * @return a' = a/b with a = a'*b. 686 */ 687 public GenSolvablePolynomial<C> divide(GenSolvablePolynomial<C> a, C b) { 688 if (b == null || b.isZERO()) { 689 throw new IllegalArgumentException("division by zero"); 690 691 } 692 if (a == null || a.isZERO()) { 693 return a; 694 } 695 return (GenSolvablePolynomial<C>) a.leftDivideCoeff(b); 696 } 697 698 699 /** 700 * GenSolvablePolynomial right division. Indirection to GenSolvablePolynomial 701 * method. 702 * @param a GenSolvablePolynomial. 703 * @param b coefficient. 704 * @return a' = a/b with a = b*a'. 705 */ 706 public GenSolvablePolynomial<C> rightDivide(GenSolvablePolynomial<C> a, C b) { 707 if (b == null || b.isZERO()) { 708 throw new IllegalArgumentException("division by zero"); 709 710 } 711 if (a == null || a.isZERO()) { 712 return a; 713 } 714 return (GenSolvablePolynomial<C>) a.rightDivideCoeff(b); 715 } 716 717 718 /** 719 * Coefficient greatest common divisor. Indirection to coefficient method. 720 * @param a coefficient. 721 * @param b coefficient. 722 * @return gcd(a,b) with a = gcd(a,b)*a' and b = gcd(a,b)*b'. 723 */ 724 public C gcd(C a, C b) { 725 if (b == null || b.isZERO()) { 726 return a; 727 } 728 if (a == null || a.isZERO()) { 729 return b; 730 } 731 return a.gcd(b); 732 } 733 734 735 /** 736 * Coefficient greatest common divisor. Indirection to coefficient method. 737 * @param a coefficient. 738 * @param b coefficient. 739 * @return gcd(a,b) with a = gcd(a,b)*a' and b = gcd(a,b)*b'. 740 */ 741 public C leftGcd(C a, C b) { 742 return a.leftGcd(b); 743 } 744 745 746 /** 747 * GenSolvablePolynomial greatest common divisor. 748 * @param P GenSolvablePolynomial. 749 * @param S GenSolvablePolynomial. 750 * @return gcd(P,S) with P = P'*gcd(P,S)*p and S = S'*gcd(P,S)*s, where 751 * deg_main(p) = deg_main(s) == 0. 752 */ 753 public GenSolvablePolynomial<C> leftGcd(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) { 754 if (S == null || S.isZERO()) { 755 return P; 756 } 757 if (P == null || P.isZERO()) { 758 return S; 759 } 760 if (P.isONE()) { 761 return P; 762 } 763 if (S.isONE()) { 764 return S; 765 } 766 GenSolvablePolynomialRing<C> pfac = P.ring; 767 if (pfac.nvar <= 1) { 768 GenSolvablePolynomial<C> T = leftBaseGcd(P, S); 769 return T; 770 } 771 GenSolvablePolynomialRing<GenPolynomial<C>> rfac = pfac.recursive(1); //RecSolvablePolynomialRing<C> 772 GenSolvablePolynomial<GenPolynomial<C>> Pr, Sr, Dr; 773 Pr = (RecSolvablePolynomial<C>) PolyUtil.<C> recursive(rfac, P); 774 Sr = (RecSolvablePolynomial<C>) PolyUtil.<C> recursive(rfac, S); 775 Dr = leftRecursiveUnivariateGcd(Pr, Sr); 776 GenSolvablePolynomial<C> D = (GenSolvablePolynomial<C>) PolyUtil.<C> distribute(pfac, Dr); 777 if (debug) { // not checkable 778 GenSolvablePolynomial<C> ps = FDUtil.<C> rightBaseSparsePseudoRemainder(P, D); 779 GenSolvablePolynomial<C> ss = FDUtil.<C> rightBaseSparsePseudoRemainder(S, D); 780 if (!ps.isZERO() || !ss.isZERO()) { 781 System.out.println("fullGcd, D = " + D); 782 System.out.println("fullGcd, P = " + P); 783 System.out.println("fullGcd, S = " + S); 784 System.out.println("fullGcd, ps = " + ps); 785 System.out.println("fullGcd, ss = " + ss); 786 throw new RuntimeException("fullGcd: not divisible"); 787 } 788 logger.info("fullGcd(P,S) okay: D = {}, P = {}, S = {}", D, P, S); 789 } 790 return D; 791 } 792 793 794 /** 795 * GenSolvablePolynomial left least common multiple. 796 * @param P GenSolvablePolynomial. 797 * @param S GenSolvablePolynomial. 798 * @return lcm(P,S) with lcm(P,S) = P'*P = S'*S. 799 */ 800 @SuppressWarnings("unchecked") 801 public GenSolvablePolynomial<C> leftLcm(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) { 802 GenSolvablePolynomial<C>[] oc = leftOreCond(P, S); 803 return oc[0].multiply(P); 804 } 805 806 807 /** 808 * Coefficient greatest common divisor. Indirection to coefficient method. 809 * @param a coefficient. 810 * @param b coefficient. 811 * @return gcd(a,b) with a = gcd(a,b)*a' and b = gcd(a,b)*b'. 812 */ 813 public C rightGcd(C a, C b) { 814 if (b == null || b.isZERO()) { 815 return a; 816 } 817 if (a == null || a.isZERO()) { 818 return b; 819 } 820 return a.rightGcd(b); // TODO 821 } 822 823 824 /** 825 * GenSolvablePolynomial right greatest common divisor. 826 * @param P GenSolvablePolynomial. 827 * @param S GenSolvablePolynomial. 828 * @return gcd(P,S) with P = p*gcd(P,S)*P' and S = s*gcd(P,S)*S', where 829 * deg_main(p) = deg_main(s) == 0. 830 */ 831 @SuppressWarnings("unchecked") 832 public GenSolvablePolynomial<C> rightGcd(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) { 833 if (S == null || S.isZERO()) { 834 return P; 835 } 836 if (P == null || P.isZERO()) { 837 return S; 838 } 839 if (P.isONE()) { 840 return P; 841 } 842 if (S.isONE()) { 843 return S; 844 } 845 GenSolvablePolynomialRing<C> pfac = P.ring; 846 if (pfac.nvar <= 1) { 847 GenSolvablePolynomial<C> T = rightBaseGcd(P, S); 848 return T; 849 } 850 GenSolvablePolynomialRing<GenPolynomial<C>> rfac = pfac.recursive(1); //RecSolvablePolynomialRing<C> 851 GenSolvablePolynomial<GenPolynomial<C>> Pr, Sr, Dr; 852 Pr = (RecSolvablePolynomial<C>) PolyUtil.<C> recursive(rfac, P); 853 Sr = (RecSolvablePolynomial<C>) PolyUtil.<C> recursive(rfac, S); 854 Dr = rightRecursiveUnivariateGcd(Pr, Sr); 855 GenSolvablePolynomial<C> D = (GenSolvablePolynomial<C>) PolyUtil.<C> distribute(pfac, Dr); 856 if (debug) { // not checkable 857 GenSolvablePolynomial<C> ps = FDUtil.<C> leftBaseSparsePseudoRemainder(P, D); 858 GenSolvablePolynomial<C> ss = FDUtil.<C> leftBaseSparsePseudoRemainder(S, D); 859 if (!ps.isZERO() || !ss.isZERO()) { 860 System.out.println("RI-fullGcd, D = " + D); 861 System.out.println("RI-fullGcd, P = " + P); 862 System.out.println("RI-fullGcd, S = " + S); 863 System.out.println("RI-fullGcd, ps = " + ps); 864 System.out.println("RI-fullGcd, ss = " + ss); 865 throw new RuntimeException("RI-fullGcd: not divisible"); 866 } 867 logger.info("RI-fullGcd(P,S) okay: D = {}", D); 868 } 869 return D; 870 } 871 872 873 /** 874 * GenSolvablePolynomial right least common multiple. 875 * @param P GenSolvablePolynomial. 876 * @param S GenSolvablePolynomial. 877 * @return lcm(P,S) with lcm(P,S) = P*P' = S*S'. 878 */ 879 @SuppressWarnings("unchecked") 880 public GenSolvablePolynomial<C> rightLcm(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) { 881 GenSolvablePolynomial<C>[] oc = rightOreCond(P, S); 882 return P.multiply(oc[0]); 883 } 884 885 886 /** 887 * List of GenSolvablePolynomials left greatest common divisor. 888 * @param A non empty list of GenSolvablePolynomials. 889 * @return gcd(A_i) with A_i = A'_i*gcd(A_i)*a_i, where deg_main(a_i) == 0. 890 */ 891 @SuppressWarnings("unchecked") 892 public GenSolvablePolynomial<C> leftGcd(List<GenSolvablePolynomial<C>> A) { 893 if (A == null || A.isEmpty()) { 894 throw new IllegalArgumentException("A may not be empty"); 895 } 896 GenSolvablePolynomial<C> g = A.get(0); 897 for (int i = 1; i < A.size(); i++) { 898 GenSolvablePolynomial<C> f = A.get(i); 899 g = leftGcd(g, f); 900 } 901 return g; 902 } 903 904 905 /** 906 * GenSolvablePolynomial co-prime list. 907 * @param A list of GenSolvablePolynomials. 908 * @return B with gcd(b,c) = 1 for all b != c in B and for all non-constant 909 * a in A there exists b in B with b|a. B does not contain zero or 910 * constant polynomials. 911 */ 912 public List<GenSolvablePolynomial<C>> leftCoPrime(List<GenSolvablePolynomial<C>> A) { 913 if (A == null || A.isEmpty()) { 914 return A; 915 } 916 List<GenSolvablePolynomial<C>> B = new ArrayList<GenSolvablePolynomial<C>>(A.size()); 917 // make a coprime to rest of list 918 GenSolvablePolynomial<C> a = A.get(0); 919 //System.out.println("a = " + a); 920 if (!a.isZERO() && !a.isConstant()) { 921 for (int i = 1; i < A.size(); i++) { 922 GenSolvablePolynomial<C> b = A.get(i); 923 GenSolvablePolynomial<C> g = leftGcd(a, b); 924 if (!g.isONE()) { 925 a = FDUtil.<C> leftBasePseudoQuotient(a, g); 926 b = FDUtil.<C> leftBasePseudoQuotient(b, g); 927 GenSolvablePolynomial<C> gp = leftGcd(a, g); //.abs(); 928 while (!gp.isONE()) { 929 a = FDUtil.<C> leftBasePseudoQuotient(a, gp); 930 g = FDUtil.<C> leftBasePseudoQuotient(g, gp); 931 B.add(g); // gcd(a,g) == 1 932 g = gp; 933 gp = leftGcd(a, gp); 934 } 935 if (!g.isZERO() && !g.isConstant() /*&& !B.contains(g)*/) { 936 B.add(g); // gcd(a,g) == 1 937 } 938 } 939 if (!b.isZERO() && !b.isConstant()) { 940 B.add(b); // gcd(a,b) == 1 941 } 942 } 943 } else { 944 B.addAll(A.subList(1, A.size())); 945 } 946 // make rest coprime 947 B = leftCoPrime(B); 948 //System.out.println("B = " + B); 949 if (!a.isZERO() && !a.isConstant() /*&& !B.contains(a)*/) { 950 a = (GenSolvablePolynomial<C>) a.abs(); 951 B.add(a); 952 } 953 return B; 954 } 955 956 957 /** 958 * GenSolvablePolynomial left co-prime list. 959 * @param A list of GenSolvablePolynomials. 960 * @return B with gcd(b,c) = 1 for all b != c in B and for all non-constant 961 * a in A there exists b in B with b|a. B does not contain zero or 962 * constant polynomials. 963 */ 964 public List<GenSolvablePolynomial<C>> leftCoPrimeRec(List<GenSolvablePolynomial<C>> A) { 965 if (A == null || A.isEmpty()) { 966 return A; 967 } 968 List<GenSolvablePolynomial<C>> B = new ArrayList<GenSolvablePolynomial<C>>(); 969 // make a co-prime to rest of list 970 for (GenSolvablePolynomial<C> a : A) { 971 //System.out.println("a = " + a); 972 B = leftCoPrime(a, B); 973 //System.out.println("B = " + B); 974 } 975 return B; 976 } 977 978 979 /** 980 * GenSolvablePolynomial left co-prime list. 981 * @param a GenSolvablePolynomial. 982 * @param P co-prime list of GenSolvablePolynomials. 983 * @return B with gcd(b,c) = 1 for all b != c in B and for non-constant a 984 * there exists b in P with b|a. B does not contain zero or constant 985 * polynomials. 986 */ 987 public List<GenSolvablePolynomial<C>> leftCoPrime(GenSolvablePolynomial<C> a, 988 List<GenSolvablePolynomial<C>> P) { 989 if (a == null || a.isZERO() || a.isConstant()) { 990 return P; 991 } 992 List<GenSolvablePolynomial<C>> B = new ArrayList<GenSolvablePolynomial<C>>(P.size() + 1); 993 // make a coprime to elements of the list P 994 for (int i = 0; i < P.size(); i++) { 995 GenSolvablePolynomial<C> b = P.get(i); 996 GenSolvablePolynomial<C> g = leftGcd(a, b); 997 if (!g.isONE()) { 998 a = FDUtil.<C> leftBasePseudoQuotient(a, g); 999 b = FDUtil.<C> leftBasePseudoQuotient(b, g); 1000 // make g co-prime to new a, g is co-prime to c != b in P, B 1001 GenSolvablePolynomial<C> gp = leftGcd(a, g); 1002 while (!gp.isONE()) { 1003 a = FDUtil.<C> leftBasePseudoQuotient(a, gp); 1004 g = FDUtil.<C> leftBasePseudoQuotient(g, gp); 1005 if (!g.isZERO() && !g.isConstant() /*&& !B.contains(g)*/) { 1006 B.add(g); // gcd(a,g) == 1 and gcd(g,c) == 1 for c != b in P, B 1007 } 1008 g = gp; 1009 gp = leftGcd(a, gp); 1010 } 1011 // make new g co-prime to new b 1012 gp = leftGcd(b, g); 1013 while (!gp.isONE()) { 1014 b = FDUtil.<C> leftBasePseudoQuotient(b, gp); 1015 g = FDUtil.<C> leftBasePseudoQuotient(g, gp); 1016 if (!g.isZERO() && !g.isConstant() /*&& !B.contains(g)*/) { 1017 B.add(g); // gcd(a,g) == 1 and gcd(g,c) == 1 for c != b in P, B 1018 } 1019 g = gp; 1020 gp = leftGcd(b, gp); 1021 } 1022 if (!g.isZERO() && !g.isConstant() /*&& !B.contains(g)*/) { 1023 B.add(g); // gcd(a,g) == 1 and gcd(g,c) == 1 for c != b in P, B 1024 } 1025 } 1026 if (!b.isZERO() && !b.isConstant() /*&& !B.contains(b)*/) { 1027 B.add(b); // gcd(a,b) == 1 and gcd(b,c) == 1 for c != b in P, B 1028 } 1029 } 1030 if (!a.isZERO() && !a.isConstant() /*&& !B.contains(a)*/) { 1031 B.add(a); 1032 } 1033 return B; 1034 } 1035 1036 1037 /** 1038 * GenSolvablePolynomial test for co-prime list. 1039 * @param A list of GenSolvablePolynomials. 1040 * @return true if gcd(b,c) = 1 for all b != c in A, else false. 1041 */ 1042 public boolean isLeftCoPrime(List<GenSolvablePolynomial<C>> A) { 1043 if (A == null || A.isEmpty()) { 1044 return true; 1045 } 1046 if (A.size() == 1) { 1047 return true; 1048 } 1049 for (int i = 0; i < A.size(); i++) { 1050 GenSolvablePolynomial<C> a = A.get(i); 1051 for (int j = i + 1; j < A.size(); j++) { 1052 GenSolvablePolynomial<C> b = A.get(j); 1053 GenSolvablePolynomial<C> g = leftGcd(a, b); 1054 if (!g.isONE()) { 1055 System.out.println("not co-prime, a: " + a); 1056 System.out.println("not co-prime, b: " + b); 1057 System.out.println("not co-prime, g: " + g); 1058 return false; 1059 } 1060 } 1061 } 1062 return true; 1063 } 1064 1065 1066 /** 1067 * GenSolvablePolynomial test for left co-prime list of given list. 1068 * @param P list of co-prime GenSolvablePolynomials. 1069 * @param A list of GenSolvablePolynomials. 1070 * @return true if isCoPrime(P) and for all a in A exists p in P with p | a, 1071 * else false. 1072 */ 1073 public boolean isLeftCoPrime(List<GenSolvablePolynomial<C>> P, List<GenSolvablePolynomial<C>> A) { 1074 if (!isLeftCoPrime(P)) { 1075 return false; 1076 } 1077 if (A == null || A.isEmpty()) { 1078 return true; 1079 } 1080 for (GenSolvablePolynomial<C> q : A) { 1081 if (q.isZERO() || q.isConstant()) { 1082 continue; 1083 } 1084 boolean divides = false; 1085 for (GenSolvablePolynomial<C> p : P) { 1086 GenSolvablePolynomial<C> a = FDUtil.<C> leftBaseSparsePseudoRemainder(q, p); 1087 if (a.isZERO()) { // p divides q 1088 divides = true; 1089 break; 1090 } 1091 } 1092 if (!divides) { 1093 System.out.println("no divisor for: " + q); 1094 return false; 1095 } 1096 } 1097 return true; 1098 } 1099 1100 1101 /** 1102 * Univariate GenSolvablePolynomial extended greatest common divisor. Uses 1103 * sparse pseudoRemainder for remainder. 1104 * @param P univariate GenSolvablePolynomial. 1105 * @param S univariate GenSolvablePolynomial. 1106 * @return [ gcd(P,S), a, b ] with a*P + b*S = gcd(P,S). 1107 */ 1108 @SuppressWarnings("unchecked") 1109 public GenSolvablePolynomial<C>[] baseExtendedGcd(GenSolvablePolynomial<C> P, 1110 GenSolvablePolynomial<C> S) { 1111 //return P.egcd(S); 1112 GenSolvablePolynomial<C>[] hegcd = baseHalfExtendedGcd(P, S); 1113 GenSolvablePolynomial<C>[] ret = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[3]; 1114 ret[0] = hegcd[0]; 1115 ret[1] = hegcd[1]; 1116 if (ret[0].isZERO()) { 1117 ret[1] = P.ring.getZERO(); 1118 ret[2] = P.ring.getZERO(); 1119 return ret; 1120 } 1121 GenSolvablePolynomial<C> x = (GenSolvablePolynomial<C>) hegcd[0].subtract(hegcd[1].multiply(P)); 1122 GenSolvablePolynomial<C>[] qr = FDUtil.<C> leftBasePseudoQuotientRemainder(x, S); 1123 // assert qr[1].isZERO() 1124 if (!qr[1].isZERO()) { 1125 //GenSolvablePolynomial<C> y = (GenSolvablePolynomial<C>) qr[0].multiply(S).sum(qr[1]); 1126 //System.out.println("qr: " + Arrays.toString(qr)); 1127 //System.out.println("x: " + x); 1128 //System.out.println("y: " + y); 1129 throw new RuntimeException("qr[1] != 0: " + Arrays.toString(qr)); 1130 } 1131 ret[2] = qr[0]; 1132 return ret; 1133 } 1134 1135 1136 /** 1137 * Univariate GenSolvablePolynomial half extended greatest common divisor. 1138 * Uses sparse pseudoRemainder for remainder. 1139 * @param S GenSolvablePolynomial. 1140 * @return [ gcd(P,S), a ] with a*P + b*S = gcd(P,S). 1141 */ 1142 @SuppressWarnings("unchecked") 1143 public GenSolvablePolynomial<C>[] baseHalfExtendedGcd(GenSolvablePolynomial<C> P, 1144 GenSolvablePolynomial<C> S) { 1145 if (P == null || S == null) { 1146 throw new IllegalArgumentException("null P or S not allowed"); 1147 } 1148 GenSolvablePolynomial<C>[] ret = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[2]; 1149 ret[0] = null; 1150 ret[1] = null; 1151 if (S.isZERO()) { 1152 ret[0] = P; 1153 ret[1] = P.ring.getONE(); 1154 return ret; 1155 } 1156 if (P.isZERO()) { 1157 ret[0] = S; 1158 ret[1] = S.ring.getZERO(); 1159 return ret; 1160 } 1161 if (P.ring.nvar != 1) { 1162 throw new IllegalArgumentException("for univariate polynomials only " + P.ring); 1163 } 1164 GenSolvablePolynomial<C> q = P; 1165 GenSolvablePolynomial<C> r = S; 1166 GenSolvablePolynomial<C> c1 = P.ring.getONE().copy(); 1167 GenSolvablePolynomial<C> d1 = P.ring.getZERO().copy(); 1168 while (!r.isZERO()) { 1169 GenSolvablePolynomial<C>[] qr = FDUtil.<C> leftBasePseudoQuotientRemainder(q, r); 1170 //q.divideAndRemainder(r); 1171 q = qr[0]; 1172 GenSolvablePolynomial<C> x = (GenSolvablePolynomial<C>) c1.subtract(q.multiply(d1)); 1173 c1 = d1; 1174 d1 = x; 1175 q = r; 1176 r = qr[1]; 1177 } 1178 // normalize ldcf(q) to 1, i.e. make monic 1179 C g = q.leadingBaseCoefficient(); 1180 if (g.isUnit()) { 1181 C h = g.inverse(); 1182 q = q.multiply(h); 1183 c1 = c1.multiply(h); 1184 } 1185 //assert ( ((c1.multiply(P)).remainder(S).equals(q) )); 1186 ret[0] = q; 1187 ret[1] = c1; 1188 return ret; 1189 } 1190 1191 1192 /** 1193 * Univariate GenSolvablePolynomial greatest common divisor diophantine 1194 * version. 1195 * @param P univariate GenSolvablePolynomial. 1196 * @param S univariate GenSolvablePolynomial. 1197 * @param c univariate GenSolvablePolynomial. 1198 * @return [ a, b ] with a*P + b*S = c and deg(a) < deg(S). 1199 */ 1200 @SuppressWarnings("unchecked") 1201 public GenSolvablePolynomial<C>[] baseGcdDiophant(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S, 1202 GenSolvablePolynomial<C> c) { 1203 GenSolvablePolynomial<C>[] egcd = baseExtendedGcd(P, S); 1204 GenSolvablePolynomial<C> g = egcd[0]; 1205 GenSolvablePolynomial<C>[] qr = FDUtil.<C> leftBasePseudoQuotientRemainder(c, g); 1206 if (!qr[1].isZERO()) { 1207 throw new ArithmeticException("not solvable, r = " + qr[1] + ", c = " + c + ", g = " + g); 1208 } 1209 GenSolvablePolynomial<C> q = qr[0]; 1210 GenSolvablePolynomial<C> a = egcd[1].multiply(q); 1211 GenSolvablePolynomial<C> b = egcd[2].multiply(q); 1212 if (!a.isZERO() && a.degree(0) >= S.degree(0)) { 1213 qr = FDUtil.<C> leftBasePseudoQuotientRemainder(a, S); 1214 a = qr[1]; 1215 b = (GenSolvablePolynomial<C>) b.sum(P.multiply(qr[0])); 1216 } 1217 GenSolvablePolynomial<C>[] ret = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[2]; 1218 ret[0] = a; 1219 ret[1] = b; 1220 if (debug) { 1221 GenSolvablePolynomial<C> y = (GenSolvablePolynomial<C>) ret[0].multiply(P) 1222 .sum(ret[1].multiply(S)); 1223 if (!y.equals(c)) { 1224 System.out.println("P = " + P); 1225 System.out.println("S = " + S); 1226 System.out.println("c = " + c); 1227 System.out.println("a = " + a); 1228 System.out.println("b = " + b); 1229 System.out.println("y = " + y); 1230 throw new ArithmeticException("not diophant, x = " + y.subtract(c)); 1231 } 1232 } 1233 return ret; 1234 } 1235 1236 1237 /** 1238 * Coefficient left Ore condition. Generators for the left Ore condition of 1239 * two coefficients. 1240 * @param a coefficient. 1241 * @param b coefficient. 1242 * @return [oa, ob] = leftOreCond(a,b), with oa*a == ob*b. 1243 */ 1244 @SuppressWarnings("unchecked") 1245 public C[] leftOreCond(C a, C b) { 1246 if (a == null || a.isZERO() || b == null || b.isZERO()) { 1247 throw new IllegalArgumentException("a and b must be non zero"); 1248 } 1249 C[] oc = (C[]) new GcdRingElem[2]; 1250 if (a instanceof GenSolvablePolynomial && b instanceof GenSolvablePolynomial) { 1251 GenSolvablePolynomial ap = (GenSolvablePolynomial) a; 1252 GenSolvablePolynomial bp = (GenSolvablePolynomial) b; 1253 GenSolvablePolynomial[] ocp = leftOreCond(ap, bp); 1254 oc[0] = (C) ocp[0]; 1255 oc[1] = (C) ocp[1]; 1256 return oc; 1257 } 1258 RingFactory<C> rf = coFac; // not usable: (RingFactory<C>) a.factory(); 1259 if (a.equals(b)) { // required because of rationals gcd 1260 oc[0] = rf.getONE(); 1261 oc[1] = rf.getONE(); 1262 logger.info("Ore multiple ==: {}", Arrays.toString(oc)); 1263 return oc; 1264 } 1265 if (a.equals(b.negate())) { // required because of rationals gcd 1266 oc[0] = rf.getONE(); 1267 oc[1] = rf.getONE().negate(); 1268 logger.info("Ore multiple ==-: {}", Arrays.toString(oc)); 1269 return oc; 1270 } 1271 if (rf.isCommutative()) { 1272 if (debug) { 1273 logger.info("left Ore condition on coefficients, commutative case: {}, {}", a, b); 1274 } 1275 C gcd = a.gcd(b); 1276 if (gcd.isONE()) { 1277 oc[0] = b; 1278 oc[1] = a; 1279 if (oc[0].compareTo(rf.getZERO()) < 0 && oc[1].compareTo(rf.getZERO()) < 0) { 1280 oc[0] = oc[0].negate(); 1281 oc[1] = oc[1].negate(); 1282 } 1283 logger.info("Ore multiple: {}", Arrays.toString(oc)); 1284 return oc; 1285 } 1286 C p = a.multiply(b); 1287 C lcm = p.divide(gcd).abs(); 1288 oc[0] = lcm.divide(a); 1289 oc[1] = lcm.divide(b); 1290 if (oc[0].compareTo(rf.getZERO()) < 0 && oc[1].compareTo(rf.getZERO()) < 0) { 1291 oc[0] = oc[0].negate(); 1292 oc[1] = oc[1].negate(); 1293 } 1294 logger.info("Ore multiple: lcm={}, gcd={}, {}", lcm, gcd, Arrays.toString(oc)); 1295 return oc; 1296 } 1297 // now non-commutative 1298 if (rf.isField()) { 1299 logger.info("left Ore condition on coefficients, skew field {} case: {}, {}", rf, a, b); 1300 //C gcd = a.gcd(b); // always one 1301 //C lcm = rf.getONE(); 1302 oc[0] = a.inverse(); //lcm.divide(a); 1303 oc[1] = b.inverse(); //lcm.divide(b); 1304 logger.info("Ore multiple: {}", Arrays.toString(oc)); 1305 return oc; 1306 } 1307 if (b instanceof StarRingElem) { 1308 logger.info("left Ore condition on coefficients, StarRing case: {}, {}", a, b); 1309 C bs = (C) ((StarRingElem) b).conjugate(); 1310 oc[0] = bs.multiply(b); // bar(b) b a = s a 1311 oc[1] = a.multiply(bs); // a bar(b) b = t b 1312 logger.info("Ore multiple: {}", Arrays.toString(oc)); 1313 return oc; 1314 } 1315 throw new UnsupportedOperationException( 1316 "leftOreCond not implemented for " + rf.getClass() + ", rf = " + rf.toScript()); 1317 //return oc; 1318 } 1319 1320 1321 /** 1322 * Left Ore condition. Generators for the left Ore condition of two solvable 1323 * polynomials. 1324 * @param a solvable polynomial 1325 * @param b solvable polynomial 1326 * @return [p,q] with p*a = q*b 1327 */ 1328 @SuppressWarnings("unchecked") 1329 public GenSolvablePolynomial<C>[] leftOreCond(GenSolvablePolynomial<C> a, GenSolvablePolynomial<C> b) { 1330 if (a == null || a.isZERO() || b == null || b.isZERO()) { 1331 throw new IllegalArgumentException("a and b must be non zero"); 1332 } 1333 GenSolvablePolynomialRing<C> pfac = a.ring; 1334 GenSolvablePolynomial<C>[] oc = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[2]; 1335 if (a.equals(b)) { 1336 oc[0] = pfac.getONE(); 1337 oc[1] = pfac.getONE(); 1338 return oc; 1339 } 1340 if (a.equals(b.negate())) { 1341 oc[0] = pfac.getONE(); 1342 oc[1] = (GenSolvablePolynomial<C>) pfac.getONE().negate(); 1343 return oc; 1344 } 1345 if (pfac.isCommutative()) { 1346 logger.info("left Ore condition, polynomial commutative case: {}, {}", a, b); 1347 edu.jas.ufd.GreatestCommonDivisorAbstract<C> cgcd = GCDFactory.<C> getImplementation(pfac.coFac); 1348 GenSolvablePolynomial<C> lcm = (GenSolvablePolynomial<C>) cgcd.lcm(a, b); 1349 //oc[0] = FDUtil.<C> basePseudoQuotient(lcm, a); 1350 //oc[1] = FDUtil.<C> basePseudoQuotient(lcm, b); 1351 oc[0] = (GenSolvablePolynomial<C>) PolyUtil.<C> basePseudoDivide(lcm, a); 1352 oc[1] = (GenSolvablePolynomial<C>) PolyUtil.<C> basePseudoDivide(lcm, b); 1353 logger.info("Ore multiple: {}, {}", lcm, Arrays.toString(oc)); 1354 return oc; 1355 } 1356 oc = syz.leftOreCond(a, b); 1357 //logger.info("Ore multiple: {}, {}", oc[0].multiply(a), Arrays.toString(oc)); 1358 return oc; 1359 } 1360 1361 1362 /** 1363 * Coefficient right Ore condition. Generators for the right Ore condition 1364 * of two coefficients. 1365 * @param a coefficient. 1366 * @param b coefficient. 1367 * @return [oa, ob] = rightOreCond(a,b), with a*oa == b*ob. 1368 */ 1369 @SuppressWarnings("unchecked") 1370 public C[] rightOreCond(C a, C b) { 1371 if (a == null || a.isZERO() || b == null || b.isZERO()) { 1372 throw new IllegalArgumentException("a and b must be non zero"); 1373 } 1374 C[] oc = (C[]) new GcdRingElem[2]; 1375 if (a instanceof GenSolvablePolynomial && b instanceof GenSolvablePolynomial) { 1376 GenSolvablePolynomial ap = (GenSolvablePolynomial) a; 1377 GenSolvablePolynomial bp = (GenSolvablePolynomial) b; 1378 GenSolvablePolynomial[] ocp = rightOreCond(ap, bp); 1379 oc[0] = (C) ocp[0]; 1380 oc[1] = (C) ocp[1]; 1381 return oc; 1382 } 1383 RingFactory<C> rf = coFac; // not usable: (RingFactory<C>) a.factory(); 1384 if (a.equals(b)) { // required because of rationals gcd 1385 oc[0] = rf.getONE(); 1386 oc[1] = rf.getONE(); 1387 return oc; 1388 } 1389 if (a.equals(b.negate())) { // required because of rationals gcd 1390 oc[0] = rf.getONE(); 1391 oc[1] = rf.getONE().negate(); 1392 return oc; 1393 } 1394 if (rf.isCommutative()) { 1395 logger.info("right Ore condition on coefficients, commutative case: {}, {}", a, b); 1396 C gcd = a.gcd(b); 1397 if (gcd.isONE()) { 1398 oc[0] = b; 1399 oc[1] = a; 1400 if (oc[0].compareTo(rf.getZERO()) < 0 && oc[1].compareTo(rf.getZERO()) < 0) { 1401 oc[0] = oc[0].negate(); 1402 oc[1] = oc[1].negate(); 1403 } 1404 return oc; 1405 } 1406 C p = a.multiply(b); 1407 C lcm = p.divide(gcd).abs(); 1408 oc[0] = lcm.divide(a); 1409 oc[1] = lcm.divide(b); 1410 if (oc[0].compareTo(rf.getZERO()) < 0 && oc[1].compareTo(rf.getZERO()) < 0) { 1411 oc[0] = oc[0].negate(); 1412 oc[1] = oc[1].negate(); 1413 } 1414 logger.info("Ore multiple: {}, {}", lcm, Arrays.toString(oc)); 1415 return oc; 1416 } 1417 // now non-commutative 1418 if (rf.isField()) { 1419 logger.info("right Ore condition on coefficients, skew field {} case: {}, {}", rf, a, b); 1420 //C gcd = a.gcd(b); // always one 1421 //C lcm = rf.getONE(); 1422 oc[0] = a.inverse(); //lcm.divide(a); 1423 oc[1] = b.inverse(); //lcm.divide(b); 1424 logger.info("Ore multiple: {}", Arrays.toString(oc)); 1425 return oc; 1426 } 1427 if (b instanceof StarRingElem) { 1428 logger.info("right Ore condition on coefficients, StarRing case: {}, {}", a, b); 1429 C bs = (C) ((StarRingElem) b).conjugate(); 1430 oc[0] = b.multiply(bs); // a b bar(b) = a s 1431 oc[1] = bs.multiply(a); // b bar(b) a = b t 1432 logger.info("Ore multiple: {}", Arrays.toString(oc)); 1433 return oc; 1434 } 1435 throw new UnsupportedOperationException( 1436 "rightOreCond not implemented for " + rf.getClass() + ", rf = {}" + rf.toScript()); 1437 //return oc; 1438 } 1439 1440 1441 /** 1442 * Right Ore condition. Generators for the right Ore condition of two 1443 * solvable polynomials. 1444 * @param a solvable polynomial 1445 * @param b solvable polynomial 1446 * @return [p,q] with a*p = b*q 1447 */ 1448 @SuppressWarnings("unchecked") 1449 public GenSolvablePolynomial<C>[] rightOreCond(GenSolvablePolynomial<C> a, GenSolvablePolynomial<C> b) { 1450 if (a == null || a.isZERO() || b == null || b.isZERO()) { 1451 throw new IllegalArgumentException("a and b must be non zero"); 1452 } 1453 GenSolvablePolynomialRing<C> pfac = a.ring; 1454 GenSolvablePolynomial<C>[] oc = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[2]; 1455 if (a.equals(b)) { 1456 oc[0] = pfac.getONE(); 1457 oc[1] = pfac.getONE(); 1458 return oc; 1459 } 1460 if (a.equals(b.negate())) { 1461 oc[0] = pfac.getONE(); 1462 oc[1] = (GenSolvablePolynomial<C>) pfac.getONE().negate(); 1463 return oc; 1464 } 1465 if (pfac.isCommutative()) { 1466 logger.info("right Ore condition, polynomial commutative case: {}, {}", a, b); 1467 edu.jas.ufd.GreatestCommonDivisorAbstract<C> cgcd = GCDFactory.<C> getImplementation(pfac.coFac); 1468 GenSolvablePolynomial<C> lcm = (GenSolvablePolynomial<C>) cgcd.lcm(a, b); 1469 //oc[0] = FDUtil.<C> basePseudoQuotient(lcm, a); 1470 //oc[1] = FDUtil.<C> basePseudoQuotient(lcm, b); 1471 oc[0] = (GenSolvablePolynomial<C>) PolyUtil.<C> basePseudoDivide(lcm, a); 1472 oc[1] = (GenSolvablePolynomial<C>) PolyUtil.<C> basePseudoDivide(lcm, b); 1473 logger.info("Ore multiple: {}, {}", lcm, Arrays.toString(oc)); 1474 return oc; 1475 } 1476 oc = syz.rightOreCond(a, b); 1477 //logger.info("Ore multiple: {}, {}", oc[0].multiply(a), Arrays.toString(oc)); 1478 return oc; 1479 } 1480 1481 1482 /** 1483 * Is left Ore condition. Test left Ore condition of two solvable 1484 * polynomials. 1485 * @param a solvable polynomial 1486 * @param b solvable polynomial 1487 * @param p solvable polynomial 1488 * @param q solvable polynomial 1489 * @return true, if p*a = q*b, else false 1490 */ 1491 public boolean isLeftOreCond(GenSolvablePolynomial<C> a, GenSolvablePolynomial<C> b, 1492 GenSolvablePolynomial<C> p, GenSolvablePolynomial<C> q) { 1493 return syz.isLeftOreCond(a, b, p, q); 1494 } 1495 1496 1497 /** 1498 * Is right Ore condition. Test right Ore condition of two solvable 1499 * polynomials. 1500 * @param a solvable polynomial 1501 * @param b solvable polynomial 1502 * @param p solvable polynomial 1503 * @param q solvable polynomial 1504 * @return true, if a*p = b*q, else false 1505 */ 1506 public boolean isRightOreCond(GenSolvablePolynomial<C> a, GenSolvablePolynomial<C> b, 1507 GenSolvablePolynomial<C> p, GenSolvablePolynomial<C> q) { 1508 return syz.isRightOreCond(a, b, p, q); 1509 } 1510 1511 1512 /** 1513 * Left greatest common divisor and cofactors. 1514 * @param r solvable polynomial ring. 1515 * @param n first solvable polynomial. 1516 * @param d second solvable polynomial. 1517 * @return [ g=leftGcd(n,d), n/g, d/g ] 1518 */ 1519 @SuppressWarnings("unchecked") 1520 public GenSolvablePolynomial<C>[] leftGcdCofactors(GenSolvablePolynomialRing<C> r, 1521 GenSolvablePolynomial<C> n, GenSolvablePolynomial<C> d) { 1522 logger.info("leftGCD_in: {}, {}", n, d); 1523 GenSolvablePolynomial<C>[] res = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[3]; 1524 res[0] = leftGcd(n, d); 1525 //res[0] = PolyModUtil.<C> syzLeftGcd(r, n, d); 1526 res[1] = n; 1527 res[2] = d; 1528 if (res[0].isONE()) { 1529 return res; 1530 } 1531 logger.info("leftGCD_out: {}", res[0]); 1532 GenSolvablePolynomial<C>[] nqr; 1533 nqr = FDUtil.<C> rightBasePseudoQuotientRemainder(n, res[0]); 1534 if (!nqr[1].isZERO()) { 1535 res[0] = r.getONE(); 1536 return res; 1537 } 1538 GenSolvablePolynomial<C>[] dqr; 1539 dqr = FDUtil.<C> rightBasePseudoQuotientRemainder(d, res[0]); 1540 if (!dqr[1].isZERO()) { 1541 res[0] = r.getONE(); 1542 return res; 1543 } 1544 res[1] = nqr[0]; 1545 res[2] = dqr[0]; 1546 return res; 1547 } 1548 1549 1550 /** 1551 * Right greatest common divisor and cofactors. 1552 * @param r solvable polynomial ring. 1553 * @param n first solvable polynomial. 1554 * @param d second solvable polynomial. 1555 * @return [ g=rightGcd(n,d), n/g, d/g ] 1556 */ 1557 @SuppressWarnings("unchecked") 1558 public GenSolvablePolynomial<C>[] rightGcdCofactors(GenSolvablePolynomialRing<C> r, 1559 GenSolvablePolynomial<C> n, GenSolvablePolynomial<C> d) { 1560 logger.info("rightGCD_in: {}, {}", n, d); 1561 GenSolvablePolynomial<C>[] res = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[3]; 1562 res[0] = rightGcd(n, d); 1563 //res[0] = PolyModUtil.<C> syzRightGcd(r, n, d); 1564 res[1] = n; 1565 res[2] = d; 1566 if (res[0].isONE()) { 1567 return res; 1568 } 1569 logger.info("rightGCD_out: {}", res[0]); 1570 GenSolvablePolynomial<C>[] nqr; 1571 nqr = FDUtil.<C> leftBasePseudoQuotientRemainder(n, res[0]); 1572 if (!nqr[1].isZERO()) { 1573 res[0] = r.getONE(); 1574 return res; 1575 } 1576 GenSolvablePolynomial<C>[] dqr; 1577 dqr = FDUtil.<C> leftBasePseudoQuotientRemainder(d, res[0]); 1578 if (!dqr[1].isZERO()) { 1579 res[0] = r.getONE(); 1580 return res; 1581 } 1582 res[1] = nqr[0]; 1583 res[2] = dqr[0]; 1584 return res; 1585 } 1586 1587}