Source code

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