001 /*
002 * $Id: SquarefreeInfiniteAlgebraicFieldCharP.java 3290 2010-08-26 09:18:48Z
003 * kredel $
004 */
005
006 package edu.jas.ufd;
007
008
009 import java.util.ArrayList;
010 import java.util.List;
011 import java.util.SortedMap;
012 import java.util.TreeMap;
013
014 import org.apache.log4j.Logger;
015
016 import edu.jas.gb.Reduction;
017 import edu.jas.gb.ReductionSeq;
018 import edu.jas.gb.GroebnerBaseAbstract;
019 import edu.jas.gb.GroebnerBaseSeq;
020 import edu.jas.poly.AlgebraicNumber;
021 import edu.jas.poly.AlgebraicNumberRing;
022 import edu.jas.poly.ExpVector;
023 import edu.jas.poly.GenPolynomial;
024 import edu.jas.poly.GenPolynomialRing;
025 import edu.jas.poly.Monomial;
026 import edu.jas.poly.PolyUtil;
027 import edu.jas.structure.GcdRingElem;
028 import edu.jas.structure.Power;
029 import edu.jas.structure.RingFactory;
030
031
032 /**
033 * Squarefree decomposition for algebraic extensions of infinite coefficient
034 * fields of characteristic p > 0.
035 * @author Heinz Kredel
036 */
037
038 public class SquarefreeInfiniteAlgebraicFieldCharP<C extends GcdRingElem<C>> extends
039 SquarefreeFieldCharP<AlgebraicNumber<C>> {
040
041
042 private static final Logger logger = Logger.getLogger(SquarefreeInfiniteAlgebraicFieldCharP.class);
043
044
045 private final boolean debug = logger.isDebugEnabled();
046
047
048 /**
049 * GCD engine for infinite ring of characteristic p base coefficients.
050 */
051 protected final SquarefreeAbstract<C> rengine;
052
053
054 /**
055 * Constructor.
056 */
057 public SquarefreeInfiniteAlgebraicFieldCharP(RingFactory<AlgebraicNumber<C>> fac) {
058 super(fac);
059 // isFinite() predicate now present
060 if (fac.isFinite()) {
061 throw new IllegalArgumentException("fac must be in-finite");
062 }
063 AlgebraicNumberRing<C> afac = (AlgebraicNumberRing<C>) fac;
064 GenPolynomialRing<C> rfac = afac.ring;
065 //System.out.println("rfac = " + rfac);
066 //System.out.println("rfac = " + rfac.coFac);
067 rengine = SquarefreeFactory.<C> getImplementation(rfac);
068 //System.out.println("rengine = " + rengine);
069 }
070
071
072 /* --------- algebraic number char-th roots --------------------- */
073
074 /**
075 * Squarefree factors of a AlgebraicNumber.
076 * @param P AlgebraicNumber.
077 * @return [p_1 -> e_1,...,p_k - > e_k] with P = prod_{i=1, ..., k}
078 * p_i**e_k.
079 */
080 @Override
081 public SortedMap<AlgebraicNumber<C>, Long> squarefreeFactors(AlgebraicNumber<C> P) {
082 if (P == null) {
083 throw new IllegalArgumentException(this.getClass().getName() + " P == null");
084 }
085 SortedMap<AlgebraicNumber<C>, Long> factors = new TreeMap<AlgebraicNumber<C>, Long>();
086 if (P.isZERO()) {
087 return factors;
088 }
089 if (P.isONE()) {
090 factors.put(P, 1L);
091 return factors;
092 }
093 GenPolynomial<C> an = P.val;
094 AlgebraicNumberRing<C> pfac = P.ring;
095 GenPolynomial<C> one = pfac.ring.getONE();
096 if (!an.isONE()) {
097 //System.out.println("an = " + an);
098 //System.out.println("rengine = " + rengine);
099 SortedMap<GenPolynomial<C>, Long> nfac = rengine.squarefreeFactors(an);
100 //System.out.println("nfac = " + nfac);
101 for (GenPolynomial<C> nfp : nfac.keySet()) {
102 AlgebraicNumber<C> nf = new AlgebraicNumber<C>(pfac, nfp);
103 factors.put(nf, nfac.get(nfp));
104 }
105 }
106 if (factors.size() == 0) {
107 factors.put(P, 1L);
108 }
109 return factors;
110 }
111
112
113 /**
114 * Characteristics root of a AlgebraicNumber.
115 * @param P AlgebraicNumber.
116 * @return [p -> k] if exists k with e=charactristic(P)*k and P = p**e,
117 * else null.
118 */
119 public SortedMap<AlgebraicNumber<C>, Long> rootCharacteristic(AlgebraicNumber<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<AlgebraicNumber<C>, Long> root = new TreeMap<AlgebraicNumber<C>, Long>();
128 if (P.isZERO()) {
129 return root;
130 }
131 if (P.isONE()) {
132 root.put(P, 1L);
133 return root;
134 }
135 // generate system of equations
136 AlgebraicNumberRing<C> afac = P.ring;
137 long deg = afac.modul.degree(0);
138 int d = (int) deg;
139 String[] vn = GenPolynomialRing.newVars("c", d);
140 GenPolynomialRing<AlgebraicNumber<C>> pfac = new GenPolynomialRing<AlgebraicNumber<C>>(afac, d, vn);
141 List<GenPolynomial<AlgebraicNumber<C>>> uv = (List<GenPolynomial<AlgebraicNumber<C>>>) pfac
142 .univariateList();
143 GenPolynomial<AlgebraicNumber<C>> cp = pfac.getZERO();
144 GenPolynomialRing<C> apfac = afac.ring;
145 long i = 0;
146 for (GenPolynomial<AlgebraicNumber<C>> pa : uv) {
147 GenPolynomial<C> ca = apfac.univariate(0, i++);
148 GenPolynomial<AlgebraicNumber<C>> pb = pa.multiply(new AlgebraicNumber<C>(afac, ca));
149 cp = cp.sum(pb);
150 }
151 GenPolynomial<AlgebraicNumber<C>> cpp = Power
152 .<GenPolynomial<AlgebraicNumber<C>>> positivePower(cp, c);
153 if (logger.isInfoEnabled()) {
154 logger.info("cp = " + cp);
155 logger.info("cp^p = " + cpp);
156 logger.info("P = " + P);
157 }
158 GenPolynomialRing<C> ppfac = new GenPolynomialRing<C>(apfac.coFac, pfac);
159 List<GenPolynomial<C>> gl = new ArrayList<GenPolynomial<C>>();
160 if (deg == c.longValue() && afac.modul.length() == 2) {
161 logger.info("deg(" + deg + ") == char_p(" + c.longValue() + ")");
162 for (Monomial<AlgebraicNumber<C>> m : cpp) {
163 ExpVector f = m.e;
164 AlgebraicNumber<C> a = m.c;
165 //System.out.println("a = " + a + " : " + a.toScriptFactory());
166 GenPolynomial<C> ap = a.val;
167 for (Monomial<C> ma : ap) {
168 ExpVector e = ma.e;
169 C cc = ma.c;
170 C pc = P.val.coefficient(e);
171 C cc1 = ((RingFactory<C>) pc.factory()).getONE();
172 C pc1 = ((RingFactory<C>) pc.factory()).getZERO();
173 //System.out.println("cc = " + cc + ", e = " + e);
174 //System.out.println("pc = " + pc + " : " + cc.toScriptFactory());
175 if (cc instanceof AlgebraicNumber && pc instanceof AlgebraicNumber) {
176 throw new UnsupportedOperationException(
177 "case multiple algebraic extensions not implemented");
178 } else if (cc instanceof Quotient && pc instanceof Quotient) {
179 Quotient<C> ccp = (Quotient<C>) (Object) cc;
180 Quotient<C> pcp = (Quotient<C>) (Object) pc;
181 if (pcp.isConstant()) {
182 //logger.error("finite field not allowed here " + afac.toScript());
183 throw new ArithmeticException("finite field not allowed here " + afac.toScript());
184 }
185 //C dc = cc.divide(pc);
186 Quotient<C> dcp = ccp.divide(pcp);
187 if (dcp.isConstant()) { // not possible: dc.isConstant()
188 //System.out.println("dcp = " + dcp + " : " + cc.toScriptFactory()); // + ", dc = " + dc);
189 //if ( dcp.num.isConstant() )
190 cc1 = cc;
191 pc1 = pc;
192 }
193 GenPolynomial<C> r = new GenPolynomial<C>(ppfac, cc1, f);
194 r = r.subtract(pc1);
195 //System.out.println("r = " + r);
196 gl.add(r);
197 }
198 }
199 }
200 } else {
201 for (Monomial<AlgebraicNumber<C>> m : cpp) {
202 ExpVector f = m.e;
203 AlgebraicNumber<C> a = m.c;
204 //System.out.println("m = " + m);
205 GenPolynomial<C> ap = a.val;
206 for (Monomial<C> ma : ap) {
207 ExpVector e = ma.e;
208 C cc = ma.c;
209 C pc = P.val.coefficient(e);
210 GenPolynomial<C> r = new GenPolynomial<C>(ppfac, cc, f);
211 r = r.subtract(pc);
212 //System.out.println("r = " + r);
213 gl.add(r);
214 }
215 }
216 }
217 if (logger.isInfoEnabled()) {
218 logger.info("equations = " + gl);
219 }
220 // solve system of equations and construct result
221 Reduction<C> red = new ReductionSeq<C>();
222 gl = red.irreducibleSet(gl);
223 GroebnerBaseAbstract<C> bb = new GroebnerBaseSeq<C>(); //GBFactory.<C>getImplementation();
224 int z = bb.commonZeroTest(gl);
225 if (z < 0) { // no solution
226 return null;
227 }
228 if (logger.isInfoEnabled()) {
229 logger.info("solution = " + gl);
230 }
231 GenPolynomial<C> car = apfac.getZERO();
232 for (GenPolynomial<C> pl : gl) {
233 if (pl.length() <= 1) {
234 continue;
235 }
236 if (pl.length() > 2) {
237 throw new IllegalArgumentException("dim > 0 not implemented " + pl);
238 }
239 //System.out.println("pl = " + pl);
240 ExpVector e = pl.leadingExpVector();
241 int[] v = e.dependencyOnVariables();
242 if (v == null || v.length == 0) {
243 continue;
244 }
245 int vi = v[0];
246 //System.out.println("vi = " + vi);
247 GenPolynomial<C> ca = apfac.univariate(0, deg - 1 - vi);
248 //System.out.println("ca = " + ca);
249 C tc = pl.trailingBaseCoefficient();
250 tc = tc.negate();
251 if (e.maxDeg() == c.longValue()) { // p-th root of tc ...
252 //SortedMap<C, Long> br = rengine.rootCharacteristic(tc);
253 SortedMap<C, Long> br = rengine.squarefreeFactors(tc);
254 //System.out.println("br = " + br);
255 if (br != null && br.size() > 0) {
256 C cc = apfac.coFac.getONE();
257 for (C bc : br.keySet()) {
258 long ll = br.get(bc);
259 if (ll % c.longValue() == 0L) {
260 long fl = ll / c.longValue();
261 cc = cc.multiply(Power.<C> positivePower(bc, fl));
262 } else { // fail ?
263 cc = cc.multiply(bc);
264 }
265 }
266 //System.out.println("cc = " + cc);
267 tc = cc;
268 }
269 }
270 ca = ca.multiply(tc);
271 car = car.sum(ca);
272 }
273 AlgebraicNumber<C> rr = new AlgebraicNumber<C>(afac, car);
274 if (logger.isInfoEnabled()) {
275 logger.info("solution AN = " + rr);
276 //System.out.println("rr = " + rr);
277 }
278 root.put(rr, 1L);
279 return root;
280 }
281
282
283 /**
284 * GenPolynomial char-th root main variable.
285 * @param P univariate GenPolynomial with AlgebraicNumber coefficients.
286 * @return char-th_rootOf(P), or null, if P is no char-th root.
287 */
288 public GenPolynomial<AlgebraicNumber<C>> rootCharacteristic(GenPolynomial<AlgebraicNumber<C>> P) {
289 if (P == null || P.isZERO()) {
290 return P;
291 }
292 GenPolynomialRing<AlgebraicNumber<C>> pfac = P.ring;
293 if (pfac.nvar > 1) {
294 // go to recursion
295 GenPolynomialRing<AlgebraicNumber<C>> cfac = pfac.contract(1);
296 GenPolynomialRing<GenPolynomial<AlgebraicNumber<C>>> rfac = new GenPolynomialRing<GenPolynomial<AlgebraicNumber<C>>>(
297 cfac, 1);
298 GenPolynomial<GenPolynomial<AlgebraicNumber<C>>> Pr = PolyUtil.<AlgebraicNumber<C>> recursive(
299 rfac, P);
300 GenPolynomial<GenPolynomial<AlgebraicNumber<C>>> Prc = recursiveUnivariateRootCharacteristic(Pr);
301 if (Prc == null) {
302 return null;
303 }
304 GenPolynomial<AlgebraicNumber<C>> D = PolyUtil.<AlgebraicNumber<C>> distribute(pfac, Prc);
305 return D;
306 }
307 RingFactory<AlgebraicNumber<C>> rf = pfac.coFac;
308 if (rf.characteristic().signum() != 1) {
309 // basePthRoot not possible
310 throw new IllegalArgumentException(P.getClass().getName() + " only for ModInteger polynomials "
311 + rf);
312 }
313 long mp = rf.characteristic().longValue();
314 GenPolynomial<AlgebraicNumber<C>> d = pfac.getZERO().clone();
315 for (Monomial<AlgebraicNumber<C>> m : P) {
316 ExpVector f = m.e;
317 long fl = f.getVal(0);
318 if (fl % mp != 0) {
319 return null;
320 }
321 fl = fl / mp;
322 SortedMap<AlgebraicNumber<C>, Long> sm = rootCharacteristic(m.c);
323 if (sm == null) {
324 return null;
325 }
326 if (logger.isInfoEnabled()) {
327 logger.info("sm_alg,root = " + sm);
328 }
329 AlgebraicNumber<C> r = rf.getONE();
330 for (AlgebraicNumber<C> rp : sm.keySet()) {
331 long gl = sm.get(rp);
332 if (gl > 1) {
333 rp = Power.<AlgebraicNumber<C>> positivePower(rp, gl);
334 }
335 r = r.multiply(rp);
336 }
337 ExpVector e = ExpVector.create(1, 0, fl);
338 d.doPutToMap(e, r);
339 }
340 logger.info("sm_alg,root,d = " + d);
341 return d;
342 }
343
344
345 /**
346 * GenPolynomial char-th root univariate polynomial.
347 * @param P GenPolynomial.
348 * @return char-th_rootOf(P).
349 */
350 @Override
351 public GenPolynomial<AlgebraicNumber<C>> baseRootCharacteristic(GenPolynomial<AlgebraicNumber<C>> P) {
352 if (P == null || P.isZERO()) {
353 return P;
354 }
355 GenPolynomialRing<AlgebraicNumber<C>> pfac = P.ring;
356 if (pfac.nvar > 1) {
357 // basePthRoot not possible by return type
358 throw new IllegalArgumentException(P.getClass().getName() + " only for univariate polynomials");
359 }
360 RingFactory<AlgebraicNumber<C>> rf = pfac.coFac;
361 if (rf.characteristic().signum() != 1) {
362 // basePthRoot not possible
363 throw new IllegalArgumentException(P.getClass().getName() + " only for char p > 0 " + rf);
364 }
365 long mp = rf.characteristic().longValue();
366 GenPolynomial<AlgebraicNumber<C>> d = pfac.getZERO().clone();
367 for (Monomial<AlgebraicNumber<C>> m : P) {
368 //System.out.println("m = " + m);
369 ExpVector f = m.e;
370 long fl = f.getVal(0);
371 if (fl % mp != 0) {
372 return null;
373 }
374 fl = fl / mp;
375 SortedMap<AlgebraicNumber<C>, Long> sm = rootCharacteristic(m.c);
376 if (sm == null) {
377 return null;
378 }
379 if (logger.isInfoEnabled()) {
380 logger.info("sm_alg,base,root = " + sm);
381 }
382 AlgebraicNumber<C> r = rf.getONE();
383 for (AlgebraicNumber<C> rp : sm.keySet()) {
384 //System.out.println("rp = " + rp);
385 long gl = sm.get(rp);
386 //System.out.println("gl = " + gl);
387 AlgebraicNumber<C> re = rp;
388 if (gl > 1) {
389 re = Power.<AlgebraicNumber<C>> positivePower(rp, gl);
390 }
391 //System.out.println("re = " + re);
392 r = r.multiply(re);
393 }
394 ExpVector e = ExpVector.create(1, 0, fl);
395 d.doPutToMap(e, r);
396 }
397 if (logger.isInfoEnabled()) {
398 logger.info("sm_alg,base,d = " + d);
399 }
400 return d;
401 }
402
403
404 /**
405 * GenPolynomial char-th root univariate polynomial with polynomial
406 * coefficients.
407 * @param P recursive univariate GenPolynomial.
408 * @return char-th_rootOf(P), or null if P is no char-th root.
409 */
410 @Override
411 public GenPolynomial<GenPolynomial<AlgebraicNumber<C>>> recursiveUnivariateRootCharacteristic(
412 GenPolynomial<GenPolynomial<AlgebraicNumber<C>>> P) {
413 if (P == null || P.isZERO()) {
414 return P;
415 }
416 GenPolynomialRing<GenPolynomial<AlgebraicNumber<C>>> pfac = P.ring;
417 if (pfac.nvar > 1) {
418 // basePthRoot not possible by return type
419 throw new IllegalArgumentException(P.getClass().getName()
420 + " only for univariate recursive polynomials");
421 }
422 RingFactory<GenPolynomial<AlgebraicNumber<C>>> rf = pfac.coFac;
423 if (rf.characteristic().signum() != 1) {
424 // basePthRoot not possible
425 throw new IllegalArgumentException(P.getClass().getName() + " only for char p > 0 " + rf);
426 }
427 long mp = rf.characteristic().longValue();
428 GenPolynomial<GenPolynomial<AlgebraicNumber<C>>> d = pfac.getZERO().clone();
429 for (Monomial<GenPolynomial<AlgebraicNumber<C>>> m : P) {
430 ExpVector f = m.e;
431 long fl = f.getVal(0);
432 if (fl % mp != 0) {
433 return null;
434 }
435 fl = fl / mp;
436 GenPolynomial<AlgebraicNumber<C>> r = rootCharacteristic(m.c);
437 if (r == null) {
438 return null;
439 }
440 ExpVector e = ExpVector.create(1, 0, fl);
441 d.doPutToMap(e, r);
442 }
443 return d;
444 }
445
446 }