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