001 /*
002 * $Id: SquarefreeFieldChar0.java 3752 2011-08-27 19:23:49Z kredel $
003 */
004
005 package edu.jas.ufd;
006
007
008 import java.util.ArrayList;
009 import java.util.List;
010 import java.util.Map;
011 import java.util.SortedMap;
012 import java.util.TreeMap;
013
014 import org.apache.log4j.Logger;
015
016 import edu.jas.poly.GenPolynomial;
017 import edu.jas.poly.GenPolynomialRing;
018 import edu.jas.poly.PolyUtil;
019 import edu.jas.structure.GcdRingElem;
020 import edu.jas.structure.RingFactory;
021
022
023 /**
024 * Squarefree decomposition for coefficient fields of characteristic 0.
025 * @author Heinz Kredel
026 */
027
028 public class SquarefreeFieldChar0<C extends GcdRingElem<C>> extends SquarefreeAbstract<C> {
029
030
031 private static final Logger logger = Logger.getLogger(SquarefreeFieldChar0.class);
032
033
034 private final boolean debug = logger.isDebugEnabled();
035
036
037 /**
038 * Factory for field of characteristic 0 coefficients.
039 */
040 protected final RingFactory<C> coFac;
041
042
043 /**
044 * Constructor.
045 */
046 public SquarefreeFieldChar0(RingFactory<C> fac) {
047 super( GCDFactory.<C> getProxy(fac) );
048 if (!fac.isField()) {
049 throw new IllegalArgumentException("fac must be a field");
050 }
051 if (fac.characteristic().signum() != 0) {
052 throw new IllegalArgumentException("characterisic(fac) must be zero");
053 }
054 coFac = fac;
055 }
056
057
058 /**
059 * Get the String representation.
060 * @see java.lang.Object#toString()
061 */
062 @Override
063 public String toString() {
064 return getClass().getName() + " with " + engine + " over " + coFac;
065 }
066
067
068 /**
069 * GenPolynomial polynomial greatest squarefree divisor.
070 * @param P GenPolynomial.
071 * @return squarefree(pp(P)).
072 */
073 @Override
074 public GenPolynomial<C> baseSquarefreePart(GenPolynomial<C> P) {
075 if (P == null || P.isZERO()) {
076 return P;
077 }
078 GenPolynomialRing<C> pfac = P.ring;
079 if (pfac.nvar > 1) {
080 throw new IllegalArgumentException(this.getClass().getName() + " only for univariate polynomials");
081 }
082 GenPolynomial<C> pp = P.monic();
083 if (pp.isConstant()) {
084 return pp;
085 }
086 GenPolynomial<C> d = PolyUtil.<C> baseDeriviative(pp);
087 d = d.monic();
088 //System.out.println("d = " + d);
089 GenPolynomial<C> g = engine.baseGcd(pp, d);
090 g = g.monic();
091 GenPolynomial<C> q = PolyUtil.<C> basePseudoDivide(pp, g);
092 q = q.monic();
093 return q;
094 }
095
096
097 /**
098 * GenPolynomial test if is squarefree.
099 * @param P GenPolynomial.
100 * @return true if P is squarefree, else false.
101 */
102 public boolean isBaseSquarefree(GenPolynomial<C> P) {
103 if (P == null || P.isZERO()) {
104 return true;
105 }
106 GenPolynomialRing<C> pfac = P.ring;
107 if (pfac.nvar > 1) {
108 throw new IllegalArgumentException(this.getClass().getName() + " only for univariate polynomials");
109 }
110 GenPolynomial<C> pp = P.monic();
111 if (pp.isConstant()) {
112 return true;
113 }
114 GenPolynomial<C> d = PolyUtil.<C> baseDeriviative(pp);
115 d = d.monic();
116 //System.out.println("d = " + d);
117 GenPolynomial<C> g = engine.baseGcd(pp, d);
118 g = g.monic();
119 return g.isONE();
120 }
121
122
123 /**
124 * GenPolynomial polynomial squarefree factorization.
125 * @param A GenPolynomial.
126 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} p_i^{e_i}
127 * and p_i squarefree.
128 */
129 @Override
130 public SortedMap<GenPolynomial<C>, Long> baseSquarefreeFactors(GenPolynomial<C> A) {
131 SortedMap<GenPolynomial<C>, Long> sfactors = new TreeMap<GenPolynomial<C>, Long>();
132 if (A == null || A.isZERO()) {
133 return sfactors;
134 }
135 if (A.isConstant()) {
136 sfactors.put(A, 1L);
137 return sfactors;
138 }
139 GenPolynomialRing<C> pfac = A.ring;
140 if (pfac.nvar > 1) {
141 throw new IllegalArgumentException(this.getClass().getName() + " only for univariate polynomials");
142 }
143 C ldbcf = A.leadingBaseCoefficient();
144 if (!ldbcf.isONE()) {
145 A = A.divide(ldbcf);
146 GenPolynomial<C> f1 = pfac.getONE().multiply(ldbcf);
147 //System.out.println("gcda sqf f1 = " + f1);
148 sfactors.put(f1, 1L);
149 ldbcf = pfac.coFac.getONE();
150 }
151 GenPolynomial<C> T0 = A;
152 GenPolynomial<C> Tp;
153 GenPolynomial<C> T = null;
154 GenPolynomial<C> V = null;
155 long k = 0L;
156 boolean init = true;
157 while (true) {
158 if (init) {
159 if (T0.isConstant() || T0.isZERO()) {
160 break;
161 }
162 Tp = PolyUtil.<C> baseDeriviative(T0);
163 T = engine.baseGcd(T0, Tp);
164 T = T.monic();
165 V = PolyUtil.<C> basePseudoDivide(T0, T);
166 //System.out.println("iT0 = " + T0);
167 //System.out.println("iTp = " + Tp);
168 //System.out.println("iT = " + T);
169 //System.out.println("iV = " + V);
170 k = 0L;
171 init = false;
172 }
173 if (V.isConstant()) {
174 break;
175 }
176 k++;
177 GenPolynomial<C> W = engine.baseGcd(T, V);
178 W = W.monic();
179 GenPolynomial<C> z = PolyUtil.<C> basePseudoDivide(V, W);
180 //System.out.println("W = " + W);
181 //System.out.println("z = " + z);
182 V = W;
183 T = PolyUtil.<C> basePseudoDivide(T, V);
184 //System.out.println("V = " + V);
185 //System.out.println("T = " + T);
186 if (z.degree(0) > 0) {
187 if (ldbcf.isONE() && !z.leadingBaseCoefficient().isONE()) {
188 z = z.monic();
189 logger.info("z,monic = " + z);
190 }
191 sfactors.put(z, k);
192 }
193 }
194 // look, a stupid error:
195 // if ( pfac.coFac.isField() && !ldbcf.isONE() ) {
196 // GenPolynomial<C> f1 = sfactors.firstKey();
197 // long e1 = sfactors.remove(f1);
198 // System.out.println("gcda sqf c = " + c);
199 // f1 = f1.multiply(c);
200 // //System.out.println("gcda sqf f1e = " + f1);
201 // sfactors.put(f1,e1);
202 // }
203 return sfactors;
204 }
205
206
207 /**
208 * GenPolynomial recursive univariate polynomial greatest squarefree
209 * divisor.
210 * @param P recursive univariate GenPolynomial.
211 * @return squarefree(pp(P)).
212 */
213 @Override
214 public GenPolynomial<GenPolynomial<C>> recursiveUnivariateSquarefreePart(GenPolynomial<GenPolynomial<C>> P) {
215 if (P == null || P.isZERO()) {
216 return P;
217 }
218 GenPolynomialRing<GenPolynomial<C>> pfac = P.ring;
219 if (pfac.nvar > 1) {
220 throw new IllegalArgumentException(this.getClass().getName() + " only for multivariate polynomials");
221 }
222 GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) pfac.coFac;
223 // squarefree content
224 GenPolynomial<GenPolynomial<C>> pp = P;
225 GenPolynomial<C> Pc = engine.recursiveContent(P);
226 Pc = Pc.monic();
227 if (!Pc.isONE()) {
228 pp = PolyUtil.<C> coefficientPseudoDivide(pp, Pc);
229 //System.out.println("pp,sqp = " + pp);
230 GenPolynomial<C> Pr = squarefreePart(Pc);
231 Pr = Pr.monic();
232 //System.out.println("Pr,sqp = " + Pr);
233 }
234 if (pp.leadingExpVector().getVal(0) < 1) {
235 //System.out.println("pp = " + pp);
236 //System.out.println("Pc = " + Pc);
237 return pp.multiply(Pc);
238 }
239 GenPolynomial<GenPolynomial<C>> d = PolyUtil.<C> recursiveDeriviative(pp);
240 //System.out.println("d = " + d);
241 GenPolynomial<GenPolynomial<C>> g = engine.recursiveUnivariateGcd(pp, d);
242 //System.out.println("g,rec = " + g);
243 g = PolyUtil.<C> monic(g);
244 GenPolynomial<GenPolynomial<C>> q = PolyUtil.<C> recursivePseudoDivide(pp, g);
245 q = PolyUtil.<C> monic(q);
246 return q.multiply(Pc);
247 }
248
249
250 /**
251 * GenPolynomial test if is squarefree.
252 * @param P GenPolynomial.
253 * @return true if P is squarefree, else false.
254 */
255 public boolean isRecursiveUnivariateSquarefree(GenPolynomial<GenPolynomial<C>> P) {
256 if (P == null || P.isZERO()) {
257 return true;
258 }
259 GenPolynomialRing<GenPolynomial<C>> pfac = P.ring;
260 if (pfac.nvar > 1) {
261 throw new IllegalArgumentException(this.getClass().getName() + " only for multivariate polynomials");
262 }
263 GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) pfac.coFac;
264 // squarefree content
265 GenPolynomial<GenPolynomial<C>> pp = P;
266 GenPolynomial<C> Pc = engine.recursiveContent(P);
267 if ( logger.isInfoEnabled() ) {
268 logger.info("recursiveContent = " + Pc);
269 }
270 if ( ! isSquarefree(Pc) ) {
271 return false;
272 }
273 Pc = Pc.monic();
274 if (!Pc.isONE()) {
275 pp = PolyUtil.<C> coefficientPseudoDivide(pp, Pc);
276 //System.out.println("pp,sqp = " + pp);
277 }
278 if (pp.leadingExpVector().getVal(0) <= 1) {
279 //System.out.println("pp = " + pp);
280 //System.out.println("Pc = " + Pc);
281 return true;
282 }
283 GenPolynomial<GenPolynomial<C>> d = PolyUtil.<C> recursiveDeriviative(pp);
284 //System.out.println("d = " + d);
285 GenPolynomial<GenPolynomial<C>> g = engine.recursiveUnivariateGcd(pp, d);
286 if ( logger.isInfoEnabled() ) {
287 logger.info("gcd = " + g);
288 }
289 //System.out.println("g,rec = " + g);
290 g = PolyUtil.<C> monic(g);
291 return g.isONE();
292 }
293
294
295 /**
296 * GenPolynomial recursive univariate polynomial squarefree factorization.
297 * @param P recursive univariate GenPolynomial.
298 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} p_i^{e_i}
299 * and p_i squarefree.
300 */
301 @Override
302 public SortedMap<GenPolynomial<GenPolynomial<C>>, Long> recursiveUnivariateSquarefreeFactors(
303 GenPolynomial<GenPolynomial<C>> P) {
304 SortedMap<GenPolynomial<GenPolynomial<C>>, Long> sfactors = new TreeMap<GenPolynomial<GenPolynomial<C>>, Long>();
305 if (P == null || P.isZERO()) {
306 return sfactors;
307 }
308 GenPolynomialRing<GenPolynomial<C>> pfac = P.ring;
309 if (pfac.nvar > 1) {
310 // recursiveContent not possible by return type
311 throw new IllegalArgumentException(this.getClass().getName() + " only for univariate polynomials");
312 }
313 // if base coefficient ring is a field, make monic
314 GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) pfac.coFac;
315 C ldbcf = P.leadingBaseCoefficient().leadingBaseCoefficient();
316 if (!ldbcf.isONE()) {
317 GenPolynomial<C> lc = cfac.getONE().multiply(ldbcf);
318 GenPolynomial<GenPolynomial<C>> pl = pfac.getONE().multiply(lc);
319 sfactors.put(pl, 1L);
320 C li = ldbcf.inverse();
321 //System.out.println("li = " + li);
322 P = P.multiply(cfac.getONE().multiply(li));
323 //System.out.println("P,monic = " + P);
324 ldbcf = P.leadingBaseCoefficient().leadingBaseCoefficient();
325 }
326 // factors of content
327 GenPolynomial<C> Pc = engine.recursiveContent(P);
328 if ( logger.isInfoEnabled() ) {
329 logger.info("recursiveContent = " + Pc);
330 }
331 Pc = Pc.monic();
332 if (!Pc.isONE()) {
333 P = PolyUtil.<C> coefficientPseudoDivide(P, Pc);
334 }
335 SortedMap<GenPolynomial<C>, Long> rsf = squarefreeFactors(Pc);
336 if ( logger.isInfoEnabled() ) {
337 logger.info("squarefreeFactors = " + rsf);
338 }
339 // add factors of content
340 for (GenPolynomial<C> c : rsf.keySet()) {
341 if (!c.isONE()) {
342 GenPolynomial<GenPolynomial<C>> cr = pfac.getONE().multiply(c);
343 Long rk = rsf.get(c);
344 sfactors.put(cr, rk);
345 }
346 }
347
348 // factors of recursive polynomial
349 GenPolynomial<GenPolynomial<C>> T0 = P;
350 GenPolynomial<GenPolynomial<C>> Tp;
351 GenPolynomial<GenPolynomial<C>> T = null;
352 GenPolynomial<GenPolynomial<C>> V = null;
353 long k = 0L;
354 boolean init = true;
355 while (true) {
356 if (init) {
357 if (T0.isConstant() || T0.isZERO()) {
358 break;
359 }
360 Tp = PolyUtil.<C> recursiveDeriviative(T0);
361 T = engine.recursiveUnivariateGcd(T0, Tp);
362 T = PolyUtil.<C> monic(T);
363 V = PolyUtil.<C> recursivePseudoDivide(T0, T);
364 //System.out.println("iT0 = " + T0);
365 //System.out.println("iTp = " + Tp);
366 //System.out.println("iT = " + T);
367 //System.out.println("iV = " + V);
368 k = 0L;
369 init = false;
370 }
371 if (V.isConstant()) {
372 break;
373 }
374 k++;
375 GenPolynomial<GenPolynomial<C>> W = engine.recursiveUnivariateGcd(T, V);
376 W = PolyUtil.<C> monic(W);
377 GenPolynomial<GenPolynomial<C>> z = PolyUtil.<C> recursivePseudoDivide(V, W);
378 //System.out.println("W = " + W);
379 //System.out.println("z = " + z);
380 V = W;
381 T = PolyUtil.<C> recursivePseudoDivide(T, V);
382 //System.out.println("V = " + V);
383 //System.out.println("T = " + T);
384 //was: if ( z.degree(0) > 0 ) {
385 if (!z.isONE() && !z.isZERO()) {
386 if (ldbcf.isONE()) {
387 z = PolyUtil.<C> monic(z);
388 logger.info("z,monic = " + z);
389 }
390 sfactors.put(z, k);
391 }
392 }
393 return sfactors;
394 }
395
396
397 /**
398 * GenPolynomial greatest squarefree divisor.
399 * @param P GenPolynomial.
400 * @return squarefree(pp(P)).
401 */
402 @Override
403 public GenPolynomial<C> squarefreePart(GenPolynomial<C> P) {
404 if (P == null) {
405 throw new IllegalArgumentException(this.getClass().getName() + " P != null");
406 }
407 if (P.isZERO()) {
408 return P;
409 }
410 GenPolynomialRing<C> pfac = P.ring;
411 if (pfac.nvar <= 1) {
412 return baseSquarefreePart(P);
413 }
414 GenPolynomialRing<C> cfac = pfac.contract(1);
415 GenPolynomialRing<GenPolynomial<C>> rfac = new GenPolynomialRing<GenPolynomial<C>>(cfac, 1);
416
417 GenPolynomial<GenPolynomial<C>> Pr = PolyUtil.<C> recursive(rfac, P);
418 GenPolynomial<C> Pc = engine.recursiveContent(Pr);
419 Pr = PolyUtil.<C> coefficientPseudoDivide(Pr, Pc);
420 GenPolynomial<C> Ps = squarefreePart(Pc);
421 if ( logger.isInfoEnabled() ) {
422 logger.info("content = " + Pc + ", squarefreePart = " + Ps);
423 }
424 GenPolynomial<GenPolynomial<C>> PP = recursiveUnivariateSquarefreePart(Pr);
425 GenPolynomial<GenPolynomial<C>> PS = PP.multiply(Ps);
426 GenPolynomial<C> D = PolyUtil.<C> distribute(pfac, PS);
427 if ( logger.isInfoEnabled() ) {
428 logger.info("univRec = " + Pr + ", squarefreePart = " + PP);
429 }
430 return D;
431 }
432
433
434 /**
435 * GenPolynomial test if is squarefree.
436 * @param P GenPolynomial.
437 * @return true if P is squarefree, else false.
438 */
439 @Override
440 public boolean isSquarefree(GenPolynomial<C> P) {
441 if (P == null) {
442 throw new IllegalArgumentException(this.getClass().getName() + " P != null");
443 }
444 if (P.isZERO()) {
445 return true;
446 }
447 GenPolynomialRing<C> pfac = P.ring;
448 if (pfac.nvar <= 1) {
449 return isBaseSquarefree(P);
450 }
451 GenPolynomialRing<C> cfac = pfac.contract(1);
452 GenPolynomialRing<GenPolynomial<C>> rfac = new GenPolynomialRing<GenPolynomial<C>>(cfac, 1);
453 GenPolynomial<GenPolynomial<C>> Pr = PolyUtil.<C> recursive(rfac, P);
454 return isRecursiveUnivariateSquarefree(Pr);
455 }
456
457
458 /**
459 * GenPolynomial squarefree factorization.
460 * @param P GenPolynomial.
461 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} p_i^{e_i}
462 * and p_i squarefree.
463 */
464 @Override
465 public SortedMap<GenPolynomial<C>, Long> squarefreeFactors(GenPolynomial<C> P) {
466 if (P == null) {
467 throw new IllegalArgumentException(this.getClass().getName() + " P != null");
468 }
469 GenPolynomialRing<C> pfac = P.ring;
470 if (pfac.nvar <= 1) {
471 return baseSquarefreeFactors(P);
472 }
473 SortedMap<GenPolynomial<C>, Long> sfactors = new TreeMap<GenPolynomial<C>, Long>();
474 if (P.isZERO()) {
475 return sfactors;
476 }
477 GenPolynomialRing<C> cfac = pfac.contract(1);
478 GenPolynomialRing<GenPolynomial<C>> rfac = new GenPolynomialRing<GenPolynomial<C>>(cfac, 1);
479
480 GenPolynomial<GenPolynomial<C>> Pr = PolyUtil.<C> recursive(rfac, P);
481 SortedMap<GenPolynomial<GenPolynomial<C>>, Long> PP = recursiveUnivariateSquarefreeFactors(Pr);
482
483 for (Map.Entry<GenPolynomial<GenPolynomial<C>>, Long> m : PP.entrySet()) {
484 Long i = m.getValue();
485 GenPolynomial<GenPolynomial<C>> Dr = m.getKey();
486 GenPolynomial<C> D = PolyUtil.<C> distribute(pfac, Dr);
487 sfactors.put(D, i);
488 }
489 if ( logger.isInfoEnabled() ) {
490 logger.info("squarefreeFactors(" + P + ") = " + sfactors);
491 }
492 return sfactors;
493 }
494
495
496 /**
497 * Coefficients squarefree factorization.
498 * @param P coefficient.
499 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} p_i^{e_i}
500 * and p_i squarefree.
501 */
502 public SortedMap<C, Long> squarefreeFactors(C P) {
503 throw new UnsupportedOperationException("method not implemented");
504 }
505
506 }