Source code

001/*
002 * $Id: SquarefreeInfiniteAlgebraicFieldCharP.java 3290 2010-08-26 09:18:48Z
003 * kredel $
004 */
005
006package edu.jas.ufd;
007
008
009import java.util.ArrayList;
010import java.util.List;
011import java.util.Map;
012import java.util.SortedMap;
013import java.util.TreeMap;
014
015import org.apache.log4j.Logger;
016
017import edu.jas.gb.GroebnerBaseAbstract;
018import edu.jas.gb.GroebnerBaseSeq;
019import edu.jas.gb.Reduction;
020import edu.jas.gb.ReductionSeq;
021import edu.jas.poly.AlgebraicNumber;
022import edu.jas.poly.AlgebraicNumberRing;
023import edu.jas.poly.ExpVector;
024import edu.jas.poly.GenPolynomial;
025import edu.jas.poly.GenPolynomialRing;
026import edu.jas.poly.Monomial;
027import edu.jas.poly.PolyUtil;
028import edu.jas.structure.GcdRingElem;
029import edu.jas.structure.Power;
030import edu.jas.structure.RingFactory;
031
032
033/**
034 * Squarefree decomposition for algebraic extensions of infinite coefficient
035 * fields of characteristic p &gt; 0.
036 * @author Heinz Kredel
037 */
038
039public class SquarefreeInfiniteAlgebraicFieldCharP<C extends GcdRingElem<C>> extends
040                SquarefreeFieldCharP<AlgebraicNumber<C>> {
041
042
043    private static final Logger logger = Logger.getLogger(SquarefreeInfiniteAlgebraicFieldCharP.class);
044
045
046    //private final boolean debug = logger.isDebugEnabled();
047
048
049    /**
050     * Squarefree engine for infinite ring of characteristic p base coefficients.
051     */
052    protected final SquarefreeAbstract<C> aengine;
053
054
055    /**
056     * Constructor.
057     */
058    public SquarefreeInfiniteAlgebraicFieldCharP(RingFactory<AlgebraicNumber<C>> fac) {
059        super(fac);
060        // isFinite() predicate now present
061        if (fac.isFinite()) {
062            throw new IllegalArgumentException("fac must be in-finite");
063        }
064        AlgebraicNumberRing<C> afac = (AlgebraicNumberRing<C>) fac;
065        GenPolynomialRing<C> rfac = afac.ring;
066        //System.out.println("rfac = " + rfac);
067        //System.out.println("rfac = " + rfac.coFac);
068        aengine = SquarefreeFactory.<C> getImplementation(rfac);
069        //System.out.println("aengine = " + aengine);
070    }
071
072
073    /* --------- algebraic number char-th roots --------------------- */
074
075    /**
076     * Squarefree factors of a AlgebraicNumber.
077     * @param P AlgebraicNumber.
078     * @return [p_1 -&gt; e_1,...,p_k - &gt; e_k] with P = prod_{i=1, ..., k}
079     *         p_i**e_k.
080     */
081    @Override
082    public SortedMap<AlgebraicNumber<C>, Long> squarefreeFactors(AlgebraicNumber<C> P) {
083        if (P == null) {
084            throw new IllegalArgumentException(this.getClass().getName() + " P == null");
085        }
086        SortedMap<AlgebraicNumber<C>, Long> factors = new TreeMap<AlgebraicNumber<C>, Long>();
087        if (P.isZERO()) {
088            return factors;
089        }
090        if (P.isONE()) {
091            factors.put(P, 1L);
092            return factors;
093        }
094        GenPolynomial<C> an = P.val;
095        AlgebraicNumberRing<C> pfac = P.ring;
096        if (!an.isONE()) {
097            //System.out.println("an = " + an);
098            //System.out.println("aengine = " + aengine);
099            SortedMap<GenPolynomial<C>, Long> nfac = aengine.squarefreeFactors(an);
100            //System.out.println("nfac = " + nfac);
101            for (Map.Entry<GenPolynomial<C>, Long> me : nfac.entrySet()) {
102                GenPolynomial<C> nfp = me.getKey();
103                AlgebraicNumber<C> nf = new AlgebraicNumber<C>(pfac, nfp);
104                factors.put(nf, me.getValue()); //nfac.get(nfp));
105            }
106        }
107        if (factors.size() == 0) {
108            factors.put(P, 1L);
109        }
110        return factors;
111    }
112
113
114    /**
115     * Characteristics root of a AlgebraicNumber.
116     * @param P AlgebraicNumber.
117     * @return [p -&gt; k] if exists k with e=charactristic(P)*k and P = p**e,
118     *         else null.
119     */
120    public SortedMap<AlgebraicNumber<C>, Long> rootCharacteristic(AlgebraicNumber<C> P) {
121        if (P == null) {
122            throw new IllegalArgumentException(this.getClass().getName() + " P == null");
123        }
124        java.math.BigInteger c = P.ring.characteristic();
125        if (c.signum() == 0) {
126            return null;
127        }
128        SortedMap<AlgebraicNumber<C>, Long> root = new TreeMap<AlgebraicNumber<C>, Long>();
129        if (P.isZERO()) {
130            return root;
131        }
132        if (P.isONE()) {
133            root.put(P, 1L);
134            return root;
135        }
136        // generate system of equations
137        AlgebraicNumberRing<C> afac = P.ring;
138        long deg = afac.modul.degree(0);
139        int d = (int) deg;
140        String[] vn = GenPolynomialRing.newVars("c", d);
141        GenPolynomialRing<AlgebraicNumber<C>> pfac = new GenPolynomialRing<AlgebraicNumber<C>>(afac, d, vn);
142        List<GenPolynomial<AlgebraicNumber<C>>> uv = (List<GenPolynomial<AlgebraicNumber<C>>>) pfac
143                        .univariateList();
144        GenPolynomial<AlgebraicNumber<C>> cp = pfac.getZERO();
145        GenPolynomialRing<C> apfac = afac.ring;
146        long i = 0;
147        for (GenPolynomial<AlgebraicNumber<C>> pa : uv) {
148            GenPolynomial<C> ca = apfac.univariate(0, i++);
149            GenPolynomial<AlgebraicNumber<C>> pb = pa.multiply(new AlgebraicNumber<C>(afac, ca));
150            cp = cp.sum(pb);
151        }
152        GenPolynomial<AlgebraicNumber<C>> cpp = Power
153                        .<GenPolynomial<AlgebraicNumber<C>>> positivePower(cp, c);
154        if (logger.isInfoEnabled()) {
155            logger.info("cp   = " + cp);
156            logger.info("cp^p = " + cpp);
157            logger.info("P    = " + P);
158        }
159        GenPolynomialRing<C> ppfac = new GenPolynomialRing<C>(apfac.coFac, pfac);
160        List<GenPolynomial<C>> gl = new ArrayList<GenPolynomial<C>>();
161        if (deg == c.longValue() && afac.modul.length() == 2) {
162            logger.info("deg(" + deg + ") == char_p(" + c.longValue() + ")");
163            for (Monomial<AlgebraicNumber<C>> m : cpp) {
164                ExpVector f = m.e;
165                AlgebraicNumber<C> a = m.c;
166                //System.out.println("a  = " + a + " : " + a.toScriptFactory());
167                GenPolynomial<C> ap = a.val;
168                for (Monomial<C> ma : ap) {
169                    ExpVector e = ma.e;
170                    C cc = ma.c;
171                    C pc = P.val.coefficient(e);
172                    C cc1 = ((RingFactory<C>) pc.factory()).getONE();
173                    C pc1 = ((RingFactory<C>) pc.factory()).getZERO();
174                    //System.out.println("cc = " + cc + ", e = " + e);
175                    //System.out.println("pc = " + pc + " : " + cc.toScriptFactory());
176                    if (cc instanceof AlgebraicNumber && pc instanceof AlgebraicNumber) {
177                        throw new UnsupportedOperationException(
178                                        "case multiple algebraic extensions not implemented");
179                    } else if (cc instanceof Quotient && pc instanceof Quotient) {
180                        Quotient<C> ccp = (Quotient<C>) (Object) cc;
181                        Quotient<C> pcp = (Quotient<C>) (Object) pc;
182                        if (pcp.isConstant()) {
183                            //logger.error("finite field not allowed here " + afac.toScript());
184                            throw new ArithmeticException("finite field not allowed here " + afac.toScript());
185                        }
186                        //C dc = cc.divide(pc);
187                        Quotient<C> dcp = ccp.divide(pcp);
188                        if (dcp.isConstant()) { // not possible: dc.isConstant() 
189                            //System.out.println("dcp = " + dcp + " : " + cc.toScriptFactory()); //  + ", dc = " + dc);
190                            //if ( dcp.num.isConstant() ) 
191                            cc1 = cc;
192                            pc1 = pc;
193                        }
194                        GenPolynomial<C> r = new GenPolynomial<C>(ppfac, cc1, f);
195                        r = r.subtract(pc1);
196                        //System.out.println("r = " + r);
197                        gl.add(r);
198                    }
199                }
200            }
201        } else {
202            for (Monomial<AlgebraicNumber<C>> m : cpp) {
203                ExpVector f = m.e;
204                AlgebraicNumber<C> a = m.c;
205                //System.out.println("m = " + m);
206                GenPolynomial<C> ap = a.val;
207                for (Monomial<C> ma : ap) {
208                    ExpVector e = ma.e;
209                    C cc = ma.c;
210                    C pc = P.val.coefficient(e);
211                    GenPolynomial<C> r = new GenPolynomial<C>(ppfac, cc, f);
212                    r = r.subtract(pc);
213                    //System.out.println("r = " + r);
214                    gl.add(r);
215                }
216            }
217        }
218        if (logger.isInfoEnabled()) {
219            logger.info("equations = " + gl);
220        }
221        // solve system of equations and construct result
222        Reduction<C> red = new ReductionSeq<C>();
223        gl = red.irreducibleSet(gl);
224        GroebnerBaseAbstract<C> bb = new GroebnerBaseSeq<C>(); //GBFactory.<C>getImplementation();
225        int z = bb.commonZeroTest(gl);
226        if (z < 0) { // no solution
227            return null;
228        }
229        if (logger.isInfoEnabled()) {
230            logger.info("solution = " + gl);
231        }
232        GenPolynomial<C> car = apfac.getZERO();
233        for (GenPolynomial<C> pl : gl) {
234            if (pl.length() <= 1) {
235                continue;
236            }
237            if (pl.length() > 2) {
238                throw new IllegalArgumentException("dim > 0 not implemented " + pl);
239            }
240            //System.out.println("pl = " + pl);
241            ExpVector e = pl.leadingExpVector();
242            int[] v = e.dependencyOnVariables();
243            if (v == null || v.length == 0) {
244                continue;
245            }
246            int vi = v[0];
247            //System.out.println("vi = " + vi);
248            GenPolynomial<C> ca = apfac.univariate(0, deg - 1 - vi);
249            //System.out.println("ca = " + ca);
250            C tc = pl.trailingBaseCoefficient();
251            tc = tc.negate();
252            if (e.maxDeg() == c.longValue()) { // p-th root of tc ...
253                //SortedMap<C, Long> br = aengine.rootCharacteristic(tc);
254                SortedMap<C, Long> br = aengine.squarefreeFactors(tc);
255                //System.out.println("br = " + br);
256                if (br != null && br.size() > 0) {
257                    C cc = apfac.coFac.getONE();
258                    for (Map.Entry<C, Long> me : br.entrySet()) {
259                        C bc = me.getKey();
260                        long ll = me.getValue(); //br.get(bc);
261                        if (ll % c.longValue() == 0L) {
262                            long fl = ll / c.longValue();
263                            cc = cc.multiply(Power.<C> positivePower(bc, fl));
264                        } else { // fail ?
265                            cc = cc.multiply(bc);
266                        }
267                    }
268                    //System.out.println("cc = " + cc);
269                    tc = cc;
270                }
271            }
272            ca = ca.multiply(tc);
273            car = car.sum(ca);
274        }
275        AlgebraicNumber<C> rr = new AlgebraicNumber<C>(afac, car);
276        if (logger.isInfoEnabled()) {
277            logger.info("solution AN = " + rr);
278            //System.out.println("rr = " + rr);
279        }
280        root.put(rr, 1L);
281        return root;
282    }
283
284
285    /**
286     * GenPolynomial char-th root main variable.
287     * @param P univariate GenPolynomial with AlgebraicNumber coefficients.
288     * @return char-th_rootOf(P), or null, if P is no char-th root.
289     */
290    public GenPolynomial<AlgebraicNumber<C>> rootCharacteristic(GenPolynomial<AlgebraicNumber<C>> P) {
291        if (P == null || P.isZERO()) {
292            return P;
293        }
294        GenPolynomialRing<AlgebraicNumber<C>> pfac = P.ring;
295        if (pfac.nvar > 1) {
296            // go to recursion
297            GenPolynomialRing<AlgebraicNumber<C>> cfac = pfac.contract(1);
298            GenPolynomialRing<GenPolynomial<AlgebraicNumber<C>>> rfac = new GenPolynomialRing<GenPolynomial<AlgebraicNumber<C>>>(
299                            cfac, 1);
300            GenPolynomial<GenPolynomial<AlgebraicNumber<C>>> Pr = PolyUtil.<AlgebraicNumber<C>> recursive(
301                            rfac, P);
302            GenPolynomial<GenPolynomial<AlgebraicNumber<C>>> Prc = recursiveUnivariateRootCharacteristic(Pr);
303            if (Prc == null) {
304                return null;
305            }
306            GenPolynomial<AlgebraicNumber<C>> D = PolyUtil.<AlgebraicNumber<C>> distribute(pfac, Prc);
307            return D;
308        }
309        RingFactory<AlgebraicNumber<C>> rf = pfac.coFac;
310        if (rf.characteristic().signum() != 1) {
311            // basePthRoot not possible
312            throw new IllegalArgumentException(P.getClass().getName() + " only for ModInteger polynomials "
313                            + rf);
314        }
315        long mp = rf.characteristic().longValue();
316        GenPolynomial<AlgebraicNumber<C>> d = pfac.getZERO().copy();
317        for (Monomial<AlgebraicNumber<C>> m : P) {
318            ExpVector f = m.e;
319            long fl = f.getVal(0);
320            if (fl % mp != 0) {
321                return null;
322            }
323            fl = fl / mp;
324            SortedMap<AlgebraicNumber<C>, Long> sm = rootCharacteristic(m.c);
325            if (sm == null) {
326                return null;
327            }
328            if (logger.isInfoEnabled()) {
329                logger.info("sm_alg,root = " + sm);
330            }
331            AlgebraicNumber<C> r = rf.getONE();
332            for (Map.Entry<AlgebraicNumber<C>, Long> me : sm.entrySet()) {
333                AlgebraicNumber<C> rp = me.getKey();
334                long gl = me.getValue(); //sm.get(rp);
335                if (gl > 1) {
336                    rp = Power.<AlgebraicNumber<C>> positivePower(rp, gl);
337                }
338                r = r.multiply(rp);
339            }
340            ExpVector e = ExpVector.create(1, 0, fl);
341            d.doPutToMap(e, r);
342        }
343        logger.info("sm_alg,root,d = " + d);
344        return d;
345    }
346
347
348    /**
349     * GenPolynomial char-th root univariate polynomial.
350     * @param P GenPolynomial.
351     * @return char-th_rootOf(P).
352     */
353    @Override
354    public GenPolynomial<AlgebraicNumber<C>> baseRootCharacteristic(GenPolynomial<AlgebraicNumber<C>> P) {
355        if (P == null || P.isZERO()) {
356            return P;
357        }
358        GenPolynomialRing<AlgebraicNumber<C>> pfac = P.ring;
359        if (pfac.nvar > 1) {
360            // basePthRoot not possible by return type
361            throw new IllegalArgumentException(P.getClass().getName() + " only for univariate polynomials");
362        }
363        RingFactory<AlgebraicNumber<C>> rf = pfac.coFac;
364        if (rf.characteristic().signum() != 1) {
365            // basePthRoot not possible
366            throw new IllegalArgumentException(P.getClass().getName() + " only for char p > 0 " + rf);
367        }
368        long mp = rf.characteristic().longValue();
369        GenPolynomial<AlgebraicNumber<C>> d = pfac.getZERO().copy();
370        for (Monomial<AlgebraicNumber<C>> m : P) {
371            //System.out.println("m = " + m);
372            ExpVector f = m.e;
373            long fl = f.getVal(0);
374            if (fl % mp != 0) {
375                return null;
376            }
377            fl = fl / mp;
378            SortedMap<AlgebraicNumber<C>, Long> sm = rootCharacteristic(m.c);
379            if (sm == null) {
380                return null;
381            }
382            if (logger.isInfoEnabled()) {
383                logger.info("sm_alg,base,root = " + sm);
384            }
385            AlgebraicNumber<C> r = rf.getONE();
386            for (Map.Entry<AlgebraicNumber<C>, Long> me : sm.entrySet()) {
387                AlgebraicNumber<C> rp = me.getKey();
388                //System.out.println("rp = " + rp);
389                long gl = me.getValue(); //sm.get(rp);
390                //System.out.println("gl = " + gl);
391                AlgebraicNumber<C> re = rp;
392                if (gl > 1) {
393                    re = Power.<AlgebraicNumber<C>> positivePower(rp, gl);
394                }
395                //System.out.println("re = " + re);
396                r = r.multiply(re);
397            }
398            ExpVector e = ExpVector.create(1, 0, fl);
399            d.doPutToMap(e, r);
400        }
401        if (logger.isInfoEnabled()) {
402            logger.info("sm_alg,base,d = " + d);
403        }
404        return d;
405    }
406
407
408    /**
409     * GenPolynomial char-th root univariate polynomial with polynomial
410     * coefficients.
411     * @param P recursive univariate GenPolynomial.
412     * @return char-th_rootOf(P), or null if P is no char-th root.
413     */
414    @Override
415    public GenPolynomial<GenPolynomial<AlgebraicNumber<C>>> recursiveUnivariateRootCharacteristic(
416                    GenPolynomial<GenPolynomial<AlgebraicNumber<C>>> P) {
417        if (P == null || P.isZERO()) {
418            return P;
419        }
420        GenPolynomialRing<GenPolynomial<AlgebraicNumber<C>>> pfac = P.ring;
421        if (pfac.nvar > 1) {
422            // basePthRoot not possible by return type
423            throw new IllegalArgumentException(P.getClass().getName()
424                            + " only for univariate recursive polynomials");
425        }
426        RingFactory<GenPolynomial<AlgebraicNumber<C>>> rf = pfac.coFac;
427        if (rf.characteristic().signum() != 1) {
428            // basePthRoot not possible
429            throw new IllegalArgumentException(P.getClass().getName() + " only for char p > 0 " + rf);
430        }
431        long mp = rf.characteristic().longValue();
432        GenPolynomial<GenPolynomial<AlgebraicNumber<C>>> d = pfac.getZERO().copy();
433        for (Monomial<GenPolynomial<AlgebraicNumber<C>>> m : P) {
434            ExpVector f = m.e;
435            long fl = f.getVal(0);
436            if (fl % mp != 0) {
437                return null;
438            }
439            fl = fl / mp;
440            GenPolynomial<AlgebraicNumber<C>> r = rootCharacteristic(m.c);
441            if (r == null) {
442                return null;
443            }
444            ExpVector e = ExpVector.create(1, 0, fl);
445            d.doPutToMap(e, r);
446        }
447        return d;
448    }
449
450}