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