001/* 002 * $Id$ 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.logging.log4j.LogManager; 017import org.apache.logging.log4j.Logger; 018 019import edu.jas.kern.JASConfig; 020import edu.jas.kern.TimeStatus; 021import edu.jas.poly.ExpVector; 022import edu.jas.poly.GenPolynomial; 023import edu.jas.poly.GenPolynomialRing; 024import edu.jas.poly.OptimizedPolynomialList; 025import edu.jas.poly.PolyUtil; 026import edu.jas.poly.TermOrderByName; 027import edu.jas.poly.TermOrderOptimization; 028import edu.jas.structure.GcdRingElem; 029import edu.jas.structure.RingFactory; 030import edu.jas.util.KsubSet; 031 032 033/** 034 * Abstract factorization algorithms class. This class contains implementations 035 * of all methods of the <code>Factorization</code> interface, except the method 036 * for factorization of a squarefree polynomial. The methods to obtain 037 * squarefree polynomials delegate the computation to the 038 * <code>GreatestCommonDivisor</code> classes and are included for convenience. 039 * @param <C> coefficient type 040 * @author Heinz Kredel 041 * @see edu.jas.ufd.FactorFactory 042 */ 043 044public abstract class FactorAbstract<C extends GcdRingElem<C>> implements Factorization<C> { 045 046 047 private static final Logger logger = LogManager.getLogger(FactorAbstract.class); 048 049 050 private static final boolean debug = logger.isDebugEnabled(); 051 052 053 /** 054 * Gcd engine for base coefficients. 055 */ 056 protected final GreatestCommonDivisorAbstract<C> engine; 057 058 059 /** 060 * Squarefree decompositon engine for base coefficients. 061 */ 062 protected final SquarefreeAbstract<C> sengine; 063 064 065 /** 066 * No argument constructor. 067 */ 068 protected FactorAbstract() { 069 throw new IllegalArgumentException("don't use this constructor"); 070 } 071 072 073 /** 074 * Constructor. 075 * @param cfac coefficient ring factory. 076 */ 077 public FactorAbstract(RingFactory<C> cfac) { 078 engine = GCDFactory.<C> getProxy(cfac); 079 //engine = GCDFactory.<C> getImplementation(cfac); 080 sengine = SquarefreeFactory.<C> getImplementation(cfac); 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 * GenPolynomial test if is irreducible. 096 * @param P GenPolynomial. 097 * @return true if P is irreducible, else false. 098 */ 099 @Override 100 public boolean isIrreducible(GenPolynomial<C> P) { 101 if (!isSquarefree(P)) { 102 return false; 103 } 104 List<GenPolynomial<C>> F = factorsSquarefree(P); 105 if (F.size() == 1) { 106 return true; 107 } else if (F.size() > 2) { 108 return false; 109 } else { //F.size() == 2 110 boolean cnst = false; 111 for (GenPolynomial<C> p : F) { 112 if (p.isConstant()) { 113 cnst = true; 114 } 115 } 116 return cnst; 117 } 118 } 119 120 121 /** 122 * GenPolynomial test if a non trivial factorization exists. 123 * @param P GenPolynomial. 124 * @return true if P is reducible, else false. 125 */ 126 @Override 127 public boolean isReducible(GenPolynomial<C> P) { 128 return !isIrreducible(P); 129 } 130 131 132 /** 133 * GenPolynomial test if is squarefree. 134 * @param P GenPolynomial. 135 * @return true if P is squarefree, else false. 136 */ 137 @Override 138 public boolean isSquarefree(GenPolynomial<C> P) { 139 return sengine.isSquarefree(P); 140 } 141 142 143 /** 144 * GenPolynomial factorization of a multivariate squarefree polynomial, 145 * using Kronecker substitution and variable order optimization. 146 * @param P squarefree and primitive! (respectively monic) multivariate 147 * GenPolynomial over the ring C. 148 * @return [p_1,...,p_k] with P = prod_{i=1,...,r} p_i. 149 */ 150 public List<GenPolynomial<C>> factorsSquarefreeOptimize(GenPolynomial<C> P) { 151 GenPolynomialRing<C> pfac = P.ring; 152 if (pfac.nvar <= 1) { 153 return baseFactorsSquarefree(P); 154 } 155 List<GenPolynomial<C>> topt = new ArrayList<GenPolynomial<C>>(1); 156 topt.add(P); 157 OptimizedPolynomialList<C> opt = TermOrderOptimization.<C> optimizeTermOrder(pfac, topt); 158 P = opt.list.get(0); 159 logger.info("optimized polynomial: {}", P); 160 List<Integer> iperm = TermOrderOptimization.inversePermutation(opt.perm); 161 logger.info("optimize perm: {}, de-optimize perm: {}", opt.perm, iperm); 162 163 ExpVector degv = P.degreeVector(); 164 int[] donv = degv.dependencyOnVariables(); 165 List<GenPolynomial<C>> facs = null; 166 if (degv.length() == donv.length) { // all variables appear 167 logger.info("do.full factorsSquarefreeKronecker: {}", P); 168 facs = factorsSquarefreeKronecker(P); 169 } else { // not all variables appear, remove unused variables 170 GenPolynomial<C> pu = PolyUtil.<C> removeUnusedUpperVariables(P); 171 //GenPolynomial<C> pl = PolyUtil.<C> removeUnusedLowerVariables(pu); // not useful after optimize 172 logger.info("do.sparse factorsSquarefreeKronecker: {}", pu); 173 facs = factorsSquarefreeKronecker(pu); // pl 174 List<GenPolynomial<C>> fs = new ArrayList<GenPolynomial<C>>(facs.size()); 175 GenPolynomialRing<C> pf = P.ring; 176 //GenPolynomialRing<C> pfu = pu.ring; 177 for (GenPolynomial<C> p : facs) { 178 //GenPolynomial<C> pel = p.extendLower(pfu, 0, 0L); 179 GenPolynomial<C> pe = p.extend(pf, 0, 0L); // pel 180 fs.add(pe); 181 } 182 //System.out.println("fs = " + fs); 183 facs = fs; 184 } 185 List<GenPolynomial<C>> iopt = TermOrderOptimization.<C> permutation(iperm, pfac, facs); 186 logger.info("de-optimized polynomials: {}", iopt); 187 facs = normalizeFactorization(iopt); 188 return facs; 189 } 190 191 192 /** 193 * GenPolynomial factorization of a squarefree polynomial, using Kronecker 194 * substitution. 195 * @param P squarefree and primitive! (respectively monic) GenPolynomial. 196 * @return [p_1,...,p_k] with P = prod_{i=1,...,r} p_i. 197 */ 198 @Override 199 public List<GenPolynomial<C>> factorsSquarefree(GenPolynomial<C> P) { 200 if (P != null && P.ring.nvar > 1) { 201 logger.warn("no multivariate factorization for {}: falling back to Kronecker algorithm in {}", P, P.ring.toScript()); 202 //if (P.ring.characteristic().signum() == 0) { 203 // throw new IllegalArgumentException("P.ring.characteristic().signum() == 0"); 204 //} 205 //throw new RuntimeException("get stack trace"); 206 } 207 //if (logger.isInfoEnabled()) { 208 // logger.info(StringUtil.selectStackTrace("edu\\.jas.*")); 209 //} 210 return factorsSquarefreeKronecker(P); 211 //return factorsSquarefreeOptimize(P); // test only 212 } 213 214 215 /** 216 * GenPolynomial factorization of a squarefree polynomial, using Kronecker 217 * substitution. 218 * @param P squarefree and primitive! (respectively monic) GenPolynomial. 219 * @return [p_1,...,p_k] with P = prod_{i=1,...,r} p_i. 220 */ 221 public List<GenPolynomial<C>> factorsSquarefreeKronecker(GenPolynomial<C> P) { 222 if (P == null) { 223 throw new IllegalArgumentException(this.getClass().getName() + " P != null"); 224 } 225 GenPolynomialRing<C> pfac = P.ring; 226 if (pfac.nvar == 1) { 227 return baseFactorsSquarefree(P); 228 } 229 List<GenPolynomial<C>> factors = new ArrayList<GenPolynomial<C>>(); 230 if (P.isZERO()) { 231 return factors; 232 } 233 if (P.degreeVector().totalDeg() <= 1L) { 234 factors.add(P); 235 return factors; 236 } 237 long d = P.degree() + 1L; 238 GenPolynomial<C> kr = PolyUfdUtil.<C> substituteKronecker(P, d); 239 GenPolynomialRing<C> ufac = kr.ring; 240 ufac.setVars(ufac.newVars("zz")); // side effects 241 logger.info("deg(subs(P,d={})) = {}, original degrees: {}", d, kr.degree(0), P.degreeVector()); 242 if (debug) { 243 logger.info("subs(P,d={}) = {}", d, kr); 244 } 245 if (kr.degree(0) > 100) { 246 logger.warn("Kronecker substitution has too high degree {}", kr.degree(0)); 247 TimeStatus.checkTime("degree > 100"); 248 } 249 if (JASConfig.MAX_DEGREE_KRONECKER_FACTORIZATION > 0 250 && JASConfig.MAX_DEGREE_KRONECKER_FACTORIZATION < kr.degree(0)) { 251 throw new ArithmeticException( 252 "Kronecker substitution maximum degree (see JASConfig) exceeded: " 253 + kr.degree(0)); 254 } 255 256 // factor Kronecker polynomial 257 List<GenPolynomial<C>> ulist = new ArrayList<GenPolynomial<C>>(); 258 // kr might not be squarefree so complete factor univariate 259 SortedMap<GenPolynomial<C>, Long> slist = baseFactors(kr); 260 if (debug && !isFactorization(kr, slist)) { 261 logger.warn("kr = {}", kr); 262 logger.warn("slist = {}", slist); 263 throw new ArithmeticException("no factorization"); 264 } 265 for (Map.Entry<GenPolynomial<C>, Long> me : slist.entrySet()) { 266 GenPolynomial<C> g = me.getKey(); 267 long e = me.getValue(); // slist.get(g); 268 for (int i = 0; i < e; i++) { // is this really required? yes! 269 ulist.add(g); 270 } 271 } 272 //System.out.println("ulist = " + ulist); 273 if (ulist.size() == 1 && ulist.get(0).degree() == P.degree()) { 274 factors.add(P); 275 return factors; 276 } 277 //wrong: List<GenPolynomial<C>> klist = PolyUfdUtil.<C> backSubstituteKronecker(pfac, ulist, d); 278 //System.out.println("back(klist) = " + PolyUfdUtil.<C> backSubstituteKronecker(pfac, ulist, d)); 279 logger.info("ulist = {}", ulist); 280 // combine trial factors 281 int dl = ulist.size() - 1; //(ulist.size() + 1) / 2; 282 //System.out.println("dl = " + dl); 283 int ti = 0; 284 GenPolynomial<C> u = P; 285 long deg = (u.degree() + 1L) / 2L; // max deg 286 ExpVector evl = u.leadingExpVector(); 287 ExpVector evt = u.trailingExpVector(); 288 //System.out.println("deg = " + deg); 289 for (int j = 1; j <= dl; j++) { 290 KsubSet<GenPolynomial<C>> ps = new KsubSet<GenPolynomial<C>>(ulist, j); 291 for (List<GenPolynomial<C>> flist : ps) { 292 //System.out.println("flist = " + flist); 293 GenPolynomial<C> utrial = ufac.getONE(); 294 for (int k = 0; k < flist.size(); k++) { 295 utrial = utrial.multiply(flist.get(k)); 296 } 297 GenPolynomial<C> trial = PolyUfdUtil.<C> backSubstituteKronecker(pfac, utrial, d); 298 ti++; 299 if (ti % 2000 == 0) { 300 logger.warn("ti({})", ti); 301 TimeStatus.checkTime(ti + " % 2000 == 0"); 302 } 303 if (JASConfig.MAX_ITERATIONS_KRONECKER_FACTORIZATION > 0 304 && JASConfig.MAX_ITERATIONS_KRONECKER_FACTORIZATION < ti) { 305 throw new ArithmeticException( 306 "Kronecker substitution iteration limit (see JASConfig) exceeeded: " + ti); 307 } 308 if (!evl.multipleOf(trial.leadingExpVector())) { 309 continue; 310 } 311 if (!evt.multipleOf(trial.trailingExpVector())) { 312 continue; 313 } 314 if (trial.degree() > deg || trial.isConstant()) { 315 continue; 316 } 317 trial = trial.monic(); 318 if (ti % 15000 == 0) { 319 logger.warn("ndl = {}, deg(u) = {}", dl, deg); 320 logger.warn("ulist = {}", ulist); 321 logger.warn("kr = {}", kr); 322 logger.warn("u = {}", u); 323 logger.warn("trial = {}", trial); 324 } 325 GenPolynomial<C> rem = PolyUtil.<C> baseSparsePseudoRemainder(u, trial); 326 //System.out.println(" rem = " + rem); 327 if (rem.isZERO()) { 328 logger.info("trial = {}", trial); 329 //System.out.println("trial = " + trial); 330 factors.add(trial); 331 u = PolyUtil.<C> basePseudoDivide(u, trial); //u = u.divide( trial ); 332 evl = u.leadingExpVector(); 333 evt = u.trailingExpVector(); 334 if (u.isConstant()) { 335 j = dl + 1; 336 break; 337 } 338 //if (ulist.removeAll(flist)) { // wrong 339 ulist = removeOnce(ulist, flist); 340 //System.out.println("new ulist = " + ulist); 341 dl = (ulist.size() + 1) / 2; 342 j = 0; // since j++ 343 break; 344 } 345 } 346 } 347 if (!u.isONE() && !u.equals(P)) { 348 logger.info("rest u = {}", u); 349 factors.add(u); 350 } 351 if (factors.size() == 0) { 352 logger.info("irred P = {}", P); 353 factors.add(P); // == u 354 } 355 return normalizeFactorization(factors); 356 } 357 358 359 /** 360 * Remove one occurrence of elements. 361 * @param a list of objects. 362 * @param b list of objects. 363 * @return remove every element of b from a, but only one occurrence. 364 * <b>Note:</b> not available in java.util. 365 */ 366 static <T> List<T> removeOnce(List<T> a, List<T> b) { 367 List<T> res = new ArrayList<T>(); 368 res.addAll(a); 369 for (T e : b) { 370 @SuppressWarnings("unused") 371 boolean t = res.remove(e); 372 } 373 return res; 374 } 375 376 377 /** 378 * Univariate GenPolynomial factorization ignoring multiplicities. 379 * @param P GenPolynomial in one variable. 380 * @return [p_1, ..., p_k] with P = prod_{i=1,...,k} p_i**{e_i} for some 381 * e_i. 382 */ 383 public List<GenPolynomial<C>> baseFactorsRadical(GenPolynomial<C> P) { 384 return new ArrayList<GenPolynomial<C>>(baseFactors(P).keySet()); 385 } 386 387 388 /** 389 * Univariate GenPolynomial factorization. 390 * @param P GenPolynomial in one variable. 391 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} 392 * p_i**e_i. 393 */ 394 public SortedMap<GenPolynomial<C>, Long> baseFactors(GenPolynomial<C> P) { 395 if (P == null) { 396 throw new IllegalArgumentException(this.getClass().getName() + " P != null"); 397 } 398 GenPolynomialRing<C> pfac = P.ring; 399 SortedMap<GenPolynomial<C>, Long> factors = new TreeMap<GenPolynomial<C>, Long>(pfac.getComparator()); 400 if (P.isZERO()) { 401 return factors; 402 } 403 if (pfac.nvar > 1) { 404 throw new IllegalArgumentException(this.getClass().getName() + " only for univariate polynomials"); 405 } 406 if (P.isConstant()) { 407 factors.put(P, 1L); 408 return factors; 409 } 410 C c; 411 if (pfac.coFac.isField()) { //pfac.characteristic().signum() > 0 412 c = P.leadingBaseCoefficient(); 413 } else { 414 c = engine.baseContent(P); 415 // move sign to the content 416 if (P.signum() < 0 && c.signum() > 0) { 417 c = c.negate(); 418 //P = P.negate(); 419 } 420 } 421 if (!c.isONE()) { 422 GenPolynomial<C> pc = pfac.getONE().multiply(c); 423 factors.put(pc, 1L); 424 P = P.divide(c); // make primitive or monic 425 } 426 logger.info("base facs for P = {}", P); 427 SortedMap<GenPolynomial<C>, Long> facs = sengine.baseSquarefreeFactors(P); 428 if (facs == null || facs.size() == 0) { 429 facs = new TreeMap<GenPolynomial<C>, Long>(); 430 facs.put(P, 1L); 431 } 432 if (logger.isInfoEnabled() 433 && (facs.size() > 1 || (facs.size() == 1 && facs.get(facs.firstKey()) > 1))) { 434 logger.info("squarefree facs = {}", facs); 435 //System.out.println("sfacs = " + facs); 436 //boolean tt = isFactorization(P,facs); 437 //System.out.println("sfacs tt = " + tt); 438 } 439 for (Map.Entry<GenPolynomial<C>, Long> me : facs.entrySet()) { 440 GenPolynomial<C> g = me.getKey(); 441 Long k = me.getValue(); //facs.get(g); 442 //System.out.println("g = " + g); 443 if (pfac.coFac.isField() && !g.leadingBaseCoefficient().isONE()) { 444 g = g.monic(); // how can this happen? 445 logger.warn("squarefree facs mon = {}", g); 446 } 447 if (g.degree(0) <= 1) { 448 if (!g.isONE()) { 449 factors.put(g, k); 450 } 451 } else { 452 List<GenPolynomial<C>> sfacs = baseFactorsSquarefree(g); 453 if (debug) { 454 logger.info("factors of squarefree = {}", sfacs); 455 } 456 for (GenPolynomial<C> h : sfacs) { 457 Long j = factors.get(h); // evtl. constants 458 if (j != null) { 459 k += j; 460 } 461 if (!h.isONE()) { 462 factors.put(h, k); 463 } 464 } 465 } 466 } 467 //System.out.println("factors = " + factors); 468 return factors; 469 } 470 471 472 /** 473 * Univariate GenPolynomial factorization of a squarefree polynomial. 474 * @param P squarefree and primitive! GenPolynomial in one variable. 475 * @return [p_1, ..., p_k] with P = prod_{i=1,...,k} p_i. 476 */ 477 public abstract List<GenPolynomial<C>> baseFactorsSquarefree(GenPolynomial<C> P); 478 479 480 /** 481 * GenPolynomial factorization ignoring multiplicities. 482 * @param P GenPolynomial. 483 * @return [p_1, ..., p_k] with P = prod_{i=1,...,k} p_i**{e_i} for some 484 * e_i. 485 */ 486 @Override 487 public List<GenPolynomial<C>> factorsRadical(GenPolynomial<C> P) { 488 return new ArrayList<GenPolynomial<C>>(factors(P).keySet()); 489 } 490 491 492 /** 493 * GenPolynomial list factorization ignoring multiplicities. 494 * @param L list of GenPolynomials. 495 * @return [p_1, ..., p_k] with p = prod_{i=1,...,k} p_i**{e_i} for some e_i 496 * for all p in L. 497 */ 498 public List<GenPolynomial<C>> factorsRadical(List<GenPolynomial<C>> L) { 499 SortedSet<GenPolynomial<C>> facs = new TreeSet<GenPolynomial<C>>(); 500 for (GenPolynomial<C> p : L) { 501 List<GenPolynomial<C>> fs = factorsRadical(p); 502 facs.addAll(fs); 503 } 504 return new ArrayList<GenPolynomial<C>>(facs); 505 } 506 507 508 /** 509 * GenPolynomial factorization. 510 * @param P GenPolynomial. 511 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} 512 * p_i**e_i. 513 */ 514 @Override 515 public SortedMap<GenPolynomial<C>, Long> factors(GenPolynomial<C> P) { 516 if (P == null) { 517 throw new IllegalArgumentException(this.getClass().getName() + " P != null"); 518 } 519 GenPolynomialRing<C> pfac = P.ring; 520 if (pfac.nvar == 1) { 521 return baseFactors(P); 522 } 523 SortedMap<GenPolynomial<C>, Long> factors = new TreeMap<GenPolynomial<C>, Long>(pfac.getComparator()); 524 if (P.isZERO()) { 525 return factors; 526 } 527 if (P.isConstant()) { 528 factors.put(P, 1L); 529 return factors; 530 } 531 if (!pfac.tord.equals(TermOrderByName.INVLEX)) { 532 logger.warn("wrong term order {}, factorization may not be correct, better use {}", pfac.tord, TermOrderByName.INVLEX); 533 } 534 C c; 535 if (pfac.coFac.isField()) { 536 c = P.leadingBaseCoefficient(); 537 } else { 538 c = engine.baseContent(P); 539 // move sign to the content 540 if (P.signum() < 0 && c.signum() > 0) { 541 c = c.negate(); 542 //P = P.negate(); 543 } 544 } 545 if (!c.isONE()) { 546 GenPolynomial<C> pc = pfac.getONE().multiply(c); 547 factors.put(pc, 1L); 548 P = P.divide(c); // make base primitive or base monic 549 } 550 logger.info("base primitive part P = {}", P); 551 GenPolynomial<C>[] cpp = engine.contentPrimitivePart(P); 552 GenPolynomial<C> pc = cpp[0]; 553 if (!pc.isONE()) { 554 SortedMap<GenPolynomial<C>, Long> rec = factors(pc); // recursion 555 for (Map.Entry<GenPolynomial<C>, Long> me : rec.entrySet()) { 556 GenPolynomial<C> g = me.getKey(); 557 Long d = me.getValue(); 558 GenPolynomial<C> pn = g.extend(pfac,0,0L); 559 factors.put(pn,d); 560 } 561 logger.info("content factors = {}", factors); 562 } 563 P = cpp[1]; 564 logger.info("primitive part P = {}", P); 565 if (P.isONE()) { 566 return factors; 567 } 568 SortedMap<GenPolynomial<C>, Long> facs = sengine.squarefreeFactors(P); 569 if (facs == null || facs.size() == 0) { 570 facs = new TreeMap<GenPolynomial<C>, Long>(); 571 facs.put(P, 1L); 572 throw new RuntimeException("this should not happen, facs is empty: " + facs); 573 } 574 if (logger.isInfoEnabled()) { 575 if (facs.size() > 1) { 576 logger.info("squarefree mfacs = {}", facs); 577 } else if (facs.size() == 1 && facs.get(facs.firstKey()) > 1L) { 578 logger.info("squarefree #mfacs 1-n = {}", facs); 579 } else { 580 logger.info("squarefree #mfacs 1-1 = {}", facs); 581 } 582 } 583 for (Map.Entry<GenPolynomial<C>, Long> me : facs.entrySet()) { 584 GenPolynomial<C> g = me.getKey(); 585 if (g.isONE()) { // skip 1 586 continue; 587 } 588 Long d = me.getValue(); // facs.get(g); 589 List<GenPolynomial<C>> sfacs = factorsSquarefree(g); 590 logger.info("factors of squarefree ^{} = {}", d, sfacs); 591 for (GenPolynomial<C> h : sfacs) { 592 long dd = d; 593 Long j = factors.get(h); // evtl. constants 594 if (j != null) { 595 dd += j; 596 } 597 factors.put(h, dd); 598 } 599 } 600 //System.out.println("factors = " + factors); 601 return factors; 602 } 603 604 605 /** 606 * GenPolynomial greatest squarefree divisor. Delegates computation to a 607 * GreatestCommonDivisor class. 608 * @param P GenPolynomial. 609 * @return squarefree(P). 610 */ 611 @Override 612 public GenPolynomial<C> squarefreePart(GenPolynomial<C> P) { 613 return sengine.squarefreePart(P); 614 } 615 616 617 /** 618 * GenPolynomial primitive part. Delegates computation to a 619 * GreatestCommonDivisor class. 620 * @param P GenPolynomial. 621 * @return primitivePart(P). 622 */ 623 public GenPolynomial<C> primitivePart(GenPolynomial<C> P) { 624 return engine.primitivePart(P); 625 } 626 627 628 /** 629 * GenPolynomial base primitive part. Delegates computation to a 630 * GreatestCommonDivisor class. 631 * @param P GenPolynomial. 632 * @return basePrimitivePart(P). 633 */ 634 public GenPolynomial<C> basePrimitivePart(GenPolynomial<C> P) { 635 return engine.basePrimitivePart(P); 636 } 637 638 639 /** 640 * GenPolynomial squarefree factorization. Delegates computation to a 641 * GreatestCommonDivisor class. 642 * @param P GenPolynomial. 643 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} 644 * p_i**e_i. 645 */ 646 @Override 647 public SortedMap<GenPolynomial<C>, Long> squarefreeFactors(GenPolynomial<C> P) { 648 return sengine.squarefreeFactors(P); 649 } 650 651 652 /** 653 * GenPolynomial is factorization. 654 * @param P GenPolynomial. 655 * @param F = [p_1,...,p_k]. 656 * @return true if P = prod_{i=1,...,r} p_i, else false. 657 */ 658 @Override 659 public boolean isFactorization(GenPolynomial<C> P, List<GenPolynomial<C>> F) { 660 return sengine.isFactorization(P, F); 661 // test irreducible 662 } 663 664 665 /** 666 * GenPolynomial is factorization. 667 * @param P GenPolynomial. 668 * @param F = [p_1 -> e_1, ..., p_k -> e_k]. 669 * @return true if P = prod_{i=1,...,k} p_i**e_i , else false. 670 */ 671 @Override 672 public boolean isFactorization(GenPolynomial<C> P, SortedMap<GenPolynomial<C>, Long> F) { 673 return sengine.isFactorization(P, F); 674 // test irreducible 675 } 676 677 678 /** 679 * Degree of a factorization. 680 * @param F a factors map [p_1 -> e_1, ..., p_k -> e_k]. 681 * @return sum_{i=1,...,k} degree(p_i)*e_i. 682 */ 683 public long factorsDegree(SortedMap<GenPolynomial<C>, Long> F) { 684 long d = 0; 685 for (Map.Entry<GenPolynomial<C>, Long> me : F.entrySet()) { 686 GenPolynomial<C> p = me.getKey(); 687 long e = me.getValue(); //F.get(p); 688 d += p.degree() * e; 689 } 690 return d; 691 } 692 693 694 /** 695 * GenPolynomial is factorization. 696 * @param P GenPolynomial. 697 * @param F = [p_1 -> e_1, ..., p_k -> e_k]. 698 * @return true if P = prod_{i=1,...,k} p_i**e_i , else false. 699 */ 700 public boolean isRecursiveFactorization(GenPolynomial<GenPolynomial<C>> P, 701 SortedMap<GenPolynomial<GenPolynomial<C>>, Long> F) { 702 return sengine.isRecursiveFactorization(P, F); 703 // test irreducible 704 } 705 706 707 /** 708 * Recursive GenPolynomial factorization of a squarefree polynomial. 709 * @param P squarefree recursive GenPolynomial. 710 * @return [p_1,...,p_k] with P = prod_{i=1, ..., k} p_i. 711 */ 712 public List<GenPolynomial<GenPolynomial<C>>> recursiveFactorsSquarefree(GenPolynomial<GenPolynomial<C>> P) { 713 if (P == null) { 714 throw new IllegalArgumentException(this.getClass().getName() + " P == null"); 715 } 716 List<GenPolynomial<GenPolynomial<C>>> factors = new ArrayList<GenPolynomial<GenPolynomial<C>>>(); 717 if (P.isZERO()) { 718 return factors; 719 } 720 if (P.isONE()) { 721 factors.add(P); 722 return factors; 723 } 724 GenPolynomialRing<GenPolynomial<C>> pfac = P.ring; 725 GenPolynomialRing<C> qi = (GenPolynomialRing<C>) pfac.coFac; 726 GenPolynomialRing<C> ifac = qi.extend(pfac.getVars()); 727 GenPolynomial<C> Pi = PolyUtil.<C> distribute(ifac, P); 728 //System.out.println("Pi = " + Pi); 729 730 C ldcf = Pi.leadingBaseCoefficient(); 731 if (!ldcf.isONE() && ldcf.isUnit()) { 732 //System.out.println("ldcf = " + ldcf); 733 Pi = Pi.monic(); 734 } 735 736 // factor in C[x_1,...,x_n,y_1,...,y_m] 737 List<GenPolynomial<C>> ifacts = factorsSquarefree(Pi); 738 logger.info("ifacts = {}", ifacts); 739 if (ifacts.size() <= 1) { 740 factors.add(P); 741 return factors; 742 } 743 if (!ldcf.isONE() && ldcf.isUnit()) { 744 GenPolynomial<C> r = ifacts.get(0); 745 ifacts.remove(r); 746 r = r.multiply(ldcf); 747 ifacts.add(0, r); 748 } 749 List<GenPolynomial<GenPolynomial<C>>> rfacts = PolyUtil.<C> recursive(pfac, ifacts); 750 //System.out.println("rfacts = " + rfacts); 751 if (logger.isDebugEnabled()) { 752 logger.info("recfacts = {}", rfacts); 753 } 754 factors.addAll(rfacts); 755 return factors; 756 } 757 758 759 /** 760 * Recursive GenPolynomial factorization. 761 * @param P recursive GenPolynomial. 762 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} 763 * p_i**e_i. 764 */ 765 public SortedMap<GenPolynomial<GenPolynomial<C>>, Long> recursiveFactors(GenPolynomial<GenPolynomial<C>> P) { 766 if (P == null) { 767 throw new IllegalArgumentException(this.getClass().getName() + " P != null"); 768 } 769 GenPolynomialRing<GenPolynomial<C>> pfac = P.ring; 770 SortedMap<GenPolynomial<GenPolynomial<C>>, Long> factors = new TreeMap<GenPolynomial<GenPolynomial<C>>, Long>( 771 pfac.getComparator()); 772 if (P.isZERO()) { 773 return factors; 774 } 775 if (P.isONE()) { 776 factors.put(P, 1L); 777 return factors; 778 } 779 GenPolynomialRing<C> qi = (GenPolynomialRing<C>) pfac.coFac; 780 GenPolynomialRing<C> ifac = qi.extend(pfac.getVars()); 781 GenPolynomial<C> Pi = PolyUtil.<C> distribute(ifac, P); 782 //System.out.println("Pi = " + Pi); 783 784 C ldcf = Pi.leadingBaseCoefficient(); 785 if (!ldcf.isONE() && ldcf.isUnit()) { 786 //System.out.println("ldcf = " + ldcf); 787 Pi = Pi.monic(); 788 } 789 790 // factor in C[x_1,...,x_n,y_1,...,y_m] 791 SortedMap<GenPolynomial<C>, Long> dfacts = factors(Pi); 792 logger.info("dfacts = {}", dfacts); 793 if (!ldcf.isONE() && ldcf.isUnit()) { 794 GenPolynomial<C> r = dfacts.firstKey(); 795 Long E = dfacts.remove(r); 796 r = r.multiply(ldcf); 797 dfacts.put(r, E); 798 } 799 for (Map.Entry<GenPolynomial<C>, Long> me : dfacts.entrySet()) { 800 GenPolynomial<C> f = me.getKey(); 801 Long E = me.getValue(); //dfacts.get(f); 802 GenPolynomial<GenPolynomial<C>> rp = PolyUtil.<C> recursive(pfac, f); 803 factors.put(rp, E); 804 } 805 //System.out.println("rfacts = " + rfacts); 806 logger.info("recursive factors = {}", factors); 807 return factors; 808 } 809 810 811 /** 812 * Normalize factorization. p'_i > 0 for i > 1 and p'_1 != 1 if k > 813 * 1. 814 * @param F = [p_1,...,p_k]. 815 * @return F' = [p'_1,...,p'_k]. 816 */ 817 public List<GenPolynomial<C>> normalizeFactorization(List<GenPolynomial<C>> F) { 818 if (F == null || F.size() <= 1) { 819 return F; 820 } 821 List<GenPolynomial<C>> Fp = new ArrayList<GenPolynomial<C>>(F.size()); 822 GenPolynomial<C> f0 = F.get(0); 823 for (int i = 1; i < F.size(); i++) { 824 GenPolynomial<C> fi = F.get(i); 825 if (fi.signum() < 0) { 826 fi = fi.negate(); 827 f0 = f0.negate(); 828 } 829 if (!fi.isONE()) { 830 Fp.add(fi); 831 } 832 } 833 if (!f0.isONE()) { 834 Fp.add(0, f0); 835 } 836 return Fp; 837 } 838}