001 /* 002 * $Id: FactorAbstract.java 3727 2011-08-07 18:00:09Z kredel $ 003 */ 004 005 package edu.jas.ufd; 006 007 008 import java.util.ArrayList; 009 import java.util.List; 010 import java.util.SortedMap; 011 import java.util.SortedSet; 012 import java.util.TreeMap; 013 import java.util.TreeSet; 014 015 import org.apache.log4j.Logger; 016 017 import edu.jas.kern.TimeStatus; 018 import edu.jas.poly.GenPolynomial; 019 import edu.jas.poly.GenPolynomialRing; 020 import edu.jas.poly.PolyUtil; 021 import edu.jas.poly.ExpVector; 022 import edu.jas.structure.GcdRingElem; 023 import edu.jas.structure.RingFactory; 024 import edu.jas.util.KsubSet; 025 026 027 /** 028 * Abstract factorization algorithms class. This class contains implementations 029 * of all methods of the <code>Factorization</code> interface, except the method 030 * for factorization of a squarefree polynomial. The methods to obtain 031 * squarefree polynomials delegate the computation to the 032 * <code>GreatestCommonDivisor</code> classes and are included for convenience. 033 * @param <C> coefficient type 034 * @author Heinz Kredel 035 * @see edu.jas.ufd.FactorFactory 036 */ 037 038 public abstract class FactorAbstract<C extends GcdRingElem<C>> implements Factorization<C> { 039 040 041 private static final Logger logger = Logger.getLogger(FactorAbstract.class); 042 043 044 private final boolean debug = logger.isDebugEnabled(); 045 046 047 /** 048 * Gcd engine for base coefficients. 049 */ 050 protected final GreatestCommonDivisorAbstract<C> engine; 051 052 053 /** 054 * Squarefree decompositon engine for base coefficients. 055 */ 056 protected final SquarefreeAbstract<C> sengine; 057 058 059 /** 060 * No argument constructor. 061 */ 062 protected FactorAbstract() { 063 throw new IllegalArgumentException("don't use this constructor"); 064 } 065 066 067 /** 068 * Constructor. 069 * @param cfac coefficient ring factory. 070 */ 071 public FactorAbstract(RingFactory<C> cfac) { 072 engine = GCDFactory.<C> getProxy(cfac); 073 //engine = GCDFactory.<C> getImplementation(cfac); 074 sengine = SquarefreeFactory.<C> getImplementation(cfac); 075 } 076 077 078 /** 079 * Get the String representation. 080 * @see java.lang.Object#toString() 081 */ 082 @Override 083 public String toString() { 084 return getClass().getName(); 085 } 086 087 088 /** 089 * GenPolynomial test if is irreducible. 090 * @param P GenPolynomial. 091 * @return true if P is irreducible, else false. 092 */ 093 public boolean isIrreducible(GenPolynomial<C> P) { 094 if (!isSquarefree(P)) { 095 return false; 096 } 097 List<GenPolynomial<C>> F = factorsSquarefree(P); 098 if (F.size() == 1) { 099 return true; 100 } else if (F.size() > 2) { 101 return false; 102 } else { //F.size() == 2 103 boolean cnst = false; 104 for (GenPolynomial<C> p : F) { 105 if (p.isConstant()) { 106 cnst = true; 107 } 108 } 109 return cnst; 110 } 111 } 112 113 114 /** 115 * GenPolynomial test if a non trivial factorization exsists. 116 * @param P GenPolynomial. 117 * @return true if P is reducible, else false. 118 */ 119 public boolean isReducible(GenPolynomial<C> P) { 120 return !isIrreducible(P); 121 } 122 123 124 /** 125 * GenPolynomial test if is squarefree. 126 * @param P GenPolynomial. 127 * @return true if P is squarefree, else false. 128 */ 129 public boolean isSquarefree(GenPolynomial<C> P) { 130 return sengine.isSquarefree(P); 131 } 132 133 134 /** 135 * GenPolynomial factorization of a squarefree polynomial, using Kronecker substitution. 136 * @param P squarefree and primitive! (respectively monic) GenPolynomial. 137 * @return [p_1,...,p_k] with P = prod_{i=1,...,r} p_i. 138 */ 139 public List<GenPolynomial<C>> factorsSquarefree(GenPolynomial<C> P) { 140 if (P == null) { 141 throw new IllegalArgumentException(this.getClass().getName() + " P != null"); 142 } 143 GenPolynomialRing<C> pfac = P.ring; 144 if (pfac.nvar == 1) { 145 return baseFactorsSquarefree(P); 146 } 147 List<GenPolynomial<C>> factors = new ArrayList<GenPolynomial<C>>(); 148 if (P.isZERO()) { 149 return factors; 150 } 151 if (P.degreeVector().totalDeg() <= 1L) { 152 factors.add(P); 153 return factors; 154 } 155 long d = P.degree() + 1L; 156 GenPolynomial<C> kr = PolyUfdUtil.<C> substituteKronecker(P, d); 157 GenPolynomialRing<C> ufac = kr.ring; 158 ufac.setVars(ufac.newVars("zz")); // side effects 159 logger.info("deg(subs(P,d=" + d + ")) = " + kr.degree(0) + ", original degrees: " + P.degreeVector()); 160 if (debug) { 161 logger.info("subs(P,d=" + d + ") = " + kr); 162 //System.out.println("subs(P,d=" + d + ") = " + kr); 163 } 164 if (kr.degree(0) > 100) { 165 logger.warn("Kronecker substitution has to high degree"); 166 TimeStatus.checkTime("degree > 100"); 167 } 168 169 // factor Kronecker polynomial 170 List<GenPolynomial<C>> ulist = new ArrayList<GenPolynomial<C>>(); 171 // kr might not be squarefree so complete factor univariate 172 SortedMap<GenPolynomial<C>, Long> slist = baseFactors(kr); 173 if (debug && !isFactorization(kr, slist)) { 174 System.out.println("kr = " + kr); 175 System.out.println("slist = " + slist); 176 throw new ArithmeticException("no factorization"); 177 } 178 for (GenPolynomial<C> g : slist.keySet()) { 179 long e = slist.get(g); 180 for (int i = 0; i < e; i++) { // is this really required? yes! 181 ulist.add(g); 182 } 183 } 184 //System.out.println("ulist = " + ulist); 185 if (ulist.size() == 1 && ulist.get(0).degree() == P.degree()) { 186 factors.add(P); 187 return factors; 188 } 189 //wrong: List<GenPolynomial<C>> klist = PolyUfdUtil.<C> backSubstituteKronecker(pfac, ulist, d); 190 //System.out.println("back(klist) = " + PolyUfdUtil.<C> backSubstituteKronecker(pfac, ulist, d)); 191 if (logger.isInfoEnabled()) { 192 logger.info("ulist = " + ulist); 193 //System.out.println("ulist = " + ulist); 194 } 195 // combine trial factors 196 int dl = ulist.size() - 1; //(ulist.size() + 1) / 2; 197 //System.out.println("dl = " + dl); 198 int ti = 0; 199 GenPolynomial<C> u = P; 200 long deg = (u.degree() + 1L) / 2L; // max deg 201 ExpVector evl = u.leadingExpVector(); 202 ExpVector evt = u.trailingExpVector(); 203 //System.out.println("deg = " + deg); 204 for (int j = 1; j <= dl; j++) { 205 KsubSet<GenPolynomial<C>> ps = new KsubSet<GenPolynomial<C>>(ulist, j); 206 for (List<GenPolynomial<C>> flist : ps) { 207 //System.out.println("flist = " + flist); 208 GenPolynomial<C> utrial = ufac.getONE(); 209 for (int k = 0; k < flist.size(); k++) { 210 utrial = utrial.multiply(flist.get(k)); 211 } 212 GenPolynomial<C> trial = PolyUfdUtil.<C> backSubstituteKronecker(pfac, utrial, d); 213 ti++; 214 if (ti % 2000 == 0) { 215 System.out.print("ti(" + ti + ") "); 216 TimeStatus.checkTime(ti + " % 2000 == 0"); 217 } 218 if ( !evl.multipleOf(trial.leadingExpVector()) ) { 219 continue; 220 } 221 if ( !evt.multipleOf(trial.trailingExpVector()) ) { 222 continue; 223 } 224 if (trial.degree() > deg || trial.isConstant()) { 225 continue; 226 } 227 trial = trial.monic(); 228 if (ti % 15000 == 0) { 229 System.out.println("\ndl = " + dl + ", deg(u) = " + deg); 230 System.out.println("ulist = " + ulist); 231 System.out.println("kr = " + kr); 232 System.out.println("u = " + u); 233 System.out.println("trial = " + trial); 234 } 235 GenPolynomial<C> rem = PolyUtil.<C> basePseudoRemainder(u, trial); 236 //System.out.println(" rem = " + rem); 237 if (rem.isZERO()) { 238 logger.info("trial = " + trial); 239 //System.out.println("trial = " + trial); 240 factors.add(trial); 241 u = PolyUtil.<C> basePseudoDivide(u, trial); //u = u.divide( trial ); 242 evl = u.leadingExpVector(); 243 evt = u.trailingExpVector(); 244 if (u.isConstant()) { 245 j = dl + 1; 246 break; 247 } 248 //if (ulist.removeAll(flist)) { 249 ulist = removeOnce(ulist, flist); 250 if (ulist != null) { 251 //System.out.println("new ulist = " + ulist); 252 dl = (ulist.size() + 1) / 2; 253 j = 0; // since j++ 254 break; 255 //} else { 256 // logger.error("error removing flist from ulist = " + ulist); 257 } 258 } 259 } 260 } 261 if (!u.isONE() && !u.equals(P)) { 262 logger.info("rest u = " + u); 263 //System.out.println("rest u = " + u); 264 factors.add(u); 265 } 266 if (factors.size() == 0) { 267 logger.info("irred u = " + u); 268 //System.out.println("irred u = " + u); 269 factors.add(P); 270 } 271 return factors; 272 } 273 274 275 /** 276 * Remove one occurence of elements. 277 * @param a list of objects. 278 * @param b list of objects. 279 * @return remove every element of b from a, but only one occurence. 280 */ 281 static <T> List<T> removeOnce(List<T> a, List<T> b) { 282 List<T> res = new ArrayList<T>(); 283 res.addAll(a); 284 for (T e : b) { 285 boolean t = res.remove(e); 286 } 287 return res; 288 } 289 290 291 /** 292 * Univariate GenPolynomial factorization ignoring multiplicities. 293 * @param P GenPolynomial in one variable. 294 * @return [p_1, ..., p_k] with P = prod_{i=1,...,k} p_i**{e_i} for some 295 * e_i. 296 */ 297 public List<GenPolynomial<C>> baseFactorsRadical(GenPolynomial<C> P) { 298 return new ArrayList<GenPolynomial<C>>(baseFactors(P).keySet()); 299 } 300 301 302 /** 303 * Univariate GenPolynomial factorization. 304 * @param P GenPolynomial in one variable. 305 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} 306 * p_i**e_i. 307 */ 308 public SortedMap<GenPolynomial<C>, Long> baseFactors(GenPolynomial<C> P) { 309 if (P == null) { 310 throw new IllegalArgumentException(this.getClass().getName() + " P != null"); 311 } 312 GenPolynomialRing<C> pfac = P.ring; 313 SortedMap<GenPolynomial<C>, Long> factors = new TreeMap<GenPolynomial<C>, Long>(pfac.getComparator()); 314 if (P.isZERO()) { 315 return factors; 316 } 317 if (pfac.nvar > 1) { 318 throw new IllegalArgumentException(this.getClass().getName() + " only for univariate polynomials"); 319 } 320 if (P.isConstant()) { 321 factors.put(P, 1L); 322 return factors; 323 } 324 C c; 325 if (pfac.coFac.isField()) { //pfac.characteristic().signum() > 0 326 c = P.leadingBaseCoefficient(); 327 } else { 328 c = engine.baseContent(P); 329 // move sign to the content 330 if (P.signum() < 0 && c.signum() > 0) { 331 c = c.negate(); 332 //P = P.negate(); 333 } 334 } 335 if (!c.isONE()) { 336 GenPolynomial<C> pc = pfac.getONE().multiply(c); 337 factors.put(pc, 1L); 338 P = P.divide(c); // make primitive or monic 339 } 340 if (logger.isInfoEnabled()) { 341 logger.info("base facs for P = " + P); 342 } 343 SortedMap<GenPolynomial<C>, Long> facs = sengine.baseSquarefreeFactors(P); 344 if (facs == null || facs.size() == 0) { 345 facs = new TreeMap<GenPolynomial<C>, Long>(); 346 facs.put(P, 1L); 347 } 348 if (logger.isInfoEnabled() 349 && (facs.size() > 1 || (facs.size() == 1 && facs.get(facs.firstKey()) > 1))) { 350 logger.info("squarefree facs = " + facs); 351 //System.out.println("sfacs = " + facs); 352 //boolean tt = isFactorization(P,facs); 353 //System.out.println("sfacs tt = " + tt); 354 } 355 for (GenPolynomial<C> g : facs.keySet()) { 356 Long k = facs.get(g); 357 //System.out.println("g = " + g); 358 if (pfac.coFac.isField() && !g.leadingBaseCoefficient().isONE()) { 359 g = g.monic(); // how can this happen? 360 logger.warn("squarefree facs mon = " + g); 361 } 362 if (g.degree(0) <= 1) { 363 if (!g.isONE()) { 364 factors.put(g, k); 365 } 366 } else { 367 List<GenPolynomial<C>> sfacs = baseFactorsSquarefree(g); 368 if (debug) { 369 logger.info("factors of squarefree = " + sfacs); 370 //System.out.println("sfacs = " + sfacs); 371 } 372 for (GenPolynomial<C> h : sfacs) { 373 Long j = factors.get(h); // evtl. constants 374 if (j != null) { 375 k += j; 376 } 377 if (!h.isONE()) { 378 factors.put(h, k); 379 } 380 } 381 } 382 } 383 //System.out.println("factors = " + factors); 384 return factors; 385 } 386 387 388 /** 389 * Univariate GenPolynomial factorization of a squarefree polynomial. 390 * @param P squarefree and primitive! GenPolynomial in one variable. 391 * @return [p_1, ..., p_k] with P = prod_{i=1,...,k} p_i. 392 */ 393 public abstract List<GenPolynomial<C>> baseFactorsSquarefree(GenPolynomial<C> P); 394 395 396 /** 397 * GenPolynomial factorization ignoring multiplicities. 398 * @param P GenPolynomial. 399 * @return [p_1, ..., p_k] with P = prod_{i=1,...,k} p_i**{e_i} for some 400 * e_i. 401 */ 402 public List<GenPolynomial<C>> factorsRadical(GenPolynomial<C> P) { 403 return new ArrayList<GenPolynomial<C>>(factors(P).keySet()); 404 } 405 406 407 /** 408 * GenPolynomial list factorization ignoring multiplicities. 409 * @param L list of GenPolynomials. 410 * @return [p_1, ..., p_k] with p = prod_{i=1,...,k} p_i**{e_i} for some e_i 411 * for all p in L. 412 */ 413 public List<GenPolynomial<C>> factorsRadical(List<GenPolynomial<C>> L) { 414 SortedSet<GenPolynomial<C>> facs = new TreeSet<GenPolynomial<C>>(); 415 for (GenPolynomial<C> p : L) { 416 List<GenPolynomial<C>> fs = factorsRadical(p); 417 facs.addAll(fs); 418 } 419 return new ArrayList<GenPolynomial<C>>(facs); 420 } 421 422 423 /** 424 * GenPolynomial factorization. 425 * @param P GenPolynomial. 426 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} 427 * p_i**e_i. 428 */ 429 public SortedMap<GenPolynomial<C>, Long> factors(GenPolynomial<C> P) { 430 if (P == null) { 431 throw new IllegalArgumentException(this.getClass().getName() + " P != null"); 432 } 433 GenPolynomialRing<C> pfac = P.ring; 434 if (pfac.nvar == 1) { 435 return baseFactors(P); 436 } 437 SortedMap<GenPolynomial<C>, Long> factors = new TreeMap<GenPolynomial<C>, Long>(pfac.getComparator()); 438 if (P.isZERO()) { 439 return factors; 440 } 441 if (P.isConstant()) { 442 factors.put(P, 1L); 443 return factors; 444 } 445 C c; 446 if (pfac.coFac.isField()) { // pfac.characteristic().signum() > 0 447 c = P.leadingBaseCoefficient(); 448 } else { 449 c = engine.baseContent(P); 450 // move sign to the content 451 if (P.signum() < 0 && c.signum() > 0) { 452 c = c.negate(); 453 //P = P.negate(); 454 } 455 } 456 if (!c.isONE()) { 457 GenPolynomial<C> pc = pfac.getONE().multiply(c); 458 factors.put(pc, 1L); 459 P = P.divide(c); // make base primitive or base monic 460 } 461 if (logger.isInfoEnabled()) { 462 logger.info("squarefree mfacs P = " + P); 463 } 464 SortedMap<GenPolynomial<C>, Long> facs = sengine.squarefreeFactors(P); 465 if (facs == null || facs.size() == 0) { 466 facs = new TreeMap<GenPolynomial<C>, Long>(); 467 facs.put(P, 1L); 468 throw new RuntimeException("this should not happen, facs is empty: " + facs); 469 } 470 if (logger.isInfoEnabled()) { 471 if (facs.size() > 1) { 472 logger.info("squarefree mfacs = " + facs); 473 } else if (facs.size() == 1 && facs.get(facs.firstKey()) > 1L) { 474 logger.info("squarefree #mfacs 1-n = " + facs); 475 } else { 476 logger.info("squarefree #mfacs 1-1 = " + facs); 477 } 478 } 479 for (GenPolynomial<C> g : facs.keySet()) { 480 if ( g.isONE() ) { // skip 1 481 continue; 482 } 483 Long d = facs.get(g); 484 List<GenPolynomial<C>> sfacs = factorsSquarefree(g); 485 if (logger.isInfoEnabled()) { 486 logger.info("factors of squarefree ^" + d + " = " + sfacs); 487 //System.out.println("sfacs = " + sfacs); 488 } 489 for (GenPolynomial<C> h : sfacs) { 490 long dd = d; 491 Long j = factors.get(h); // evtl. constants 492 if (j != null) { 493 dd += j; 494 } 495 factors.put(h, dd); 496 } 497 } 498 //System.out.println("factors = " + factors); 499 return factors; 500 } 501 502 503 /** 504 * GenPolynomial greatest squarefree divisor. Delegates computation to a 505 * GreatestCommonDivisor class. 506 * @param P GenPolynomial. 507 * @return squarefree(P). 508 */ 509 public GenPolynomial<C> squarefreePart(GenPolynomial<C> P) { 510 return sengine.squarefreePart(P); 511 } 512 513 514 /** 515 * GenPolynomial primitive part. Delegates computation to a 516 * GreatestCommonDivisor class. 517 * @param P GenPolynomial. 518 * @return primitivePart(P). 519 */ 520 public GenPolynomial<C> primitivePart(GenPolynomial<C> P) { 521 return engine.primitivePart(P); 522 } 523 524 525 /** 526 * GenPolynomial base primitive part. Delegates computation to a 527 * GreatestCommonDivisor class. 528 * @param P GenPolynomial. 529 * @return basePrimitivePart(P). 530 */ 531 public GenPolynomial<C> basePrimitivePart(GenPolynomial<C> P) { 532 return engine.basePrimitivePart(P); 533 } 534 535 536 /** 537 * GenPolynomial squarefree factorization. Delegates computation to a 538 * GreatestCommonDivisor class. 539 * @param P GenPolynomial. 540 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} 541 * p_i**e_i. 542 */ 543 public SortedMap<GenPolynomial<C>, Long> squarefreeFactors(GenPolynomial<C> P) { 544 return sengine.squarefreeFactors(P); 545 } 546 547 548 /** 549 * GenPolynomial is factorization. 550 * @param P GenPolynomial. 551 * @param F = [p_1,...,p_k]. 552 * @return true if P = prod_{i=1,...,r} p_i, else false. 553 */ 554 public boolean isFactorization(GenPolynomial<C> P, List<GenPolynomial<C>> F) { 555 return sengine.isFactorization(P, F); 556 // test irreducible 557 } 558 559 560 /** 561 * GenPolynomial is factorization. 562 * @param P GenPolynomial. 563 * @param F = [p_1 -> e_1, ..., p_k -> e_k]. 564 * @return true if P = prod_{i=1,...,k} p_i**e_i , else false. 565 */ 566 public boolean isFactorization(GenPolynomial<C> P, SortedMap<GenPolynomial<C>, Long> F) { 567 return sengine.isFactorization(P, F); 568 // test irreducible 569 } 570 571 572 /** 573 * Degree of a factorization. 574 * @param F a factors map [p_1 -> e_1, ..., p_k -> e_k]. 575 * @return sum_{i=1,...,k} degree(p_i)*e_i. 576 */ 577 public long factorsDegree(SortedMap<GenPolynomial<C>,Long> F) { 578 long d = 0; 579 for ( GenPolynomial<C> p : F.keySet() ) { 580 long e = F.get(p); 581 d += p.degree() * e; 582 } 583 return d; 584 } 585 586 587 /** 588 * GenPolynomial is factorization. 589 * @param P GenPolynomial. 590 * @param F = [p_1 -> e_1, ..., p_k -> e_k]. 591 * @return true if P = prod_{i=1,...,k} p_i**e_i , else false. 592 */ 593 public boolean isRecursiveFactorization(GenPolynomial<GenPolynomial<C>> P, 594 SortedMap<GenPolynomial<GenPolynomial<C>>, Long> F) { 595 return sengine.isRecursiveFactorization(P, F); 596 // test irreducible 597 } 598 599 600 /** 601 * Recursive GenPolynomial factorization of a squarefree polynomial. 602 * @param P squarefree recursive GenPolynomial. 603 * @return [p_1,...,p_k] with P = prod_{i=1, ..., k} p_i. 604 */ 605 public List<GenPolynomial<GenPolynomial<C>>> recursiveFactorsSquarefree(GenPolynomial<GenPolynomial<C>> P) { 606 if (P == null) { 607 throw new IllegalArgumentException(this.getClass().getName() + " P == null"); 608 } 609 List<GenPolynomial<GenPolynomial<C>>> factors = new ArrayList<GenPolynomial<GenPolynomial<C>>>(); 610 if (P.isZERO()) { 611 return factors; 612 } 613 if (P.isONE()) { 614 factors.add(P); 615 return factors; 616 } 617 GenPolynomialRing<GenPolynomial<C>> pfac = P.ring; 618 GenPolynomialRing<C> qi = (GenPolynomialRing<C>) pfac.coFac; 619 GenPolynomialRing<C> ifac = qi.extend(pfac.getVars()); 620 GenPolynomial<C> Pi = PolyUtil.<C> distribute(ifac, P); 621 //System.out.println("Pi = " + Pi); 622 623 C ldcf = Pi.leadingBaseCoefficient(); 624 if (!ldcf.isONE() && ldcf.isUnit()) { 625 //System.out.println("ldcf = " + ldcf); 626 Pi = Pi.monic(); 627 } 628 629 // factor in C[x_1,...,x_n,y_1,...,y_m] 630 List<GenPolynomial<C>> ifacts = factorsSquarefree(Pi); 631 if (logger.isInfoEnabled()) { 632 logger.info("ifacts = " + ifacts); 633 } 634 if (ifacts.size() <= 1) { 635 factors.add(P); 636 return factors; 637 } 638 if (!ldcf.isONE() && ldcf.isUnit()) { 639 GenPolynomial<C> r = ifacts.get(0); 640 ifacts.remove(r); 641 r = r.multiply(ldcf); 642 ifacts.add(0, r); 643 } 644 List<GenPolynomial<GenPolynomial<C>>> rfacts = PolyUtil.<C> recursive(pfac, ifacts); 645 //System.out.println("rfacts = " + rfacts); 646 if (logger.isDebugEnabled()) { 647 logger.info("recfacts = " + rfacts); 648 } 649 factors.addAll(rfacts); 650 return factors; 651 } 652 653 654 /** 655 * Recursive GenPolynomial factorization. 656 * @param P recursive GenPolynomial. 657 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} 658 * p_i**e_i. 659 */ 660 public SortedMap<GenPolynomial<GenPolynomial<C>>, Long> recursiveFactors(GenPolynomial<GenPolynomial<C>> P) { 661 if (P == null) { 662 throw new IllegalArgumentException(this.getClass().getName() + " P != null"); 663 } 664 GenPolynomialRing<GenPolynomial<C>> pfac = P.ring; 665 SortedMap<GenPolynomial<GenPolynomial<C>>, Long> factors = new TreeMap<GenPolynomial<GenPolynomial<C>>, Long>( 666 pfac.getComparator()); 667 if (P.isZERO()) { 668 return factors; 669 } 670 if (P.isONE()) { 671 factors.put(P, 1L); 672 return factors; 673 } 674 GenPolynomialRing<C> qi = (GenPolynomialRing<C>) pfac.coFac; 675 GenPolynomialRing<C> ifac = qi.extend(pfac.getVars()); 676 GenPolynomial<C> Pi = PolyUtil.<C> distribute(ifac, P); 677 //System.out.println("Pi = " + Pi); 678 679 C ldcf = Pi.leadingBaseCoefficient(); 680 if (!ldcf.isONE() && ldcf.isUnit()) { 681 //System.out.println("ldcf = " + ldcf); 682 Pi = Pi.monic(); 683 } 684 685 // factor in C[x_1,...,x_n,y_1,...,y_m] 686 SortedMap<GenPolynomial<C>, Long> dfacts = factors(Pi); 687 if (logger.isInfoEnabled()) { 688 logger.info("dfacts = " + dfacts); 689 } 690 if (!ldcf.isONE() && ldcf.isUnit()) { 691 GenPolynomial<C> r = dfacts.firstKey(); 692 Long E = dfacts.remove(r); 693 r = r.multiply(ldcf); 694 dfacts.put(r, E); 695 } 696 for (GenPolynomial<C> f : dfacts.keySet()) { 697 Long E = dfacts.get(f); 698 GenPolynomial<GenPolynomial<C>> rp = PolyUtil.<C> recursive(pfac, f); 699 factors.put(rp, E); 700 } 701 //System.out.println("rfacts = " + rfacts); 702 if (logger.isInfoEnabled()) { 703 logger.info("recursive factors = " + factors); 704 } 705 return factors; 706 } 707 708 }