Source code

001/*
002 * $Id: PolyUfdUtil.java 5997 2020-03-17 15:34:31Z kredel $
003 */
004
005package edu.jas.ufd;
006
007
008import java.util.ArrayList;
009import java.util.Collection;
010import java.util.List;
011import java.util.Map;
012
013import org.apache.logging.log4j.LogManager;
014import org.apache.logging.log4j.Logger;
015
016import edu.jas.arith.BigInteger;
017import edu.jas.arith.BigRational;
018import edu.jas.poly.AlgebraicNumber;
019import edu.jas.poly.AlgebraicNumberRing;
020import edu.jas.poly.ExpVector;
021import edu.jas.poly.GenPolynomial;
022import edu.jas.poly.GenPolynomialRing;
023import edu.jas.poly.PolyUtil;
024import edu.jas.poly.TermOrderByName;
025import edu.jas.structure.GcdRingElem;
026import edu.jas.structure.RingElem;
027import edu.jas.structure.RingFactory;
028import edu.jas.structure.UnaryFunctor;
029import edu.jas.util.ListUtil;
030
031
032/**
033 * Polynomial ufd utilities. For example conversion between different
034 * representations and Kronecker substitution.
035 * @author Heinz Kredel
036 */
037
038public class PolyUfdUtil {
039
040
041    private static final Logger logger = LogManager.getLogger(PolyUfdUtil.class);
042
043
044    private static final boolean debug = logger.isDebugEnabled();
045
046
047    /**
048     * Integral polynomial from rational function coefficients. Represent as
049     * polynomial with integral polynomial coefficients by multiplication with
050     * the lcm of the numerators of the rational function coefficients.
051     * @param fac result polynomial factory.
052     * @param A polynomial with rational function coefficients to be converted.
053     * @return polynomial with integral polynomial coefficients.
054     */
055    public static <C extends GcdRingElem<C>> GenPolynomial<GenPolynomial<C>> integralFromQuotientCoefficients(
056                    GenPolynomialRing<GenPolynomial<C>> fac, GenPolynomial<Quotient<C>> A) {
057        GenPolynomial<GenPolynomial<C>> B = fac.getZERO().copy();
058        if (A == null || A.isZERO()) {
059            return B;
060        }
061        GenPolynomial<C> c = null;
062        GenPolynomial<C> d;
063        GenPolynomial<C> x;
064        GreatestCommonDivisor<C> ufd = new GreatestCommonDivisorSubres<C>();
065        int s = 0;
066        // lcm of denominators
067        for (Quotient<C> y : A.getMap().values()) {
068            x = y.den;
069            // c = lcm(c,x)
070            if (c == null) {
071                c = x;
072                s = x.signum();
073            } else {
074                d = ufd.gcd(c, x);
075                c = c.multiply(x.divide(d));
076            }
077        }
078        if (s < 0) {
079            c = c.negate();
080        }
081        for (Map.Entry<ExpVector, Quotient<C>> y : A.getMap().entrySet()) {
082            ExpVector e = y.getKey();
083            Quotient<C> a = y.getValue();
084            // p = n*(c/d)
085            GenPolynomial<C> b = c.divide(a.den);
086            GenPolynomial<C> p = a.num.multiply(b);
087            //B = B.sum( p, e ); // inefficient
088            B.doPutToMap(e, p);
089        }
090        return B;
091    }
092
093
094    /**
095     * Integral polynomial from rational function coefficients. Represent as
096     * polynomial with integral polynomial coefficients by multiplication with
097     * the lcm of the numerators of the rational function coefficients.
098     * @param fac result polynomial factory.
099     * @param L list of polynomial with rational function coefficients to be
100     *            converted.
101     * @return list of polynomials with integral polynomial coefficients.
102     */
103    public static <C extends GcdRingElem<C>> List<GenPolynomial<GenPolynomial<C>>> integralFromQuotientCoefficients(
104                    GenPolynomialRing<GenPolynomial<C>> fac, Collection<GenPolynomial<Quotient<C>>> L) {
105        if (L == null) {
106            return null;
107        }
108        List<GenPolynomial<GenPolynomial<C>>> list = new ArrayList<GenPolynomial<GenPolynomial<C>>>(L.size());
109        for (GenPolynomial<Quotient<C>> p : L) {
110            list.add(integralFromQuotientCoefficients(fac, p));
111        }
112        return list;
113    }
114
115
116    /**
117     * Rational function from integral polynomial coefficients. Represent as
118     * polynomial with type Quotient<C> coefficients.
119     * @param fac result polynomial factory.
120     * @param A polynomial with integral polynomial coefficients to be
121     *            converted.
122     * @return polynomial with type Quotient<C> coefficients.
123     */
124    public static <C extends GcdRingElem<C>> GenPolynomial<Quotient<C>> quotientFromIntegralCoefficients(
125                    GenPolynomialRing<Quotient<C>> fac, GenPolynomial<GenPolynomial<C>> A) {
126        GenPolynomial<Quotient<C>> B = fac.getZERO().copy();
127        if (A == null || A.isZERO()) {
128            return B;
129        }
130        RingFactory<Quotient<C>> cfac = fac.coFac;
131        QuotientRing<C> qfac = (QuotientRing<C>) cfac;
132        for (Map.Entry<ExpVector, GenPolynomial<C>> y : A.getMap().entrySet()) {
133            ExpVector e = y.getKey();
134            GenPolynomial<C> a = y.getValue();
135            Quotient<C> p = new Quotient<C>(qfac, a); // can not be zero
136            if (!p.isZERO()) {
137                //B = B.sum( p, e ); // inefficient
138                B.doPutToMap(e, p);
139            }
140        }
141        return B;
142    }
143
144
145    /**
146     * Rational function from integral polynomial coefficients. Represent as
147     * polynomial with type Quotient<C> coefficients.
148     * @param fac result polynomial factory.
149     * @param L list of polynomials with integral polynomial coefficients to be
150     *            converted.
151     * @return list of polynomials with type Quotient<C> coefficients.
152     */
153    public static <C extends GcdRingElem<C>> List<GenPolynomial<Quotient<C>>> quotientFromIntegralCoefficients(
154                    GenPolynomialRing<Quotient<C>> fac, Collection<GenPolynomial<GenPolynomial<C>>> L) {
155        if (L == null) {
156            return null;
157        }
158        List<GenPolynomial<Quotient<C>>> list = new ArrayList<GenPolynomial<Quotient<C>>>(L.size());
159        for (GenPolynomial<GenPolynomial<C>> p : L) {
160            list.add(quotientFromIntegralCoefficients(fac, p));
161        }
162        return list;
163    }
164
165
166    /**
167     * From BigInteger coefficients. Represent as polynomial with type
168     * GenPolynomial&lt;C&gt; coefficients, e.g. ModInteger or BigRational.
169     * @param fac result polynomial factory.
170     * @param A polynomial with GenPolynomial&lt;BigInteger&gt; coefficients to
171     *            be converted.
172     * @return polynomial with type GenPolynomial&lt;C&gt; coefficients.
173     */
174    public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> fromIntegerCoefficients(
175                    GenPolynomialRing<GenPolynomial<C>> fac, GenPolynomial<GenPolynomial<BigInteger>> A) {
176        GenPolynomial<GenPolynomial<C>> B = fac.getZERO().copy();
177        if (A == null || A.isZERO()) {
178            return B;
179        }
180        RingFactory<GenPolynomial<C>> cfac = fac.coFac;
181        GenPolynomialRing<C> rfac = (GenPolynomialRing<C>) cfac;
182        for (Map.Entry<ExpVector, GenPolynomial<BigInteger>> y : A.getMap().entrySet()) {
183            ExpVector e = y.getKey();
184            GenPolynomial<BigInteger> a = y.getValue();
185            GenPolynomial<C> p = PolyUtil.<C> fromIntegerCoefficients(rfac, a);
186            if (!p.isZERO()) {
187                //B = B.sum( p, e ); // inefficient
188                B.doPutToMap(e, p);
189            }
190        }
191        return B;
192    }
193
194
195    /**
196     * From BigInteger coefficients. Represent as polynomial with type
197     * GenPolynomial&lt;C&gt; coefficients, e.g. ModInteger or BigRational.
198     * @param fac result polynomial factory.
199     * @param L polynomial list with GenPolynomial&lt;BigInteger&gt;
200     *            coefficients to be converted.
201     * @return polynomial list with polynomials with type GenPolynomial&lt;C&gt;
202     *         coefficients.
203     */
204    public static <C extends RingElem<C>> List<GenPolynomial<GenPolynomial<C>>> fromIntegerCoefficients(
205                    GenPolynomialRing<GenPolynomial<C>> fac,
206                    List<GenPolynomial<GenPolynomial<BigInteger>>> L) {
207        List<GenPolynomial<GenPolynomial<C>>> K = null;
208        if (L == null) {
209            return K;
210        }
211        K = new ArrayList<GenPolynomial<GenPolynomial<C>>>(L.size());
212        if (L.size() == 0) {
213            return K;
214        }
215        for (GenPolynomial<GenPolynomial<BigInteger>> a : L) {
216            GenPolynomial<GenPolynomial<C>> b = fromIntegerCoefficients(fac, a);
217            K.add(b);
218        }
219        return K;
220    }
221
222
223    //------------------------------
224
225    /**
226     * BigInteger from BigRational coefficients. Represent as polynomial with
227     * type GenPolynomial&lt;BigInteger&gt; coefficients.
228     * @param fac result polynomial factory.
229     * @param A polynomial with GenPolynomial&lt;BigRational&gt; coefficients to
230     *            be converted.
231     * @return polynomial with type GenPolynomial&lt;BigInteger&gt;
232     *         coefficients.
233     */
234    public static GenPolynomial<GenPolynomial<BigInteger>> integerFromRationalCoefficients(
235                    GenPolynomialRing<GenPolynomial<BigInteger>> fac,
236                    GenPolynomial<GenPolynomial<BigRational>> A) {
237        GenPolynomial<GenPolynomial<BigInteger>> B = fac.getZERO().copy();
238        if (A == null || A.isZERO()) {
239            return B;
240        }
241        java.math.BigInteger gcd = null;
242        java.math.BigInteger lcm = null;
243        int sLCM = 0;
244        int sGCD = 0;
245        // lcm of all denominators
246        for (GenPolynomial<BigRational> av : A.getMap().values()) {
247            for (BigRational y : av.getMap().values()) {
248                java.math.BigInteger numerator = y.numerator();
249                java.math.BigInteger denominator = y.denominator();
250                // lcm = lcm(lcm,x)
251                if (lcm == null) {
252                    lcm = denominator;
253                    sLCM = denominator.signum();
254                } else {
255                    java.math.BigInteger d = lcm.gcd(denominator);
256                    lcm = lcm.multiply(denominator.divide(d));
257                }
258                // gcd = gcd(gcd,x)
259                if (gcd == null) {
260                    gcd = numerator;
261                    sGCD = numerator.signum();
262                } else {
263                    gcd = gcd.gcd(numerator);
264                }
265            }
266            //System.out.println("gcd = " + gcd + ", lcm = " + lcm);
267        }
268        if (sLCM < 0) {
269            lcm = lcm.negate();
270        }
271        if (sGCD < 0) {
272            gcd = gcd.negate();
273        }
274        //System.out.println("gcd** = " + gcd + ", lcm = " + lcm);
275        RingFactory<GenPolynomial<BigInteger>> cfac = fac.coFac;
276        GenPolynomialRing<BigInteger> rfac = (GenPolynomialRing<BigInteger>) cfac;
277        for (Map.Entry<ExpVector, GenPolynomial<BigRational>> y : A.getMap().entrySet()) {
278            ExpVector e = y.getKey();
279            GenPolynomial<BigRational> a = y.getValue();
280            // common denominator over all coefficients
281            GenPolynomial<BigInteger> p = PolyUtil.integerFromRationalCoefficients(rfac, gcd, lcm, a);
282            if (!p.isZERO()) {
283                //B = B.sum( p, e ); // inefficient
284                B.doPutToMap(e, p);
285            }
286        }
287        return B;
288    }
289
290
291    /**
292     * BigInteger from BigRational coefficients. Represent as polynomial with
293     * type GenPolynomial&lt;BigInteger&gt; coefficients.
294     * @param fac result polynomial factory.
295     * @param L polynomial list with GenPolynomial&lt;BigRational&gt;
296     *            coefficients to be converted.
297     * @return polynomial list with polynomials with type
298     *         GenPolynomial&lt;BigInteger&gt; coefficients.
299     */
300    public static List<GenPolynomial<GenPolynomial<BigInteger>>> integerFromRationalCoefficients(
301                    GenPolynomialRing<GenPolynomial<BigInteger>> fac,
302                    List<GenPolynomial<GenPolynomial<BigRational>>> L) {
303        List<GenPolynomial<GenPolynomial<BigInteger>>> K = null;
304        if (L == null) {
305            return K;
306        }
307        K = new ArrayList<GenPolynomial<GenPolynomial<BigInteger>>>(L.size());
308        if (L.isEmpty()) {
309            return K;
310        }
311        for (GenPolynomial<GenPolynomial<BigRational>> a : L) {
312            GenPolynomial<GenPolynomial<BigInteger>> b = integerFromRationalCoefficients(fac, a);
313            K.add(b);
314        }
315        return K;
316    }
317
318
319    /**
320     * Introduce lower variable. Represent as polynomial with type
321     * GenPolynomial&lt;C&gt; coefficients.
322     * @param rfac result polynomial factory.
323     * @param A polynomial to be extended.
324     * @return polynomial with type GenPolynomial&lt;C&gt; coefficients.
325     */
326    public static <C extends GcdRingElem<C>> GenPolynomial<GenPolynomial<C>> introduceLowerVariable(
327                    GenPolynomialRing<GenPolynomial<C>> rfac, GenPolynomial<C> A) {
328        if (A == null || rfac == null) {
329            return null;
330        }
331        GenPolynomial<GenPolynomial<C>> Pc = rfac.getONE().multiply(A);
332        if (Pc.isZERO()) {
333            return Pc;
334        }
335        Pc = PolyUtil.<C> switchVariables(Pc);
336        return Pc;
337    }
338
339
340    /**
341     * From AlgebraicNumber coefficients. Represent as polynomial with type
342     * GenPolynomial&lt;C&gt; coefficients, e.g. ModInteger or BigRational.
343     * @param rfac result polynomial factory.
344     * @param A polynomial with AlgebraicNumber coefficients to be converted.
345     * @param k for (y-k x) substitution.
346     * @return polynomial with type GenPolynomial&lt;C&gt; coefficients.
347     */
348    public static <C extends GcdRingElem<C>> GenPolynomial<GenPolynomial<C>> substituteFromAlgebraicCoefficients(
349                    GenPolynomialRing<GenPolynomial<C>> rfac, GenPolynomial<AlgebraicNumber<C>> A, long k) {
350        if (A == null || rfac == null) {
351            return null;
352        }
353        if (A.isZERO()) {
354            return rfac.getZERO();
355        }
356        // setup x - k alpha
357        GenPolynomialRing<AlgebraicNumber<C>> apfac = A.ring;
358        GenPolynomial<AlgebraicNumber<C>> x = apfac.univariate(0);
359        AlgebraicNumberRing<C> afac = (AlgebraicNumberRing<C>) A.ring.coFac;
360        AlgebraicNumber<C> alpha = afac.getGenerator();
361        AlgebraicNumber<C> ka = afac.fromInteger(k);
362        GenPolynomial<AlgebraicNumber<C>> s = x.subtract(ka.multiply(alpha)); // x - k alpha
363        //System.out.println("x - k alpha = " + s);
364        //System.out.println("s.ring = " + s.ring.toScript());
365        if (debug) {
366            logger.info("x - k alpha: " + s);
367        }
368        // substitute, convert and switch
369        //System.out.println("Asubs = " + A);
370        GenPolynomial<AlgebraicNumber<C>> B;
371        if (s.ring.nvar <= 1) {
372            B = PolyUtil.<AlgebraicNumber<C>> substituteMain(A, s);
373        } else {
374            B = PolyUtil.<AlgebraicNumber<C>> substituteUnivariateMult(A, s);
375        }
376        //System.out.println("Bsubs = " + B);
377        GenPolynomial<GenPolynomial<C>> Pc = PolyUtil.<C> fromAlgebraicCoefficients(rfac, B); // Q[alpha][x]
378        //System.out.println("Pc[a,x] = " + Pc);
379        Pc = PolyUtil.<C> switchVariables(Pc); // Q[x][alpha]
380        //System.out.println("Pc[x,a] = " + Pc);
381        return Pc;
382    }
383
384
385    /**
386     * Convert to AlgebraicNumber coefficients. Represent as polynomial with
387     * AlgebraicNumber<C> coefficients, C is e.g. ModInteger or BigRational.
388     * @param pfac result polynomial factory.
389     * @param A polynomial with GenPolynomial&lt;BigInteger&gt; coefficients to
390     *            be converted.
391     * @param k for (y-k x) substitution.
392     * @return polynomial with AlgebraicNumber&lt;C&gt; coefficients.
393     */
394    public static <C extends GcdRingElem<C>> GenPolynomial<AlgebraicNumber<C>> substituteConvertToAlgebraicCoefficients(
395                    GenPolynomialRing<AlgebraicNumber<C>> pfac, GenPolynomial<C> A, long k) {
396        if (A == null || pfac == null) {
397            return null;
398        }
399        if (A.isZERO()) {
400            return pfac.getZERO();
401        }
402        // convert to Q(alpha)[x]
403        GenPolynomial<AlgebraicNumber<C>> B = PolyUtil.<C> convertToAlgebraicCoefficients(pfac, A);
404        // setup x .+. k alpha for back substitution
405        GenPolynomial<AlgebraicNumber<C>> x = pfac.univariate(0);
406        AlgebraicNumberRing<C> afac = (AlgebraicNumberRing<C>) pfac.coFac;
407        AlgebraicNumber<C> alpha = afac.getGenerator();
408        AlgebraicNumber<C> ka = afac.fromInteger(k);
409        GenPolynomial<AlgebraicNumber<C>> s = x.sum(ka.multiply(alpha)); // x + k alpha
410        // substitute
411        //System.out.println("s.ring = " + s.ring.toScript());
412        GenPolynomial<AlgebraicNumber<C>> N;
413        if (s.ring.nvar <= 1) {
414            N = PolyUtil.<AlgebraicNumber<C>> substituteMain(B, s);
415        } else {
416            N = PolyUtil.<AlgebraicNumber<C>> substituteUnivariateMult(B, s);
417        }
418        return N;
419    }
420
421
422    /**
423     * Norm of a polynomial with AlgebraicNumber coefficients.
424     * @param A uni or multivariate polynomial from
425     *            GenPolynomial&lt;AlgebraicNumber&lt;C&gt;&gt;.
426     * @param k for (y - k x) substitution.
427     * @return norm(A) = res_x(A(x,y),m(x)) in GenPolynomialRing&lt;C&gt;.
428     */
429    public static <C extends GcdRingElem<C>> GenPolynomial<C> norm(GenPolynomial<AlgebraicNumber<C>> A,
430                    long k) {
431        if (A == null) {
432            return null;
433        }
434        GenPolynomialRing<AlgebraicNumber<C>> pfac = A.ring; // Q(alpha)[x]
435        //if (pfac.nvar > 1) {
436        //    throw new IllegalArgumentException("only for univariate polynomials");
437        //}
438        AlgebraicNumberRing<C> afac = (AlgebraicNumberRing<C>) pfac.coFac;
439        GenPolynomial<C> agen = afac.modul;
440        GenPolynomialRing<C> cfac = afac.ring;
441        if (A.isZERO()) {
442            return cfac.getZERO();
443        }
444        AlgebraicNumber<C> ldcf = A.leadingBaseCoefficient();
445        if (!ldcf.isONE()) {
446            A = A.monic();
447        }
448        GenPolynomialRing<GenPolynomial<C>> rfac = new GenPolynomialRing<GenPolynomial<C>>(cfac, pfac);
449        //System.out.println("rfac = " + rfac.toScript());
450
451        // transform minimal polynomial to bi-variate polynomial
452        GenPolynomial<GenPolynomial<C>> Ac = PolyUfdUtil.<C> introduceLowerVariable(rfac, agen);
453
454        // transform to bi-variate polynomial, 
455        // switching varaible sequence from Q[alpha][x] to Q[X][alpha]
456        GenPolynomial<GenPolynomial<C>> Pc = PolyUfdUtil.<C> substituteFromAlgebraicCoefficients(rfac, A, k);
457        Pc = PolyUtil.<C> monic(Pc);
458        //System.out.println("Pc = " + Pc.toScript() + " :: " + Pc.ring.toScript());
459
460        GreatestCommonDivisorSubres<C> engine = new GreatestCommonDivisorSubres<C>( /*cfac.coFac*/);
461        // = (GreatestCommonDivisorAbstract<C>)GCDFactory.<C>getImplementation( cfac.coFac );
462
463        GenPolynomial<GenPolynomial<C>> Rc = engine.recursiveUnivariateResultant(Pc, Ac);
464        //System.out.println("Rc = " + Rc.toScript());
465        GenPolynomial<C> res = Rc.leadingBaseCoefficient();
466        res = res.monic();
467        return res;
468    }
469
470
471    /**
472     * Norm of a polynomial with AlgebraicNumber coefficients.
473     * @param A polynomial from GenPolynomial&lt;AlgebraicNumber&lt;C&gt;&gt;.
474     * @return norm(A) = resultant_x( A(x,y), m(x) ) in K[y].
475     */
476    public static <C extends GcdRingElem<C>> GenPolynomial<C> norm(GenPolynomial<AlgebraicNumber<C>> A) {
477        return norm(A, 0L);
478    }
479
480
481    /**
482     * Ensure that the field property is determined. Checks if modul is
483     * irreducible and modifies the algebraic number ring.
484     * @param afac algebraic number ring.
485     */
486    public static <C extends GcdRingElem<C>> void ensureFieldProperty(AlgebraicNumberRing<C> afac) {
487        if (afac.getField() != -1) {
488            return;
489        }
490        if (!afac.ring.coFac.isField()) {
491            afac.setField(false);
492            return;
493        }
494        Factorization<C> mf = FactorFactory.<C> getImplementation(afac.ring);
495        if (mf.isIrreducible(afac.modul)) {
496            afac.setField(true);
497        } else {
498            afac.setField(false);
499        }
500    }
501
502
503    /**
504     * Construct a random irreducible univariate polynomial of degree d.
505     * @param cfac coefficient ring.
506     * @param degree of random polynomial.
507     * @return irreducible univariate polynomial.
508     */
509    public static <C extends GcdRingElem<C>> GenPolynomial<C> randomIrreduciblePolynomial(RingFactory<C> cfac,
510                    int degree) {
511        if (!cfac.isField()) {
512            throw new IllegalArgumentException("coefficient ring must be a field " + cfac);
513        }
514        GenPolynomialRing<C> ring = new GenPolynomialRing<C>(cfac, 1, TermOrderByName.INVLEX);
515        Factorization<C> eng = FactorFactory.<C> getImplementation(ring);
516        GenPolynomial<C> mod = ring.getZERO();
517        int k = cfac.characteristic().bitLength(); // log
518        if (k < 3) {
519            k = 7;
520        }
521        int l = degree / 2 + 2;
522        int d = degree + 1;
523        float q = 0.55f;
524        for (;;) {
525            mod = ring.random(k, l, d, q).monic();
526            if (mod.degree() != degree) {
527                mod = mod.sum(ring.univariate(0, degree));
528            }
529            if (mod.trailingBaseCoefficient().isZERO()) {
530                mod = mod.sum(ring.getONE());
531            }
532            //System.out.println("algebriacNumberField: mod = " + mod + ", k = " + k);
533            if (eng.isIrreducible(mod)) {
534                break;
535            }
536        }
537        return mod;
538    }
539
540
541    /**
542     * Construct an algebraic number field of degree d. Uses a random
543     * irreducible polynomial of degree d as modulus of the algebraic number
544     * ring.
545     * @param cfac coefficient ring.
546     * @param degree of random polynomial.
547     * @return algebraic number field.
548     */
549    public static <C extends GcdRingElem<C>> AlgebraicNumberRing<C> algebraicNumberField(RingFactory<C> cfac,
550                    int degree) {
551        GenPolynomial<C> mod = randomIrreduciblePolynomial(cfac, degree);
552        AlgebraicNumberRing<C> afac = new AlgebraicNumberRing<C>(mod, true);
553        return afac;
554    }
555
556
557    /**
558     * Kronecker substitution. Substitute x_i by x**d**(i-1) to construct a
559     * univariate polynomial.
560     * @param A polynomial to be converted.
561     * @return a univariate polynomial.
562     */
563    public static <C extends GcdRingElem<C>> GenPolynomial<C> substituteKronecker(GenPolynomial<C> A) {
564        if (A == null) {
565            return A;
566        }
567        long d = A.degree() + 1L;
568        return substituteKronecker(A, d);
569    }
570
571
572    /**
573     * Kronecker substitution. Substitute x_i by x**d**(i-1) to construct a
574     * univariate polynomial.
575     * @param A polynomial to be converted.
576     * @return a univariate polynomial.
577     */
578    public static <C extends GcdRingElem<C>> GenPolynomial<C> substituteKronecker(GenPolynomial<C> A,
579                    long d) {
580        if (A == null) {
581            return A;
582        }
583        RingFactory<C> cfac = A.ring.coFac;
584        GenPolynomialRing<C> ufac = new GenPolynomialRing<C>(cfac, 1);
585        GenPolynomial<C> B = ufac.getZERO().copy();
586        if (A.isZERO()) {
587            return B;
588        }
589        for (Map.Entry<ExpVector, C> y : A.getMap().entrySet()) {
590            ExpVector e = y.getKey();
591            C a = y.getValue();
592            long f = 0L;
593            long h = 1L;
594            for (int i = 0; i < e.length(); i++) {
595                long j = e.getVal(i) * h;
596                f += j;
597                h *= d;
598            }
599            ExpVector g = ExpVector.create(1, 0, f);
600            B.doPutToMap(g, a);
601        }
602        return B;
603    }
604
605
606    /**
607     * Kronecker substitution. Substitute x_i by x**d**(i-1) to construct
608     * univariate polynomials.
609     * @param A list of polynomials to be converted.
610     * @return a list of univariate polynomials.
611     */
612    public static <C extends GcdRingElem<C>> List<GenPolynomial<C>> substituteKronecker(
613                    List<GenPolynomial<C>> A, int d) {
614        if (A == null || A.get(0) == null) {
615            return null;
616        }
617        return ListUtil.<GenPolynomial<C>, GenPolynomial<C>> map(A, new SubstKronecker<C>(d));
618    }
619
620
621    /**
622     * Kronecker back substitution. Substitute x**d**(i-1) to x_i to construct a
623     * multivariate polynomial.
624     * @param A polynomial to be converted.
625     * @param fac result polynomial factory.
626     * @return a multivariate polynomial.
627     */
628    public static <C extends GcdRingElem<C>> GenPolynomial<C> backSubstituteKronecker(
629                    GenPolynomialRing<C> fac, GenPolynomial<C> A, long d) {
630        if (A == null) {
631            return A;
632        }
633        if (fac == null) {
634            throw new IllegalArgumentException("null factory not allowed ");
635        }
636        int n = fac.nvar;
637        GenPolynomial<C> B = fac.getZERO().copy();
638        if (A.isZERO()) {
639            return B;
640        }
641        for (Map.Entry<ExpVector, C> y : A.getMap().entrySet()) {
642            ExpVector e = y.getKey();
643            C a = y.getValue();
644            long f = e.getVal(0);
645            ExpVector g = ExpVector.create(n);
646            for (int i = 0; i < n; i++) {
647                long j = f % d;
648                f /= d;
649                g = g.subst(i, j);
650            }
651            B.doPutToMap(g, a);
652        }
653        return B;
654    }
655
656
657    /**
658     * Kronecker back substitution. Substitute x**d**(i-1) to x_i to construct
659     * multivariate polynomials.
660     * @param A list of polynomials to be converted.
661     * @param fac result polynomial factory.
662     * @return a list of multivariate polynomials.
663     */
664    public static <C extends GcdRingElem<C>> List<GenPolynomial<C>> backSubstituteKronecker(
665                    GenPolynomialRing<C> fac, List<GenPolynomial<C>> A, long d) {
666        return ListUtil.<GenPolynomial<C>, GenPolynomial<C>> map(A, new BackSubstKronecker<C>(fac, d));
667    }
668
669}
670
671
672/**
673 * Kronecker substitutuion functor.
674 */
675class SubstKronecker<C extends GcdRingElem<C>> implements UnaryFunctor<GenPolynomial<C>, GenPolynomial<C>> {
676
677
678    final long d;
679
680
681    public SubstKronecker(long d) {
682        this.d = d;
683    }
684
685
686    public GenPolynomial<C> eval(GenPolynomial<C> c) {
687        if (c == null) {
688            return null;
689        }
690        return PolyUfdUtil.<C> substituteKronecker(c, d);
691    }
692}
693
694
695/**
696 * Kronecker back substitutuion functor.
697 */
698class BackSubstKronecker<C extends GcdRingElem<C>>
699                implements UnaryFunctor<GenPolynomial<C>, GenPolynomial<C>> {
700
701
702    final long d;
703
704
705    final GenPolynomialRing<C> fac;
706
707
708    public BackSubstKronecker(GenPolynomialRing<C> fac, long d) {
709        this.d = d;
710        this.fac = fac;
711    }
712
713
714    public GenPolynomial<C> eval(GenPolynomial<C> c) {
715        if (c == null) {
716            return null;
717        }
718        return PolyUfdUtil.<C> backSubstituteKronecker(fac, c, d);
719    }
720}