001/* 002 * $Id$ 003 */ 004 005package edu.jas.ufd; 006 007 008import java.util.Map; 009import java.util.SortedMap; 010import java.util.TreeMap; 011 012import org.apache.logging.log4j.LogManager; 013import org.apache.logging.log4j.Logger; 014 015import edu.jas.poly.ExpVector; 016import edu.jas.poly.GenPolynomial; 017import edu.jas.poly.GenPolynomialRing; 018import edu.jas.poly.PolyUtil; 019import edu.jas.structure.GcdRingElem; 020import edu.jas.structure.RingFactory; 021 022 023/** 024 * Squarefree decomposition for coefficient fields of characteristic 0. 025 * @author Heinz Kredel 026 */ 027 028public class SquarefreeFieldChar0<C extends GcdRingElem<C>> extends SquarefreeAbstract<C> { 029 030 031 private static final Logger logger = LogManager.getLogger(SquarefreeFieldChar0.class); 032 033 034 private static final boolean debug = logger.isDebugEnabled(); 035 036 037 /** 038 * Factory for field of characteristic 0 coefficients. 039 */ 040 protected final RingFactory<C> coFac; 041 042 043 /** 044 * Constructor. 045 */ 046 public SquarefreeFieldChar0(RingFactory<C> fac) { 047 super(GCDFactory.<C> getProxy(fac)); 048 if (!fac.isField()) { 049 throw new IllegalArgumentException("fac must be a field"); 050 } 051 if (fac.characteristic().signum() != 0) { 052 throw new IllegalArgumentException("characteristic(fac) must be zero"); 053 } 054 coFac = fac; 055 } 056 057 058 /** 059 * Get the String representation. 060 * @see java.lang.Object#toString() 061 */ 062 @Override 063 public String toString() { 064 return getClass().getName() + " with " + engine + " over " + coFac; 065 } 066 067 068 /** 069 * GenPolynomial polynomial greatest squarefree divisor. 070 * @param P GenPolynomial. 071 * @return squarefree(P). 072 */ 073 @Override 074 public GenPolynomial<C> baseSquarefreePart(GenPolynomial<C> P) { 075 if (P == null || P.isZERO()) { 076 return P; 077 } 078 GenPolynomialRing<C> pfac = P.ring; 079 if (pfac.nvar > 1) { 080 throw new IllegalArgumentException( 081 this.getClass().getName() + " only for univariate polynomials"); 082 } 083 GenPolynomial<C> pp = P.monic(); 084 if (pp.isConstant()) { 085 return pp; 086 } 087 GenPolynomial<C> d = PolyUtil.<C> baseDerivative(pp); 088 d = d.monic(); 089 //System.out.println("d = " + d); 090 GenPolynomial<C> g = engine.baseGcd(pp, d); 091 g = g.monic(); 092 GenPolynomial<C> q = PolyUtil.<C> basePseudoDivide(pp, g); 093 q = q.monic(); 094 return q; 095 } 096 097 098 /** 099 * GenPolynomial test if is squarefree. 100 * @param P GenPolynomial. 101 * @return true if P is squarefree, else false. 102 */ 103 public boolean isBaseSquarefree(GenPolynomial<C> P) { 104 if (P == null || P.isZERO()) { 105 return true; 106 } 107 GenPolynomialRing<C> pfac = P.ring; 108 if (pfac.nvar > 1) { 109 throw new IllegalArgumentException( 110 this.getClass().getName() + " only for univariate polynomials"); 111 } 112 GenPolynomial<C> pp = P.monic(); 113 if (pp.isConstant()) { 114 return true; 115 } 116 GenPolynomial<C> d = PolyUtil.<C> baseDerivative(pp); 117 d = d.monic(); 118 //System.out.println("d = " + d); 119 GenPolynomial<C> g = engine.baseGcd(pp, d); 120 //g = g.monic(); 121 //System.out.println("baseGcd: g = " + g); 122 if (g.isONE()) { 123 return true; 124 } 125 if (g.degree() >= 1) { // 1 here okay 126 return false; 127 } 128 //return g.isONE(); 129 return true; 130 } 131 132 133 /** 134 * GenPolynomial polynomial squarefree factorization. 135 * @param A GenPolynomial. 136 * @return [p_1 -> e_1, ..., p_k -> e_k] with A = prod_{i=1,...,k} 137 * p_i^{e_i} and p_i squarefree and gcd(p_i, p_j) = 1, for i != j. 138 */ 139 @Override 140 public SortedMap<GenPolynomial<C>, Long> baseSquarefreeFactors(GenPolynomial<C> A) { 141 SortedMap<GenPolynomial<C>, Long> sfactors = new TreeMap<GenPolynomial<C>, Long>(); 142 if (A == null || A.isZERO()) { 143 return sfactors; 144 } 145 if (A.isConstant()) { 146 sfactors.put(A, 1L); 147 return sfactors; 148 } 149 GenPolynomialRing<C> pfac = A.ring; 150 if (pfac.nvar > 1) { 151 throw new IllegalArgumentException( 152 this.getClass().getName() + " only for univariate polynomials"); 153 } 154 C ldbcf = A.leadingBaseCoefficient(); 155 if (!ldbcf.isONE()) { 156 A = A.divide(ldbcf); 157 GenPolynomial<C> f1 = pfac.getONE().multiply(ldbcf); 158 //System.out.println("gcda sqf f1 = " + f1); 159 sfactors.put(f1, 1L); 160 ldbcf = pfac.coFac.getONE(); 161 } 162 // divide by trailing term 163 ExpVector et = A.trailingExpVector(); 164 if (!et.isZERO()) { 165 GenPolynomial<C> tr = pfac.valueOf(et); 166 logger.info("trailing term = {}", tr); 167 A = PolyUtil.<C> basePseudoDivide(A, tr); 168 long ep = et.getVal(0); // univariate 169 et = et.subst(0, 1); 170 tr = pfac.valueOf(et); 171 logger.info("tr, ep = {}, {}", tr, ep); 172 sfactors.put(tr, ep); 173 if (A.length() == 1) { 174 return sfactors; 175 } 176 } 177 GenPolynomial<C> T0 = A; 178 GenPolynomial<C> Tp; 179 GenPolynomial<C> T = null; 180 GenPolynomial<C> V = null; 181 long k = 0L; 182 boolean init = true; 183 while (true) { 184 if (init) { 185 if (T0.isConstant() || T0.isZERO()) { 186 break; 187 } 188 Tp = PolyUtil.<C> baseDerivative(T0); 189 T = engine.baseGcd(T0, Tp); 190 T = T.monic(); 191 V = PolyUtil.<C> basePseudoDivide(T0, T); 192 //System.out.println("iT0 = " + T0); 193 //System.out.println("iTp = " + Tp); 194 //System.out.println("iT = " + T); 195 //System.out.println("iV = " + V); 196 k = 0L; 197 init = false; 198 } 199 if (V.isConstant()) { 200 break; 201 } 202 k++; 203 GenPolynomial<C> W = engine.baseGcd(T, V); 204 W = W.monic(); 205 GenPolynomial<C> z = PolyUtil.<C> basePseudoDivide(V, W); 206 //System.out.println("W = " + W); 207 //System.out.println("z = " + z); 208 V = W; 209 T = PolyUtil.<C> basePseudoDivide(T, V); 210 //System.out.println("V = " + V); 211 //System.out.println("T = " + T); 212 if (z.degree(0) > 0) { 213 if (ldbcf.isONE() && !z.leadingBaseCoefficient().isONE()) { 214 z = z.monic(); 215 //logger.info("z,monic = {}", z); 216 } 217 logger.info("z, k = {}, {}", z, k); 218 sfactors.put(z, k); 219 } 220 } 221 return normalizeFactorization(sfactors); 222 } 223 224 225 /** 226 * GenPolynomial recursive univariate polynomial greatest squarefree 227 * divisor. 228 * @param P recursive univariate GenPolynomial. 229 * @return squarefree(P). 230 */ 231 @Override 232 public GenPolynomial<GenPolynomial<C>> recursiveUnivariateSquarefreePart( 233 GenPolynomial<GenPolynomial<C>> P) { 234 if (P == null || P.isZERO()) { 235 return P; 236 } 237 GenPolynomialRing<GenPolynomial<C>> pfac = P.ring; 238 if (pfac.nvar > 1) { 239 throw new IllegalArgumentException( 240 this.getClass().getName() + " only for univariate recursive polynomials"); 241 } 242 // remove content 243 GenPolynomial<GenPolynomial<C>> pp = P; 244 GenPolynomial<C> Pc = engine.recursiveContent(P); 245 //?? Pc = Pc.monic(); 246 if (!Pc.isONE()) { 247 pp = PolyUtil.<C> coefficientPseudoDivide(pp, Pc); 248 //System.out.println("P/cont = " + pp + ", cont = " + Pc); 249 } 250 // squarefree content 251 GenPolynomial<C> Ps = squarefreePart(Pc); 252 //System.out.println("Pc = " + Pc + ", Ps = " + Ps); 253 if (pp.leadingExpVector().getVal(0) < 1) { 254 //System.out.println("pp = " + pp); 255 //System.out.println("Ps = " + Ps); 256 pp = pp.multiply(Ps); 257 pp = PolyUtil.<C> monic(pp); 258 return pp; 259 } 260 GenPolynomial<GenPolynomial<C>> d = PolyUtil.<C> recursiveDerivative(pp); 261 //System.out.println("d = " + d); 262 GenPolynomial<GenPolynomial<C>> g = engine.recursiveUnivariateGcd(pp, d); 263 //System.out.println("g,rec = " + g); 264 //??g = PolyUtil.<C> monic(g); 265 GenPolynomial<GenPolynomial<C>> q = PolyUtil.<C> recursivePseudoDivide(pp, g); 266 q = q.multiply(Ps); 267 q = PolyUtil.<C> monic(q); 268 return q; 269 } 270 271 272 /** 273 * GenPolynomial test if is squarefree. 274 * @param P GenPolynomial. 275 * @return true if P is squarefree, else false. 276 */ 277 public boolean isRecursiveUnivariateSquarefree(GenPolynomial<GenPolynomial<C>> P) { 278 if (P == null || P.isZERO()) { 279 return true; 280 } 281 if (P.isConstant() || (P.degree(0) == 1 && P.length() == 1)) { 282 return isSquarefree(P.leadingBaseCoefficient()); 283 } 284 GenPolynomialRing<GenPolynomial<C>> pfac = P.ring; 285 if (pfac.nvar > 1) { 286 throw new IllegalArgumentException( 287 this.getClass().getName() + " only for univariate recursive polynomials"); 288 } 289 GenPolynomial<GenPolynomial<C>> pp = P; 290 GenPolynomial<GenPolynomial<C>> d = PolyUtil.<C> recursiveDerivative(pp); 291 //System.out.println("d = " + d); 292 if (d.isZERO()) { 293 return false; 294 } 295 GenPolynomial<GenPolynomial<C>> g = engine.recursiveUnivariateGcd(pp, d); 296 //logger.info("gcd = {} :: {}, pp={}, d={}", g, g.ring.toScript(), pp, d); 297 //System.out.println("g,rec = " + g); 298 if (g.isONE()) { 299 return true; 300 } 301 if (g.degree() >= 1) { // 1 here okay 302 return false; 303 } 304 GenPolynomial<C> lcg = g.leadingBaseCoefficient(); 305 logger.info("lcg = {}, degree {}, g = {}", lcg, lcg.degree(), g); 306 if (isSquarefree(lcg)) { 307 return true; 308 } 309 return false; 310 } 311 312 313 /** 314 * GenPolynomial recursive univariate polynomial squarefree factorization. 315 * @param P recursive univariate GenPolynomial. 316 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} 317 * p_i^{e_i} and p_i squarefree and gcd(p_i, p_j) = 1, for i != j. 318 */ 319 @Override 320 public SortedMap<GenPolynomial<GenPolynomial<C>>, Long> recursiveUnivariateSquarefreeFactors( 321 GenPolynomial<GenPolynomial<C>> P) { 322 SortedMap<GenPolynomial<GenPolynomial<C>>, Long> sfactors = new TreeMap<GenPolynomial<GenPolynomial<C>>, Long>(); 323 if (P == null || P.isZERO()) { 324 return sfactors; 325 } 326 GenPolynomialRing<GenPolynomial<C>> pfac = P.ring; 327 if (pfac.nvar > 1) { 328 // recursiveContent not possible by return type 329 throw new IllegalArgumentException( 330 this.getClass().getName() + " only for univariate polynomials"); 331 } 332 // if base coefficient ring is a field, make monic 333 GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) pfac.coFac; 334 C ldbcf = P.leadingBaseCoefficient().leadingBaseCoefficient(); 335 if (!ldbcf.isONE()) { 336 GenPolynomial<C> lc = cfac.getONE().multiply(ldbcf); 337 GenPolynomial<GenPolynomial<C>> pl = pfac.getONE().multiply(lc); 338 sfactors.put(pl, 1L); 339 C li = ldbcf.inverse(); 340 //System.out.println("li = " + li); 341 P = P.multiply(cfac.getONE().multiply(li)); 342 //System.out.println("P,monic = " + P); 343 ldbcf = P.leadingBaseCoefficient().leadingBaseCoefficient(); 344 } 345 // factors of content 346 GenPolynomial<C> Pc = engine.recursiveContent(P); 347 logger.info("recursiveContent = {}", Pc); 348 Pc = Pc.monic(); 349 if (!Pc.isONE()) { 350 P = PolyUtil.<C> coefficientPseudoDivide(P, Pc); 351 } 352 SortedMap<GenPolynomial<C>, Long> rsf = squarefreeFactors(Pc); 353 logger.info("squarefreeFactors = {}", rsf); 354 // add factors of content 355 for (Map.Entry<GenPolynomial<C>, Long> me : rsf.entrySet()) { 356 GenPolynomial<C> c = me.getKey(); 357 if (!c.isONE()) { 358 GenPolynomial<GenPolynomial<C>> cr = pfac.getONE().multiply(c); 359 Long rk = me.getValue(); // rsf.get(c); 360 sfactors.put(cr, rk); 361 } 362 } 363 // divide by trailing term 364 ExpVector et = P.trailingExpVector(); 365 if (!et.isZERO()) { 366 GenPolynomial<GenPolynomial<C>> tr = pfac.valueOf(et); 367 logger.info("trailing term = {}", tr); 368 P = PolyUtil.<C> recursivePseudoDivide(P, tr); 369 long ep = et.getVal(0); // univariate 370 et = et.subst(0, 1); 371 tr = pfac.valueOf(et); 372 sfactors.put(tr, ep); 373 } 374 375 // factors of recursive polynomial 376 GenPolynomial<GenPolynomial<C>> T0 = P; 377 GenPolynomial<GenPolynomial<C>> Tp; 378 GenPolynomial<GenPolynomial<C>> T = null; 379 GenPolynomial<GenPolynomial<C>> V = null; 380 long k = 0L; 381 boolean init = true; 382 while (true) { 383 if (init) { 384 if (T0.isConstant() || T0.isZERO()) { 385 break; 386 } 387 Tp = PolyUtil.<C> recursiveDerivative(T0); 388 T = engine.recursiveUnivariateGcd(T0, Tp); 389 T = PolyUtil.<C> monic(T); 390 V = PolyUtil.<C> recursivePseudoDivide(T0, T); 391 //System.out.println("iT0 = " + T0); 392 //System.out.println("iTp = " + Tp); 393 //System.out.println("iT = " + T); 394 //System.out.println("iV = " + V); 395 k = 0L; 396 init = false; 397 } 398 if (V.isConstant()) { 399 break; 400 } 401 k++; 402 GenPolynomial<GenPolynomial<C>> W = engine.recursiveUnivariateGcd(T, V); 403 W = PolyUtil.<C> monic(W); 404 GenPolynomial<GenPolynomial<C>> z = PolyUtil.<C> recursivePseudoDivide(V, W); 405 //System.out.println("W = " + W); 406 //System.out.println("z = " + z); 407 V = W; 408 T = PolyUtil.<C> recursivePseudoDivide(T, V); 409 //System.out.println("V = " + V); 410 //System.out.println("T = " + T); 411 //was: if ( z.degree(0) > 0 ) { 412 if (!z.isONE() && !z.isZERO()) { 413 if (ldbcf.isONE()) { 414 z = PolyUtil.<C> monic(z); 415 logger.info("z,monic = {}", z); 416 } 417 sfactors.put(z, k); 418 } 419 } 420 return sfactors; 421 } 422 423 424 /** 425 * GenPolynomial greatest squarefree divisor. 426 * @param P GenPolynomial. 427 * @return squarefree(pp(P)). 428 */ 429 @Override 430 public GenPolynomial<C> squarefreePart(GenPolynomial<C> P) { 431 if (P == null) { 432 throw new IllegalArgumentException(this.getClass().getName() + " P != null"); 433 } 434 if (P.isZERO()) { 435 return P; 436 } 437 GenPolynomialRing<C> pfac = P.ring; 438 if (pfac.nvar <= 1) { 439 return baseSquarefreePart(P); 440 } 441 GenPolynomialRing<GenPolynomial<C>> rfac = pfac.recursive(1); 442 GenPolynomial<GenPolynomial<C>> Pr = PolyUtil.<C> recursive(rfac, P); 443 GenPolynomial<C> Pc = engine.recursiveContent(Pr); 444 Pr = PolyUtil.<C> coefficientPseudoDivide(Pr, Pc); 445 GenPolynomial<C> Ps = squarefreePart(Pc); 446 logger.info("content = {}, squarefreePart = {}", Pc, Ps); 447 GenPolynomial<GenPolynomial<C>> PP = recursiveUnivariateSquarefreePart(Pr); 448 GenPolynomial<GenPolynomial<C>> PS = PP.multiply(Ps); 449 GenPolynomial<C> D = PolyUtil.<C> distribute(pfac, PS); 450 logger.info("univRec = {}, squarefreePart = {}", Pr, PP); 451 return D; 452 } 453 454 455 /** 456 * GenPolynomial test if is squarefree. 457 * @param P GenPolynomial. 458 * @return true if P is squarefree, else false. 459 */ 460 @Override 461 public boolean isSquarefree(GenPolynomial<C> P) { 462 if (P == null) { 463 throw new IllegalArgumentException(this.getClass().getName() + " P != null"); 464 } 465 if (P.isZERO()) { 466 return true; 467 } 468 GenPolynomialRing<C> pfac = P.ring; 469 if (pfac.nvar <= 1) { 470 return isBaseSquarefree(P); 471 } 472 GenPolynomialRing<GenPolynomial<C>> rfac = pfac.recursive(1); 473 GenPolynomial<GenPolynomial<C>> Pr = PolyUtil.<C> recursive(rfac, P); 474 boolean s1 = isRecursiveUnivariateSquarefree(Pr); 475 if (debug) { 476 boolean s2 = super.isSquarefree(P); 477 if (s1 != s2) { 478 logger.info("s_rec != s2_sup: {}", P); 479 throw new RuntimeException("s_rec != s2_sup: " + s1 + ", " + s2); 480 } 481 } 482 return s1; 483 } 484 485 486 /** 487 * GenPolynomial squarefree factorization. 488 * @param P GenPolynomial. 489 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} 490 * p_i^{e_i} and p_i squarefree and gcd(p_i, p_j) = 1, for i != j. 491 */ 492 @Override 493 public SortedMap<GenPolynomial<C>, Long> squarefreeFactors(GenPolynomial<C> P) { 494 if (P == null) { 495 throw new IllegalArgumentException(this.getClass().getName() + " P != null"); 496 } 497 GenPolynomialRing<C> pfac = P.ring; 498 if (pfac.nvar <= 1) { 499 return normalizeFactorization(baseSquarefreeFactors(P)); 500 } 501 SortedMap<GenPolynomial<C>, Long> sfactors = new TreeMap<GenPolynomial<C>, Long>(); 502 if (P.isZERO()) { 503 return normalizeFactorization(sfactors); 504 } 505 if (P.isONE()) { 506 sfactors.put(P, 1L); 507 return normalizeFactorization(sfactors); 508 } 509 GenPolynomialRing<GenPolynomial<C>> rfac = pfac.recursive(1); 510 GenPolynomial<GenPolynomial<C>> Pr = PolyUtil.<C> recursive(rfac, P); 511 SortedMap<GenPolynomial<GenPolynomial<C>>, Long> PP = recursiveUnivariateSquarefreeFactors(Pr); 512 513 for (Map.Entry<GenPolynomial<GenPolynomial<C>>, Long> m : PP.entrySet()) { 514 Long i = m.getValue(); 515 GenPolynomial<GenPolynomial<C>> Dr = m.getKey(); 516 GenPolynomial<C> D = PolyUtil.<C> distribute(pfac, Dr); 517 sfactors.put(D, i); 518 } 519 logger.info("squarefreeFactors({}) = {}", P, sfactors); 520 return normalizeFactorization(sfactors); 521 } 522 523 524 /** 525 * Coefficients squarefree factorization. 526 * @param P coefficient. 527 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} 528 * p_i^{e_i} and p_i squarefree and gcd(p_i, p_j) = 1, for i != j. 529 */ 530 @Override 531 public SortedMap<C, Long> squarefreeFactors(C P) { 532 throw new UnsupportedOperationException("method not implemented"); 533 } 534 535}