Source code

001/*
002 * $Id: SquarefreeInfiniteFieldCharP.java 4965 2014-10-17 20:07:51Z 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.ExpVector;
015import edu.jas.poly.GenPolynomial;
016import edu.jas.poly.GenPolynomialRing;
017import edu.jas.poly.Monomial;
018import edu.jas.poly.PolyUtil;
019import edu.jas.structure.GcdRingElem;
020import edu.jas.structure.Power;
021import edu.jas.structure.RingFactory;
022
023
024/**
025 * Squarefree decomposition for infinite coefficient fields of characteristic p.
026 * @author Heinz Kredel
027 */
028
029public class SquarefreeInfiniteFieldCharP<C extends GcdRingElem<C>> extends SquarefreeFieldCharP<Quotient<C>> {
030
031
032    private static final Logger logger = Logger.getLogger(SquarefreeInfiniteFieldCharP.class);
033
034
035    //private final boolean debug = logger.isDebugEnabled();
036
037
038    /**
039     * Squarefree engine for infinite ring of characteristic p base
040     * coefficients.
041     */
042    protected final SquarefreeAbstract<C> qengine;
043
044
045    /**
046     * Constructor.
047     */
048    @SuppressWarnings("cast")
049    public SquarefreeInfiniteFieldCharP(RingFactory<Quotient<C>> fac) {
050        super(fac);
051        // isFinite() predicate now present
052        if (fac.isFinite()) {
053            throw new IllegalArgumentException("fac must be in-finite");
054        }
055        QuotientRing<C> qfac = (QuotientRing<C>) fac;
056        GenPolynomialRing<C> rfac = qfac.ring;
057        qengine = (SquarefreeAbstract) SquarefreeFactory.<C> getImplementation(rfac);
058        //qengine = new SquarefreeFiniteFieldCharP<C>(rfac.coFac);
059        //qengine = new SquarefreeInfiniteRingCharP<C>( rfac.coFac );
060    }
061
062
063    /* --------- quotient char-th roots --------------------- */
064
065
066    /**
067     * Squarefree factors of a Quotient.
068     * @param P Quotient.
069     * @return [p_1 -&gt; e_1,...,p_k - &gt; e_k] with P = prod_{i=1, ..., k}
070     *         p_i**e_k.
071     */
072    @Override
073    public SortedMap<Quotient<C>, Long> squarefreeFactors(Quotient<C> P) {
074        if (P == null) {
075            throw new IllegalArgumentException(this.getClass().getName() + " P == null");
076        }
077        SortedMap<Quotient<C>, Long> factors = new TreeMap<Quotient<C>, Long>();
078        if (P.isZERO()) {
079            return factors;
080        }
081        if (P.isONE()) {
082            factors.put(P, 1L);
083            return factors;
084        }
085        GenPolynomial<C> num = P.num;
086        GenPolynomial<C> den = P.den;
087        QuotientRing<C> pfac = P.ring;
088        GenPolynomial<C> one = pfac.ring.getONE();
089        if (!num.isONE()) {
090            SortedMap<GenPolynomial<C>, Long> nfac = qengine.squarefreeFactors(num);
091            //System.out.println("nfac = " + nfac);
092            for (Map.Entry<GenPolynomial<C>, Long> me : nfac.entrySet()) {
093                GenPolynomial<C> nfp = me.getKey();
094                Quotient<C> nf = new Quotient<C>(pfac, nfp);
095                factors.put(nf, me.getValue()); //nfac.get(nfp));
096            }
097        }
098        if (den.isONE()) {
099            if (factors.size() == 0) {
100                factors.put(P, 1L);
101            }
102            return factors;
103        }
104        SortedMap<GenPolynomial<C>, Long> dfac = qengine.squarefreeFactors(den);
105        //System.out.println("dfac = " + dfac);
106        for (Map.Entry<GenPolynomial<C>, Long> me : dfac.entrySet()) {
107            GenPolynomial<C> dfp = me.getKey();
108            Quotient<C> df = new Quotient<C>(pfac, one, dfp);
109            factors.put(df, me.getValue()); //dfac.get(dfp));
110        }
111        if (factors.size() == 0) {
112            factors.put(P, 1L);
113        }
114        return factors;
115    }
116
117
118    /**
119     * Characteristics root of a Quotient.
120     * @param P Quotient.
121     * @return [p -&gt; k] if exists k with e=charactristic(P)*k and P = p**e,
122     *         else null.
123     */
124    public SortedMap<Quotient<C>, Long> rootCharacteristic(Quotient<C> P) {
125        if (P == null) {
126            throw new IllegalArgumentException(this.getClass().getName() + " P == null");
127        }
128        java.math.BigInteger c = P.ring.characteristic();
129        if (c.signum() == 0) {
130            return null;
131        }
132        SortedMap<Quotient<C>, Long> root = new TreeMap<Quotient<C>, Long>();
133        if (P.isZERO()) {
134            return root;
135        }
136        if (P.isONE()) {
137            root.put(P, 1L);
138            return root;
139        }
140        SortedMap<Quotient<C>, Long> sf = squarefreeFactors(P);
141        if (sf.size() == 0) {
142            return null;
143        }
144        if (logger.isInfoEnabled()) {
145            logger.info("sf,quot = " + sf);
146        }
147        // better: test if sf.size() == 2 // no, since num and den factors 
148        Long k = null;
149        Long cl = c.longValue();
150        for (Map.Entry<Quotient<C>, Long> me : sf.entrySet()) {
151            Quotient<C> p = me.getKey();
152            //System.out.println("p = " + p);
153            if (p.isConstant()) { // todo: check for non-constants in coefficients
154                continue;
155            }
156            Long e = me.getValue(); //sf.get(p);
157            long E = e.longValue();
158            long r = E % cl;
159            if (r != 0) {
160                //System.out.println("r = " + r);
161                return null;
162            }
163            if (k == null) {
164                k = e;
165            } else if (k >= e) {
166                k = e;
167            }
168        }
169        if (k == null) {
170            k = 1L; //return null;
171        }
172        // now c divides all exponents of non constant elements
173        for (Map.Entry<Quotient<C>, Long> me : sf.entrySet()) {
174            Quotient<C> q = me.getKey();
175            Long e = me.getValue(); //sf.get(q);
176            //System.out.println("q = " + q + ", e = " + e);
177            if (e >= k) {
178                e = e / cl;
179                //q = Power.<Quotient<C>> positivePower(q, e);
180                root.put(q, e);
181            } else { // constant case
182                root.put(q, e);
183            }
184        }
185        //System.out.println("root = " + root);
186        return root;
187    }
188
189
190    /**
191     * GenPolynomial char-th root main variable.
192     * @param P univariate GenPolynomial with Quotient coefficients.
193     * @return char-th_rootOf(P), or null, if P is no char-th root.
194     */
195    public GenPolynomial<Quotient<C>> rootCharacteristic(GenPolynomial<Quotient<C>> P) {
196        if (P == null || P.isZERO()) {
197            return P;
198        }
199        GenPolynomialRing<Quotient<C>> pfac = P.ring;
200        if (pfac.nvar > 1) {
201            // go to recursion
202            GenPolynomialRing<Quotient<C>> cfac = pfac.contract(1);
203            GenPolynomialRing<GenPolynomial<Quotient<C>>> rfac = new GenPolynomialRing<GenPolynomial<Quotient<C>>>(
204                            cfac, 1);
205            GenPolynomial<GenPolynomial<Quotient<C>>> Pr = PolyUtil.<Quotient<C>> recursive(rfac, P);
206            GenPolynomial<GenPolynomial<Quotient<C>>> Prc = recursiveUnivariateRootCharacteristic(Pr);
207            if (Prc == null) {
208                return null;
209            }
210            GenPolynomial<Quotient<C>> D = PolyUtil.<Quotient<C>> distribute(pfac, Prc);
211            return D;
212        }
213        RingFactory<Quotient<C>> rf = pfac.coFac;
214        if (rf.characteristic().signum() != 1) {
215            // basePthRoot not possible
216            throw new IllegalArgumentException(P.getClass().getName() + " only for ModInteger polynomials "
217                            + rf);
218        }
219        long mp = rf.characteristic().longValue();
220        GenPolynomial<Quotient<C>> d = pfac.getZERO().copy();
221        for (Monomial<Quotient<C>> m : P) {
222            ExpVector f = m.e;
223            long fl = f.getVal(0);
224            if (fl % mp != 0) {
225                return null;
226            }
227            fl = fl / mp;
228            SortedMap<Quotient<C>, Long> sm = rootCharacteristic(m.c);
229            if (sm == null) {
230                return null;
231            }
232            if (logger.isInfoEnabled()) {
233                logger.info("sm,root = " + sm);
234            }
235            Quotient<C> r = rf.getONE();
236            for (Map.Entry<Quotient<C>, Long> me : sm.entrySet()) {
237                Quotient<C> rp = me.getKey();
238                long gl = me.getValue(); // sm.get(rp);
239                if (gl > 1) {
240                    rp = Power.<Quotient<C>> positivePower(rp, gl);
241                }
242                r = r.multiply(rp);
243            }
244            ExpVector e = ExpVector.create(1, 0, fl);
245            d.doPutToMap(e, r);
246        }
247        logger.info("sm,root,d = " + d);
248        return d;
249    }
250
251
252    /**
253     * GenPolynomial char-th root univariate polynomial.
254     * @param P GenPolynomial.
255     * @return char-th_rootOf(P).
256     */
257    @Override
258    public GenPolynomial<Quotient<C>> baseRootCharacteristic(GenPolynomial<Quotient<C>> P) {
259        if (P == null || P.isZERO()) {
260            return P;
261        }
262        GenPolynomialRing<Quotient<C>> pfac = P.ring;
263        if (pfac.nvar > 1) {
264            // basePthRoot not possible by return type
265            throw new IllegalArgumentException(P.getClass().getName() + " only for univariate polynomials");
266        }
267        RingFactory<Quotient<C>> rf = pfac.coFac;
268        if (rf.characteristic().signum() != 1) {
269            // basePthRoot not possible
270            throw new IllegalArgumentException(P.getClass().getName() + " only for char p > 0 " + rf);
271        }
272        long mp = rf.characteristic().longValue();
273        GenPolynomial<Quotient<C>> d = pfac.getZERO().copy();
274        for (Monomial<Quotient<C>> m : P) {
275            //System.out.println("m = " + m);
276            ExpVector f = m.e;
277            long fl = f.getVal(0);
278            if (fl % mp != 0) {
279                return null;
280            }
281            fl = fl / mp;
282            SortedMap<Quotient<C>, Long> sm = rootCharacteristic(m.c);
283            if (sm == null) {
284                return null;
285            }
286            if (logger.isInfoEnabled()) {
287                logger.info("sm,base,root = " + sm);
288            }
289            Quotient<C> r = rf.getONE();
290            for (Map.Entry<Quotient<C>, Long> me : sm.entrySet()) {
291                Quotient<C> rp = me.getKey();
292                //System.out.println("rp = " + rp);
293                long gl = me.getValue(); //sm.get(rp);
294                //System.out.println("gl = " + gl);
295                Quotient<C> re = rp;
296                if (gl > 1) {
297                    re = Power.<Quotient<C>> positivePower(rp, gl);
298                }
299                //System.out.println("re = " + re);
300                r = r.multiply(re);
301            }
302            ExpVector e = ExpVector.create(1, 0, fl);
303            d.doPutToMap(e, r);
304        }
305        if (logger.isInfoEnabled()) {
306            logger.info("sm,base,d = " + d);
307        }
308        return d;
309    }
310
311
312    /**
313     * GenPolynomial char-th root univariate polynomial with polynomial
314     * coefficients.
315     * @param P recursive univariate GenPolynomial.
316     * @return char-th_rootOf(P), or null if P is no char-th root.
317     */
318    @Override
319    public GenPolynomial<GenPolynomial<Quotient<C>>> recursiveUnivariateRootCharacteristic(
320                    GenPolynomial<GenPolynomial<Quotient<C>>> P) {
321        if (P == null || P.isZERO()) {
322            return P;
323        }
324        GenPolynomialRing<GenPolynomial<Quotient<C>>> pfac = P.ring;
325        if (pfac.nvar > 1) {
326            // basePthRoot not possible by return type
327            throw new IllegalArgumentException(P.getClass().getName()
328                            + " only for univariate recursive polynomials");
329        }
330        RingFactory<GenPolynomial<Quotient<C>>> rf = pfac.coFac;
331        if (rf.characteristic().signum() != 1) {
332            // basePthRoot not possible
333            throw new IllegalArgumentException(P.getClass().getName() + " only for char p > 0 " + rf);
334        }
335        long mp = rf.characteristic().longValue();
336        GenPolynomial<GenPolynomial<Quotient<C>>> d = pfac.getZERO().copy();
337        for (Monomial<GenPolynomial<Quotient<C>>> m : P) {
338            ExpVector f = m.e;
339            long fl = f.getVal(0);
340            if (fl % mp != 0) {
341                return null;
342            }
343            fl = fl / mp;
344            GenPolynomial<Quotient<C>> r = rootCharacteristic(m.c);
345            if (r == null) {
346                return null;
347            }
348            ExpVector e = ExpVector.create(1, 0, fl);
349            d.doPutToMap(e, r);
350        }
351        return d;
352    }
353
354}