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