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