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