Source code

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 * algorithm of Yun.
026 * @author Heinz Kredel
027 */
028
029public class SquarefreeFieldChar0Yun<C extends GcdRingElem<C>> extends SquarefreeFieldChar0<C> {
030
031
032    private static final Logger logger = LogManager.getLogger(SquarefreeFieldChar0Yun.class);
033
034
035    //private static final boolean debug = logger.isDebugEnabled();
036
037
038    /**
039     * Constructor.
040     */
041    public SquarefreeFieldChar0Yun(RingFactory<C> fac) {
042        super(fac);
043    }
044
045
046    /**
047     * Get the String representation.
048     * @see java.lang.Object#toString()
049     */
050    @Override
051    public String toString() {
052        return getClass().getName() + " with " + engine + " over " + coFac;
053    }
054
055
056    /**
057     * GenPolynomial polynomial squarefree factorization.
058     * @param A GenPolynomial.
059     * @return [p_1 -&gt; e_1, ..., p_k -&gt; e_k] with A = prod_{i=1,...,k}
060     *         p_i^{e_i} and p_i squarefree and gcd(p_i, p_j) = 1, for i != j.
061     */
062    @Override
063    public SortedMap<GenPolynomial<C>, Long> baseSquarefreeFactors(GenPolynomial<C> A) {
064        SortedMap<GenPolynomial<C>, Long> sfactors = new TreeMap<GenPolynomial<C>, Long>();
065        if (A == null || A.isZERO()) {
066            return sfactors;
067        }
068        if (A.isConstant()) {
069            sfactors.put(A, 1L);
070            return sfactors;
071        }
072        GenPolynomialRing<C> pfac = A.ring;
073        if (pfac.nvar > 1) {
074            throw new IllegalArgumentException(
075                            this.getClass().getName() + " only for univariate polynomials");
076        }
077        C ldbcf = A.leadingBaseCoefficient();
078        if (!ldbcf.isONE()) {
079            A = A.divide(ldbcf);
080            GenPolynomial<C> f1 = pfac.getONE().multiply(ldbcf);
081            //System.out.println("gcda sqf f1 = " + f1);
082            sfactors.put(f1, 1L);
083            ldbcf = pfac.coFac.getONE();
084        }
085        // divide by trailing term
086        ExpVector et = A.trailingExpVector();
087        if (!et.isZERO()) {
088            GenPolynomial<C> tr = pfac.valueOf(et);
089            logger.info("trailing term = {}", tr);
090            A = PolyUtil.<C> basePseudoDivide(A, tr);
091            long ep = et.getVal(0); // univariate
092            et = et.subst(0, 1);
093            tr = pfac.valueOf(et);
094            logger.info("tr, ep = {}, {}", tr, ep);
095            sfactors.put(tr, ep);
096            if (A.length() == 1) {
097                return sfactors;
098            }
099        }
100        GenPolynomial<C> Tp, T, W, Y, Z;
101        long k = 1L; //0L
102        Tp = PolyUtil.<C> baseDerivative(A);
103        T = engine.baseGcd(A, Tp);
104        T = T.monic();
105        if (T.isConstant()) {
106            sfactors.put(A, k);
107            return sfactors;
108        }
109        W = PolyUtil.<C> basePseudoDivide(A, T);
110        //if (W.isConstant()) {
111        //    return sfactors;
112        //}
113        Y = PolyUtil.<C> basePseudoDivide(Tp, T);
114        GenPolynomial<C> Wp = PolyUtil.<C> baseDerivative(W);
115        Z = Y.subtract(Wp);
116        while (!Z.isZERO()) {
117            GenPolynomial<C> g = engine.baseGcd(W, Z);
118            g = g.monic();
119            if (!g.isONE()) {
120                sfactors.put(g, k);
121            }
122            W = PolyUtil.<C> basePseudoDivide(W, g);
123            //System.out.println("W = " + W);
124            //System.out.println("g = " + g);
125            Y = PolyUtil.<C> basePseudoDivide(Z, g);
126            Wp = PolyUtil.<C> baseDerivative(W);
127            Z = Y.subtract(Wp);
128            k++;
129        }
130        logger.info("W, k = {}, {}", W, k);
131        if (!W.isONE()) {
132            sfactors.put(W, k);
133        }
134        return normalizeFactorization(sfactors);
135    }
136
137
138    /**
139     * GenPolynomial recursive univariate polynomial squarefree factorization.
140     * @param P recursive univariate GenPolynomial.
141     * @return [p_1 -&gt; e_1, ..., p_k -&gt; e_k] with P = prod_{i=1,...,k}
142     *         p_i^{e_i} and p_i squarefree and gcd(p_i, p_j) = 1, for i != j.
143     */
144    @Override
145    public SortedMap<GenPolynomial<GenPolynomial<C>>, Long> recursiveUnivariateSquarefreeFactors(
146                    GenPolynomial<GenPolynomial<C>> P) {
147        SortedMap<GenPolynomial<GenPolynomial<C>>, Long> sfactors = new TreeMap<GenPolynomial<GenPolynomial<C>>, Long>();
148        if (P == null || P.isZERO()) {
149            return sfactors;
150        }
151        GenPolynomialRing<GenPolynomial<C>> pfac = P.ring;
152        if (pfac.nvar > 1) {
153            // recursiveContent not possible by return type
154            throw new IllegalArgumentException(
155                            this.getClass().getName() + " only for univariate polynomials");
156        }
157        // if base coefficient ring is a field, make monic
158        GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) pfac.coFac;
159        C ldbcf = P.leadingBaseCoefficient().leadingBaseCoefficient();
160        if (!ldbcf.isONE()) {
161            GenPolynomial<C> lc = cfac.getONE().multiply(ldbcf);
162            GenPolynomial<GenPolynomial<C>> pl = pfac.getONE().multiply(lc);
163            sfactors.put(pl, 1L);
164            C li = ldbcf.inverse();
165            //System.out.println("li = " + li);
166            P = P.multiply(cfac.getONE().multiply(li));
167            //System.out.println("P,monic = " + P);
168            ldbcf = P.leadingBaseCoefficient().leadingBaseCoefficient();
169        }
170        // factors of content
171        GenPolynomial<C> Pc = engine.recursiveContent(P);
172        logger.info("recursiveContent = {}", Pc);
173        Pc = Pc.monic();
174        if (!Pc.isONE()) {
175            P = PolyUtil.<C> coefficientPseudoDivide(P, Pc);
176        }
177        SortedMap<GenPolynomial<C>, Long> rsf = squarefreeFactors(Pc);
178        logger.info("squarefreeFactors = {}", rsf);
179        // add factors of content
180        for (Map.Entry<GenPolynomial<C>, Long> me : rsf.entrySet()) {
181            GenPolynomial<C> c = me.getKey();
182            if (!c.isONE()) {
183                GenPolynomial<GenPolynomial<C>> cr = pfac.getONE().multiply(c);
184                Long rk = me.getValue();
185                sfactors.put(cr, rk);
186            }
187        }
188        // divide by trailing term
189        ExpVector et = P.trailingExpVector();
190        if (!et.isZERO()) {
191            GenPolynomial<GenPolynomial<C>> tr = pfac.valueOf(et);
192            logger.info("trailing term = {}", tr);
193            P = PolyUtil.<C> recursivePseudoDivide(P, tr);
194            long ep = et.getVal(0); // univariate
195            et = et.subst(0, 1);
196            tr = pfac.valueOf(et);
197            sfactors.put(tr, ep);
198            //P.length == 1 ??
199        }
200        // factors of recursive polynomial
201        GenPolynomial<GenPolynomial<C>> Tp, T, W, Y, Z;
202        long k = 1L; //0L
203        Tp = PolyUtil.<C> recursiveDerivative(P);
204        T = engine.recursiveUnivariateGcd(P, Tp);
205        T = PolyUtil.<C> monic(T);
206        if (T.isConstant()) {
207            sfactors.put(P, k);
208            return sfactors;
209        }
210        W = PolyUtil.<C> recursivePseudoDivide(P, T);
211        //if (W.isConstant()) {
212        //    return sfactors;
213        //}
214        Y = PolyUtil.<C> recursivePseudoDivide(Tp, T);
215        GenPolynomial<GenPolynomial<C>> Wp = PolyUtil.<C> recursiveDerivative(W);
216        Z = Y.subtract(Wp);
217
218        while (!Z.isZERO()) {
219            GenPolynomial<GenPolynomial<C>> g = engine.recursiveGcd(W, Z);
220            g = PolyUtil.<C> monic(g);
221            if (!g.isONE()) {
222                sfactors.put(g, k);
223            }
224            W = PolyUtil.<C> recursivePseudoDivide(W, g);
225            //System.out.println("W = " + W);
226            //System.out.println("g = " + g);
227            Y = PolyUtil.<C> recursivePseudoDivide(Z, g);
228            Wp = PolyUtil.<C> recursiveDerivative(W);
229            Z = Y.subtract(Wp);
230            k++;
231        }
232        logger.info("W, k = {}, {}", W, k);
233        if (!W.isONE()) {
234            sfactors.put(W, k);
235        }
236        return sfactors; //normalizeFactorization(sfactors);
237    }
238
239}