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