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