001/* 002 * $Id: SquarefreeInfiniteFieldCharP.java 4965 2014-10-17 20:07:51Z 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.ExpVector; 015import edu.jas.poly.GenPolynomial; 016import edu.jas.poly.GenPolynomialRing; 017import edu.jas.poly.Monomial; 018import edu.jas.poly.PolyUtil; 019import edu.jas.structure.GcdRingElem; 020import edu.jas.structure.Power; 021import edu.jas.structure.RingFactory; 022 023 024/** 025 * Squarefree decomposition for infinite coefficient fields of characteristic p. 026 * @author Heinz Kredel 027 */ 028 029public class SquarefreeInfiniteFieldCharP<C extends GcdRingElem<C>> extends SquarefreeFieldCharP<Quotient<C>> { 030 031 032 private static final Logger logger = Logger.getLogger(SquarefreeInfiniteFieldCharP.class); 033 034 035 //private final boolean debug = logger.isDebugEnabled(); 036 037 038 /** 039 * Squarefree engine for infinite ring of characteristic p base 040 * coefficients. 041 */ 042 protected final SquarefreeAbstract<C> qengine; 043 044 045 /** 046 * Constructor. 047 */ 048 @SuppressWarnings("cast") 049 public SquarefreeInfiniteFieldCharP(RingFactory<Quotient<C>> fac) { 050 super(fac); 051 // isFinite() predicate now present 052 if (fac.isFinite()) { 053 throw new IllegalArgumentException("fac must be in-finite"); 054 } 055 QuotientRing<C> qfac = (QuotientRing<C>) fac; 056 GenPolynomialRing<C> rfac = qfac.ring; 057 qengine = (SquarefreeAbstract) SquarefreeFactory.<C> getImplementation(rfac); 058 //qengine = new SquarefreeFiniteFieldCharP<C>(rfac.coFac); 059 //qengine = new SquarefreeInfiniteRingCharP<C>( rfac.coFac ); 060 } 061 062 063 /* --------- quotient char-th roots --------------------- */ 064 065 066 /** 067 * Squarefree factors of a Quotient. 068 * @param P Quotient. 069 * @return [p_1 -> e_1,...,p_k - > e_k] with P = prod_{i=1, ..., k} 070 * p_i**e_k. 071 */ 072 @Override 073 public SortedMap<Quotient<C>, Long> squarefreeFactors(Quotient<C> P) { 074 if (P == null) { 075 throw new IllegalArgumentException(this.getClass().getName() + " P == null"); 076 } 077 SortedMap<Quotient<C>, Long> factors = new TreeMap<Quotient<C>, Long>(); 078 if (P.isZERO()) { 079 return factors; 080 } 081 if (P.isONE()) { 082 factors.put(P, 1L); 083 return factors; 084 } 085 GenPolynomial<C> num = P.num; 086 GenPolynomial<C> den = P.den; 087 QuotientRing<C> pfac = P.ring; 088 GenPolynomial<C> one = pfac.ring.getONE(); 089 if (!num.isONE()) { 090 SortedMap<GenPolynomial<C>, Long> nfac = qengine.squarefreeFactors(num); 091 //System.out.println("nfac = " + nfac); 092 for (Map.Entry<GenPolynomial<C>, Long> me : nfac.entrySet()) { 093 GenPolynomial<C> nfp = me.getKey(); 094 Quotient<C> nf = new Quotient<C>(pfac, nfp); 095 factors.put(nf, me.getValue()); //nfac.get(nfp)); 096 } 097 } 098 if (den.isONE()) { 099 if (factors.size() == 0) { 100 factors.put(P, 1L); 101 } 102 return factors; 103 } 104 SortedMap<GenPolynomial<C>, Long> dfac = qengine.squarefreeFactors(den); 105 //System.out.println("dfac = " + dfac); 106 for (Map.Entry<GenPolynomial<C>, Long> me : dfac.entrySet()) { 107 GenPolynomial<C> dfp = me.getKey(); 108 Quotient<C> df = new Quotient<C>(pfac, one, dfp); 109 factors.put(df, me.getValue()); //dfac.get(dfp)); 110 } 111 if (factors.size() == 0) { 112 factors.put(P, 1L); 113 } 114 return factors; 115 } 116 117 118 /** 119 * Characteristics root of a Quotient. 120 * @param P Quotient. 121 * @return [p -> k] if exists k with e=charactristic(P)*k and P = p**e, 122 * else null. 123 */ 124 public SortedMap<Quotient<C>, Long> rootCharacteristic(Quotient<C> P) { 125 if (P == null) { 126 throw new IllegalArgumentException(this.getClass().getName() + " P == null"); 127 } 128 java.math.BigInteger c = P.ring.characteristic(); 129 if (c.signum() == 0) { 130 return null; 131 } 132 SortedMap<Quotient<C>, Long> root = new TreeMap<Quotient<C>, Long>(); 133 if (P.isZERO()) { 134 return root; 135 } 136 if (P.isONE()) { 137 root.put(P, 1L); 138 return root; 139 } 140 SortedMap<Quotient<C>, Long> sf = squarefreeFactors(P); 141 if (sf.size() == 0) { 142 return null; 143 } 144 if (logger.isInfoEnabled()) { 145 logger.info("sf,quot = " + sf); 146 } 147 // better: test if sf.size() == 2 // no, since num and den factors 148 Long k = null; 149 Long cl = c.longValue(); 150 for (Map.Entry<Quotient<C>, Long> me : sf.entrySet()) { 151 Quotient<C> p = me.getKey(); 152 //System.out.println("p = " + p); 153 if (p.isConstant()) { // todo: check for non-constants in coefficients 154 continue; 155 } 156 Long e = me.getValue(); //sf.get(p); 157 long E = e.longValue(); 158 long r = E % cl; 159 if (r != 0) { 160 //System.out.println("r = " + r); 161 return null; 162 } 163 if (k == null) { 164 k = e; 165 } else if (k >= e) { 166 k = e; 167 } 168 } 169 if (k == null) { 170 k = 1L; //return null; 171 } 172 // now c divides all exponents of non constant elements 173 for (Map.Entry<Quotient<C>, Long> me : sf.entrySet()) { 174 Quotient<C> q = me.getKey(); 175 Long e = me.getValue(); //sf.get(q); 176 //System.out.println("q = " + q + ", e = " + e); 177 if (e >= k) { 178 e = e / cl; 179 //q = Power.<Quotient<C>> positivePower(q, e); 180 root.put(q, e); 181 } else { // constant case 182 root.put(q, e); 183 } 184 } 185 //System.out.println("root = " + root); 186 return root; 187 } 188 189 190 /** 191 * GenPolynomial char-th root main variable. 192 * @param P univariate GenPolynomial with Quotient coefficients. 193 * @return char-th_rootOf(P), or null, if P is no char-th root. 194 */ 195 public GenPolynomial<Quotient<C>> rootCharacteristic(GenPolynomial<Quotient<C>> P) { 196 if (P == null || P.isZERO()) { 197 return P; 198 } 199 GenPolynomialRing<Quotient<C>> pfac = P.ring; 200 if (pfac.nvar > 1) { 201 // go to recursion 202 GenPolynomialRing<Quotient<C>> cfac = pfac.contract(1); 203 GenPolynomialRing<GenPolynomial<Quotient<C>>> rfac = new GenPolynomialRing<GenPolynomial<Quotient<C>>>( 204 cfac, 1); 205 GenPolynomial<GenPolynomial<Quotient<C>>> Pr = PolyUtil.<Quotient<C>> recursive(rfac, P); 206 GenPolynomial<GenPolynomial<Quotient<C>>> Prc = recursiveUnivariateRootCharacteristic(Pr); 207 if (Prc == null) { 208 return null; 209 } 210 GenPolynomial<Quotient<C>> D = PolyUtil.<Quotient<C>> distribute(pfac, Prc); 211 return D; 212 } 213 RingFactory<Quotient<C>> rf = pfac.coFac; 214 if (rf.characteristic().signum() != 1) { 215 // basePthRoot not possible 216 throw new IllegalArgumentException(P.getClass().getName() + " only for ModInteger polynomials " 217 + rf); 218 } 219 long mp = rf.characteristic().longValue(); 220 GenPolynomial<Quotient<C>> d = pfac.getZERO().copy(); 221 for (Monomial<Quotient<C>> m : P) { 222 ExpVector f = m.e; 223 long fl = f.getVal(0); 224 if (fl % mp != 0) { 225 return null; 226 } 227 fl = fl / mp; 228 SortedMap<Quotient<C>, Long> sm = rootCharacteristic(m.c); 229 if (sm == null) { 230 return null; 231 } 232 if (logger.isInfoEnabled()) { 233 logger.info("sm,root = " + sm); 234 } 235 Quotient<C> r = rf.getONE(); 236 for (Map.Entry<Quotient<C>, Long> me : sm.entrySet()) { 237 Quotient<C> rp = me.getKey(); 238 long gl = me.getValue(); // sm.get(rp); 239 if (gl > 1) { 240 rp = Power.<Quotient<C>> positivePower(rp, gl); 241 } 242 r = r.multiply(rp); 243 } 244 ExpVector e = ExpVector.create(1, 0, fl); 245 d.doPutToMap(e, r); 246 } 247 logger.info("sm,root,d = " + d); 248 return d; 249 } 250 251 252 /** 253 * GenPolynomial char-th root univariate polynomial. 254 * @param P GenPolynomial. 255 * @return char-th_rootOf(P). 256 */ 257 @Override 258 public GenPolynomial<Quotient<C>> baseRootCharacteristic(GenPolynomial<Quotient<C>> P) { 259 if (P == null || P.isZERO()) { 260 return P; 261 } 262 GenPolynomialRing<Quotient<C>> pfac = P.ring; 263 if (pfac.nvar > 1) { 264 // basePthRoot not possible by return type 265 throw new IllegalArgumentException(P.getClass().getName() + " only for univariate polynomials"); 266 } 267 RingFactory<Quotient<C>> rf = pfac.coFac; 268 if (rf.characteristic().signum() != 1) { 269 // basePthRoot not possible 270 throw new IllegalArgumentException(P.getClass().getName() + " only for char p > 0 " + rf); 271 } 272 long mp = rf.characteristic().longValue(); 273 GenPolynomial<Quotient<C>> d = pfac.getZERO().copy(); 274 for (Monomial<Quotient<C>> m : P) { 275 //System.out.println("m = " + m); 276 ExpVector f = m.e; 277 long fl = f.getVal(0); 278 if (fl % mp != 0) { 279 return null; 280 } 281 fl = fl / mp; 282 SortedMap<Quotient<C>, Long> sm = rootCharacteristic(m.c); 283 if (sm == null) { 284 return null; 285 } 286 if (logger.isInfoEnabled()) { 287 logger.info("sm,base,root = " + sm); 288 } 289 Quotient<C> r = rf.getONE(); 290 for (Map.Entry<Quotient<C>, Long> me : sm.entrySet()) { 291 Quotient<C> rp = me.getKey(); 292 //System.out.println("rp = " + rp); 293 long gl = me.getValue(); //sm.get(rp); 294 //System.out.println("gl = " + gl); 295 Quotient<C> re = rp; 296 if (gl > 1) { 297 re = Power.<Quotient<C>> positivePower(rp, gl); 298 } 299 //System.out.println("re = " + re); 300 r = r.multiply(re); 301 } 302 ExpVector e = ExpVector.create(1, 0, fl); 303 d.doPutToMap(e, r); 304 } 305 if (logger.isInfoEnabled()) { 306 logger.info("sm,base,d = " + d); 307 } 308 return d; 309 } 310 311 312 /** 313 * GenPolynomial char-th root univariate polynomial with polynomial 314 * coefficients. 315 * @param P recursive univariate GenPolynomial. 316 * @return char-th_rootOf(P), or null if P is no char-th root. 317 */ 318 @Override 319 public GenPolynomial<GenPolynomial<Quotient<C>>> recursiveUnivariateRootCharacteristic( 320 GenPolynomial<GenPolynomial<Quotient<C>>> P) { 321 if (P == null || P.isZERO()) { 322 return P; 323 } 324 GenPolynomialRing<GenPolynomial<Quotient<C>>> pfac = P.ring; 325 if (pfac.nvar > 1) { 326 // basePthRoot not possible by return type 327 throw new IllegalArgumentException(P.getClass().getName() 328 + " only for univariate recursive polynomials"); 329 } 330 RingFactory<GenPolynomial<Quotient<C>>> rf = pfac.coFac; 331 if (rf.characteristic().signum() != 1) { 332 // basePthRoot not possible 333 throw new IllegalArgumentException(P.getClass().getName() + " only for char p > 0 " + rf); 334 } 335 long mp = rf.characteristic().longValue(); 336 GenPolynomial<GenPolynomial<Quotient<C>>> d = pfac.getZERO().copy(); 337 for (Monomial<GenPolynomial<Quotient<C>>> m : P) { 338 ExpVector f = m.e; 339 long fl = f.getVal(0); 340 if (fl % mp != 0) { 341 return null; 342 } 343 fl = fl / mp; 344 GenPolynomial<Quotient<C>> r = rootCharacteristic(m.c); 345 if (r == null) { 346 return null; 347 } 348 ExpVector e = ExpVector.create(1, 0, fl); 349 d.doPutToMap(e, r); 350 } 351 return d; 352 } 353 354}