Source code

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