001/*
002 * $Id$
003 */
004
005package edu.jas.poly;
006
007
008import java.util.ArrayList;
009import java.util.List;
010import java.util.Map;
011import java.util.SortedMap;
012import java.util.TreeMap;
013
014import org.apache.logging.log4j.LogManager;
015import org.apache.logging.log4j.Logger;
016
017import edu.jas.arith.BigComplex;
018import edu.jas.arith.BigDecimal;
019import edu.jas.arith.BigDecimalComplex;
020import edu.jas.arith.BigInteger;
021import edu.jas.arith.BigRational;
022import edu.jas.arith.ModInteger;
023import edu.jas.arith.ModIntegerRing;
024import edu.jas.arith.Modular;
025import edu.jas.arith.ModularRingFactory;
026import edu.jas.arith.Product;
027import edu.jas.arith.ProductRing;
028import edu.jas.arith.Rational;
029import edu.jas.arith.Roots;
030import edu.jas.structure.Element;
031import edu.jas.structure.GcdRingElem;
032import edu.jas.structure.RingElem;
033import edu.jas.structure.RingFactory;
034import edu.jas.structure.StarRingElem;
035import edu.jas.structure.UnaryFunctor;
036import edu.jas.util.ListUtil;
037
038
039/**
040 * Polynomial utilities, for example conversion between different
041 * representations, evaluation and interpolation.
042 * @author Heinz Kredel
043 */
044
045public class PolyUtil {
046
047
048    private static final Logger logger = LogManager.getLogger(PolyUtil.class);
049
050
051    private static final boolean debug = logger.isDebugEnabled();
052
053
054    /**
055     * Recursive representation. Represent as polynomial in i variables with
056     * coefficients in n-i variables. Works for arbitrary term orders.
057     * @param <C> coefficient type.
058     * @param rfac recursive polynomial ring factory.
059     * @param A polynomial to be converted.
060     * @return Recursive representations of this in the ring rfac.
061     */
062    public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> recursive(
063                    GenPolynomialRing<GenPolynomial<C>> rfac, GenPolynomial<C> A) {
064
065        GenPolynomial<GenPolynomial<C>> B = rfac.getZERO().copy();
066        if (A.isZERO()) {
067            return B;
068        }
069        int i = rfac.nvar;
070        GenPolynomial<C> zero = rfac.getZEROCoefficient();
071        Map<ExpVector, GenPolynomial<C>> Bv = B.val; //getMap();
072        for (Map.Entry<ExpVector, C> y : A.getMap().entrySet()) {
073            ExpVector e = y.getKey();
074            C a = y.getValue();
075            ExpVector f = e.contract(0, i);
076            ExpVector g = e.contract(i, e.length() - i);
077            GenPolynomial<C> p = Bv.get(f);
078            if (p == null) {
079                p = zero;
080            }
081            p = p.sum(a, g);
082            Bv.put(f, p);
083        }
084        return B;
085    }
086
087
088    /**
089     * Distribute a recursive polynomial to a generic polynomial. Works for
090     * arbitrary term orders.
091     * @param <C> coefficient type.
092     * @param dfac combined polynomial ring factory of coefficients and this.
093     * @param B polynomial to be converted.
094     * @return distributed polynomial.
095     */
096    public static <C extends RingElem<C>> GenPolynomial<C> distribute(GenPolynomialRing<C> dfac,
097                    GenPolynomial<GenPolynomial<C>> B) {
098        GenPolynomial<C> C = dfac.getZERO().copy();
099        if (B.isZERO()) {
100            return C;
101        }
102        Map<ExpVector, C> Cm = C.val; //getMap();
103        for (Map.Entry<ExpVector, GenPolynomial<C>> y : B.getMap().entrySet()) {
104            ExpVector e = y.getKey();
105            GenPolynomial<C> A = y.getValue();
106            for (Map.Entry<ExpVector, C> x : A.val.entrySet()) {
107                ExpVector f = x.getKey();
108                C b = x.getValue();
109                ExpVector g = e.combine(f);
110                assert (Cm.get(g) == null);
111                Cm.put(g, b);
112            }
113        }
114        return C;
115    }
116
117
118    /**
119     * Recursive representation. Represent as polynomials in i variables with
120     * coefficients in n-i variables. Works for arbitrary term orders.
121     * @param <C> coefficient type.
122     * @param rfac recursive polynomial ring factory.
123     * @param L list of polynomials to be converted.
124     * @return Recursive representations of the list in the ring rfac.
125     */
126    public static <C extends RingElem<C>> List<GenPolynomial<GenPolynomial<C>>> recursive(
127                    GenPolynomialRing<GenPolynomial<C>> rfac, List<GenPolynomial<C>> L) {
128        return ListUtil.<GenPolynomial<C>, GenPolynomial<GenPolynomial<C>>> map(L, new DistToRec<C>(rfac));
129    }
130
131
132    /**
133     * Distribute a recursive polynomial list to a generic polynomial list.
134     * Works for arbitrary term orders.
135     * @param <C> coefficient type.
136     * @param dfac combined polynomial ring factory of coefficients and this.
137     * @param L list of polynomials to be converted.
138     * @return distributed polynomial list.
139     */
140    public static <C extends RingElem<C>> List<GenPolynomial<C>> distribute(GenPolynomialRing<C> dfac,
141                    List<GenPolynomial<GenPolynomial<C>>> L) {
142        return ListUtil.<GenPolynomial<GenPolynomial<C>>, GenPolynomial<C>> map(L, new RecToDist<C>(dfac));
143    }
144
145
146    /**
147     * BigInteger from ModInteger coefficients, symmetric. Represent as
148     * polynomial with BigInteger coefficients by removing the modules and
149     * making coefficients symmetric to 0.
150     * @param fac result polynomial factory.
151     * @param A polynomial with ModInteger coefficients to be converted.
152     * @return polynomial with BigInteger coefficients.
153     */
154    public static <C extends RingElem<C> & Modular> GenPolynomial<BigInteger> integerFromModularCoefficients(
155                    GenPolynomialRing<BigInteger> fac, GenPolynomial<C> A) {
156        return PolyUtil.<C, BigInteger> map(fac, A, new ModSymToInt<C>());
157    }
158
159
160    /**
161     * BigInteger from ModInteger coefficients, symmetric. Represent as
162     * polynomial with BigInteger coefficients by removing the modules and
163     * making coefficients symmetric to 0.
164     * @param fac result polynomial factory.
165     * @param L list of polynomials with ModInteger coefficients to be
166     *            converted.
167     * @return list of polynomials with BigInteger coefficients.
168     */
169    public static <C extends RingElem<C> & Modular> List<GenPolynomial<BigInteger>> integerFromModularCoefficients(
170                    final GenPolynomialRing<BigInteger> fac, List<GenPolynomial<C>> L) {
171        return ListUtil.<GenPolynomial<C>, GenPolynomial<BigInteger>> map(L,
172                        new UnaryFunctor<GenPolynomial<C>, GenPolynomial<BigInteger>>() {
173
174
175                            public GenPolynomial<BigInteger> eval(GenPolynomial<C> c) {
176                                return PolyUtil.<C> integerFromModularCoefficients(fac, c);
177                            }
178                        });
179    }
180
181
182    /**
183     * BigInteger from ModInteger coefficients, positive. Represent as
184     * polynomial with BigInteger coefficients by removing the modules.
185     * @param fac result polynomial factory.
186     * @param A polynomial with ModInteger coefficients to be converted.
187     * @return polynomial with BigInteger coefficients.
188     */
189    public static <C extends RingElem<C> & Modular> GenPolynomial<BigInteger> integerFromModularCoefficientsPositive(
190                    GenPolynomialRing<BigInteger> fac, GenPolynomial<C> A) {
191        return PolyUtil.<C, BigInteger> map(fac, A, new ModToInt<C>());
192    }
193
194
195    /**
196     * BigInteger from BigRational coefficients. Represent as polynomial with
197     * BigInteger coefficients by multiplication with the lcm of the numerators
198     * of the BigRational coefficients.
199     * @param fac result polynomial factory.
200     * @param A polynomial with BigRational coefficients to be converted.
201     * @return polynomial with BigInteger coefficients.
202     */
203    public static GenPolynomial<BigInteger> integerFromRationalCoefficients(GenPolynomialRing<BigInteger> fac,
204                    GenPolynomial<BigRational> A) {
205        if (A == null || A.isZERO()) {
206            return fac.getZERO();
207        }
208        java.math.BigInteger c = null;
209        int s = 0;
210        // lcm of denominators
211        for (BigRational y : A.val.values()) {
212            java.math.BigInteger x = y.denominator();
213            // c = lcm(c,x)
214            if (c == null) {
215                c = x;
216                s = x.signum();
217            } else {
218                java.math.BigInteger d = c.gcd(x);
219                c = c.multiply(x.divide(d));
220            }
221        }
222        if (s < 0) {
223            c = c.negate();
224        }
225        return PolyUtil.<BigRational, BigInteger> map(fac, A, new RatToInt(c));
226    }
227
228
229    /**
230     * BigInteger from BigRational coefficients. Represent as polynomial with
231     * BigInteger coefficients by multiplication with the gcd of the numerators
232     * and the lcm of the denominators of the BigRational coefficients. <br />
233     * <b>Author:</b> Axel Kramer
234     * @param fac result polynomial factory.
235     * @param A polynomial with BigRational coefficients to be converted.
236     * @return Object[] with 3 entries: [0]=gcd [1]=lcm and [2]=polynomial with
237     *         BigInteger coefficients.
238     */
239    public static Object[] integerFromRationalCoefficientsFactor(GenPolynomialRing<BigInteger> fac,
240                    GenPolynomial<BigRational> A) {
241        Object[] result = new Object[3];
242        if (A == null || A.isZERO()) {
243            result[0] = java.math.BigInteger.ONE;
244            result[1] = java.math.BigInteger.ZERO;
245            result[2] = fac.getZERO();
246            return result;
247        }
248        java.math.BigInteger gcd = null;
249        java.math.BigInteger lcm = null;
250        int sLCM = 0;
251        int sGCD = 0;
252        // lcm of denominators
253        for (BigRational y : A.val.values()) {
254            java.math.BigInteger numerator = y.numerator();
255            java.math.BigInteger denominator = y.denominator();
256            // lcm = lcm(lcm,x)
257            if (lcm == null) {
258                lcm = denominator;
259                sLCM = denominator.signum();
260            } else {
261                java.math.BigInteger d = lcm.gcd(denominator);
262                lcm = lcm.multiply(denominator.divide(d));
263            }
264            // gcd = gcd(gcd,x)
265            if (gcd == null) {
266                gcd = numerator;
267                sGCD = numerator.signum();
268            } else {
269                gcd = gcd.gcd(numerator);
270            }
271        }
272        if (sLCM < 0) {
273            lcm = lcm.negate();
274        }
275        if (sGCD < 0) {
276            gcd = gcd.negate();
277        }
278        //System.out.println("gcd* = " + gcd + ", lcm = " + lcm);
279        result[0] = gcd;
280        result[1] = lcm;
281        result[2] = PolyUtil.<BigRational, BigInteger> map(fac, A, new RatToIntFactor(gcd, lcm));
282        return result;
283    }
284
285
286    /**
287     * BigInteger from BigRational coefficients. Represent as polynomial with
288     * BigInteger coefficients by multiplication with the gcd of the numerators
289     * and the lcm of the denominators of the BigRational coefficients. <br />
290     * @param fac result polynomial factory.
291     * @param gcd of rational coefficient numerators.
292     * @param lcm of rational coefficient denominators.
293     * @param A polynomial with BigRational coefficients to be converted.
294     * @return polynomial with BigInteger coefficients.
295     */
296    public static GenPolynomial<BigInteger> integerFromRationalCoefficients(GenPolynomialRing<BigInteger> fac,
297                    java.math.BigInteger gcd, java.math.BigInteger lcm, GenPolynomial<BigRational> A) {
298        //System.out.println("gcd = " + gcd + ", lcm = " + lcm);
299        GenPolynomial<BigInteger> Ai = PolyUtil.<BigRational, BigInteger> map(fac, A,
300                        new RatToIntFactor(gcd, lcm));
301        return Ai;
302    }
303
304
305    /**
306     * BigInteger from BigRational coefficients. Represent as list of
307     * polynomials with BigInteger coefficients by multiplication with the lcm
308     * of the numerators of the BigRational coefficients of each polynomial.
309     * @param fac result polynomial factory.
310     * @param L list of polynomials with BigRational coefficients to be
311     *            converted.
312     * @return polynomial list with BigInteger coefficients.
313     */
314    public static List<GenPolynomial<BigInteger>> integerFromRationalCoefficients(
315                    GenPolynomialRing<BigInteger> fac, List<GenPolynomial<BigRational>> L) {
316        return ListUtil.<GenPolynomial<BigRational>, GenPolynomial<BigInteger>> map(L, new RatToIntPoly(fac));
317    }
318
319
320    /**
321     * From BigInteger coefficients. Represent as polynomial with type C
322     * coefficients, e.g. ModInteger or BigRational.
323     * @param <C> coefficient type.
324     * @param fac result polynomial factory.
325     * @param A polynomial with BigInteger coefficients to be converted.
326     * @return polynomial with type C coefficients.
327     */
328    public static <C extends RingElem<C>> GenPolynomial<C> fromIntegerCoefficients(GenPolynomialRing<C> fac,
329                    GenPolynomial<BigInteger> A) {
330        return PolyUtil.<BigInteger, C> map(fac, A, new FromInteger<C>(fac.coFac));
331    }
332
333
334    /**
335     * From BigInteger coefficients. Represent as list of polynomials with type
336     * C coefficients, e.g. ModInteger or BigRational.
337     * @param <C> coefficient type.
338     * @param fac result polynomial factory.
339     * @param L list of polynomials with BigInteger coefficients to be
340     *            converted.
341     * @return list of polynomials with type C coefficients.
342     */
343    public static <C extends RingElem<C>> List<GenPolynomial<C>> fromIntegerCoefficients(
344                    GenPolynomialRing<C> fac, List<GenPolynomial<BigInteger>> L) {
345        return ListUtil.<GenPolynomial<BigInteger>, GenPolynomial<C>> map(L, new FromIntegerPoly<C>(fac));
346    }
347
348
349    /**
350     * Convert to decimal coefficients.
351     * @param fac result polynomial factory.
352     * @param A polynomial with Rational coefficients to be converted.
353     * @return polynomial with BigDecimal coefficients.
354     */
355    public static <C extends RingElem<C> & Rational> GenPolynomial<BigDecimal> decimalFromRational(
356                    GenPolynomialRing<BigDecimal> fac, GenPolynomial<C> A) {
357        return PolyUtil.<C, BigDecimal> map(fac, A, new RatToDec<C>());
358    }
359
360
361    /**
362     * Convert to complex decimal coefficients.
363     * @param fac result polynomial factory.
364     * @param A polynomial with complex Rational coefficients to be converted.
365     * @return polynomial with Complex BigDecimal coefficients.
366     */
367    public static <C extends RingElem<C> & Rational> GenPolynomial<Complex<BigDecimal>> complexDecimalFromRational(
368                    GenPolynomialRing<Complex<BigDecimal>> fac, GenPolynomial<Complex<C>> A) {
369        return PolyUtil.<Complex<C>, Complex<BigDecimal>> map(fac, A, new CompRatToDec<C>(fac.coFac));
370    }
371
372
373    /**
374     * Real part.
375     * @param fac result polynomial factory.
376     * @param A polynomial with BigComplex coefficients to be converted.
377     * @return polynomial with real part of the coefficients.
378     */
379    public static GenPolynomial<BigRational> realPart(GenPolynomialRing<BigRational> fac,
380                    GenPolynomial<BigComplex> A) {
381        return PolyUtil.<BigComplex, BigRational> map(fac, A, new RealPart());
382    }
383
384
385    /**
386     * Imaginary part.
387     * @param fac result polynomial factory.
388     * @param A polynomial with BigComplex coefficients to be converted.
389     * @return polynomial with imaginary part of coefficients.
390     */
391    public static GenPolynomial<BigRational> imaginaryPart(GenPolynomialRing<BigRational> fac,
392                    GenPolynomial<BigComplex> A) {
393        return PolyUtil.<BigComplex, BigRational> map(fac, A, new ImagPart());
394    }
395
396
397    /**
398     * Conjugate coefficients.
399     * @param A polynomial with StarRingElem coefficients to be conjugated.
400     * @return polynomial with conjugate coefficients.
401     */
402    @SuppressWarnings("unchecked")
403    public static <C extends RingElem<C>> GenPolynomial<C> conjugateCoeff(GenPolynomial<C> A) {
404        //return PolyUtil.<C,C> map(A, new ConjugPart());
405        if (! (A.ring.coFac.getONE() instanceof StarRingElem)) {
406            return A;
407        }
408        return PolyUtil.<C,C> map(A.ring, A, (a) -> (C)(((StarRingElem)a).conjugate()));
409    }
410
411
412    /**
413     * Real part.
414     * @param fac result polynomial factory.
415     * @param A polynomial with BigComplex coefficients to be converted.
416     * @return polynomial with real part of the coefficients.
417     */
418    public static <C extends RingElem<C>> GenPolynomial<C> realPartFromComplex(GenPolynomialRing<C> fac,
419                    GenPolynomial<Complex<C>> A) {
420        return PolyUtil.<Complex<C>, C> map(fac, A, new RealPartComplex<C>());
421    }
422
423
424    /**
425     * Imaginary part.
426     * @param fac result polynomial factory.
427     * @param A polynomial with BigComplex coefficients to be converted.
428     * @return polynomial with imaginary part of coefficients.
429     */
430    public static <C extends RingElem<C>> GenPolynomial<C> imaginaryPartFromComplex(GenPolynomialRing<C> fac,
431                    GenPolynomial<Complex<C>> A) {
432        return PolyUtil.<Complex<C>, C> map(fac, A, new ImagPartComplex<C>());
433    }
434
435
436    /**
437     * Complex from real polynomial.
438     * @param fac result polynomial factory.
439     * @param A polynomial with C coefficients to be converted.
440     * @return polynomial with Complex<C> coefficients.
441     */
442    public static <C extends RingElem<C>> GenPolynomial<Complex<C>> toComplex(
443                    GenPolynomialRing<Complex<C>> fac, GenPolynomial<C> A) {
444        return PolyUtil.<C, Complex<C>> map(fac, A, new ToComplex<C>(fac.coFac));
445    }
446
447
448    /**
449     * Complex from rational coefficients.
450     * @param fac result polynomial factory.
451     * @param A polynomial with BigRational coefficients to be converted.
452     * @return polynomial with BigComplex coefficients.
453     */
454    public static GenPolynomial<BigComplex> complexFromRational(GenPolynomialRing<BigComplex> fac,
455                    GenPolynomial<BigRational> A) {
456        return PolyUtil.<BigRational, BigComplex> map(fac, A, new RatToCompl());
457    }
458
459
460    /**
461     * Complex from ring element coefficients.
462     * @param fac result polynomial factory.
463     * @param A polynomial with RingElem coefficients to be converted.
464     * @return polynomial with Complex coefficients.
465     */
466    public static <C extends GcdRingElem<C>> GenPolynomial<Complex<C>> complexFromAny(
467                    GenPolynomialRing<Complex<C>> fac, GenPolynomial<C> A) {
468        ComplexRing<C> cr = (ComplexRing<C>) fac.coFac;
469        return PolyUtil.<C, Complex<C>> map(fac, A, new AnyToComplex<C>(cr));
470    }
471
472
473    /**
474     * From AlgebraicNumber coefficients. Represent as polynomial with type
475     * GenPolynomial&lt;C&gt; coefficients, e.g. ModInteger or BigRational.
476     * @param rfac result polynomial factory.
477     * @param A polynomial with AlgebraicNumber coefficients to be converted.
478     * @return polynomial with type GenPolynomial&lt;C&gt; coefficients.
479     */
480    public static <C extends GcdRingElem<C>> GenPolynomial<GenPolynomial<C>> fromAlgebraicCoefficients(
481                    GenPolynomialRing<GenPolynomial<C>> rfac, GenPolynomial<AlgebraicNumber<C>> A) {
482        return PolyUtil.<AlgebraicNumber<C>, GenPolynomial<C>> map(rfac, A, new AlgToPoly<C>());
483    }
484
485
486    /**
487     * Convert to AlgebraicNumber coefficients. Represent as polynomial with
488     * AlgebraicNumber<C> coefficients, C is e.g. ModInteger or BigRational.
489     * @param pfac result polynomial factory.
490     * @param A polynomial with C coefficients to be converted.
491     * @return polynomial with AlgebraicNumber&lt;C&gt; coefficients.
492     */
493    public static <C extends GcdRingElem<C>> GenPolynomial<AlgebraicNumber<C>> convertToAlgebraicCoefficients(
494                    GenPolynomialRing<AlgebraicNumber<C>> pfac, GenPolynomial<C> A) {
495        AlgebraicNumberRing<C> afac = (AlgebraicNumberRing<C>) pfac.coFac;
496        return PolyUtil.<C, AlgebraicNumber<C>> map(pfac, A, new CoeffToAlg<C>(afac));
497    }
498
499
500    /**
501     * Convert to recursive AlgebraicNumber coefficients. Represent as
502     * polynomial with recursive AlgebraicNumber<C> coefficients, C is e.g.
503     * ModInteger or BigRational.
504     * @param depth recursion depth of AlgebraicNumber coefficients.
505     * @param pfac result polynomial factory.
506     * @param A polynomial with C coefficients to be converted.
507     * @return polynomial with AlgebraicNumber&lt;C&gt; coefficients.
508     */
509    public static <C extends GcdRingElem<C>> GenPolynomial<AlgebraicNumber<C>> convertToRecAlgebraicCoefficients(
510                    int depth, GenPolynomialRing<AlgebraicNumber<C>> pfac, GenPolynomial<C> A) {
511        AlgebraicNumberRing<C> afac = (AlgebraicNumberRing<C>) pfac.coFac;
512        return PolyUtil.<C, AlgebraicNumber<C>> map(pfac, A, new CoeffToRecAlg<C>(depth, afac));
513    }
514
515
516    /**
517     * Convert to AlgebraicNumber coefficients. Represent as polynomial with
518     * AlgebraicNumber<C> coefficients, C is e.g. ModInteger or BigRational.
519     * @param pfac result polynomial factory.
520     * @param A recursive polynomial with GenPolynomial&lt;BigInteger&gt;
521     *            coefficients to be converted.
522     * @return polynomial with AlgebraicNumber&lt;C&gt; coefficients.
523     */
524    public static <C extends GcdRingElem<C>> GenPolynomial<AlgebraicNumber<C>> convertRecursiveToAlgebraicCoefficients(
525                    GenPolynomialRing<AlgebraicNumber<C>> pfac, GenPolynomial<GenPolynomial<C>> A) {
526        AlgebraicNumberRing<C> afac = (AlgebraicNumberRing<C>) pfac.coFac;
527        return PolyUtil.<GenPolynomial<C>, AlgebraicNumber<C>> map(pfac, A, new PolyToAlg<C>(afac));
528    }
529
530
531    /**
532     * Complex from algebraic coefficients.
533     * @param fac result polynomial factory.
534     * @param A polynomial with AlgebraicNumber coefficients Q(i) to be
535     *            converted.
536     * @return polynomial with Complex coefficients.
537     */
538    public static <C extends GcdRingElem<C>> GenPolynomial<Complex<C>> complexFromAlgebraic(
539                    GenPolynomialRing<Complex<C>> fac, GenPolynomial<AlgebraicNumber<C>> A) {
540        ComplexRing<C> cfac = (ComplexRing<C>) fac.coFac;
541        return PolyUtil.<AlgebraicNumber<C>, Complex<C>> map(fac, A, new AlgebToCompl<C>(cfac));
542    }
543
544
545    /**
546     * AlgebraicNumber from complex coefficients.
547     * @param fac result polynomial factory over Q(i).
548     * @param A polynomial with Complex coefficients to be converted.
549     * @return polynomial with AlgebraicNumber coefficients.
550     */
551    public static <C extends GcdRingElem<C>> GenPolynomial<AlgebraicNumber<C>> algebraicFromComplex(
552                    GenPolynomialRing<AlgebraicNumber<C>> fac, GenPolynomial<Complex<C>> A) {
553        AlgebraicNumberRing<C> afac = (AlgebraicNumberRing<C>) fac.coFac;
554        return PolyUtil.<Complex<C>, AlgebraicNumber<C>> map(fac, A, new ComplToAlgeb<C>(afac));
555    }
556
557
558    /**
559     * ModInteger chinese remainder algorithm on coefficients.
560     * @param fac GenPolynomial&lt;ModInteger&gt; result factory with
561     *            A.coFac.modul*B.coFac.modul = C.coFac.modul.
562     * @param A GenPolynomial&lt;ModInteger&gt;.
563     * @param B other GenPolynomial&lt;ModInteger&gt;.
564     * @param mi inverse of A.coFac.modul in ring B.coFac.
565     * @return S = cra(A,B), with S mod A.coFac.modul == A and S mod
566     *         B.coFac.modul == B.
567     */
568    public static <C extends RingElem<C> & Modular> GenPolynomial<C> chineseRemainder(
569                    GenPolynomialRing<C> fac, GenPolynomial<C> A, C mi, GenPolynomial<C> B) {
570        ModularRingFactory<C> cfac = (ModularRingFactory<C>) fac.coFac; // get RingFactory
571        GenPolynomial<C> S = fac.getZERO().copy();
572        GenPolynomial<C> Ap = A.copy();
573        SortedMap<ExpVector, C> av = Ap.val; //getMap();
574        SortedMap<ExpVector, C> bv = B.getMap();
575        SortedMap<ExpVector, C> sv = S.val; //getMap();
576        C c = null;
577        for (Map.Entry<ExpVector, C> me : bv.entrySet()) {
578            ExpVector e = me.getKey();
579            C y = me.getValue(); //bv.get(e); // assert y != null
580            C x = av.get(e);
581            if (x != null) {
582                av.remove(e);
583                c = cfac.chineseRemainder(x, mi, y);
584                if (!c.isZERO()) { // 0 cannot happen
585                    sv.put(e, c);
586                }
587            } else {
588                //c = cfac.fromInteger( y.getVal() );
589                c = cfac.chineseRemainder(A.ring.coFac.getZERO(), mi, y);
590                if (!c.isZERO()) { // 0 cannot happen
591                    sv.put(e, c); // c != null
592                }
593            }
594        }
595        // assert bv is empty = done
596        for (Map.Entry<ExpVector, C> me : av.entrySet()) { // rest of av
597            ExpVector e = me.getKey();
598            C x = me.getValue(); // av.get(e); // assert x != null
599            //c = cfac.fromInteger( x.getVal() );
600            c = cfac.chineseRemainder(x, mi, B.ring.coFac.getZERO());
601            if (!c.isZERO()) { // 0 cannot happen
602                sv.put(e, c); // c != null
603            }
604        }
605        return S;
606    }
607
608
609    /**
610     * GenPolynomial monic, i.e. leadingBaseCoefficient == 1. If
611     * leadingBaseCoefficient is not invertible returns this unmodified.
612     * @param <C> coefficient type.
613     * @param p recursive GenPolynomial&lt;GenPolynomial<C>&gt;.
614     * @return monic(p).
615     */
616    public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> monic(
617                    GenPolynomial<GenPolynomial<C>> p) {
618        if (p == null || p.isZERO()) {
619            return p;
620        }
621        C lc = p.leadingBaseCoefficient().leadingBaseCoefficient();
622        if (!lc.isUnit()) {
623            return p;
624        }
625        C lm = lc.inverse();
626        GenPolynomial<C> L = p.ring.coFac.getONE();
627        L = L.multiply(lm);
628        return p.multiplyLeft(L);
629    }
630
631
632    /**
633     * GenSolvablePolynomial monic, i.e. leadingBaseCoefficient == 1. If
634     * leadingBaseCoefficient is not invertible returns this unmodified.
635     * @param <C> coefficient type.
636     * @param p recursive GenSolvablePolynomial&lt;GenPolynomial<C>&gt;.
637     * @return monic(p).
638     */
639    public static <C extends RingElem<C>> GenSolvablePolynomial<GenPolynomial<C>> monic(
640                    GenSolvablePolynomial<GenPolynomial<C>> p) {
641        if (p == null || p.isZERO()) {
642            return p;
643        }
644        C lc = p.leadingBaseCoefficient().leadingBaseCoefficient();
645        if (!lc.isUnit()) {
646            return p;
647        }
648        C lm = lc.inverse();
649        GenPolynomial<C> L = p.ring.coFac.getONE();
650        L = L.multiply(lm);
651        return p.multiplyLeft(L);
652    }
653
654
655    /**
656     * Polynomial list monic.
657     * @param <C> coefficient type.
658     * @param L list of polynomials with field coefficients.
659     * @return list of polynomials with leading coefficient 1.
660     */
661    public static <C extends RingElem<C>> List<GenPolynomial<C>> monic(List<GenPolynomial<C>> L) {
662        return ListUtil.<GenPolynomial<C>, GenPolynomial<C>> map(L,
663                        new UnaryFunctor<GenPolynomial<C>, GenPolynomial<C>>() {
664
665
666                            public GenPolynomial<C> eval(GenPolynomial<C> c) {
667                                if (c == null) {
668                                    return null;
669                                }
670                                return c.monic();
671                            }
672                        });
673    }
674
675
676    /**
677     * Solvable polynomial list right monic.
678     * @param <C> coefficient type.
679     * @param L list of solvable polynomials with field coefficients.
680     * @return list of solvable polynomials with leading coefficient 1.
681     */
682    public static <C extends RingElem<C>> List<GenPolynomial<C>> rightMonic(List<GenPolynomial<C>> L) {
683        return ListUtil.<GenPolynomial<C>, GenPolynomial<C>> map(L,
684                        new UnaryFunctor<GenPolynomial<C>, GenPolynomial<C>>() {
685
686
687                            public GenPolynomial<C> eval(GenPolynomial<C> c) {
688                                if (c == null) {
689                                    return null;
690                                }
691                                GenSolvablePolynomial<C> d = (GenSolvablePolynomial<C>) c;
692                                return (GenPolynomial<C>) d.rightMonic();
693                            }
694                        });
695    }
696
697
698    /**
699     * Word polynomial list monic.
700     * @param <C> coefficient type.
701     * @param L list of word polynomials with field coefficients.
702     * @return list of word polynomials with leading coefficient 1.
703     */
704    public static <C extends RingElem<C>> List<GenWordPolynomial<C>> wordMonic(List<GenWordPolynomial<C>> L) {
705        return ListUtil.<GenWordPolynomial<C>, GenWordPolynomial<C>> map(L,
706                        new UnaryFunctor<GenWordPolynomial<C>, GenWordPolynomial<C>>() {
707
708
709                            public GenWordPolynomial<C> eval(GenWordPolynomial<C> c) {
710                                if (c == null) {
711                                    return null;
712                                }
713                                return c.monic();
714                            }
715                        });
716    }
717
718
719    /**
720     * Recursive polynomial list monic.
721     * @param <C> coefficient type.
722     * @param L list of recursive polynomials with field coefficients.
723     * @return list of polynomials with leading base coefficient 1.
724     */
725    public static <C extends RingElem<C>> List<GenPolynomial<GenPolynomial<C>>> monicRec(
726                    List<GenPolynomial<GenPolynomial<C>>> L) {
727        return ListUtil.<GenPolynomial<GenPolynomial<C>>, GenPolynomial<GenPolynomial<C>>> map(L,
728                        new UnaryFunctor<GenPolynomial<GenPolynomial<C>>, GenPolynomial<GenPolynomial<C>>>() {
729
730
731                            public GenPolynomial<GenPolynomial<C>> eval(GenPolynomial<GenPolynomial<C>> c) {
732                                if (c == null) {
733                                    return null;
734                                }
735                                return PolyUtil.<C> monic(c);
736                            }
737                        });
738    }
739
740
741    /**
742     * Polynomial list leading exponent vectors.
743     * @param <C> coefficient type.
744     * @param L list of polynomials.
745     * @return list of leading exponent vectors.
746     */
747    public static <C extends RingElem<C>> List<ExpVector> leadingExpVector(List<GenPolynomial<C>> L) {
748        return ListUtil.<GenPolynomial<C>, ExpVector> map(L, new UnaryFunctor<GenPolynomial<C>, ExpVector>() {
749
750
751            public ExpVector eval(GenPolynomial<C> c) {
752                if (c == null) {
753                    return null;
754                }
755                return c.leadingExpVector();
756            }
757        });
758    }
759
760
761    /**
762     * Extend coefficient variables. Extend all coefficient ExpVectors by i
763     * elements and multiply by x_j^k.
764     * @param pfac extended polynomial ring factory (by i variables in the
765     *            coefficients).
766     * @param j index of variable to be used for multiplication.
767     * @param k exponent for x_j.
768     * @return extended polynomial.
769     */
770    public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> extendCoefficients(
771                    GenPolynomialRing<GenPolynomial<C>> pfac, GenPolynomial<GenPolynomial<C>> A, int j,
772                    long k) {
773        GenPolynomial<GenPolynomial<C>> Cp = pfac.getZERO().copy();
774        if (A.isZERO()) {
775            return Cp;
776        }
777        GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) pfac.coFac;
778        //GenPolynomialRing<C> acfac = (GenPolynomialRing<C>) A.ring.coFac;
779        //int i = cfac.nvar - acfac.nvar;
780        Map<ExpVector, GenPolynomial<C>> CC = Cp.val; //getMap();
781        for (Map.Entry<ExpVector, GenPolynomial<C>> y : A.val.entrySet()) {
782            ExpVector e = y.getKey();
783            GenPolynomial<C> a = y.getValue();
784            GenPolynomial<C> f = a.extend(cfac, j, k);
785            CC.put(e, f);
786        }
787        return Cp;
788    }
789
790
791    /**
792     * Extend coefficient variables. Extend all coefficient ExpVectors by i
793     * elements and multiply by x_j^k.
794     * @param pfac extended polynomial ring factory (by i variables in the
795     *            coefficients).
796     * @param j index of variable to be used for multiplication.
797     * @param k exponent for x_j.
798     * @return extended polynomial.
799     */
800    public static <C extends RingElem<C>> GenSolvablePolynomial<GenPolynomial<C>> extendCoefficients(
801                    GenSolvablePolynomialRing<GenPolynomial<C>> pfac,
802                    GenSolvablePolynomial<GenPolynomial<C>> A, int j, long k) {
803        GenSolvablePolynomial<GenPolynomial<C>> Cp = pfac.getZERO().copy();
804        if (A.isZERO()) {
805            return Cp;
806        }
807        GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) pfac.coFac;
808        //GenPolynomialRing<C> acfac = (GenPolynomialRing<C>) A.ring.coFac;
809        //int i = cfac.nvar - acfac.nvar;
810        Map<ExpVector, GenPolynomial<C>> CC = Cp.val; //getMap();
811        for (Map.Entry<ExpVector, GenPolynomial<C>> y : A.val.entrySet()) {
812            ExpVector e = y.getKey();
813            GenPolynomial<C> a = y.getValue();
814            GenPolynomial<C> f = a.extend(cfac, j, k);
815            CC.put(e, f);
816        }
817        return Cp;
818    }
819
820
821    /**
822     * To recursive representation. Represent as polynomial in i+r variables
823     * with coefficients in i variables. Works for arbitrary term orders.
824     * @param <C> coefficient type.
825     * @param rfac recursive polynomial ring factory.
826     * @param A polynomial to be converted.
827     * @return Recursive representations of A in the ring rfac.
828     */
829    public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> toRecursive(
830                    GenPolynomialRing<GenPolynomial<C>> rfac, GenPolynomial<C> A) {
831
832        GenPolynomial<GenPolynomial<C>> B = rfac.getZERO().copy();
833        if (A.isZERO()) {
834            return B;
835        }
836        //int i = rfac.nvar;
837        //GenPolynomial<C> zero = rfac.getZEROCoefficient();
838        GenPolynomial<C> one = rfac.getONECoefficient();
839        Map<ExpVector, GenPolynomial<C>> Bv = B.val; //getMap();
840        for (Monomial<C> m : A) {
841            ExpVector e = m.e;
842            C a = m.c;
843            GenPolynomial<C> p = one.multiply(a);
844            Bv.put(e, p);
845        }
846        return B;
847    }
848
849
850    /**
851     * To recursive representation. Represent as solvable polynomial in i+r
852     * variables with coefficients in i variables. Works for arbitrary term
853     * orders.
854     * @param <C> coefficient type.
855     * @param rfac recursive solvable polynomial ring factory.
856     * @param A solvable polynomial to be converted.
857     * @return Recursive representations of A in the ring rfac.
858     */
859    public static <C extends RingElem<C>> GenSolvablePolynomial<GenPolynomial<C>> toRecursive(
860                    GenSolvablePolynomialRing<GenPolynomial<C>> rfac, GenSolvablePolynomial<C> A) {
861
862        GenSolvablePolynomial<GenPolynomial<C>> B = rfac.getZERO().copy();
863        if (A.isZERO()) {
864            return B;
865        }
866        //int i = rfac.nvar;
867        //GenPolynomial<C> zero = rfac.getZEROCoefficient();
868        GenPolynomial<C> one = rfac.getONECoefficient();
869        Map<ExpVector, GenPolynomial<C>> Bv = B.val; //getMap();
870        for (Monomial<C> m : A) {
871            ExpVector e = m.e;
872            C a = m.c;
873            GenPolynomial<C> p = one.multiply(a);
874            Bv.put(e, p);
875        }
876        return B;
877    }
878
879
880    /**
881     * GenPolynomial coefficient wise remainder.
882     * @param <C> coefficient type.
883     * @param P GenPolynomial.
884     * @param s nonzero coefficient.
885     * @return coefficient wise remainder.
886     * @see edu.jas.poly.GenPolynomial#remainder(edu.jas.poly.GenPolynomial).
887     */
888    public static <C extends RingElem<C>> GenPolynomial<C> baseRemainderPoly(GenPolynomial<C> P, C s) {
889        if (s == null || s.isZERO()) {
890            throw new ArithmeticException(P + " division by zero " + s);
891        }
892        GenPolynomial<C> h = P.ring.getZERO().copy();
893        Map<ExpVector, C> hm = h.val; //getMap();
894        for (Map.Entry<ExpVector, C> m : P.getMap().entrySet()) {
895            ExpVector f = m.getKey();
896            C a = m.getValue();
897            C x = a.remainder(s);
898            hm.put(f, x);
899        }
900        return h;
901    }
902
903
904    /**
905     * GenPolynomial sparse pseudo remainder. For univariate polynomials.
906     * @param <C> coefficient type.
907     * @param P GenPolynomial.
908     * @param S nonzero GenPolynomial.
909     * @return remainder with ldcf(S)<sup>m'</sup> P = quotient * S + remainder.
910     *         m' &le; deg(P)-deg(S)
911     * @see edu.jas.poly.GenPolynomial#remainder(edu.jas.poly.GenPolynomial).
912     * @deprecated(forRemoval=true) Use
913     *                              {@link #baseSparsePseudoRemainder(edu.jas.poly.GenPolynomial,edu.jas.poly.GenPolynomial)}
914     *                              instead
915     */
916    @Deprecated
917    public static <C extends RingElem<C>> GenPolynomial<C> basePseudoRemainder(GenPolynomial<C> P,
918                    GenPolynomial<C> S) {
919        return baseSparsePseudoRemainder(P, S);
920    }
921
922
923    /**
924     * GenPolynomial sparse pseudo remainder. For univariate polynomials.
925     * @param <C> coefficient type.
926     * @param P GenPolynomial.
927     * @param S nonzero GenPolynomial.
928     * @return remainder with ldcf(S)<sup>m'</sup> P = quotient * S + remainder.
929     *         m' &le; deg(P)-deg(S)
930     * @see edu.jas.poly.GenPolynomial#remainder(edu.jas.poly.GenPolynomial).
931     */
932    public static <C extends RingElem<C>> GenPolynomial<C> baseSparsePseudoRemainder(GenPolynomial<C> P,
933                    GenPolynomial<C> S) {
934        if (S == null || S.isZERO()) {
935            throw new ArithmeticException(P.toString() + " division by zero " + S);
936        }
937        if (P.isZERO()) {
938            return P;
939        }
940        if (S.isConstant()) {
941            return P.ring.getZERO();
942        }
943        C c = S.leadingBaseCoefficient();
944        ExpVector e = S.leadingExpVector();
945        GenPolynomial<C> h;
946        GenPolynomial<C> r = P;
947        while (!r.isZERO()) {
948            ExpVector f = r.leadingExpVector();
949            if (f.multipleOf(e)) {
950                C a = r.leadingBaseCoefficient();
951                ExpVector fe = f.subtract(e);
952                C x = a.remainder(c);
953                if (x.isZERO()) {
954                    C y = a.divide(c);
955                    h = S.multiply(y, fe); // coeff a
956                } else {
957                    r = r.multiply(c); // coeff ac
958                    h = S.multiply(a, fe); // coeff ac
959                }
960                r = r.subtract(h);
961            } else {
962                break;
963            }
964        }
965        return r;
966    }
967
968
969    /**
970     * GenPolynomial dense pseudo remainder. For univariate polynomials.
971     * @param P GenPolynomial.
972     * @param S nonzero GenPolynomial.
973     * @return remainder with ldcf(S)<sup>m</sup> P = quotient * S + remainder.
974     *         m == deg(P)-deg(S)
975     * @see edu.jas.poly.GenPolynomial#remainder(edu.jas.poly.GenPolynomial).
976     */
977    public static <C extends RingElem<C>> GenPolynomial<C> baseDensePseudoRemainder(GenPolynomial<C> P,
978                    GenPolynomial<C> S) {
979        if (S == null || S.isZERO()) {
980            throw new ArithmeticException(P + " division by zero " + S);
981        }
982        if (P.isZERO()) {
983            return P;
984        }
985        if (S.isConstant()) {
986            return P.ring.getZERO();
987        }
988        long m = P.degree(0);
989        long n = S.degree(0);
990        C c = S.leadingBaseCoefficient();
991        ExpVector e = S.leadingExpVector();
992        GenPolynomial<C> h;
993        GenPolynomial<C> r = P;
994        for (long i = m; i >= n; i--) {
995            if (r.isZERO()) {
996                return r;
997            }
998            long k = r.degree(0);
999            if (i == k) {
1000                ExpVector f = r.leadingExpVector();
1001                C a = r.leadingBaseCoefficient();
1002                f = f.subtract(e); // EVDIF( f, e );
1003                //System.out.println("red div = " + f);
1004                r = r.multiply(c); // coeff ac
1005                h = S.multiply(a, f); // coeff ac
1006                r = r.subtract(h);
1007            } else {
1008                r = r.multiply(c);
1009            }
1010        }
1011        return r;
1012    }
1013
1014
1015    /**
1016     * GenPolynomial dense pseudo quotient. For univariate polynomials.
1017     * @param P GenPolynomial.
1018     * @param S nonzero GenPolynomial.
1019     * @return quotient with ldcf(S)<sup>m</sup> P = quotient * S + remainder. m
1020     *         == deg(P)-deg(S)
1021     * @see edu.jas.poly.GenPolynomial#remainder(edu.jas.poly.GenPolynomial).
1022     */
1023    public static <C extends RingElem<C>> GenPolynomial<C> baseDensePseudoQuotient(GenPolynomial<C> P,
1024                    GenPolynomial<C> S) {
1025        if (S == null || S.isZERO()) {
1026            throw new ArithmeticException(P + " division by zero " + S);
1027        }
1028        if (P.isZERO()) {
1029            return P;
1030        }
1031        //if (S.degree() <= 0) {
1032        //    return l^n P; //P.ring.getZERO();
1033        //}
1034        long m = P.degree(0);
1035        long n = S.degree(0);
1036        C c = S.leadingBaseCoefficient();
1037        ExpVector e = S.leadingExpVector();
1038        GenPolynomial<C> q = P.ring.getZERO();
1039        GenPolynomial<C> h;
1040        GenPolynomial<C> r = P;
1041        for (long i = m; i >= n; i--) {
1042            if (r.isZERO()) {
1043                return q;
1044            }
1045            long k = r.degree(0);
1046            if (i == k) {
1047                ExpVector f = r.leadingExpVector();
1048                C a = r.leadingBaseCoefficient();
1049                f = f.subtract(e); // EVDIF( f, e );
1050                //System.out.println("red div = " + f);
1051                r = r.multiply(c); // coeff ac
1052                h = S.multiply(a, f); // coeff ac
1053                r = r.subtract(h);
1054                q = q.multiply(c);
1055                q = q.sum(a, f);
1056            } else {
1057                q = q.multiply(c);
1058                r = r.multiply(c);
1059            }
1060        }
1061        return q;
1062    }
1063
1064
1065    /**
1066     * GenPolynomial sparse pseudo divide. For univariate polynomials or exact
1067     * division.
1068     * @param <C> coefficient type.
1069     * @param P GenPolynomial.
1070     * @param S nonzero GenPolynomial.
1071     * @return quotient with ldcf(S)<sup>m'</sup> P = quotient * S + remainder.
1072     *         m' &le; deg(P)-deg(S)
1073     * @see edu.jas.poly.GenPolynomial#divide(edu.jas.poly.GenPolynomial).
1074     */
1075    public static <C extends RingElem<C>> GenPolynomial<C> basePseudoDivide(GenPolynomial<C> P,
1076                    GenPolynomial<C> S) {
1077        if (S == null || S.isZERO()) {
1078            throw new ArithmeticException(P.toString() + " division by zero " + S);
1079        }
1080        //if (S.ring.nvar != 1) {
1081        // ok if exact division
1082        // throw new RuntimeException(this.getClass().getName()
1083        //                            + " univariate polynomials only");
1084        //}
1085        if (P.isZERO() || S.isONE()) {
1086            return P;
1087        }
1088        C c = S.leadingBaseCoefficient();
1089        ExpVector e = S.leadingExpVector();
1090        GenPolynomial<C> h;
1091        GenPolynomial<C> r = P;
1092        GenPolynomial<C> q = S.ring.getZERO().copy();
1093
1094        while (!r.isZERO()) {
1095            ExpVector f = r.leadingExpVector();
1096            if (f.multipleOf(e)) {
1097                C a = r.leadingBaseCoefficient();
1098                f = f.subtract(e);
1099                C x = a.remainder(c);
1100                if (x.isZERO()) {
1101                    C y = a.divide(c);
1102                    q = q.sum(y, f);
1103                    h = S.multiply(y, f); // coeff a
1104                } else {
1105                    q = q.multiply(c);
1106                    q = q.sum(a, f);
1107                    r = r.multiply(c); // coeff ac
1108                    h = S.multiply(a, f); // coeff ac
1109                }
1110                r = r.subtract(h);
1111            } else {
1112                break;
1113            }
1114        }
1115        return q;
1116    }
1117
1118
1119    /**
1120     * GenPolynomial sparse pseudo quotient and remainder. For univariate
1121     * polynomials or exact division.
1122     * @param <C> coefficient type.
1123     * @param P GenPolynomial.
1124     * @param S nonzero GenPolynomial.
1125     * @return [ quotient, remainder ] with ldcf(S)<sup>m'</sup> P = quotient *
1126     *         S + remainder. m' &le; deg(P)-deg(S)
1127     * @see edu.jas.poly.GenPolynomial#divide(edu.jas.poly.GenPolynomial).
1128     */
1129    @SuppressWarnings("unchecked")
1130    public static <C extends RingElem<C>> GenPolynomial<C>[] basePseudoQuotientRemainder(
1131                    final GenPolynomial<C> P, final GenPolynomial<C> S) {
1132        if (S == null || S.isZERO()) {
1133            throw new ArithmeticException(P.toString() + " division by zero " + S);
1134        }
1135        //if (S.ring.nvar != 1) {
1136        // ok if exact division
1137        // throw new RuntimeException(this.getClass().getName()
1138        //                            + " univariate polynomials only");
1139        //}
1140        GenPolynomial<C>[] ret = new GenPolynomial[2];
1141        ret[0] = null;
1142        ret[1] = null;
1143        if (P.isZERO() || S.isONE()) {
1144            ret[0] = P;
1145            ret[1] = S.ring.getZERO();
1146            return ret;
1147        }
1148        //logger.debug("P, S = " + P + ", " + S);
1149        final C c = S.leadingBaseCoefficient();
1150        final ExpVector e = S.leadingExpVector();
1151        GenPolynomial<C> h;
1152        GenPolynomial<C> r = P;
1153        GenPolynomial<C> q = S.ring.getZERO().copy();
1154
1155        while (!r.isZERO()) {
1156            ExpVector f = r.leadingExpVector();
1157            if (f.multipleOf(e)) {
1158                C a = r.leadingBaseCoefficient();
1159                f = f.subtract(e);
1160                C x = a.remainder(c);
1161                if (x.isZERO()) {
1162                    C y = a.divide(c);
1163                    q = q.sum(y, f);
1164                    h = S.multiply(y, f); // coeff a
1165                } else {
1166                    q = q.multiply(c);
1167                    q = q.sum(a, f);
1168                    r = r.multiply(c); // coeff a c
1169                    h = S.multiply(a, f); // coeff c a
1170                }
1171                r = r.subtract(h);
1172                //logger.debug("q, r = " + q + ", " + r);
1173            } else {
1174                break;
1175            }
1176        }
1177        //GenPolynomial<C> rhs = q.multiply(S).sum(r);
1178        //GenPolynomial<C> lhs = P;
1179        ret[0] = q;
1180        ret[1] = r;
1181        return ret;
1182    }
1183
1184
1185    /**
1186     * Is GenPolynomial pseudo quotient and remainder. For univariate
1187     * polynomials.
1188     * @param <C> coefficient type.
1189     * @param P base GenPolynomial.
1190     * @param S nonzero base GenPolynomial.
1191     * @return true, if P = q * S + r, else false.
1192     * @see edu.jas.poly.GenPolynomial#remainder(edu.jas.poly.GenPolynomial).
1193     *      <b>Note:</b> not always meaningful and working
1194     */
1195    public static <C extends RingElem<C>> boolean isBasePseudoQuotientRemainder(GenPolynomial<C> P,
1196                    GenPolynomial<C> S, GenPolynomial<C> q, GenPolynomial<C> r) {
1197        GenPolynomial<C> rhs = q.multiply(S).sum(r);
1198        //System.out.println("rhs,1 = " + rhs);
1199        GenPolynomial<C> lhs = P;
1200        C ldcf = S.leadingBaseCoefficient();
1201        long d = P.degree(0) - S.degree(0) + 1;
1202        d = (d > 0 ? d : -d + 2);
1203        for (long i = 0; i <= d; i++) {
1204            //System.out.println("lhs-rhs = " + lhs.subtract(rhs));
1205            if (lhs.equals(rhs) || lhs.negate().equals(rhs)) {
1206                //System.out.println("lhs,1 = " + lhs);
1207                return true;
1208            }
1209            lhs = lhs.multiply(ldcf);
1210        }
1211        GenPolynomial<C> Pp = P;
1212        rhs = q.multiply(S);
1213        //System.out.println("rhs,2 = " + rhs);
1214        for (long i = 0; i <= d; i++) {
1215            lhs = Pp.subtract(r);
1216            //System.out.println("lhs-rhs = " + lhs.subtract(rhs));
1217            if (lhs.equals(rhs) || lhs.negate().equals(rhs)) {
1218                //System.out.println("lhs,2 = " + lhs);
1219                return true;
1220            }
1221            Pp = Pp.multiply(ldcf);
1222        }
1223        C a = P.leadingBaseCoefficient();
1224        rhs = q.multiply(S).sum(r);
1225        C b = rhs.leadingBaseCoefficient();
1226        C gcd = a.gcd(b);
1227        C p = a.multiply(b);
1228        C lcm = p.divide(gcd);
1229        C ap = lcm.divide(a);
1230        C bp = lcm.divide(b);
1231        if (P.multiply(ap).equals(rhs.multiply(bp))) {
1232            return true;
1233        }
1234        return false;
1235    }
1236
1237
1238    /**
1239     * GenPolynomial divide. For recursive polynomials. Division by coefficient
1240     * ring element.
1241     * @param <C> coefficient type.
1242     * @param P recursive GenPolynomial.
1243     * @param s GenPolynomial.
1244     * @return this/s.
1245     */
1246    public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> recursiveDivide(
1247                    GenPolynomial<GenPolynomial<C>> P, GenPolynomial<C> s) {
1248        if (s == null || s.isZERO()) {
1249            throw new ArithmeticException("division by zero " + P + ", " + s);
1250        }
1251        if (P.isZERO()) {
1252            return P;
1253        }
1254        if (s.isONE()) {
1255            return P;
1256        }
1257        GenPolynomial<GenPolynomial<C>> p = P.ring.getZERO().copy();
1258        SortedMap<ExpVector, GenPolynomial<C>> pv = p.val; //getMap();
1259        for (Map.Entry<ExpVector, GenPolynomial<C>> m1 : P.getMap().entrySet()) {
1260            GenPolynomial<C> c1 = m1.getValue();
1261            ExpVector e1 = m1.getKey();
1262            GenPolynomial<C> c = PolyUtil.<C> basePseudoDivide(c1, s);
1263            if (!c.isZERO()) {
1264                pv.put(e1, c); // or m1.setValue( c )
1265            } else {
1266                logger.warn("rDiv, P  = {}", P);
1267                logger.warn("rDiv, c1 = {}", c1);
1268                logger.warn("rDiv, s  = {}", s);
1269                logger.warn("rDiv, c  = {}", c);
1270                throw new RuntimeException("something is wrong");
1271            }
1272        }
1273        return p;
1274    }
1275
1276
1277    /**
1278     * GenPolynomial divide. For recursive polynomials. Division by coefficient
1279     * ring element.
1280     * @param <C> coefficient type.
1281     * @param P recursive GenPolynomial.
1282     * @param s GenPolynomial.
1283     * @return this/s.
1284     */
1285    public static <C extends RingElem<C>> GenWordPolynomial<GenPolynomial<C>> recursiveDivide(
1286                    GenWordPolynomial<GenPolynomial<C>> P, GenPolynomial<C> s) {
1287        if (s == null || s.isZERO()) {
1288            throw new ArithmeticException("division by zero " + P + ", " + s);
1289        }
1290        if (P.isZERO()) {
1291            return P;
1292        }
1293        if (s.isONE()) {
1294            return P;
1295        }
1296        GenWordPolynomial<GenPolynomial<C>> p = P.ring.getZERO().copy();
1297        SortedMap<Word, GenPolynomial<C>> pv = p.val; //getMap();
1298        for (Map.Entry<Word, GenPolynomial<C>> m1 : P.getMap().entrySet()) {
1299            GenPolynomial<C> c1 = m1.getValue();
1300            Word e1 = m1.getKey();
1301            GenPolynomial<C> c = PolyUtil.<C> basePseudoDivide(c1, s);
1302            if (!c.isZERO()) {
1303                pv.put(e1, c); // or m1.setValue( c )
1304            } else {
1305                logger.warn("rDiv, P  = {}", P);
1306                logger.warn("rDiv, c1 = {}", c1);
1307                logger.warn("rDiv, s  = {}", s);
1308                logger.warn("rDiv, c  = {}", c);
1309                throw new RuntimeException("something is wrong");
1310            }
1311        }
1312        return p;
1313    }
1314
1315
1316    /**
1317     * GenPolynomial base divide. For recursive polynomials. Division by
1318     * coefficient ring element.
1319     * @param <C> coefficient type.
1320     * @param P recursive GenPolynomial.
1321     * @param s coefficient.
1322     * @return this/s.
1323     */
1324    public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> baseRecursiveDivide(
1325                    GenPolynomial<GenPolynomial<C>> P, C s) {
1326        if (s == null || s.isZERO()) {
1327            throw new ArithmeticException("division by zero " + P + ", " + s);
1328        }
1329        if (P.isZERO()) {
1330            return P;
1331        }
1332        if (s.isONE()) {
1333            return P;
1334        }
1335        GenPolynomial<GenPolynomial<C>> p = P.ring.getZERO().copy();
1336        SortedMap<ExpVector, GenPolynomial<C>> pv = p.val; //getMap();
1337        for (Map.Entry<ExpVector, GenPolynomial<C>> m1 : P.getMap().entrySet()) {
1338            GenPolynomial<C> c1 = m1.getValue();
1339            ExpVector e1 = m1.getKey();
1340            GenPolynomial<C> c = PolyUtil.<C> coefficientBasePseudoDivide(c1, s);
1341            if (!c.isZERO()) {
1342                pv.put(e1, c); // or m1.setValue( c )
1343            } else {
1344                logger.warn("pu, c1 = {}", c1);
1345                logger.warn("pu, s  = {}", s);
1346                logger.warn("pu, c  = {}", c);
1347                throw new RuntimeException("something is wrong");
1348            }
1349        }
1350        return p;
1351    }
1352
1353
1354    /**
1355     * GenPolynomial sparse pseudo remainder. For recursive polynomials.
1356     * @param <C> coefficient type.
1357     * @param P recursive GenPolynomial.
1358     * @param S nonzero recursive GenPolynomial.
1359     * @return remainder with ldcf(S)<sup>m'</sup> P = quotient * S + remainder.
1360     * @see edu.jas.poly.GenPolynomial#remainder(edu.jas.poly.GenPolynomial).
1361     * @deprecated(forRemoval=true) Use
1362     *                              {@link #recursiveSparsePseudoRemainder(edu.jas.poly.GenPolynomial,edu.jas.poly.GenPolynomial)}
1363     *                              instead
1364     */
1365    @Deprecated
1366    public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> recursivePseudoRemainder(
1367                    GenPolynomial<GenPolynomial<C>> P, GenPolynomial<GenPolynomial<C>> S) {
1368        return recursiveSparsePseudoRemainder(P, S);
1369    }
1370
1371
1372    /**
1373     * GenPolynomial sparse pseudo remainder. For recursive polynomials.
1374     * @param <C> coefficient type.
1375     * @param P recursive GenPolynomial.
1376     * @param S nonzero recursive GenPolynomial.
1377     * @return remainder with ldcf(S)<sup>m'</sup> P = quotient * S + remainder.
1378     * @see edu.jas.poly.GenPolynomial#remainder(edu.jas.poly.GenPolynomial).
1379     */
1380    public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> recursiveSparsePseudoRemainder(
1381                    GenPolynomial<GenPolynomial<C>> P, GenPolynomial<GenPolynomial<C>> S) {
1382        if (S == null || S.isZERO()) {
1383            throw new ArithmeticException(P + " division by zero " + S);
1384        }
1385        if (P == null || P.isZERO()) {
1386            return P;
1387        }
1388        if (S.isConstant()) {
1389            return P.ring.getZERO();
1390        }
1391        GenPolynomial<C> c = S.leadingBaseCoefficient();
1392        ExpVector e = S.leadingExpVector();
1393        GenPolynomial<GenPolynomial<C>> h;
1394        GenPolynomial<GenPolynomial<C>> r = P;
1395        while (!r.isZERO()) {
1396            ExpVector f = r.leadingExpVector();
1397            if (f.multipleOf(e)) {
1398                GenPolynomial<C> a = r.leadingBaseCoefficient();
1399                f = f.subtract(e);
1400                GenPolynomial<C> x = c; //test basePseudoRemainder(a,c);
1401                if (x.isZERO()) {
1402                    GenPolynomial<C> y = PolyUtil.<C> basePseudoDivide(a, c);
1403                    h = S.multiply(y, f); // coeff a
1404                } else {
1405                    r = r.multiply(c); // coeff a c
1406                    h = S.multiply(a, f); // coeff c a
1407                }
1408                r = r.subtract(h);
1409            } else {
1410                break;
1411            }
1412        }
1413        return r;
1414    }
1415
1416
1417    /**
1418     * GenPolynomial dense pseudo remainder. For recursive polynomials.
1419     * @param P recursive GenPolynomial.
1420     * @param S nonzero recursive GenPolynomial.
1421     * @return remainder with ldcf(S)<sup>m'</sup> P = quotient * S + remainder.
1422     * @see edu.jas.poly.GenPolynomial#remainder(edu.jas.poly.GenPolynomial).
1423     */
1424    public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> recursiveDensePseudoRemainder(
1425                    GenPolynomial<GenPolynomial<C>> P, GenPolynomial<GenPolynomial<C>> S) {
1426        if (S == null || S.isZERO()) {
1427            throw new ArithmeticException(P + " division by zero " + S);
1428        }
1429        if (P == null || P.isZERO()) {
1430            return P;
1431        }
1432        if (S.isConstant()) {
1433            return P.ring.getZERO();
1434        }
1435        long m = P.degree(0);
1436        long n = S.degree(0);
1437        GenPolynomial<C> c = S.leadingBaseCoefficient();
1438        ExpVector e = S.leadingExpVector();
1439        GenPolynomial<GenPolynomial<C>> h;
1440        GenPolynomial<GenPolynomial<C>> r = P;
1441        for (long i = m; i >= n; i--) {
1442            if (r.isZERO()) {
1443                return r;
1444            }
1445            long k = r.degree(0);
1446            if (i == k) {
1447                ExpVector f = r.leadingExpVector();
1448                GenPolynomial<C> a = r.leadingBaseCoefficient();
1449                f = f.subtract(e); //EVDIF( f, e );
1450                //System.out.println("red div = " + f);
1451                r = r.multiply(c); // coeff ac
1452                h = S.multiply(a, f); // coeff ac
1453                r = r.subtract(h);
1454            } else {
1455                r = r.multiply(c);
1456            }
1457        }
1458        return r;
1459    }
1460
1461
1462    /**
1463     * GenPolynomial recursive pseudo divide. For recursive polynomials.
1464     * @param <C> coefficient type.
1465     * @param P recursive GenPolynomial.
1466     * @param S nonzero recursive GenPolynomial.
1467     * @return quotient with ldcf(S)<sup>m'</sup> P = quotient * S + remainder.
1468     * @see edu.jas.poly.GenPolynomial#remainder(edu.jas.poly.GenPolynomial).
1469     */
1470    public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> recursivePseudoDivide(
1471                    GenPolynomial<GenPolynomial<C>> P, GenPolynomial<GenPolynomial<C>> S) {
1472        if (S == null || S.isZERO()) {
1473            throw new ArithmeticException(P + " division by zero " + S);
1474        }
1475        //if (S.ring.nvar != 1) {
1476        // ok if exact division
1477        // throw new RuntimeException(this.getClass().getName()
1478        //                            + " univariate polynomials only");
1479        //}
1480        if (P == null || P.isZERO()) {
1481            return P;
1482        }
1483        if (S.isONE()) {
1484            return P;
1485        }
1486        GenPolynomial<C> c = S.leadingBaseCoefficient();
1487        ExpVector e = S.leadingExpVector();
1488        GenPolynomial<GenPolynomial<C>> h;
1489        GenPolynomial<GenPolynomial<C>> r = P;
1490        GenPolynomial<GenPolynomial<C>> q = S.ring.getZERO().copy();
1491        while (!r.isZERO()) {
1492            ExpVector f = r.leadingExpVector();
1493            if (f.multipleOf(e)) {
1494                GenPolynomial<C> a = r.leadingBaseCoefficient();
1495                f = f.subtract(e);
1496                GenPolynomial<C> x = PolyUtil.<C> baseSparsePseudoRemainder(a, c);
1497                if (x.isZERO() && !c.isConstant()) {
1498                    GenPolynomial<C> y = PolyUtil.<C> basePseudoDivide(a, c);
1499                    q = q.sum(y, f);
1500                    h = S.multiply(y, f); // coeff a
1501                } else {
1502                    q = q.multiply(c);
1503                    q = q.sum(a, f);
1504                    r = r.multiply(c); // coeff ac
1505                    h = S.multiply(a, f); // coeff ac
1506                }
1507                r = r.subtract(h);
1508            } else {
1509                break;
1510            }
1511        }
1512        return q;
1513    }
1514
1515
1516    /**
1517     * Is recursive GenPolynomial pseudo quotient and remainder. For recursive
1518     * polynomials.
1519     * @param <C> coefficient type.
1520     * @param P recursive GenPolynomial.
1521     * @param S nonzero recursive GenPolynomial.
1522     * @return true, if P ~= q * S + r, else false.
1523     * @see edu.jas.poly.GenPolynomial#remainder(edu.jas.poly.GenPolynomial).
1524     *      <b>Note:</b> not always meaningful and working
1525     */
1526    public static <C extends RingElem<C>> boolean isRecursivePseudoQuotientRemainder(
1527                    GenPolynomial<GenPolynomial<C>> P, GenPolynomial<GenPolynomial<C>> S,
1528                    GenPolynomial<GenPolynomial<C>> q, GenPolynomial<GenPolynomial<C>> r) {
1529        GenPolynomial<GenPolynomial<C>> rhs = q.multiply(S).sum(r);
1530        GenPolynomial<GenPolynomial<C>> lhs = P;
1531        GenPolynomial<C> ldcf = S.leadingBaseCoefficient();
1532        long d = P.degree(0) - S.degree(0) + 1;
1533        d = (d > 0 ? d : -d + 2);
1534        for (long i = 0; i <= d; i++) {
1535            //System.out.println("lhs = " + lhs);
1536            //System.out.println("rhs = " + rhs);
1537            //System.out.println("lhs-rhs = " + lhs.subtract(rhs));
1538            if (lhs.equals(rhs)) {
1539                return true;
1540            }
1541            lhs = lhs.multiply(ldcf);
1542        }
1543        GenPolynomial<GenPolynomial<C>> Pp = P;
1544        rhs = q.multiply(S);
1545        //System.out.println("rhs,2 = " + rhs);
1546        for (long i = 0; i <= d; i++) {
1547            lhs = Pp.subtract(r);
1548            //System.out.println("lhs-rhs = " + lhs.subtract(rhs));
1549            if (lhs.equals(rhs)) {
1550                //System.out.println("lhs,2 = " + lhs);
1551                return true;
1552            }
1553            Pp = Pp.multiply(ldcf);
1554        }
1555        GenPolynomial<C> a = P.leadingBaseCoefficient();
1556        rhs = q.multiply(S).sum(r);
1557        GenPolynomial<C> b = rhs.leadingBaseCoefficient();
1558        GenPolynomial<GenPolynomial<C>> Pb = P.multiply(b);
1559        GenPolynomial<GenPolynomial<C>> rhsa = rhs.multiply(a);
1560        if (Pb.equals(rhsa)) {
1561            return true;
1562        }
1563        //System.out.println("b     = " + b);
1564        //System.out.println("a     = " + a);
1565        System.out.println("P*b   = " + Pb);
1566        System.out.println("rhs*a = " + rhsa);
1567        if (Pb.degree() != rhsa.degree()
1568                        || !Pb.leadingBaseCoefficient().equals(rhsa.leadingBaseCoefficient())) {
1569            return false;
1570        }
1571        return false;
1572    }
1573
1574
1575    /**
1576     * GenPolynomial pseudo divide. For recursive polynomials.
1577     * @param <C> coefficient type.
1578     * @param P recursive GenPolynomial.
1579     * @param s nonzero GenPolynomial.
1580     * @return quotient with ldcf(s)<sup>m</sup> P = quotient * s + remainder.
1581     * @see edu.jas.poly.GenPolynomial#remainder(edu.jas.poly.GenPolynomial).
1582     */
1583    public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> coefficientPseudoDivide(
1584                    GenPolynomial<GenPolynomial<C>> P, GenPolynomial<C> s) {
1585        if (s == null || s.isZERO()) {
1586            throw new ArithmeticException(P + " division by zero " + s);
1587        }
1588        if (P.isZERO()) {
1589            return P;
1590        }
1591        GenPolynomial<GenPolynomial<C>> p = P.ring.getZERO().copy();
1592        SortedMap<ExpVector, GenPolynomial<C>> pv = p.val;
1593        for (Map.Entry<ExpVector, GenPolynomial<C>> m : P.getMap().entrySet()) {
1594            ExpVector e = m.getKey();
1595            GenPolynomial<C> c1 = m.getValue();
1596            GenPolynomial<C> c = basePseudoDivide(c1, s);
1597            if (debug) {
1598                GenPolynomial<C> x = c1.remainder(s);
1599                if (!x.isZERO()) {
1600                    logger.info("divide x = {}", x);
1601                    throw new ArithmeticException("no exact division: " + c1 + "/" + s);
1602                }
1603            }
1604            if (c.isZERO()) {
1605                //logger.warn("no exact division: {}/{}", c1, s);
1606                throw new ArithmeticException("no exact division: " + c1 + "/" + s);
1607            }
1608            pv.put(e, c); // or m1.setValue( c )
1609        }
1610        return p;
1611    }
1612
1613
1614    /**
1615     * GenPolynomial pseudo divide. For polynomials.
1616     * @param <C> coefficient type.
1617     * @param P GenPolynomial.
1618     * @param s nonzero coefficient.
1619     * @return quotient with ldcf(s)<sup>m</sup> P = quotient * s + remainder.
1620     * @see edu.jas.poly.GenPolynomial#remainder(edu.jas.poly.GenPolynomial).
1621     */
1622    public static <C extends RingElem<C>> GenPolynomial<C> coefficientBasePseudoDivide(GenPolynomial<C> P,
1623                    C s) {
1624        if (s == null || s.isZERO()) {
1625            throw new ArithmeticException(P + " division by zero " + s);
1626        }
1627        if (P.isZERO()) {
1628            return P;
1629        }
1630        GenPolynomial<C> p = P.ring.getZERO().copy();
1631        SortedMap<ExpVector, C> pv = p.val;
1632        for (Map.Entry<ExpVector, C> m : P.getMap().entrySet()) {
1633            ExpVector e = m.getKey();
1634            C c1 = m.getValue();
1635            C c = c1.divide(s);
1636            if (debug) {
1637                C x = c1.remainder(s);
1638                if (!x.isZERO()) {
1639                    logger.info("divide x = {}", x);
1640                    throw new ArithmeticException("no exact division: " + c1 + "/" + s);
1641                }
1642            }
1643            if (c.isZERO()) {
1644                //logger.warn("no exact division: {}/{}", c1, s);
1645                throw new ArithmeticException("no exact division: " + c1 + "/" + s);
1646            }
1647            pv.put(e, c); // or m1.setValue( c )
1648        }
1649        return p;
1650    }
1651
1652
1653    /**
1654     * GenExteriorPolynomial polynomial exterior derivative.
1655     * @param <C> coefficient type.
1656     * @param P GenExteriorPolynomial.
1657     * @return exteriorDerivative(P).
1658     */
1659    public static <C extends RingElem<C>> GenExteriorPolynomial<C> exteriorDerivative(
1660                    GenExteriorPolynomial<C> P) {
1661        if (P == null || P.isZERO()) {
1662            return P;
1663        }
1664        GenExteriorPolynomialRing<C> pfac = P.ring;
1665        IndexFactory ifac = pfac.ixfac;
1666        int im = ifac.imaxlength;
1667        if (im == 0) {
1668            return pfac.getZERO();
1669        }
1670        //RingFactory<C> rf = pfac.coFac;
1671        GenExteriorPolynomial<C> d = pfac.getZERO().copy();
1672        Map<IndexList, C> dm = d.val;
1673        for (Map.Entry<IndexList, C> m : P.getMap().entrySet()) {
1674            //if (P.length() == 1) {
1675            //Map.Entry<IndexList, C> m = P.leadingMonomial();
1676            C a = m.getValue();
1677            IndexList il = m.getKey();
1678            C b;
1679            IndexList bi;
1680            for (int i = 1; i <= im; i++) {
1681                IndexList di = new IndexList(ifac, new int[] { i });
1682                bi = di.multiply(il);
1683                if (bi.signum() == 0) {
1684                    continue;
1685                }
1686                b = a; // b = a.derivative();
1687                if (bi.signum() < 0) {
1688                    bi = bi.negate();
1689                    b = b.negate();
1690                }
1691                dm.put(bi, b);
1692            }
1693        }
1694        return d;
1695    }
1696
1697
1698    /**
1699     * GenExteriorPolynomial over polynomial exterior derivative.
1700     * @param <C> coefficient type.
1701     * @param P GenExteriorPolynomial<GenPolynomial>.
1702     * @return exteriorDerivativePoly(P).
1703     */
1704    public static <C extends RingElem<C>> GenExteriorPolynomial<GenPolynomial<C>> exteriorDerivativePoly(
1705                    GenExteriorPolynomial<GenPolynomial<C>> P) {
1706        if (P == null || P.isZERO()) {
1707            return P;
1708        }
1709        GenExteriorPolynomialRing<GenPolynomial<C>> pfac = P.ring;
1710        IndexFactory ifac = pfac.ixfac;
1711        int im = ifac.imaxlength;
1712        if (im == 0) {
1713            return pfac.getZERO();
1714        }
1715        //RingFactory<GenPolynomial<C>> rf = pfac.coFac;
1716        GenExteriorPolynomial<GenPolynomial<C>> d = pfac.getZERO().copy();
1717        Map<IndexList, GenPolynomial<C>> dm = d.val;
1718        for (Map.Entry<IndexList, GenPolynomial<C>> m : P.getMap().entrySet()) {
1719            //if (P.length() == 1) {
1720            //Map.Entry<IndexList, C> m = P.leadingMonomial();
1721            GenPolynomial<C> a = m.getValue();
1722            IndexList il = m.getKey();
1723            GenPolynomial<C> b;
1724            IndexList bi;
1725            for (int i = 1; i <= im; i++) {
1726                IndexList di = new IndexList(ifac, new int[] { i });
1727                bi = di.multiply(il);
1728                if (bi.signum() == 0) {
1729                    continue;
1730                }
1731                b = PolyUtil.<C> baseDerivative(a, i - 1); //a.derivative();
1732                //System.out.println("baseDerivative a = " + a + ", i-1 = " + (i-1) + ", b = " + b);
1733                if (b.isZERO()) {
1734                    continue;
1735                }
1736                if (bi.signum() < 0) {
1737                    bi = bi.negate();
1738                    b = b.negate();
1739                }
1740                dm.put(bi, b);
1741            }
1742        }
1743        return d;
1744    }
1745
1746
1747    /**
1748     * GenPolynomial polynomial derivative main variable.
1749     * @param <C> coefficient type.
1750     * @param P GenPolynomial.
1751     * @return derivative(P).
1752     */
1753    public static <C extends RingElem<C>> GenPolynomial<C> baseDerivative(GenPolynomial<C> P) {
1754        if (P == null || P.isZERO()) {
1755            return P;
1756        }
1757        GenPolynomialRing<C> pfac = P.ring;
1758        if (pfac.nvar == 0) {
1759            return pfac.getZERO();
1760        }
1761        if (pfac.nvar > 1) {
1762            // baseContent not possible by return type
1763            throw new IllegalArgumentException(P.getClass().getName() + " only for univariate polynomials");
1764        }
1765        RingFactory<C> rf = pfac.coFac;
1766        GenPolynomial<C> d = pfac.getZERO().copy();
1767        Map<ExpVector, C> dm = d.val; //getMap();
1768        for (Map.Entry<ExpVector, C> m : P.getMap().entrySet()) {
1769            ExpVector f = m.getKey();
1770            long fl = f.getVal(0);
1771            if (fl > 0) {
1772                C cf = rf.fromInteger(fl);
1773                C a = m.getValue();
1774                C x = a.multiply(cf);
1775                if (x != null && !x.isZERO()) {
1776                    ExpVector e = ExpVector.create(1, 0, fl - 1L);
1777                    dm.put(e, x);
1778                }
1779            }
1780        }
1781        return d;
1782    }
1783
1784
1785    /**
1786     * GenPolynomial polynomial partial derivative variable r.
1787     * @param <C> coefficient type.
1788     * @param P GenPolynomial.
1789     * @param r variable for partial deriviate.
1790     * @return derivative(P,r).
1791     */
1792    public static <C extends RingElem<C>> GenPolynomial<C> baseDerivative(GenPolynomial<C> P, int r) {
1793        if (P == null || P.isZERO()) {
1794            return P;
1795        }
1796        GenPolynomialRing<C> pfac = P.ring;
1797        if (r < 0 || pfac.nvar <= r) {
1798            throw new IllegalArgumentException(
1799                            P.getClass().getName() + " derivative variable out of bound " + r);
1800        }
1801        int rp = pfac.nvar - 1 - r;
1802        RingFactory<C> rf = pfac.coFac;
1803        GenPolynomial<C> d = pfac.getZERO().copy();
1804        Map<ExpVector, C> dm = d.val; //getMap();
1805        for (Map.Entry<ExpVector, C> m : P.getMap().entrySet()) {
1806            ExpVector f = m.getKey();
1807            long fl = f.getVal(rp);
1808            if (fl > 0) {
1809                C cf = rf.fromInteger(fl);
1810                C a = m.getValue();
1811                C x = a.multiply(cf);
1812                if (x != null && !x.isZERO()) {
1813                    ExpVector e = f.subst(rp, fl - 1L);
1814                    dm.put(e, x);
1815                }
1816            }
1817        }
1818        return d;
1819    }
1820
1821
1822    /**
1823     * GenPolynomial polynomial integral main variable.
1824     * @param <C> coefficient type.
1825     * @param P GenPolynomial.
1826     * @return integral(P).
1827     */
1828    public static <C extends RingElem<C>> GenPolynomial<C> baseIntegral(GenPolynomial<C> P) {
1829        if (P == null || P.isZERO()) {
1830            return P;
1831        }
1832        GenPolynomialRing<C> pfac = P.ring;
1833        if (pfac.nvar == 0) {
1834            return pfac.getONE();
1835        }
1836        if (pfac.nvar > 1) {
1837            // baseContent not possible by return type
1838            throw new IllegalArgumentException(P.getClass().getName() + " only for univariate polynomials");
1839        }
1840        RingFactory<C> rf = pfac.coFac;
1841        GenPolynomial<C> d = pfac.getZERO().copy();
1842        Map<ExpVector, C> dm = d.val; //getMap();
1843        for (Map.Entry<ExpVector, C> m : P.getMap().entrySet()) {
1844            ExpVector f = m.getKey();
1845            long fl = f.getVal(0);
1846            fl++;
1847            C cf = rf.fromInteger(fl);
1848            C a = m.getValue();
1849            C x = a.divide(cf);
1850            if (x != null && !x.isZERO()) {
1851                ExpVector e = ExpVector.create(1, 0, fl);
1852                dm.put(e, x);
1853            }
1854        }
1855        return d;
1856    }
1857
1858
1859    /**
1860     * GenPolynomial recursive polynomial derivative main variable.
1861     * @param <C> coefficient type.
1862     * @param P recursive GenPolynomial.
1863     * @return derivative(P).
1864     */
1865    public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> recursiveDerivative(
1866                    GenPolynomial<GenPolynomial<C>> P) {
1867        if (P == null || P.isZERO()) {
1868            return P;
1869        }
1870        GenPolynomialRing<GenPolynomial<C>> pfac = P.ring;
1871        if (pfac.nvar == 0) {
1872            return pfac.getZERO();
1873        }
1874        if (pfac.nvar > 1) {
1875            // baseContent not possible by return type
1876            throw new IllegalArgumentException(P.getClass().getName() + " only for univariate polynomials");
1877        }
1878        GenPolynomialRing<C> pr = (GenPolynomialRing<C>) pfac.coFac;
1879        RingFactory<C> rf = pr.coFac;
1880        GenPolynomial<GenPolynomial<C>> d = pfac.getZERO().copy();
1881        Map<ExpVector, GenPolynomial<C>> dm = d.val; //getMap();
1882        for (Map.Entry<ExpVector, GenPolynomial<C>> m : P.getMap().entrySet()) {
1883            ExpVector f = m.getKey();
1884            long fl = f.getVal(0);
1885            if (fl > 0) {
1886                C cf = rf.fromInteger(fl);
1887                GenPolynomial<C> a = m.getValue();
1888                GenPolynomial<C> x = a.multiply(cf);
1889                if (x != null && !x.isZERO()) {
1890                    ExpVector e = ExpVector.create(1, 0, fl - 1L);
1891                    dm.put(e, x);
1892                }
1893            }
1894        }
1895        return d;
1896    }
1897
1898
1899    /**
1900     * Factor coefficient bound. The product of all maxNorms of potential
1901     * factors is less than or equal to 2**b times the maxNorm of A. Gelfonds
1902     * bound is used.
1903     * @param e degree vector of a GenPolynomial A.
1904     * @return 2**b.
1905     * @see "maspoly.SACIPOL.mi#IPFCB from SAC2/MAS"
1906     */
1907    public static BigInteger factorBound(ExpVector e) {
1908        long n = 0;
1909        java.math.BigInteger p = java.math.BigInteger.ONE;
1910        java.math.BigInteger v;
1911        if (e == null || e.isZERO()) {
1912            return BigInteger.ONE;
1913        }
1914        for (int i = 0; i < e.length(); i++) {
1915            if (e.getVal(i) > 0L) {
1916                n += (2 * e.getVal(i) - 1);
1917                v = new java.math.BigInteger("" + (e.getVal(i) - 1));
1918                p = p.multiply(v);
1919            }
1920        }
1921        n += (p.bitCount() + 1); // log2(p)
1922        n /= 2;
1923        v = new java.math.BigInteger("" + 2);
1924        while (n >= 16) {
1925            n -= 16;
1926            v = v.shiftLeft(16);
1927        }
1928        if (n > 0) {
1929            v = v.shiftLeft((int) n); // n < 16
1930        }
1931        BigInteger N = new BigInteger(v);
1932        return N;
1933    }
1934
1935
1936    /**
1937     * Absolute norm. Square root of the sum of the squared coefficients.
1938     * @param p GenPolynomial
1939     * @return sqrt( sum<sub>i</sub> |c<sub>i</sub>|<sup>2</sup> ).
1940     */
1941    @SuppressWarnings("unchecked")
1942    public static <C extends RingElem<C>> C absNorm(GenPolynomial<C> p) {
1943        if (p == null) {
1944            return null;
1945        }
1946        C a = p.ring.getZEROCoefficient();
1947        if (a instanceof StarRingElem) {
1948            //System.out.println("StarRingElem case");
1949            for (C c : p.val.values()) {
1950                C n = (C) ((StarRingElem) c).norm();
1951                a = a.sum(n);
1952            }
1953        } else {
1954            for (C c : p.val.values()) {
1955                C n = c.multiply(c);
1956                a = a.sum(n);
1957            }
1958        }
1959        // compute square root if possible
1960        // refactor for sqrt in RingElem ?
1961        if (a instanceof BigRational) {
1962            BigRational b = (BigRational) a;
1963            a = (C) Roots.sqrt(b);
1964        } else if (a instanceof BigComplex) {
1965            BigComplex b = (BigComplex) a;
1966            a = (C) Roots.sqrt(b);
1967        } else if (a instanceof BigInteger) {
1968            BigInteger b = (BigInteger) a;
1969            a = (C) Roots.sqrt(b);
1970        } else if (a instanceof BigDecimal) {
1971            BigDecimal b = (BigDecimal) a;
1972            a = (C) Roots.sqrt(b);
1973        } else if (a instanceof BigDecimalComplex) {
1974            BigDecimalComplex b = (BigDecimalComplex) a;
1975            a = (C) Roots.sqrt(b);
1976        } else {
1977            logger.error("no square root implemented for {}", a.toScriptFactory());
1978        }
1979        return a;
1980    }
1981
1982
1983    /**
1984     * Polynomial reciprocal transformation.
1985     * @param <C> coefficient type.
1986     * @param A is a non-zero polynomial, with n=DEG(A).
1987     * @return B with B(x) = x**n*A(1/x), where x is the main variable of A.
1988     * @see "maspoly.SACPOL.mi#PRT from SAC2/MAS"
1989     */
1990    public static <C extends RingElem<C>> GenPolynomial<C> reciprocalTransformation(GenPolynomial<C> A) {
1991        return reciprocalTransformation(A, 0);
1992    }
1993
1994
1995    /**
1996     * Polynomial reciprocal transformation.
1997     * @param <C> coefficient type.
1998     * @param A is a non-zero polynomial, with n=DEG(A,i), A(x_r, ..., x_0).
1999     * @param i variable to be transformed, 0 is the main variable.
2000     * @return B with B(x) = x_i**n*A(1/x_i), where x_i is the i-th variable of
2001     *         A.
2002     * @see "maspoly.SACPOL.mi#PRT from SAC2/MAS"
2003     */
2004    public static <C extends RingElem<C>> GenPolynomial<C> reciprocalTransformation(GenPolynomial<C> A,
2005                    int i) {
2006        if (A == null) {
2007            return null;
2008        }
2009        GenPolynomialRing<C> pfac = A.ring;
2010        GenPolynomial<C> B = pfac.getZERO().copy();
2011        if (A.isZERO()) {
2012            return B;
2013        }
2014        int m = i;
2015        long d = A.degree(m);
2016        //System.out.println("d = " + d + ", m = " + m);
2017        Map<ExpVector, C> val = A.val;
2018        Map<ExpVector, C> valb = B.val;
2019        for (Map.Entry<ExpVector, C> me : val.entrySet()) {
2020            ExpVector e = me.getKey();
2021            long de = d - e.getVal(m);
2022            ExpVector f = e.subst(m, de);
2023            C c = me.getValue();
2024            valb.put(f, c);
2025        }
2026        return B;
2027    }
2028
2029
2030    /**
2031     * Polynomial translation, main variable.
2032     * @param <C> coefficient type.
2033     * @param A is a non-zero polynomial in r variables, A(x_1, ..., x(r-1),
2034     *            x_r).
2035     * @param h is a coefficient ring element.
2036     * @return B with B(x1, ..., x(r-1), xr) = A(x1, ..., x(r-1), xr+h).
2037     * @see "maspoly.SACIPOL.mi#IPTRAN from SAC2/MAS"
2038     */
2039    public static <C extends RingElem<C>> GenPolynomial<C> translationMain(GenPolynomial<C> A, C h) {
2040        if (A == null) {
2041            return null;
2042        }
2043        if (A.isZERO() || h.isZERO()) {
2044            return A;
2045        }
2046        GenPolynomialRing<C> pfac = A.ring;
2047        GenPolynomialRing<GenPolynomial<C>> rfac = pfac.recursive(1);
2048        GenPolynomial<GenPolynomial<C>> Ar = recursive(rfac, A);
2049        GenPolynomial<GenPolynomial<C>> Br = translationMainRecursive(Ar, h);
2050        GenPolynomial<C> B = distribute(pfac, Br);
2051        return B;
2052    }
2053
2054
2055    /**
2056     * Polynomial translation, main variable.
2057     * @param <C> coefficient type.
2058     * @param A is a non-zero recursive polynomial in r variables, A(x_1, ...,
2059     *            x(r-1))(x_r).
2060     * @param h is a coefficient ring element.
2061     * @return B with B(x1, ..., x(r-1))(xr) = A(x1, ..., x(r-1))(xr+h).
2062     * @see "maspoly.SACIPOL.mi#IPTRAN from SAC2/MAS"
2063     */
2064    public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> translationMainRecursive(
2065                    GenPolynomial<GenPolynomial<C>> A, C h) {
2066        if (A == null) {
2067            return null;
2068        }
2069        GenPolynomialRing<GenPolynomial<C>> pfac = A.ring;
2070        if (pfac.nvar != 1) {
2071            throw new IllegalArgumentException("translationMainRecursive no univariate polynomial");
2072        }
2073        if (A.isZERO() || h.isZERO()) {
2074            return A;
2075        }
2076        // assert descending exponents, i.e. compatible term order
2077        Map<ExpVector, GenPolynomial<C>> val = A.val;
2078        GenPolynomial<GenPolynomial<C>> c = null;
2079        ExpVector z = pfac.evzero;
2080        ExpVector x = pfac.evzero.subst(0, 1L);
2081        GenPolynomial<C> H = pfac.getONECoefficient().multiply(h);
2082        long el1 = -1; // undefined
2083        long el2 = -1;
2084        for (Map.Entry<ExpVector, GenPolynomial<C>> me : val.entrySet()) {
2085            ExpVector e = me.getKey();
2086            el2 = e.getVal(0);
2087            GenPolynomial<C> b = me.getValue();
2088            if (c == null) {
2089                c = pfac.valueOf(b, z);
2090            } else {
2091                for (long i = el2; i < el1; i++) { // i = 0, el1-el2.
2092                    GenPolynomial<GenPolynomial<C>> d1 = c.multiply(x);
2093                    GenPolynomial<GenPolynomial<C>> d2 = c.multiply(H);
2094                    c = d1.sum(d2);
2095                }
2096                c = c.sum(b);
2097            }
2098            el1 = el2;
2099        }
2100        for (long i = 0; i < el2; i++) {
2101            GenPolynomial<GenPolynomial<C>> d1 = c.multiply(x);
2102            GenPolynomial<GenPolynomial<C>> d2 = c.multiply(H);
2103            c = d1.sum(d2);
2104        }
2105        return c;
2106    }
2107
2108
2109    /**
2110     * Polynomial translation, base univariate.
2111     * @param <C> coefficient type.
2112     * @param A is a non-zero polynomial in 1 variables, A(x_1).
2113     * @param h is a coefficient ring element.
2114     * @return B with B(x1) = A(x1+h1).
2115     * @see "maspoly.SACIPOL.mi#IPTRAN from SAC2/MAS"
2116     */
2117    public static <C extends RingElem<C>> GenPolynomial<C> translationBase(GenPolynomial<C> A, C h) {
2118        if (A == null) {
2119            return null;
2120        }
2121        GenPolynomialRing<C> pfac = A.ring;
2122        if (pfac.nvar != 1) {
2123            throw new IllegalArgumentException("translationBase no univariate polynomial");
2124        }
2125        if (A.isZERO()) {
2126            return A;
2127        }
2128        // assert descending exponents, i.e. compatible term order
2129        Map<ExpVector, C> val = A.val;
2130        GenPolynomial<C> c = null;
2131        ExpVector z = pfac.evzero;
2132        ExpVector x = pfac.evzero.subst(0, 1L);
2133        long el1 = -1; // undefined
2134        long el2 = -1;
2135        for (Map.Entry<ExpVector, C> me : val.entrySet()) {
2136            ExpVector e = me.getKey();
2137            el2 = e.getVal(0);
2138            C b = me.getValue();
2139            if (c == null) {
2140                c = pfac.valueOf(b, z);
2141            } else {
2142                for (long i = el2; i < el1; i++) { // i = 0, el1-el2.
2143                    GenPolynomial<C> d1 = c.multiply(x);
2144                    GenPolynomial<C> d2 = c.multiply(h);
2145                    c = d1.sum(d2);
2146                }
2147                c = c.sum(b);
2148            }
2149            el1 = el2;
2150        }
2151        for (long i = 0; i < el2; i++) {
2152            GenPolynomial<C> d1 = c.multiply(x);
2153            GenPolynomial<C> d2 = c.multiply(h);
2154            c = d1.sum(d2);
2155        }
2156        return c;
2157    }
2158
2159
2160    /**
2161     * Polynomial translation, all variables.
2162     * @param <C> coefficient type.
2163     * @param A is a non-zero polynomial in r variables, A(x_1, ..., x(r-1),
2164     *            x_r).
2165     * @param H is a list of coefficient ring elements H = (h1, ..., hr).
2166     * @return B with B(x1, ..., x(r-1), xr) = A(x1+h1, ..., x(r-1)+h(r-1),
2167     *         xr+hr).
2168     * @see "maspoly.SACIPOL.mi#IPTRAN from SAC2/MAS"
2169     */
2170    public static <C extends RingElem<C>> GenPolynomial<C> translation(GenPolynomial<C> A, List<C> H) {
2171        if (A == null) {
2172            return null;
2173        }
2174        if (A.isZERO()) {
2175            return A;
2176        }
2177        GenPolynomialRing<C> pfac = A.ring;
2178        if (pfac.nvar <= 1) {
2179            return translationBase(A, H.get(0));
2180        }
2181        if (H == null || pfac.nvar != H.size()) {
2182            throw new IllegalArgumentException(
2183                            "number of translation points do not match number of variables " + pfac.nvar
2184                                            + " != " + H.size());
2185        }
2186        C h = H.get(0);
2187        List<C> L = H.subList(1, H.size());
2188        GenPolynomialRing<GenPolynomial<C>> rfac = pfac.recursive(1);
2189        GenPolynomial<GenPolynomial<C>> Ar = recursive(rfac, A);
2190        GenPolynomial<GenPolynomial<C>> Br = translationMainRecursive(Ar, h);
2191        GenPolynomial<GenPolynomial<C>> Cr = rfac.getZERO().copy();
2192        Map<ExpVector, GenPolynomial<C>> val = Br.val;
2193        Map<ExpVector, GenPolynomial<C>> cval = Cr.val;
2194        for (Map.Entry<ExpVector, GenPolynomial<C>> me : val.entrySet()) {
2195            ExpVector e = me.getKey();
2196            GenPolynomial<C> b = me.getValue();
2197            GenPolynomial<C> c = translation(b, L);
2198            cval.put(e, c);
2199        }
2200        GenPolynomial<C> B = distribute(pfac, Cr);
2201        return B;
2202    }
2203
2204
2205    /**
2206     * Polynomial translation, r-1 variables.
2207     * @param <C> coefficient type.
2208     * @param A is a non-zero polynomial in r variables, A(x_1, ..., x(r-1),
2209     *            x_r).
2210     * @param H is a list of coefficient ring elements H = (h2, ..., hr).
2211     * @return B with B(x1, ..., x(r-1), xr) = A(x1, x2+h2, ..., x(r-1)+h(r-1),
2212     *         xr+hr).
2213     * @see "maspoly.SACIPOL.mi#IPTRAN from SAC2/MAS"
2214     */
2215    public static <C extends RingElem<C>> GenPolynomial<C> translation1(GenPolynomial<C> A, List<C> H) {
2216        if (A == null) {
2217            return null;
2218        }
2219        if (A.isZERO()) {
2220            return A;
2221        }
2222        GenPolynomialRing<C> pfac = A.ring;
2223        if (pfac.nvar <= 1) {
2224            return A; //translationBase(A, H.get(0));
2225        }
2226        if (H == null || pfac.nvar - 1 != H.size()) {
2227            throw new IllegalArgumentException(
2228                            "number of translation points do not match number of variables " + (pfac.nvar - 1)
2229                                            + " != " + H.size());
2230        }
2231        C h = H.get(0);
2232        List<C> L = H.subList(1, H.size());
2233        GenPolynomialRing<GenPolynomial<C>> rfac = pfac.recursive(1);
2234        GenPolynomial<GenPolynomial<C>> Ar = recursive(rfac, A);
2235        GenPolynomial<GenPolynomial<C>> Br = translationMainRecursive(Ar, h);
2236        GenPolynomial<GenPolynomial<C>> Cr = rfac.getZERO().copy();
2237        Map<ExpVector, GenPolynomial<C>> val = Br.val;
2238        Map<ExpVector, GenPolynomial<C>> cval = Cr.val;
2239        for (Map.Entry<ExpVector, GenPolynomial<C>> me : val.entrySet()) {
2240            ExpVector e = me.getKey();
2241            GenPolynomial<C> b = me.getValue();
2242            GenPolynomial<C> c = translation1(b, L);
2243            cval.put(e, c);
2244        }
2245        GenPolynomial<C> B = distribute(pfac, Cr);
2246        return B;
2247    }
2248
2249
2250    /**
2251     * Evaluate at main variable.
2252     * @param <C> coefficient type.
2253     * @param cfac coefficient polynomial ring factory.
2254     * @param A recursive polynomial to be evaluated.
2255     * @param a value to evaluate at.
2256     * @return A( x_1, ..., x_{n-1}, a ).
2257     */
2258    public static <C extends RingElem<C>> GenPolynomial<C> evaluateMainRecursive(GenPolynomialRing<C> cfac,
2259                    GenPolynomial<GenPolynomial<C>> A, C a) {
2260        if (A == null || A.isZERO()) {
2261            return cfac.getZERO();
2262        }
2263        if (A.ring.nvar != 1) {
2264            throw new IllegalArgumentException("evaluateMain no univariate polynomial");
2265        }
2266        if (a == null || a.isZERO()) {
2267            return A.trailingBaseCoefficient();
2268        }
2269        // assert descending exponents, i.e. compatible term order
2270        Map<ExpVector, GenPolynomial<C>> val = A.getMap();
2271        GenPolynomial<C> B = null;
2272        long el1 = -1; // undefined
2273        long el2 = -1;
2274        for (Map.Entry<ExpVector, GenPolynomial<C>> me : val.entrySet()) {
2275            ExpVector e = me.getKey();
2276            el2 = e.getVal(0);
2277            if (B == null /*el1 < 0*/) { // first turn
2278                B = me.getValue();
2279            } else {
2280                for (long i = el2; i < el1; i++) {
2281                    B = B.multiply(a);
2282                }
2283                B = B.sum(me.getValue());
2284            }
2285            el1 = el2;
2286        }
2287        for (long i = 0; i < el2; i++) {
2288            B = B.multiply(a);
2289        }
2290        return B;
2291    }
2292
2293
2294    /**
2295     * Evaluate at main variable.
2296     * @param <C> coefficient type.
2297     * @param cfac coefficient polynomial ring factory.
2298     * @param A distributed polynomial to be evaluated.
2299     * @param a value to evaluate at.
2300     * @return A( x_1, ..., x_{n-1}, a ).
2301     */
2302    public static <C extends RingElem<C>> GenPolynomial<C> evaluateMain(GenPolynomialRing<C> cfac,
2303                    GenPolynomial<C> A, C a) {
2304        if (A == null || A.isZERO()) {
2305            return cfac.getZERO();
2306        }
2307        GenPolynomialRing<GenPolynomial<C>> rfac = A.ring.recursive(1);
2308        if (rfac.nvar + cfac.nvar != A.ring.nvar) {
2309            throw new IllegalArgumentException("evaluateMain number of variables mismatch");
2310        }
2311        GenPolynomial<GenPolynomial<C>> Ap = recursive(rfac, A);
2312        return PolyUtil.<C> evaluateMainRecursive(cfac, Ap, a);
2313    }
2314
2315
2316    /**
2317     * Evaluate at main variable.
2318     * @param <C> coefficient type.
2319     * @param cfac coefficient ring factory.
2320     * @param L list of univariate polynomials to be evaluated.
2321     * @param a value to evaluate at.
2322     * @return list( A( x_1, ..., x_{n-1}, a ) ) for A in L.
2323     */
2324    public static <C extends RingElem<C>> List<GenPolynomial<C>> evaluateMain(GenPolynomialRing<C> cfac,
2325                    List<GenPolynomial<C>> L, C a) {
2326        return ListUtil.<GenPolynomial<C>, GenPolynomial<C>> map(L, new EvalMainPol<C>(cfac, a));
2327    }
2328
2329
2330    /**
2331     * Evaluate at main variable.
2332     * @param <C> coefficient type.
2333     * @param cfac coefficient ring factory.
2334     * @param A univariate polynomial to be evaluated.
2335     * @param a value to evaluate at.
2336     * @return A( a ).
2337     */
2338    public static <C extends RingElem<C>> C evaluateMain(RingFactory<C> cfac, GenPolynomial<C> A, C a) {
2339        if (A == null || A.isZERO()) {
2340            return cfac.getZERO();
2341        }
2342        if (A.ring.nvar != 1) {
2343            throw new IllegalArgumentException("evaluateMain no univariate polynomial");
2344        }
2345        if (a == null || a.isZERO()) {
2346            return A.trailingBaseCoefficient();
2347        }
2348        // assert decreasing exponents, i.e. compatible term order
2349        Map<ExpVector, C> val = A.getMap();
2350        C B = null;
2351        long el1 = -1; // undefined
2352        long el2 = -1;
2353        for (Map.Entry<ExpVector, C> me : val.entrySet()) {
2354            ExpVector e = me.getKey();
2355            el2 = e.getVal(0);
2356            if (B == null /*el1 < 0*/) { // first turn
2357                B = me.getValue();
2358            } else {
2359                for (long i = el2; i < el1; i++) {
2360                    B = B.multiply(a);
2361                }
2362                B = B.sum(me.getValue());
2363            }
2364            el1 = el2;
2365        }
2366        for (long i = 0; i < el2; i++) {
2367            B = B.multiply(a);
2368        }
2369        return B;
2370    }
2371
2372
2373    /**
2374     * Evaluate at main variable.
2375     * @param <C> coefficient type.
2376     * @param cfac coefficient ring factory.
2377     * @param L list of univariate polynomial to be evaluated.
2378     * @param a value to evaluate at.
2379     * @return list( A( a ) ) for A in L.
2380     */
2381    public static <C extends RingElem<C>> List<C> evaluateMain(RingFactory<C> cfac, List<GenPolynomial<C>> L,
2382                    C a) {
2383        return ListUtil.<GenPolynomial<C>, C> map(L, new EvalMain<C>(cfac, a));
2384    }
2385
2386
2387    /**
2388     * Evaluate at k-th variable.
2389     * @param <C> coefficient type.
2390     * @param cfac coefficient polynomial ring in k variables C[x_1, ..., x_k]
2391     *            factory.
2392     * @param rfac coefficient polynomial ring C[x_1, ..., x_{k-1}] [x_k]
2393     *            factory, a recursive polynomial ring in 1 variable with
2394     *            coefficients in k-1 variables.
2395     * @param nfac polynomial ring in n-1 variables C[x_1, ..., x_{k-1}]
2396     *            [x_{k+1}, ..., x_n] factory, a recursive polynomial ring in
2397     *            n-k+1 variables with coefficients in k-1 variables.
2398     * @param dfac polynomial ring in n-1 variables. C[x_1, ..., x_{k-1},
2399     *            x_{k+1}, ..., x_n] factory.
2400     * @param A polynomial to be evaluated.
2401     * @param a value to evaluate at.
2402     * @return A( x_1, ..., x_{k-1}, a, x_{k+1}, ..., x_n).
2403     */
2404    public static <C extends RingElem<C>> GenPolynomial<C> evaluate(GenPolynomialRing<C> cfac,
2405                    GenPolynomialRing<GenPolynomial<C>> rfac, GenPolynomialRing<GenPolynomial<C>> nfac,
2406                    GenPolynomialRing<C> dfac, GenPolynomial<C> A, C a) {
2407        if (rfac.nvar != 1) {
2408            throw new IllegalArgumentException("evaluate coefficient ring not univariate");
2409        }
2410        if (A == null || A.isZERO()) {
2411            return cfac.getZERO();
2412        }
2413        Map<ExpVector, GenPolynomial<C>> Ap = A.contract(cfac);
2414        GenPolynomialRing<C> rcf = (GenPolynomialRing<C>) rfac.coFac;
2415        GenPolynomial<GenPolynomial<C>> Ev = nfac.getZERO().copy();
2416        Map<ExpVector, GenPolynomial<C>> Evm = Ev.val; //getMap();
2417        for (Map.Entry<ExpVector, GenPolynomial<C>> m : Ap.entrySet()) {
2418            ExpVector e = m.getKey();
2419            GenPolynomial<C> b = m.getValue();
2420            GenPolynomial<GenPolynomial<C>> c = recursive(rfac, b);
2421            GenPolynomial<C> d = evaluateMainRecursive(rcf, c, a);
2422            if (d != null && !d.isZERO()) {
2423                Evm.put(e, d);
2424            }
2425        }
2426        GenPolynomial<C> B = distribute(dfac, Ev);
2427        return B;
2428    }
2429
2430
2431    /**
2432     * Evaluate at first (lowest) variable.
2433     * @param <C> coefficient type.
2434     * @param cfac coefficient polynomial ring in first variable C[x_1] factory.
2435     * @param dfac polynomial ring in n-1 variables. C[x_2, ..., x_n] factory.
2436     * @param A polynomial to be evaluated.
2437     * @param a value to evaluate at.
2438     * @return A( a, x_2, ..., x_n).
2439     */
2440    public static <C extends RingElem<C>> GenPolynomial<C> evaluateFirst(GenPolynomialRing<C> cfac,
2441                    GenPolynomialRing<C> dfac, GenPolynomial<C> A, C a) {
2442        if (A == null || A.isZERO()) {
2443            return dfac.getZERO();
2444        }
2445        Map<ExpVector, GenPolynomial<C>> Ap = A.contract(cfac);
2446        //RingFactory<C> rcf = cfac.coFac; // == dfac.coFac
2447
2448        GenPolynomial<C> B = dfac.getZERO().copy();
2449        Map<ExpVector, C> Bm = B.val; //getMap();
2450
2451        for (Map.Entry<ExpVector, GenPolynomial<C>> m : Ap.entrySet()) {
2452            ExpVector e = m.getKey();
2453            GenPolynomial<C> b = m.getValue();
2454            C d = evaluateMain(cfac.coFac, b, a);
2455            if (d != null && !d.isZERO()) {
2456                Bm.put(e, d);
2457            }
2458        }
2459        return B;
2460    }
2461
2462
2463    /**
2464     * Evaluate at first (lowest) variable. Could also be called
2465     * <code>evaluateFirst()</code>, but type erasure of parameter
2466     * <code>A</code> does not allow the same name.
2467     * @param <C> coefficient type.
2468     * @param cfac coefficient polynomial ring in first variable C[x_1] factory.
2469     * @param dfac polynomial ring in n-1 variables. C[x_2, ..., x_n] factory.
2470     * @param A recursive polynomial to be evaluated.
2471     * @param a value to evaluate at.
2472     * @return A( a, x_2, ..., x_n).
2473     */
2474    public static <C extends RingElem<C>> GenPolynomial<C> evaluateFirstRec(GenPolynomialRing<C> cfac,
2475                    GenPolynomialRing<C> dfac, GenPolynomial<GenPolynomial<C>> A, C a) {
2476        if (A == null || A.isZERO()) {
2477            return dfac.getZERO();
2478        }
2479        Map<ExpVector, GenPolynomial<C>> Ap = A.getMap();
2480        GenPolynomial<C> B = dfac.getZERO().copy();
2481        Map<ExpVector, C> Bm = B.val; //getMap();
2482        for (Map.Entry<ExpVector, GenPolynomial<C>> m : Ap.entrySet()) {
2483            ExpVector e = m.getKey();
2484            GenPolynomial<C> b = m.getValue();
2485            C d = evaluateMain(cfac.coFac, b, a);
2486            if (d != null && !d.isZERO()) {
2487                Bm.put(e, d);
2488            }
2489        }
2490        return B;
2491    }
2492
2493
2494    /**
2495     * Evaluate all variables.
2496     * @param <C> coefficient type.
2497     * @param cfac coefficient ring factory.
2498     * @param L list of polynomials to be evaluated.
2499     * @param a = (a_1, a_2, ..., a_n) a tuple of values to evaluate at.
2500     * @return L = ( A_1(a_1, a_2, ..., a_n), ... A_k(a_1, a_2, ..., a_n)).
2501     */
2502    public static <C extends RingElem<C>> List<C> evaluateAll(RingFactory<C> cfac, List<GenPolynomial<C>> L,
2503                    List<C> a) {
2504        return ListUtil.<GenPolynomial<C>, C> map(L, new EvalAllPol<C>(cfac, a));
2505    }
2506
2507
2508    /**
2509     * Evaluate all variables.
2510     * @param <C> coefficient type.
2511     * @param cfac coefficient ring factory.
2512     * @param A polynomial to be evaluated.
2513     * @param a = (a_1, a_2, ..., a_n) a tuple of values to evaluate at.
2514     * @return A(a_1, a_2, ..., a_n).
2515     */
2516    public static <C extends RingElem<C>> C evaluateAll(RingFactory<C> cfac, GenPolynomial<C> A, List<C> a) {
2517        if (A == null || A.isZERO()) {
2518            return cfac.getZERO();
2519        }
2520        GenPolynomialRing<C> dfac = A.ring;
2521        if (a == null || a.size() != dfac.nvar) {
2522            throw new IllegalArgumentException("evaluate tuple size not equal to number of variables");
2523        }
2524        if (dfac.nvar == 0) {
2525            return A.trailingBaseCoefficient();
2526        }
2527        if (dfac.nvar == 1) {
2528            return evaluateMain(cfac, A, a.get(0));
2529        }
2530        C b = cfac.getZERO();
2531        GenPolynomial<C> Ap = A;
2532        for (int k = 0; k < dfac.nvar - 1; k++) {
2533            C ap = a.get(k);
2534            GenPolynomialRing<C> c1fac = new GenPolynomialRing<C>(cfac, 1); // no vars
2535            GenPolynomialRing<C> cnfac = new GenPolynomialRing<C>(cfac, dfac.nvar - 1 - k); // no vars
2536            GenPolynomial<C> Bp = evaluateFirst(c1fac, cnfac, Ap, ap);
2537            if (Bp.isZERO()) {
2538                return b;
2539            }
2540            Ap = Bp;
2541            //System.out.println("Ap = " + Ap);
2542        }
2543        C ap = a.get(dfac.nvar - 1);
2544        b = evaluateMain(cfac, Ap, ap);
2545        return b;
2546    }
2547
2548
2549    /**
2550     * Substitute main variable.
2551     * @param A univariate polynomial.
2552     * @param s polynomial for substitution.
2553     * @return polynomial A(x &lt;- s).
2554     */
2555    public static <C extends RingElem<C>> GenPolynomial<C> substituteMain(GenPolynomial<C> A,
2556                    GenPolynomial<C> s) {
2557        return substituteUnivariate(A, s);
2558    }
2559
2560
2561    /**
2562     * Substitute univariate polynomial.
2563     * @param f univariate polynomial.
2564     * @param t polynomial for substitution.
2565     * @return polynomial f(x &lt;- t).
2566     */
2567    public static <C extends RingElem<C>> GenPolynomial<C> substituteUnivariate(GenPolynomial<C> f,
2568                    GenPolynomial<C> t) {
2569        if (f == null || t == null) {
2570            return null;
2571        }
2572        GenPolynomialRing<C> fac = f.ring;
2573        if (fac.nvar > 1) {
2574            throw new IllegalArgumentException("only for univariate polynomial f");
2575        }
2576        if (f.isZERO() || f.isConstant()) {
2577            return f;
2578        }
2579        if (t.ring.nvar > 1) {
2580            fac = t.ring;
2581        }
2582        // assert descending exponents, i.e. compatible term order
2583        Map<ExpVector, C> val = f.getMap();
2584        GenPolynomial<C> s = null;
2585        long el1 = -1; // undefined
2586        long el2 = -1;
2587        for (Map.Entry<ExpVector, C> me : val.entrySet()) {
2588            ExpVector e = me.getKey();
2589            el2 = e.getVal(0);
2590            if (s == null /*el1 < 0*/) { // first turn
2591                s = fac.getZERO().sum(me.getValue());
2592            } else {
2593                for (long i = el2; i < el1; i++) {
2594                    s = s.multiply(t);
2595                }
2596                s = s.sum(me.getValue());
2597            }
2598            el1 = el2;
2599        }
2600        for (long i = 0; i < el2; i++) {
2601            s = s.multiply(t);
2602        }
2603        //System.out.println("s = " + s);
2604        return s;
2605    }
2606
2607
2608    /**
2609     * Substitute univariate polynomial with multivariate coefficients.
2610     * @param f univariate polynomial with multivariate coefficients.
2611     * @param t polynomial for substitution.
2612     * @return polynomial f(x &lt;- t).
2613     */
2614    public static <C extends RingElem<C>> GenPolynomial<C> substituteUnivariateMult(GenPolynomial<C> f,
2615                    GenPolynomial<C> t) {
2616        if (f == null || t == null) {
2617            return null;
2618        }
2619        GenPolynomialRing<C> fac = f.ring;
2620        if (fac.nvar == 1) {
2621            return substituteUnivariate(f, t);
2622        }
2623        GenPolynomialRing<GenPolynomial<C>> rfac = fac.recursive(1);
2624        GenPolynomial<GenPolynomial<C>> fr = PolyUtil.<C> recursive(rfac, f);
2625        GenPolynomial<GenPolynomial<C>> tr = PolyUtil.<C> recursive(rfac, t);
2626        //System.out.println("fr = " + fr);
2627        //System.out.println("tr = " + tr);
2628        GenPolynomial<GenPolynomial<C>> sr = PolyUtil.<GenPolynomial<C>> substituteUnivariate(fr, tr);
2629        //System.out.println("sr = " + sr);
2630        GenPolynomial<C> s = PolyUtil.<C> distribute(fac, sr);
2631        return s;
2632    }
2633
2634
2635    /**
2636     * Taylor series for polynomial.
2637     * @param f univariate polynomial.
2638     * @param a expansion point.
2639     * @return Taylor series (a polynomial) of f at a.
2640     */
2641    public static <C extends RingElem<C>> GenPolynomial<C> seriesOfTaylor(GenPolynomial<C> f, C a) {
2642        if (f == null) {
2643            return null;
2644        }
2645        GenPolynomialRing<C> fac = f.ring;
2646        if (fac.nvar > 1) {
2647            throw new IllegalArgumentException("only for univariate polynomials");
2648        }
2649        if (f.isZERO() || f.isConstant()) {
2650            return f;
2651        }
2652        GenPolynomial<C> s = fac.getZERO();
2653        C fa = PolyUtil.<C> evaluateMain(fac.coFac, f, a);
2654        s = s.sum(fa);
2655        long n = 1;
2656        long i = 0;
2657        GenPolynomial<C> g = PolyUtil.<C> baseDerivative(f);
2658        //GenPolynomial<C> p = fac.getONE();
2659        while (!g.isZERO()) {
2660            i++;
2661            n *= i;
2662            fa = PolyUtil.<C> evaluateMain(fac.coFac, g, a);
2663            GenPolynomial<C> q = fac.univariate(0, i); //p;
2664            q = q.multiply(fa);
2665            q = q.divide(fac.fromInteger(n));
2666            s = s.sum(q);
2667            g = PolyUtil.<C> baseDerivative(g);
2668        }
2669        //System.out.println("s = " + s);
2670        return s;
2671    }
2672
2673
2674    /**
2675     * ModInteger interpolate on first variable.
2676     * @param <C> coefficient type.
2677     * @param fac GenPolynomial<C> result factory.
2678     * @param A GenPolynomial.
2679     * @param M GenPolynomial interpolation modul of A.
2680     * @param mi inverse of M(am) in ring fac.coFac.
2681     * @param B evaluation of other GenPolynomial.
2682     * @param am evaluation point (interpolation modul) of B, i.e. P(am) = B.
2683     * @return S, with S mod M == A and S(am) == B.
2684     */
2685    public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> interpolate(
2686                    GenPolynomialRing<GenPolynomial<C>> fac, GenPolynomial<GenPolynomial<C>> A,
2687                    GenPolynomial<C> M, C mi, GenPolynomial<C> B, C am) {
2688        GenPolynomial<GenPolynomial<C>> S = fac.getZERO().copy();
2689        GenPolynomial<GenPolynomial<C>> Ap = A.copy();
2690        SortedMap<ExpVector, GenPolynomial<C>> av = Ap.val; //getMap();
2691        SortedMap<ExpVector, C> bv = B.getMap();
2692        SortedMap<ExpVector, GenPolynomial<C>> sv = S.val; //getMap();
2693        GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) fac.coFac;
2694        RingFactory<C> bfac = cfac.coFac;
2695        GenPolynomial<C> c = null;
2696        for (Map.Entry<ExpVector, C> me : bv.entrySet()) {
2697            ExpVector e = me.getKey();
2698            C y = me.getValue(); //bv.get(e); // assert y != null
2699            GenPolynomial<C> x = av.get(e);
2700            if (x != null) {
2701                av.remove(e);
2702                c = PolyUtil.<C> interpolate(cfac, x, M, mi, y, am);
2703                if (!c.isZERO()) { // 0 cannot happen
2704                    sv.put(e, c);
2705                }
2706            } else {
2707                c = PolyUtil.<C> interpolate(cfac, cfac.getZERO(), M, mi, y, am);
2708                if (!c.isZERO()) { // 0 cannot happen
2709                    sv.put(e, c); // c != null
2710                }
2711            }
2712        }
2713        // assert bv is empty = done
2714        for (Map.Entry<ExpVector, GenPolynomial<C>> me : av.entrySet()) { // rest of av
2715            ExpVector e = me.getKey();
2716            GenPolynomial<C> x = me.getValue(); //av.get(e); // assert x != null
2717            c = PolyUtil.<C> interpolate(cfac, x, M, mi, bfac.getZERO(), am);
2718            if (!c.isZERO()) { // 0 cannot happen
2719                sv.put(e, c); // c != null
2720            }
2721        }
2722        return S;
2723    }
2724
2725
2726    /**
2727     * Univariate polynomial interpolation.
2728     * @param <C> coefficient type.
2729     * @param fac GenPolynomial<C> result factory.
2730     * @param A GenPolynomial.
2731     * @param M GenPolynomial interpolation modul of A.
2732     * @param mi inverse of M(am) in ring fac.coFac.
2733     * @param a evaluation of other GenPolynomial.
2734     * @param am evaluation point (interpolation modul) of a, i.e. P(am) = a.
2735     * @return S, with S mod M == A and S(am) == a.
2736     */
2737    public static <C extends RingElem<C>> GenPolynomial<C> interpolate(GenPolynomialRing<C> fac,
2738                    GenPolynomial<C> A, GenPolynomial<C> M, C mi, C a, C am) {
2739        GenPolynomial<C> s;
2740        C b = PolyUtil.<C> evaluateMain(fac.coFac, A, am);
2741        // A mod a.modul
2742        C d = a.subtract(b); // a-A mod a.modul
2743        if (d.isZERO()) {
2744            return A;
2745        }
2746        b = d.multiply(mi); // b = (a-A)*mi mod a.modul
2747        // (M*b)+A mod M = A mod M = 
2748        // (M*mi*(a-A)+A) mod a.modul = a mod a.modul
2749        s = M.multiply(b);
2750        s = s.sum(A);
2751        return s;
2752    }
2753
2754
2755    /**
2756     * Recursive GenPolynomial switch variable blocks.
2757     * @param <C> coefficient type.
2758     * @param P recursive GenPolynomial in R[X,Y].
2759     * @return this in R[Y,X].
2760     */
2761    public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> switchVariables(
2762                    GenPolynomial<GenPolynomial<C>> P) {
2763        if (P == null) {
2764            throw new IllegalArgumentException("P == null");
2765        }
2766        GenPolynomialRing<GenPolynomial<C>> rfac1 = P.ring;
2767        GenPolynomialRing<C> cfac1 = (GenPolynomialRing<C>) rfac1.coFac;
2768        GenPolynomialRing<C> cfac2 = new GenPolynomialRing<C>(cfac1.coFac, rfac1);
2769        GenPolynomial<C> zero = cfac2.getZERO();
2770        GenPolynomialRing<GenPolynomial<C>> rfac2 = new GenPolynomialRing<GenPolynomial<C>>(cfac2, cfac1);
2771        GenPolynomial<GenPolynomial<C>> B = rfac2.getZERO().copy();
2772        if (P.isZERO()) {
2773            return B;
2774        }
2775        for (Monomial<GenPolynomial<C>> mr : P) {
2776            GenPolynomial<C> cr = mr.c;
2777            for (Monomial<C> mc : cr) {
2778                GenPolynomial<C> c = zero.sum(mc.c, mr.e);
2779                B = B.sum(c, mc.e);
2780            }
2781        }
2782        return B;
2783    }
2784
2785
2786    /**
2787     * Maximal degree of leading terms of a polynomial list.
2788     * @return maximum degree of the leading terms of a polynomial list.
2789     */
2790    public static <C extends RingElem<C>> long totalDegreeLeadingTerm(List<GenPolynomial<C>> P) {
2791        long degree = 0;
2792        for (GenPolynomial<C> g : P) {
2793            long total = g.leadingExpVector().totalDeg();
2794            if (degree < total) {
2795                degree = total;
2796            }
2797        }
2798        return degree;
2799    }
2800
2801
2802    /**
2803     * Total degree of polynomial list.
2804     * @return total degree of the polynomial list.
2805     */
2806    public static <C extends RingElem<C>> long totalDegree(List<GenPolynomial<C>> P) {
2807        long degree = 0;
2808        for (GenPolynomial<C> g : P) {
2809            long total = g.totalDegree();
2810            if (degree < total) {
2811                degree = total;
2812            }
2813        }
2814        return degree;
2815    }
2816
2817
2818    /**
2819     * Maximal degree of polynomial list.
2820     * @return maximal degree of the polynomial list.
2821     */
2822    public static <C extends RingElem<C>> long maxDegree(List<GenPolynomial<C>> P) {
2823        long degree = 0;
2824        for (GenPolynomial<C> g : P) {
2825            long total = g.degree();
2826            if (degree < total) {
2827                degree = total;
2828            }
2829        }
2830        return degree;
2831    }
2832
2833
2834    /**
2835     * Maximal degree in the coefficient polynomials.
2836     * @param <C> coefficient type.
2837     * @return maximal degree in the coefficients.
2838     */
2839    public static <C extends RingElem<C>> long coeffMaxDegree(GenPolynomial<GenPolynomial<C>> A) {
2840        if (A.isZERO()) {
2841            return 0; // 0 or -1 ?;
2842        }
2843        long deg = 0;
2844        for (GenPolynomial<C> a : A.getMap().values()) {
2845            long d = a.degree();
2846            if (d > deg) {
2847                deg = d;
2848            }
2849        }
2850        return deg;
2851    }
2852
2853
2854    /**
2855     * Map a unary function to the coefficients.
2856     * @param ring result polynomial ring factory.
2857     * @param p polynomial.
2858     * @param f evaluation functor.
2859     * @return new polynomial with coefficients f(p(e)).
2860     */
2861    public static <C extends RingElem<C>, D extends RingElem<D>> GenPolynomial<D> map(
2862                    GenPolynomialRing<D> ring, GenPolynomial<C> p, UnaryFunctor<C, D> f) {
2863        GenPolynomial<D> n = ring.getZERO().copy();
2864        SortedMap<ExpVector, D> nv = n.val;
2865        for (Monomial<C> m : p) {
2866            D c = f.eval(m.c);
2867            if (c != null && !c.isZERO()) {
2868                nv.put(m.e, c);
2869            }
2870        }
2871        return n;
2872    }
2873
2874
2875    /**
2876     * Product representation.
2877     * @param <C> coefficient type.
2878     * @param pfac polynomial ring factory.
2879     * @param L list of polynomials to be represented.
2880     * @return Product representation of L in the polynomial ring pfac.
2881     */
2882    public static <C extends GcdRingElem<C>> List<GenPolynomial<Product<C>>> toProductGen(
2883                    GenPolynomialRing<Product<C>> pfac, List<GenPolynomial<C>> L) {
2884
2885        List<GenPolynomial<Product<C>>> list = new ArrayList<GenPolynomial<Product<C>>>();
2886        if (L == null || L.size() == 0) {
2887            return list;
2888        }
2889        for (GenPolynomial<C> a : L) {
2890            GenPolynomial<Product<C>> b = toProductGen(pfac, a);
2891            list.add(b);
2892        }
2893        return list;
2894    }
2895
2896
2897    /**
2898     * Product representation.
2899     * @param <C> coefficient type.
2900     * @param pfac polynomial ring factory.
2901     * @param A polynomial to be represented.
2902     * @return Product representation of A in the polynomial ring pfac.
2903     */
2904    public static <C extends GcdRingElem<C>> GenPolynomial<Product<C>> toProductGen(
2905                    GenPolynomialRing<Product<C>> pfac, GenPolynomial<C> A) {
2906
2907        GenPolynomial<Product<C>> P = pfac.getZERO().copy();
2908        if (A == null || A.isZERO()) {
2909            return P;
2910        }
2911        RingFactory<Product<C>> rpfac = pfac.coFac;
2912        ProductRing<C> rfac = (ProductRing<C>) rpfac;
2913        for (Map.Entry<ExpVector, C> y : A.getMap().entrySet()) {
2914            ExpVector e = y.getKey();
2915            C a = y.getValue();
2916            Product<C> p = toProductGen(rfac, a);
2917            if (!p.isZERO()) {
2918                P.doPutToMap(e, p);
2919            }
2920        }
2921        return P;
2922    }
2923
2924
2925    /**
2926     * Product representation.
2927     * @param <C> coefficient type.
2928     * @param pfac product ring factory.
2929     * @param c coefficient to be represented.
2930     * @return Product representation of c in the ring pfac.
2931     */
2932    public static <C extends GcdRingElem<C>> Product<C> toProductGen(ProductRing<C> pfac, C c) {
2933
2934        SortedMap<Integer, C> elem = new TreeMap<Integer, C>();
2935        for (int i = 0; i < pfac.length(); i++) {
2936            RingFactory<C> rfac = pfac.getFactory(i);
2937            C u = rfac.copy(c);
2938            if (u != null && !u.isZERO()) {
2939                elem.put(i, u);
2940            }
2941        }
2942        return new Product<C>(pfac, elem);
2943    }
2944
2945
2946    /**
2947     * Product representation.
2948     * @param <C> coefficient type.
2949     * @param pfac product polynomial ring factory.
2950     * @param c coefficient to be used.
2951     * @param e exponent vector.
2952     * @return Product representation of c X^e in the ring pfac.
2953     */
2954    public static <C extends RingElem<C>> Product<GenPolynomial<C>> toProduct(
2955                    ProductRing<GenPolynomial<C>> pfac, C c, ExpVector e) {
2956        SortedMap<Integer, GenPolynomial<C>> elem = new TreeMap<Integer, GenPolynomial<C>>();
2957        for (int i = 0; i < e.length(); i++) {
2958            RingFactory<GenPolynomial<C>> rfac = pfac.getFactory(i);
2959            GenPolynomialRing<C> fac = (GenPolynomialRing<C>) rfac;
2960            //GenPolynomialRing<C> cfac = fac.ring;
2961            long a = e.getVal(i);
2962            GenPolynomial<C> u;
2963            if (a == 0) {
2964                u = fac.getONE();
2965            } else {
2966                u = fac.univariate(0, a);
2967            }
2968            u = u.multiply(c);
2969            elem.put(i, u);
2970        }
2971        return new Product<GenPolynomial<C>>(pfac, elem);
2972    }
2973
2974
2975    /**
2976     * Product representation.
2977     * @param <C> coefficient type.
2978     * @param pfac product polynomial ring factory.
2979     * @param A polynomial.
2980     * @return Product representation of the terms of A in the ring pfac.
2981     */
2982    public static <C extends RingElem<C>> Product<GenPolynomial<C>> toProduct(
2983                    ProductRing<GenPolynomial<C>> pfac, GenPolynomial<C> A) {
2984        Product<GenPolynomial<C>> P = pfac.getZERO();
2985        if (A == null || A.isZERO()) {
2986            return P;
2987        }
2988        for (Map.Entry<ExpVector, C> y : A.getMap().entrySet()) {
2989            ExpVector e = y.getKey();
2990            C a = y.getValue();
2991            Product<GenPolynomial<C>> p = toProduct(pfac, a, e);
2992            P = P.sum(p);
2993        }
2994        return P;
2995    }
2996
2997
2998    /**
2999     * Product representation.
3000     * @param pfac product ring factory.
3001     * @param c coefficient to be represented.
3002     * @return Product representation of c in the ring pfac.
3003     */
3004    public static Product<ModInteger> toProduct(ProductRing<ModInteger> pfac, BigInteger c) {
3005
3006        SortedMap<Integer, ModInteger> elem = new TreeMap<Integer, ModInteger>();
3007        for (int i = 0; i < pfac.length(); i++) {
3008            RingFactory<ModInteger> rfac = pfac.getFactory(i);
3009            ModIntegerRing fac = (ModIntegerRing) rfac;
3010            ModInteger u = fac.fromInteger(c.getVal());
3011            if (!u.isZERO()) {
3012                elem.put(i, u);
3013            }
3014        }
3015        return new Product<ModInteger>(pfac, elem);
3016    }
3017
3018
3019    /**
3020     * Product representation.
3021     * @param pfac polynomial ring factory.
3022     * @param A polynomial to be represented.
3023     * @return Product representation of A in the polynomial ring pfac.
3024     */
3025    public static GenPolynomial<Product<ModInteger>> toProduct(GenPolynomialRing<Product<ModInteger>> pfac,
3026                    GenPolynomial<BigInteger> A) {
3027
3028        GenPolynomial<Product<ModInteger>> P = pfac.getZERO().copy();
3029        if (A == null || A.isZERO()) {
3030            return P;
3031        }
3032        RingFactory<Product<ModInteger>> rpfac = pfac.coFac;
3033        ProductRing<ModInteger> fac = (ProductRing<ModInteger>) rpfac;
3034        for (Map.Entry<ExpVector, BigInteger> y : A.getMap().entrySet()) {
3035            ExpVector e = y.getKey();
3036            BigInteger a = y.getValue();
3037            Product<ModInteger> p = toProduct(fac, a);
3038            if (!p.isZERO()) {
3039                P.doPutToMap(e, p);
3040            }
3041        }
3042        return P;
3043    }
3044
3045
3046    /**
3047     * Product representation.
3048     * @param pfac polynomial ring factory.
3049     * @param L list of polynomials to be represented.
3050     * @return Product representation of L in the polynomial ring pfac.
3051     */
3052    public static List<GenPolynomial<Product<ModInteger>>> toProduct(
3053                    GenPolynomialRing<Product<ModInteger>> pfac, List<GenPolynomial<BigInteger>> L) {
3054
3055        List<GenPolynomial<Product<ModInteger>>> list = new ArrayList<GenPolynomial<Product<ModInteger>>>();
3056        if (L == null || L.size() == 0) {
3057            return list;
3058        }
3059        for (GenPolynomial<BigInteger> a : L) {
3060            GenPolynomial<Product<ModInteger>> b = toProduct(pfac, a);
3061            list.add(b);
3062        }
3063        return list;
3064    }
3065
3066
3067    /**
3068     * Intersection. Intersection of a list of polynomials with a polynomial
3069     * ring. The polynomial ring must be a contraction of the polynomial ring of
3070     * the list of polynomials and the TermOrder must be an elimination order.
3071     * @param R polynomial ring
3072     * @param F list of polynomials
3073     * @return R \cap F
3074     */
3075    public static <C extends RingElem<C>> List<GenPolynomial<C>> intersect(GenPolynomialRing<C> R,
3076                    List<GenPolynomial<C>> F) {
3077        if (F == null || F.isEmpty()) {
3078            return F;
3079        }
3080        GenPolynomialRing<C> pfac = F.get(0).ring;
3081        int d = pfac.nvar - R.nvar;
3082        if (d <= 0) {
3083            return F;
3084        }
3085        List<GenPolynomial<C>> H = new ArrayList<GenPolynomial<C>>(F.size());
3086        for (GenPolynomial<C> p : F) {
3087            Map<ExpVector, GenPolynomial<C>> m = null;
3088            m = p.contract(R);
3089            logger.debug("intersect contract m = {}", m);
3090            if (m.size() == 1) { // contains one power of variables
3091                for (Map.Entry<ExpVector, GenPolynomial<C>> me : m.entrySet()) {
3092                    ExpVector e = me.getKey();
3093                    if (e.isZERO()) {
3094                        H.add(me.getValue());
3095                    }
3096                }
3097            }
3098        }
3099        GenPolynomialRing<C> tfac = pfac.contract(d);
3100        if (tfac.equals(R)) { // check 
3101            return H;
3102        }
3103        logger.warn("tfac != R: tfac = {}, R = {}, pdac = {}", tfac.toScript(), R.toScript(),
3104                        pfac.toScript());
3105        // throw new RuntimeException("contract(pfac) != R");
3106        return H;
3107    }
3108
3109
3110    /**
3111     * Intersection. Intersection of a list of solvable polynomials with a
3112     * solvable polynomial ring. The solvable polynomial ring must be a
3113     * contraction of the solvable polynomial ring of the list of polynomials
3114     * and the TermOrder must be an elimination order.
3115     * @param R solvable polynomial ring
3116     * @param F list of solvable polynomials
3117     * @return R \cap F
3118     */
3119    @SuppressWarnings("cast")
3120    public static <C extends RingElem<C>> List<GenSolvablePolynomial<C>> intersect(
3121                    GenSolvablePolynomialRing<C> R, List<GenSolvablePolynomial<C>> F) {
3122        List<GenPolynomial<C>> Fp = PolynomialList.<C> castToList(F);
3123        GenPolynomialRing<C> Rp = (GenPolynomialRing<C>) R;
3124        List<GenPolynomial<C>> H = intersect(Rp, Fp);
3125        return PolynomialList.<C> castToSolvableList(H);
3126    }
3127
3128
3129    /**
3130     * Intersection. Intersection of a list of word polynomials with a word
3131     * polynomial ring. The polynomial ring must be a contraction of the
3132     * polynomial ring of the list of polynomials,
3133     * @param R word polynomial ring
3134     * @param F list of word polynomials
3135     * @return R \cap F
3136     */
3137    public static <C extends RingElem<C>> List<GenWordPolynomial<C>> intersect(GenWordPolynomialRing<C> R,
3138                    List<GenWordPolynomial<C>> F) {
3139        if (F == null || F.isEmpty()) {
3140            return F;
3141        }
3142        GenWordPolynomialRing<C> pfac = F.get(0).ring;
3143        assert pfac.alphabet.isSubFactory(R.alphabet) : "pfac=" + pfac.alphabet + ", R=" + R.alphabet;
3144        List<GenWordPolynomial<C>> H = new ArrayList<GenWordPolynomial<C>>(F.size());
3145        for (GenWordPolynomial<C> p : F) {
3146            if (p == null || p.isZERO()) {
3147                continue;
3148            }
3149            GenWordPolynomial<C> m = p.contract(R);
3150            logger.debug("intersect contract m = {}", m);
3151            if (!m.isZERO()) {
3152                H.add(m);
3153            }
3154        }
3155        // throw new RuntimeException("contract(pfac) != R");
3156        return H;
3157    }
3158
3159
3160    /**
3161     * Remove all upper variables which do not occur in polynomial.
3162     * @param p polynomial.
3163     * @return polynomial with removed variables
3164     */
3165    public static <C extends RingElem<C>> GenPolynomial<C> removeUnusedUpperVariables(GenPolynomial<C> p) {
3166        GenPolynomialRing<C> fac = p.ring;
3167        if (fac.nvar <= 1) { // univariate
3168            return p;
3169        }
3170        int[] dep = p.degreeVector().dependencyOnVariables();
3171        if (fac.nvar == dep.length) { // all variables appear
3172            return p;
3173        }
3174        if (dep.length == 0) { // no variables
3175            GenPolynomialRing<C> fac0 = new GenPolynomialRing<C>(fac.coFac, 0);
3176            GenPolynomial<C> p0 = new GenPolynomial<C>(fac0, p.leadingBaseCoefficient());
3177            return p0;
3178        }
3179        int l = dep[0]; // higher variable
3180        int r = dep[dep.length - 1]; // lower variable
3181        if (l == 0 /*|| l == fac.nvar-1*/) { // upper variable appears
3182            return p;
3183        }
3184        int n = l;
3185        GenPolynomialRing<C> facr = fac.contract(n);
3186        Map<ExpVector, GenPolynomial<C>> mpr = p.contract(facr);
3187        if (mpr.size() != 1) {
3188            logger.warn("upper ex, l = {}, r = {}, p = {}, fac = {}", l, r, p, fac.toScript());
3189            throw new RuntimeException("this should not happen " + mpr);
3190        }
3191        GenPolynomial<C> pr = mpr.values().iterator().next();
3192        n = fac.nvar - 1 - r;
3193        if (n == 0) {
3194            return pr;
3195        } // else case not implemented
3196        return pr;
3197    }
3198
3199
3200    /**
3201     * Remove all lower variables which do not occur in polynomial.
3202     * @param p polynomial.
3203     * @return polynomial with removed variables
3204     */
3205    public static <C extends RingElem<C>> GenPolynomial<C> removeUnusedLowerVariables(GenPolynomial<C> p) {
3206        GenPolynomialRing<C> fac = p.ring;
3207        if (fac.nvar <= 1) { // univariate
3208            return p;
3209        }
3210        int[] dep = p.degreeVector().dependencyOnVariables();
3211        if (fac.nvar == dep.length) { // all variables appear
3212            return p;
3213        }
3214        if (dep.length == 0) { // no variables
3215            GenPolynomialRing<C> fac0 = new GenPolynomialRing<C>(fac.coFac, 0);
3216            GenPolynomial<C> p0 = new GenPolynomial<C>(fac0, p.leadingBaseCoefficient());
3217            return p0;
3218        }
3219        int l = dep[0]; // higher variable
3220        int r = dep[dep.length - 1]; // lower variable
3221        if (r == fac.nvar - 1) { // lower variable appears
3222            return p;
3223        }
3224        int n = r + 1;
3225        GenPolynomialRing<GenPolynomial<C>> rfac = fac.recursive(n);
3226        GenPolynomial<GenPolynomial<C>> mpr = recursive(rfac, p);
3227        if (mpr.length() != p.length()) {
3228            logger.warn("lower ex, l = {}, r = {}, p = {}, fac = {}", l, r, p, fac.toScript());
3229            throw new RuntimeException("this should not happen " + mpr);
3230        }
3231        RingFactory<C> cf = fac.coFac;
3232        GenPolynomialRing<C> facl = new GenPolynomialRing<C>(cf, rfac);
3233        GenPolynomial<C> pr = facl.getZERO().copy();
3234        for (Monomial<GenPolynomial<C>> m : mpr) {
3235            ExpVector e = m.e;
3236            GenPolynomial<C> a = m.c;
3237            if (!a.isConstant()) {
3238                throw new RuntimeException("this can not happen " + a);
3239            }
3240            C c = a.leadingBaseCoefficient();
3241            pr.doPutToMap(e, c);
3242        }
3243        return pr;
3244    }
3245
3246
3247    /**
3248     * Remove upper block of middle variables which do not occur in polynomial.
3249     * @param p polynomial.
3250     * @return polynomial with removed variables
3251     */
3252    public static <C extends RingElem<C>> GenPolynomial<C> removeUnusedMiddleVariables(GenPolynomial<C> p) {
3253        GenPolynomialRing<C> fac = p.ring;
3254        if (fac.nvar <= 2) { // univariate or bi-variate
3255            return p;
3256        }
3257        int[] dep = p.degreeVector().dependencyOnVariables();
3258        if (fac.nvar == dep.length) { // all variables appear
3259            return p;
3260        }
3261        if (dep.length == 0) { // no variables
3262            GenPolynomialRing<C> fac0 = new GenPolynomialRing<C>(fac.coFac, 0);
3263            GenPolynomial<C> p0 = new GenPolynomial<C>(fac0, p.leadingBaseCoefficient());
3264            return p0;
3265        }
3266        ExpVector e1 = p.leadingExpVector();
3267        if (dep.length == 1) { // one variable
3268            TermOrder to = new TermOrder(fac.tord.getEvord());
3269            int i = dep[0];
3270            String v1 = e1.indexVarName(i, fac.getVars());
3271            String[] vars = new String[] { v1 };
3272            GenPolynomialRing<C> fac1 = new GenPolynomialRing<C>(fac.coFac, to, vars);
3273            GenPolynomial<C> p1 = fac1.getZERO().copy();
3274            for (Monomial<C> m : p) {
3275                ExpVector e = m.e;
3276                ExpVector f = ExpVector.create(1, 0, e.getVal(i));
3277                p1.doPutToMap(f, m.c);
3278            }
3279            return p1;
3280        }
3281        GenPolynomialRing<GenPolynomial<C>> rfac = fac.recursive(1);
3282        GenPolynomial<GenPolynomial<C>> mpr = recursive(rfac, p);
3283
3284        int l = dep[0]; // higher variable
3285        int r = fac.nvar - dep[1]; // next variable
3286        //System.out.println("l  = " + l);
3287        //System.out.println("r  = " + r);
3288
3289        TermOrder to = new TermOrder(fac.tord.getEvord());
3290        String[] vs = fac.getVars();
3291        String[] vars = new String[r + 1];
3292        for (int i = 0; i < r; i++) {
3293            vars[i] = vs[i];
3294        }
3295        vars[r] = e1.indexVarName(l, vs);
3296        //System.out.println("fac  = " + fac);
3297        GenPolynomialRing<C> dfac = new GenPolynomialRing<C>(fac.coFac, to, vars);
3298        //System.out.println("dfac = " + dfac);
3299        GenPolynomialRing<GenPolynomial<C>> fac2 = dfac.recursive(1);
3300        GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) fac2.coFac;
3301        GenPolynomial<GenPolynomial<C>> p2r = fac2.getZERO().copy();
3302        for (Monomial<GenPolynomial<C>> m : mpr) {
3303            ExpVector e = m.e;
3304            GenPolynomial<C> a = m.c;
3305            Map<ExpVector, GenPolynomial<C>> cc = a.contract(cfac);
3306            for (Map.Entry<ExpVector, GenPolynomial<C>> me : cc.entrySet()) {
3307                ExpVector f = me.getKey();
3308                if (f.isZERO()) {
3309                    GenPolynomial<C> c = me.getValue(); //cc.get(f);
3310                    p2r.doPutToMap(e, c);
3311                } else {
3312                    throw new RuntimeException("this should not happen " + cc);
3313                }
3314            }
3315        }
3316        GenPolynomial<C> p2 = distribute(dfac, p2r);
3317        return p2;
3318    }
3319
3320
3321    /**
3322     * Select polynomial with univariate leading term in variable i.
3323     * @param i variable index.
3324     * @return polynomial with head term in variable i
3325     */
3326    public static <C extends RingElem<C>> GenPolynomial<C> selectWithVariable(List<GenPolynomial<C>> P,
3327                    int i) {
3328        for (GenPolynomial<C> p : P) {
3329            int[] dep = p.leadingExpVector().dependencyOnVariables();
3330            if (dep.length == 1 && dep[0] == i) {
3331                return p;
3332            }
3333        }
3334        return null; // not found       
3335    }
3336
3337}
3338
3339
3340/**
3341 * Conversion of distributive to recursive representation.
3342 */
3343class DistToRec<C extends RingElem<C>>
3344                implements UnaryFunctor<GenPolynomial<C>, GenPolynomial<GenPolynomial<C>>> {
3345
3346
3347    GenPolynomialRing<GenPolynomial<C>> fac;
3348
3349
3350    public DistToRec(GenPolynomialRing<GenPolynomial<C>> fac) {
3351        this.fac = fac;
3352    }
3353
3354
3355    public GenPolynomial<GenPolynomial<C>> eval(GenPolynomial<C> c) {
3356        if (c == null) {
3357            return fac.getZERO();
3358        }
3359        return PolyUtil.<C> recursive(fac, c);
3360    }
3361}
3362
3363
3364/**
3365 * Conversion of recursive to distributive representation.
3366 */
3367class RecToDist<C extends RingElem<C>>
3368                implements UnaryFunctor<GenPolynomial<GenPolynomial<C>>, GenPolynomial<C>> {
3369
3370
3371    GenPolynomialRing<C> fac;
3372
3373
3374    public RecToDist(GenPolynomialRing<C> fac) {
3375        this.fac = fac;
3376    }
3377
3378
3379    public GenPolynomial<C> eval(GenPolynomial<GenPolynomial<C>> c) {
3380        if (c == null) {
3381            return fac.getZERO();
3382        }
3383        return PolyUtil.<C> distribute(fac, c);
3384    }
3385}
3386
3387
3388/**
3389 * BigRational numerator functor.
3390 */
3391class RatNumer implements UnaryFunctor<BigRational, BigInteger> {
3392
3393
3394    public BigInteger eval(BigRational c) {
3395        if (c == null) {
3396            return new BigInteger();
3397        }
3398        return new BigInteger(c.numerator());
3399    }
3400}
3401
3402
3403/**
3404 * Conversion of symmetric ModInteger to BigInteger functor.
3405 */
3406class ModSymToInt<C extends RingElem<C> & Modular> implements UnaryFunctor<C, BigInteger> {
3407
3408
3409    public BigInteger eval(C c) {
3410        if (c == null) {
3411            return new BigInteger();
3412        }
3413        return c.getSymmetricInteger();
3414    }
3415}
3416
3417
3418/**
3419 * Conversion of ModInteger to BigInteger functor.
3420 */
3421class ModToInt<C extends RingElem<C> & Modular> implements UnaryFunctor<C, BigInteger> {
3422
3423
3424    public BigInteger eval(C c) {
3425        if (c == null) {
3426            return new BigInteger();
3427        }
3428        return c.getInteger();
3429    }
3430}
3431
3432
3433/**
3434 * Conversion of BigRational to BigInteger with division by lcm functor. result
3435 * = num*(lcm/denom).
3436 */
3437class RatToInt implements UnaryFunctor<BigRational, BigInteger> {
3438
3439
3440    java.math.BigInteger lcm;
3441
3442
3443    public RatToInt(java.math.BigInteger lcm) {
3444        this.lcm = lcm; //.getVal();
3445    }
3446
3447
3448    public BigInteger eval(BigRational c) {
3449        if (c == null) {
3450            return new BigInteger();
3451        }
3452        // p = num*(lcm/denom)
3453        java.math.BigInteger b = lcm.divide(c.denominator());
3454        return new BigInteger(c.numerator().multiply(b));
3455    }
3456}
3457
3458
3459/**
3460 * Conversion of BigRational to BigInteger. result = (num/gcd)*(lcm/denom).
3461 */
3462class RatToIntFactor implements UnaryFunctor<BigRational, BigInteger> {
3463
3464
3465    final java.math.BigInteger lcm;
3466
3467
3468    final java.math.BigInteger gcd;
3469
3470
3471    public RatToIntFactor(java.math.BigInteger gcd, java.math.BigInteger lcm) {
3472        this.gcd = gcd;
3473        this.lcm = lcm; // .getVal();
3474    }
3475
3476
3477    public BigInteger eval(BigRational c) {
3478        if (c == null) {
3479            return new BigInteger();
3480        }
3481        if (gcd.equals(java.math.BigInteger.ONE)) {
3482            // p = num*(lcm/denom)
3483            java.math.BigInteger b = lcm.divide(c.denominator());
3484            return new BigInteger(c.numerator().multiply(b));
3485        }
3486        // p = (num/gcd)*(lcm/denom)
3487        java.math.BigInteger a = c.numerator().divide(gcd);
3488        java.math.BigInteger b = lcm.divide(c.denominator());
3489        return new BigInteger(a.multiply(b));
3490    }
3491}
3492
3493
3494/**
3495 * Conversion of Rational to BigDecimal. result = decimal(r).
3496 */
3497class RatToDec<C extends Element<C> & Rational> implements UnaryFunctor<C, BigDecimal> {
3498
3499
3500    public BigDecimal eval(C c) {
3501        if (c == null) {
3502            return new BigDecimal();
3503        }
3504        return new BigDecimal(c.getRational());
3505    }
3506}
3507
3508
3509/**
3510 * Conversion of Complex Rational to Complex BigDecimal. result = decimal(r).
3511 */
3512class CompRatToDec<C extends RingElem<C> & Rational>
3513                implements UnaryFunctor<Complex<C>, Complex<BigDecimal>> {
3514
3515
3516    ComplexRing<BigDecimal> ring;
3517
3518
3519    public CompRatToDec(RingFactory<Complex<BigDecimal>> ring) {
3520        this.ring = (ComplexRing<BigDecimal>) ring;
3521    }
3522
3523
3524    public Complex<BigDecimal> eval(Complex<C> c) {
3525        if (c == null) {
3526            return ring.getZERO();
3527        }
3528        BigDecimal r = new BigDecimal(c.getRe().getRational());
3529        BigDecimal i = new BigDecimal(c.getIm().getRational());
3530        return new Complex<BigDecimal>(ring, r, i);
3531    }
3532}
3533
3534
3535/**
3536 * Conversion from BigInteger functor.
3537 */
3538class FromInteger<D extends RingElem<D>> implements UnaryFunctor<BigInteger, D> {
3539
3540
3541    RingFactory<D> ring;
3542
3543
3544    public FromInteger(RingFactory<D> ring) {
3545        this.ring = ring;
3546    }
3547
3548
3549    public D eval(BigInteger c) {
3550        if (c == null) {
3551            return ring.getZERO();
3552        }
3553        return ring.fromInteger(c.getVal());
3554    }
3555}
3556
3557
3558/**
3559 * Conversion from GenPolynomial<BigInteger> functor.
3560 */
3561class FromIntegerPoly<D extends RingElem<D>>
3562                implements UnaryFunctor<GenPolynomial<BigInteger>, GenPolynomial<D>> {
3563
3564
3565    GenPolynomialRing<D> ring;
3566
3567
3568    FromInteger<D> fi;
3569
3570
3571    public FromIntegerPoly(GenPolynomialRing<D> ring) {
3572        if (ring == null) {
3573            throw new IllegalArgumentException("ring must not be null");
3574        }
3575        this.ring = ring;
3576        fi = new FromInteger<D>(ring.coFac);
3577    }
3578
3579
3580    public GenPolynomial<D> eval(GenPolynomial<BigInteger> c) {
3581        if (c == null) {
3582            return ring.getZERO();
3583        }
3584        return PolyUtil.<BigInteger, D> map(ring, c, fi);
3585    }
3586}
3587
3588
3589/**
3590 * Conversion from GenPolynomial<BigRational> to GenPolynomial <BigInteger>
3591 * functor.
3592 */
3593class RatToIntPoly implements UnaryFunctor<GenPolynomial<BigRational>, GenPolynomial<BigInteger>> {
3594
3595
3596    GenPolynomialRing<BigInteger> ring;
3597
3598
3599    public RatToIntPoly(GenPolynomialRing<BigInteger> ring) {
3600        if (ring == null) {
3601            throw new IllegalArgumentException("ring must not be null");
3602        }
3603        this.ring = ring;
3604    }
3605
3606
3607    public GenPolynomial<BigInteger> eval(GenPolynomial<BigRational> c) {
3608        if (c == null) {
3609            return ring.getZERO();
3610        }
3611        return PolyUtil.integerFromRationalCoefficients(ring, c);
3612    }
3613}
3614
3615
3616/**
3617 * Real part functor.
3618 */
3619class RealPart implements UnaryFunctor<BigComplex, BigRational> {
3620
3621
3622    public BigRational eval(BigComplex c) {
3623        if (c == null) {
3624            return new BigRational();
3625        }
3626        return c.getRe();
3627    }
3628}
3629
3630
3631/**
3632 * Imaginary part functor.
3633 */
3634class ImagPart implements UnaryFunctor<BigComplex, BigRational> {
3635
3636
3637    public BigRational eval(BigComplex c) {
3638        if (c == null) {
3639            return new BigRational();
3640        }
3641        return c.getIm();
3642    }
3643}
3644
3645
3646/**
3647 * Real part functor.
3648 */
3649class RealPartComplex<C extends RingElem<C>> implements UnaryFunctor<Complex<C>, C> {
3650
3651
3652    public C eval(Complex<C> c) {
3653        if (c == null) {
3654            return null;
3655        }
3656        return c.getRe();
3657    }
3658}
3659
3660
3661/**
3662 * Imaginary part functor.
3663 */
3664class ImagPartComplex<C extends RingElem<C>> implements UnaryFunctor<Complex<C>, C> {
3665
3666
3667    public C eval(Complex<C> c) {
3668        if (c == null) {
3669            return null;
3670        }
3671        return c.getIm();
3672    }
3673}
3674
3675
3676/**
3677 * Rational to complex functor.
3678 */
3679class ToComplex<C extends RingElem<C>> implements UnaryFunctor<C, Complex<C>> {
3680
3681
3682    final protected ComplexRing<C> cfac;
3683
3684
3685    @SuppressWarnings("unchecked")
3686    public ToComplex(RingFactory<Complex<C>> fac) {
3687        if (fac == null) {
3688            throw new IllegalArgumentException("fac must not be null");
3689        }
3690        cfac = (ComplexRing<C>) fac;
3691    }
3692
3693
3694    public Complex<C> eval(C c) {
3695        if (c == null) {
3696            return cfac.getZERO();
3697        }
3698        return new Complex<C>(cfac, c);
3699    }
3700}
3701
3702
3703/**
3704 * Rational to complex functor.
3705 */
3706class RatToCompl implements UnaryFunctor<BigRational, BigComplex> {
3707
3708
3709    public BigComplex eval(BigRational c) {
3710        if (c == null) {
3711            return new BigComplex();
3712        }
3713        return new BigComplex(c);
3714    }
3715}
3716
3717
3718/**
3719 * Any ring element to generic complex functor.
3720 */
3721class AnyToComplex<C extends GcdRingElem<C>> implements UnaryFunctor<C, Complex<C>> {
3722
3723
3724    final protected ComplexRing<C> cfac;
3725
3726
3727    public AnyToComplex(ComplexRing<C> fac) {
3728        if (fac == null) {
3729            throw new IllegalArgumentException("fac must not be null");
3730        }
3731        cfac = fac;
3732    }
3733
3734
3735    public AnyToComplex(RingFactory<C> fac) {
3736        this(new ComplexRing<C>(fac));
3737    }
3738
3739
3740    public Complex<C> eval(C a) {
3741        if (a == null || a.isZERO()) { // should not happen
3742            return cfac.getZERO();
3743        } else if (a.isONE()) {
3744            return cfac.getONE();
3745        } else {
3746            return new Complex<C>(cfac, a);
3747        }
3748    }
3749}
3750
3751
3752/**
3753 * Algebraic to generic complex functor.
3754 */
3755class AlgebToCompl<C extends GcdRingElem<C>> implements UnaryFunctor<AlgebraicNumber<C>, Complex<C>> {
3756
3757
3758    final protected ComplexRing<C> cfac;
3759
3760
3761    public AlgebToCompl(ComplexRing<C> fac) {
3762        if (fac == null) {
3763            throw new IllegalArgumentException("fac must not be null");
3764        }
3765        cfac = fac;
3766    }
3767
3768
3769    public Complex<C> eval(AlgebraicNumber<C> a) {
3770        if (a == null || a.isZERO()) { // should not happen
3771            return cfac.getZERO();
3772        } else if (a.isONE()) {
3773            return cfac.getONE();
3774        } else {
3775            GenPolynomial<C> p = a.getVal();
3776            C real = cfac.ring.getZERO();
3777            C imag = cfac.ring.getZERO();
3778            for (Monomial<C> m : p) {
3779                if (m.exponent().getVal(0) == 1L) {
3780                    imag = m.coefficient();
3781                } else if (m.exponent().getVal(0) == 0L) {
3782                    real = m.coefficient();
3783                } else {
3784                    throw new IllegalArgumentException("unexpected monomial " + m);
3785                }
3786            }
3787            //Complex<C> c = new Complex<C>(cfac,real,imag);
3788            return new Complex<C>(cfac, real, imag);
3789        }
3790    }
3791}
3792
3793
3794/**
3795 * Ceneric complex to algebraic number functor.
3796 */
3797class ComplToAlgeb<C extends GcdRingElem<C>> implements UnaryFunctor<Complex<C>, AlgebraicNumber<C>> {
3798
3799
3800    final protected AlgebraicNumberRing<C> afac;
3801
3802
3803    final protected AlgebraicNumber<C> I;
3804
3805
3806    public ComplToAlgeb(AlgebraicNumberRing<C> fac) {
3807        if (fac == null) {
3808            throw new IllegalArgumentException("fac must not be null");
3809        }
3810        afac = fac;
3811        I = afac.getGenerator();
3812    }
3813
3814
3815    public AlgebraicNumber<C> eval(Complex<C> c) {
3816        if (c == null || c.isZERO()) { // should not happen
3817            return afac.getZERO();
3818        } else if (c.isONE()) {
3819            return afac.getONE();
3820        } else if (c.isIMAG()) {
3821            return I;
3822        } else {
3823            return I.multiply(c.getIm()).sum(c.getRe());
3824        }
3825    }
3826}
3827
3828
3829/**
3830 * Algebraic to polynomial functor.
3831 */
3832class AlgToPoly<C extends GcdRingElem<C>> implements UnaryFunctor<AlgebraicNumber<C>, GenPolynomial<C>> {
3833
3834
3835    public GenPolynomial<C> eval(AlgebraicNumber<C> c) {
3836        if (c == null) {
3837            return null;
3838        }
3839        return c.val;
3840    }
3841}
3842
3843
3844/**
3845 * Polynomial to algebriac functor.
3846 */
3847class PolyToAlg<C extends GcdRingElem<C>> implements UnaryFunctor<GenPolynomial<C>, AlgebraicNumber<C>> {
3848
3849
3850    final protected AlgebraicNumberRing<C> afac;
3851
3852
3853    public PolyToAlg(AlgebraicNumberRing<C> fac) {
3854        if (fac == null) {
3855            throw new IllegalArgumentException("fac must not be null");
3856        }
3857        afac = fac;
3858    }
3859
3860
3861    public AlgebraicNumber<C> eval(GenPolynomial<C> c) {
3862        if (c == null) {
3863            return afac.getZERO();
3864        }
3865        return new AlgebraicNumber<C>(afac, c);
3866    }
3867}
3868
3869
3870/**
3871 * Coefficient to algebriac functor.
3872 */
3873class CoeffToAlg<C extends GcdRingElem<C>> implements UnaryFunctor<C, AlgebraicNumber<C>> {
3874
3875
3876    final protected AlgebraicNumberRing<C> afac;
3877
3878
3879    final protected GenPolynomial<C> zero;
3880
3881
3882    public CoeffToAlg(AlgebraicNumberRing<C> fac) {
3883        if (fac == null) {
3884            throw new IllegalArgumentException("fac must not be null");
3885        }
3886        afac = fac;
3887        GenPolynomialRing<C> pfac = afac.ring;
3888        zero = pfac.getZERO();
3889    }
3890
3891
3892    public AlgebraicNumber<C> eval(C c) {
3893        if (c == null) {
3894            return afac.getZERO();
3895        }
3896        return new AlgebraicNumber<C>(afac, zero.sum(c));
3897    }
3898}
3899
3900
3901/**
3902 * Coefficient to recursive algebriac functor.
3903 */
3904class CoeffToRecAlg<C extends GcdRingElem<C>> implements UnaryFunctor<C, AlgebraicNumber<C>> {
3905
3906
3907    final protected List<AlgebraicNumberRing<C>> lfac;
3908
3909
3910    final int depth;
3911
3912
3913    @SuppressWarnings("unchecked")
3914    public CoeffToRecAlg(int depth, AlgebraicNumberRing<C> fac) {
3915        if (fac == null) {
3916            throw new IllegalArgumentException("fac must not be null");
3917        }
3918        AlgebraicNumberRing<C> afac = fac;
3919        this.depth = depth;
3920        lfac = new ArrayList<AlgebraicNumberRing<C>>(this.depth);
3921        lfac.add(fac);
3922        for (int i = 1; i < this.depth; i++) {
3923            RingFactory<C> rf = afac.ring.coFac;
3924            if (!(rf instanceof AlgebraicNumberRing)) {
3925                throw new IllegalArgumentException("fac depth to low");
3926            }
3927            afac = (AlgebraicNumberRing<C>) (Object) rf;
3928            lfac.add(afac);
3929        }
3930    }
3931
3932
3933    @SuppressWarnings("unchecked")
3934    public AlgebraicNumber<C> eval(C c) {
3935        if (c == null) {
3936            return lfac.get(0).getZERO();
3937        }
3938        C ac = c;
3939        AlgebraicNumberRing<C> af = lfac.get(lfac.size() - 1);
3940        GenPolynomial<C> zero = af.ring.getZERO();
3941        AlgebraicNumber<C> an = new AlgebraicNumber<C>(af, zero.sum(ac));
3942        for (int i = lfac.size() - 2; i >= 0; i--) {
3943            af = lfac.get(i);
3944            zero = af.ring.getZERO();
3945            ac = (C) (Object) an;
3946            an = new AlgebraicNumber<C>(af, zero.sum(ac));
3947        }
3948        return an;
3949    }
3950}
3951
3952
3953/**
3954 * Evaluate main variable functor.
3955 */
3956class EvalMain<C extends RingElem<C>> implements UnaryFunctor<GenPolynomial<C>, C> {
3957
3958
3959    final RingFactory<C> cfac;
3960
3961
3962    final C a;
3963
3964
3965    public EvalMain(RingFactory<C> cfac, C a) {
3966        this.cfac = cfac;
3967        this.a = a;
3968    }
3969
3970
3971    public C eval(GenPolynomial<C> c) {
3972        if (c == null) {
3973            return cfac.getZERO();
3974        }
3975        return PolyUtil.<C> evaluateMain(cfac, c, a);
3976    }
3977}
3978
3979
3980/**
3981 * Evaluate main variable functor.
3982 */
3983class EvalMainPol<C extends RingElem<C>> implements UnaryFunctor<GenPolynomial<C>, GenPolynomial<C>> {
3984
3985
3986    final GenPolynomialRing<C> cfac;
3987
3988
3989    final C a;
3990
3991
3992    public EvalMainPol(GenPolynomialRing<C> cfac, C a) {
3993        this.cfac = cfac;
3994        this.a = a;
3995    }
3996
3997
3998    public GenPolynomial<C> eval(GenPolynomial<C> c) {
3999        if (c == null) {
4000            return cfac.getZERO();
4001        }
4002        return PolyUtil.<C> evaluateMain(cfac, c, a);
4003    }
4004}
4005
4006
4007/**
4008 * Evaluate all variable functor.
4009 */
4010class EvalAllPol<C extends RingElem<C>> implements UnaryFunctor<GenPolynomial<C>, C> {
4011
4012
4013    final RingFactory<C> cfac;
4014
4015
4016    final List<C> a;
4017
4018
4019    public EvalAllPol(RingFactory<C> cfac, List<C> a) {
4020        this.cfac = cfac;
4021        this.a = a;
4022    }
4023
4024
4025    public C eval(GenPolynomial<C> c) {
4026        if (c == null) {
4027            return cfac.getZERO();
4028        }
4029        return PolyUtil.<C> evaluateAll(cfac, c, a);
4030    }
4031}