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