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 rings of characteristic 0. 025 * @author Heinz Kredel 026 */ 027 028public class SquarefreeRingChar0<C extends GcdRingElem<C>> 029 extends SquarefreeAbstract<C> /*implements Squarefree<C>*/ { 030 031 032 private static final Logger logger = LogManager.getLogger(SquarefreeRingChar0.class); 033 034 035 private static final boolean debug = logger.isDebugEnabled(); 036 037 038 /** 039 * Factory for ring of characteristic 0 coefficients. 040 */ 041 protected final RingFactory<C> coFac; 042 043 044 /** 045 * Constructor. 046 */ 047 public SquarefreeRingChar0(RingFactory<C> fac) { 048 super(GCDFactory.<C> getProxy(fac)); 049 if (fac.isField()) { 050 throw new IllegalArgumentException("fac is a field: use SquarefreeFieldChar0"); 051 } 052 if (fac.characteristic().signum() != 0) { 053 throw new IllegalArgumentException("characteristic(fac) must be zero"); 054 } 055 coFac = fac; 056 } 057 058 059 /** 060 * Get the String representation. 061 * @see java.lang.Object#toString() 062 */ 063 @Override 064 public String toString() { 065 return getClass().getName() + " with " + engine + " over " + coFac; 066 } 067 068 069 /** 070 * GenPolynomial polynomial greatest squarefree divisor. 071 * @param P GenPolynomial. 072 * @return squarefree(pp(P)). 073 */ 074 @Override 075 public GenPolynomial<C> baseSquarefreePart(GenPolynomial<C> P) { 076 if (P == null || P.isZERO()) { 077 return P; 078 } 079 GenPolynomialRing<C> pfac = P.ring; 080 if (pfac.nvar > 1) { 081 throw new IllegalArgumentException( 082 this.getClass().getName() + " only for univariate polynomials"); 083 } 084 GenPolynomial<C> pp = engine.basePrimitivePart(P); 085 if (pp.isConstant()) { 086 return pp; 087 } 088 GenPolynomial<C> d = PolyUtil.<C> baseDerivative(pp); 089 d = engine.basePrimitivePart(d); 090 GenPolynomial<C> g = engine.baseGcd(pp, d); 091 g = engine.basePrimitivePart(g); 092 GenPolynomial<C> q = PolyUtil.<C> basePseudoDivide(pp, g); 093 q = engine.basePrimitivePart(q); 094 return q; 095 } 096 097 098 /** 099 * GenPolynomial polynomial squarefree factorization. 100 * @param A GenPolynomial. 101 * @return [p_1 -> e_1, ..., p_k -> e_k] with A = prod_{i=1,...,k} 102 * p_i^{e_i} and p_i squarefree and gcd(p_i, p_j) = 1, for i != j. 103 */ 104 @Override 105 public SortedMap<GenPolynomial<C>, Long> baseSquarefreeFactors(GenPolynomial<C> A) { 106 SortedMap<GenPolynomial<C>, Long> sfactors = new TreeMap<GenPolynomial<C>, Long>(); 107 if (A == null || A.isZERO()) { 108 return sfactors; 109 } 110 if (A.isConstant()) { 111 sfactors.put(A, 1L); 112 return sfactors; 113 } 114 GenPolynomialRing<C> pfac = A.ring; 115 if (pfac.nvar > 1) { 116 throw new IllegalArgumentException( 117 this.getClass().getName() + " only for univariate polynomials"); 118 } 119 C ldbcf = A.leadingBaseCoefficient(); 120 if (!ldbcf.isONE()) { 121 C cc = engine.baseContent(A); 122 A = A.divide(cc); 123 GenPolynomial<C> f1 = pfac.getONE().multiply(cc); 124 //System.out.println("gcda sqf f1 = " + f1); 125 sfactors.put(f1, 1L); 126 } 127 // divide by trailing term 128 ExpVector et = A.trailingExpVector(); 129 if (!et.isZERO()) { 130 GenPolynomial<C> tr = pfac.valueOf(et); 131 logger.info("trailing term = {}", tr); 132 A = PolyUtil.<C> basePseudoDivide(A, tr); 133 long ep = et.getVal(0); // univariate 134 et = et.subst(0, 1); 135 tr = pfac.valueOf(et); 136 logger.info("tr, ep = {}, {}", tr, ep); 137 sfactors.put(tr, ep); 138 if (A.length() == 1) { 139 return sfactors; 140 } 141 } 142 GenPolynomial<C> T0 = A; 143 GenPolynomial<C> Tp; 144 GenPolynomial<C> T = null; 145 GenPolynomial<C> V = null; 146 long k = 0L; 147 boolean init = true; 148 while (true) { 149 if (init) { 150 if (T0.isConstant() || T0.isZERO()) { 151 break; 152 } 153 Tp = PolyUtil.<C> baseDerivative(T0); 154 T = engine.baseGcd(T0, Tp); 155 T = engine.basePrimitivePart(T); 156 V = PolyUtil.<C> basePseudoDivide(T0, T); 157 //System.out.println("iT0 = " + T0); 158 //System.out.println("iTp = " + Tp); 159 //System.out.println("iT = " + T); 160 //System.out.println("iV = " + V); 161 k = 0L; 162 init = false; 163 } 164 if (V.isConstant()) { 165 break; 166 } 167 k++; 168 GenPolynomial<C> W = engine.baseGcd(T, V); 169 W = engine.basePrimitivePart(W); 170 GenPolynomial<C> z = PolyUtil.<C> basePseudoDivide(V, W); 171 //System.out.println("W = " + W); 172 //System.out.println("z = " + z); 173 V = W; 174 T = PolyUtil.<C> basePseudoDivide(T, V); 175 //System.out.println("V = " + V); 176 //System.out.println("T = " + T); 177 if (z.degree(0) > 0) { 178 if (ldbcf.isONE() && !z.leadingBaseCoefficient().isONE()) { 179 z = engine.basePrimitivePart(z); 180 //logger.info("z,pp = {}", z); 181 } 182 logger.info("z, k = {}, {}", z, k); 183 sfactors.put(z, k); 184 } 185 } 186 return normalizeFactorization(sfactors); 187 } 188 189 190 /** 191 * GenPolynomial recursive univariate polynomial greatest squarefree 192 * divisor. 193 * @param P recursive univariate GenPolynomial. 194 * @return squarefree(P). 195 */ 196 @Override 197 public GenPolynomial<GenPolynomial<C>> recursiveUnivariateSquarefreePart( 198 GenPolynomial<GenPolynomial<C>> P) { 199 if (P == null || P.isZERO()) { 200 return P; 201 } 202 GenPolynomialRing<GenPolynomial<C>> pfac = P.ring; 203 if (pfac.nvar > 1) { 204 throw new IllegalArgumentException( 205 this.getClass().getName() + " only for multivariate polynomials"); 206 } 207 // remove content 208 GenPolynomial<GenPolynomial<C>> pp = P; 209 GenPolynomial<C> Pc = engine.recursiveContent(P); 210 Pc = engine.basePrimitivePart(Pc); 211 if (!Pc.isONE()) { 212 pp = PolyUtil.<C> coefficientPseudoDivide(pp, Pc); 213 //System.out.println("pp/cont = " + pp); 214 } 215 // squarefree content 216 GenPolynomial<C> Ps = squarefreePart(Pc); 217 Ps = engine.basePrimitivePart(Ps); 218 //System.out.println("Pc = " + Pc + ", Ps = " + Ps); 219 if (pp.leadingExpVector().getVal(0) < 1) { 220 //System.out.println("pp = " + pp); 221 //System.out.println("Ps = " + Ps); 222 pp = pp.multiply(Ps); 223 pp = engine.baseRecursivePrimitivePart(pp); 224 return pp; 225 } 226 GenPolynomial<GenPolynomial<C>> d = PolyUtil.<C> recursiveDerivative(pp); 227 //System.out.println("d = " + d); 228 GenPolynomial<GenPolynomial<C>> g = engine.recursiveUnivariateGcd(pp, d); 229 //System.out.println("g,rec = " + g); 230 g = engine.baseRecursivePrimitivePart(g); 231 //System.out.println("g,bPP = " + g); 232 GenPolynomial<GenPolynomial<C>> q = PolyUtil.<C> recursivePseudoDivide(pp, g); 233 //System.out.println("q,bPP = " + q); 234 q = q.multiply(Ps); 235 //q = engine.basePrimitivePart(q); 236 q = engine.baseRecursivePrimitivePart(q); 237 return q; 238 } 239 240 241 /** 242 * GenPolynomial recursive univariate polynomial squarefree factorization. 243 * @param P recursive univariate GenPolynomial. 244 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} 245 * p_i^{e_i} and p_i squarefree and gcd(p_i, p_j) = 1, for i != j. 246 */ 247 @Override 248 public SortedMap<GenPolynomial<GenPolynomial<C>>, Long> recursiveUnivariateSquarefreeFactors( 249 GenPolynomial<GenPolynomial<C>> P) { 250 SortedMap<GenPolynomial<GenPolynomial<C>>, Long> sfactors = new TreeMap<GenPolynomial<GenPolynomial<C>>, Long>(); 251 if (P == null || P.isZERO()) { 252 return sfactors; 253 } 254 GenPolynomialRing<GenPolynomial<C>> pfac = P.ring; 255 if (pfac.nvar > 1) { 256 // recursiveContent not possible by return type 257 throw new IllegalArgumentException( 258 this.getClass().getName() + " only for univariate polynomials"); 259 } 260 // if base coefficient ring is a field, make monic 261 GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) pfac.coFac; 262 C bcc = engine.baseRecursiveContent(P); 263 if (!bcc.isONE()) { 264 GenPolynomial<C> lc = cfac.getONE().multiply(bcc); 265 GenPolynomial<GenPolynomial<C>> pl = pfac.getONE().multiply(lc); 266 sfactors.put(pl, 1L); 267 P = PolyUtil.<C> baseRecursiveDivide(P, bcc); 268 } 269 // factors of content 270 GenPolynomial<C> Pc = engine.recursiveContent(P); 271 logger.info("Pc = {}", Pc); 272 Pc = engine.basePrimitivePart(Pc); 273 //System.out.println("Pc,PP = " + Pc); 274 if (!Pc.isONE()) { 275 P = PolyUtil.<C> coefficientPseudoDivide(P, Pc); 276 } 277 SortedMap<GenPolynomial<C>, Long> rsf = squarefreeFactors(Pc); 278 logger.info("rsf = {}", rsf); 279 // add factors of content 280 for (Map.Entry<GenPolynomial<C>, Long> me : rsf.entrySet()) { 281 GenPolynomial<C> c = me.getKey(); 282 if (!c.isONE()) { 283 GenPolynomial<GenPolynomial<C>> cr = pfac.getONE().multiply(c); 284 Long rk = me.getValue(); //rsf.get(c); 285 sfactors.put(cr, rk); 286 } 287 } 288 // divide by trailing term 289 ExpVector et = P.trailingExpVector(); 290 if (!et.isZERO()) { 291 GenPolynomial<GenPolynomial<C>> tr = pfac.valueOf(et); 292 logger.info("trailing term = {}", tr); 293 P = PolyUtil.<C> recursivePseudoDivide(P, tr); 294 long ep = et.getVal(0); // univariate 295 et = et.subst(0, 1); 296 tr = pfac.valueOf(et); 297 sfactors.put(tr, ep); 298 } 299 300 // factors of recursive polynomial 301 GenPolynomial<GenPolynomial<C>> T0 = P; 302 GenPolynomial<GenPolynomial<C>> Tp; 303 GenPolynomial<GenPolynomial<C>> T = null; 304 GenPolynomial<GenPolynomial<C>> V = null; 305 long k = 0L; 306 boolean init = true; 307 while (true) { 308 if (init) { 309 if (T0.isConstant() || T0.isZERO()) { 310 break; 311 } 312 Tp = PolyUtil.<C> recursiveDerivative(T0); 313 //System.out.println("iTp = " + Tp); 314 T = engine.recursiveUnivariateGcd(T0, Tp); 315 //System.out.println("iT = " + T); 316 if (debug) { 317 logger.info("T0 = {}, Tp = {}, T = {}", T0, Tp, T); 318 } 319 T = engine.baseRecursivePrimitivePart(T); 320 //System.out.println("iT = " + T); 321 V = PolyUtil.<C> recursivePseudoDivide(T0, T); 322 //System.out.println("iT0 = " + T0); 323 //System.out.println("iV = " + V); 324 k = 0L; 325 init = false; 326 } 327 if (V.isConstant()) { 328 break; 329 } 330 k++; 331 GenPolynomial<GenPolynomial<C>> W = engine.recursiveUnivariateGcd(T, V); 332 if (debug) { 333 logger.info("T = {}, V = {}, W = {}", T, V, W); 334 } 335 W = engine.baseRecursivePrimitivePart(W); 336 GenPolynomial<GenPolynomial<C>> z = PolyUtil.<C> recursivePseudoDivide(V, W); 337 //System.out.println("W = " + W); 338 //System.out.println("z = " + z); 339 V = W; 340 T = PolyUtil.<C> recursivePseudoDivide(T, V); 341 //System.out.println("V = " + V); 342 //System.out.println("T = " + T); 343 //was: if ( z.degree(0) > 0 ) { 344 if (!z.isONE() && !z.isZERO()) { 345 z = engine.baseRecursivePrimitivePart(z); 346 logger.info("z = {}, k = {}", z, k); 347 sfactors.put(z, k); 348 } 349 } 350 return sfactors; 351 } 352 353 354 /** 355 * GenPolynomial greatest squarefree divisor. 356 * @param P GenPolynomial. 357 * @return squarefree(P). 358 */ 359 @Override 360 public GenPolynomial<C> squarefreePart(GenPolynomial<C> P) { 361 if (P == null) { 362 throw new IllegalArgumentException(this.getClass().getName() + " P != null"); 363 } 364 if (P.isZERO()) { 365 return P; 366 } 367 GenPolynomialRing<C> pfac = P.ring; 368 if (pfac.nvar <= 1) { 369 return baseSquarefreePart(P); 370 } 371 GenPolynomialRing<GenPolynomial<C>> rfac = pfac.recursive(1); 372 GenPolynomial<GenPolynomial<C>> Pr = PolyUtil.<C> recursive(rfac, P); 373 GenPolynomial<C> Pc = engine.recursiveContent(Pr); 374 Pr = PolyUtil.<C> coefficientPseudoDivide(Pr, Pc); 375 GenPolynomial<C> Ps = squarefreePart(Pc); 376 GenPolynomial<GenPolynomial<C>> PP = recursiveUnivariateSquarefreePart(Pr); 377 GenPolynomial<GenPolynomial<C>> PS = PP.multiply(Ps); 378 GenPolynomial<C> D = PolyUtil.<C> distribute(pfac, PS); 379 return D; 380 } 381 382 383 /** 384 * GenPolynomial squarefree factorization. 385 * @param P GenPolynomial. 386 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} 387 * p_i^{e_i} and p_i squarefree and gcd(p_i, p_j) = 1, for i != j. 388 */ 389 @Override 390 public SortedMap<GenPolynomial<C>, Long> squarefreeFactors(GenPolynomial<C> P) { 391 if (P == null) { 392 throw new IllegalArgumentException(this.getClass().getName() + " P != null"); 393 } 394 GenPolynomialRing<C> pfac = P.ring; 395 if (pfac.nvar <= 1) { 396 return baseSquarefreeFactors(P); 397 } 398 SortedMap<GenPolynomial<C>, Long> sfactors = new TreeMap<GenPolynomial<C>, Long>(); 399 if (P.isZERO()) { 400 return sfactors; 401 } 402 if (P.isONE()) { 403 sfactors.put(P, 1L); 404 return sfactors; 405 } 406 GenPolynomialRing<GenPolynomial<C>> rfac = pfac.recursive(1); 407 408 GenPolynomial<GenPolynomial<C>> Pr = PolyUtil.<C> recursive(rfac, P); 409 SortedMap<GenPolynomial<GenPolynomial<C>>, Long> PP = recursiveUnivariateSquarefreeFactors(Pr); 410 411 for (Map.Entry<GenPolynomial<GenPolynomial<C>>, Long> m : PP.entrySet()) { 412 Long i = m.getValue(); 413 GenPolynomial<GenPolynomial<C>> Dr = m.getKey(); 414 GenPolynomial<C> D = PolyUtil.<C> distribute(pfac, Dr); 415 sfactors.put(D, i); 416 } 417 return normalizeFactorization(sfactors); 418 } 419 420 421 /** 422 * Coefficients squarefree factorization. 423 * @param P coefficient. 424 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} 425 * p_i^{e_i} and p_i squarefree and gcd(p_i, p_j) = 1, for i != j. 426 */ 427 @Override 428 public SortedMap<C, Long> squarefreeFactors(C P) { 429 throw new UnsupportedOperationException("method not implemented"); 430 } 431 432}