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