Source code

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