001 /*
002 * $Id: PolyUtil.java 3756 2011-09-03 11:37:03Z kredel $
003 */
004
005 package edu.jas.poly;
006
007
008 import java.util.ArrayList;
009 import java.util.List;
010 import java.util.Map;
011 import java.util.SortedMap;
012 import java.util.TreeMap;
013
014 import org.apache.log4j.Logger;
015
016 import edu.jas.arith.BigComplex;
017 import edu.jas.arith.BigDecimal;
018 import edu.jas.arith.BigInteger;
019 import edu.jas.arith.BigRational;
020 import edu.jas.arith.ModInteger;
021 import edu.jas.arith.ModIntegerRing;
022 import edu.jas.arith.Modular;
023 import edu.jas.arith.ModularRingFactory;
024 import edu.jas.arith.Product;
025 import edu.jas.arith.ProductRing;
026 import edu.jas.arith.Rational;
027 import edu.jas.structure.Element;
028 import edu.jas.structure.GcdRingElem;
029 import edu.jas.structure.RingElem;
030 import edu.jas.structure.RingFactory;
031 import edu.jas.structure.UnaryFunctor;
032 import edu.jas.util.ListUtil;
033
034
035 /**
036 * Polynomial utilities, for example conversion between different
037 * representations, evaluation and interpolation.
038 * @author Heinz Kredel
039 */
040
041 public class PolyUtil {
042
043
044 private static final Logger logger = Logger.getLogger(PolyUtil.class);
045
046
047 private static boolean debug = logger.isDebugEnabled();
048
049
050 /**
051 * Recursive representation. Represent as polynomial in i variables with
052 * coefficients in n-i variables. Works for arbitrary term orders.
053 * @param <C> coefficient type.
054 * @param rfac recursive polynomial ring factory.
055 * @param A polynomial to be converted.
056 * @return Recursive represenations of this in the ring rfac.
057 */
058 public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> recursive(
059 GenPolynomialRing<GenPolynomial<C>> rfac, GenPolynomial<C> A) {
060
061 GenPolynomial<GenPolynomial<C>> B = rfac.getZERO().clone();
062 if (A.isZERO()) {
063 return B;
064 }
065 int i = rfac.nvar;
066 GenPolynomial<C> zero = rfac.getZEROCoefficient();
067 Map<ExpVector, GenPolynomial<C>> Bv = B.val; //getMap();
068 for (Map.Entry<ExpVector, C> y : A.getMap().entrySet()) {
069 ExpVector e = y.getKey();
070 C a = y.getValue();
071 ExpVector f = e.contract(0, i);
072 ExpVector g = e.contract(i, e.length() - i);
073 GenPolynomial<C> p = Bv.get(f);
074 if (p == null) {
075 p = zero;
076 }
077 p = p.sum(a, g);
078 Bv.put(f, p);
079 }
080 return B;
081 }
082
083
084 /**
085 * Distribute a recursive polynomial to a generic polynomial. Works for
086 * arbitrary term orders.
087 * @param <C> coefficient type.
088 * @param dfac combined polynomial ring factory of coefficients and this.
089 * @param B polynomial to be converted.
090 * @return distributed polynomial.
091 */
092 public static <C extends RingElem<C>> GenPolynomial<C> distribute(GenPolynomialRing<C> dfac,
093 GenPolynomial<GenPolynomial<C>> B) {
094 GenPolynomial<C> C = dfac.getZERO().clone();
095 if (B.isZERO()) {
096 return C;
097 }
098 Map<ExpVector, C> Cm = C.val; //getMap();
099 for (Map.Entry<ExpVector, GenPolynomial<C>> y : B.getMap().entrySet()) {
100 ExpVector e = y.getKey();
101 GenPolynomial<C> A = y.getValue();
102 for (Map.Entry<ExpVector, C> x : A.val.entrySet()) {
103 ExpVector f = x.getKey();
104 C b = x.getValue();
105 ExpVector g = e.combine(f);
106 assert (Cm.get(g) != null);
107 //if ( Cm.get(g) != null ) { // todo assert, done
108 // throw new RuntimeException("PolyUtil debug error");
109 //}
110 Cm.put(g, b);
111 }
112 }
113 return C;
114 }
115
116
117 /**
118 * Recursive representation. Represent as polynomials in i variables with
119 * coefficients in n-i variables. Works for arbitrary term orders.
120 * @param <C> coefficient type.
121 * @param rfac recursive polynomial ring factory.
122 * @param L list of polynomials to be converted.
123 * @return Recursive represenations of the list in the ring rfac.
124 */
125 public static <C extends RingElem<C>> List<GenPolynomial<GenPolynomial<C>>> recursive(
126 GenPolynomialRing<GenPolynomial<C>> rfac, List<GenPolynomial<C>> L) {
127 return ListUtil.<GenPolynomial<C>, GenPolynomial<GenPolynomial<C>>> map(L, new DistToRec<C>(rfac));
128 }
129
130
131 /**
132 * Distribute a recursive polynomial list to a generic polynomial list.
133 * Works for arbitrary term orders.
134 * @param <C> coefficient type.
135 * @param dfac combined polynomial ring factory of coefficients and this.
136 * @param L list of polynomials to be converted.
137 * @return distributed polynomial list.
138 */
139 public static <C extends RingElem<C>> List<GenPolynomial<C>> distribute(GenPolynomialRing<C> dfac,
140 List<GenPolynomial<GenPolynomial<C>>> L) {
141 return ListUtil.<GenPolynomial<GenPolynomial<C>>, GenPolynomial<C>> map(L, new RecToDist<C>(dfac));
142 }
143
144
145 /**
146 * BigInteger from ModInteger coefficients, symmetric. Represent as
147 * polynomial with BigInteger coefficients by removing the modules and
148 * making coefficients symmetric to 0.
149 * @param fac result polynomial factory.
150 * @param A polynomial with ModInteger coefficients to be converted.
151 * @return polynomial with BigInteger coefficients.
152 */
153 public static <C extends RingElem<C> & Modular> GenPolynomial<BigInteger> integerFromModularCoefficients(
154 GenPolynomialRing<BigInteger> fac, GenPolynomial<C> A) {
155 return PolyUtil.<C, BigInteger> map(fac, A, new ModSymToInt<C>());
156 }
157
158
159 /**
160 * BigInteger from ModInteger coefficients, symmetric. Represent as
161 * polynomial with BigInteger coefficients by removing the modules and
162 * making coefficients symmetric to 0.
163 * @param fac result polynomial factory.
164 * @param L list of polynomials with ModInteger coefficients to be
165 * converted.
166 * @return list of polynomials with BigInteger coefficients.
167 */
168 public static <C extends RingElem<C> & Modular> List<GenPolynomial<BigInteger>> integerFromModularCoefficients(
169 final GenPolynomialRing<BigInteger> fac, List<GenPolynomial<C>> L) {
170 return ListUtil.<GenPolynomial<C>, GenPolynomial<BigInteger>> map(L,
171 new UnaryFunctor<GenPolynomial<C>, GenPolynomial<BigInteger>>() {
172
173
174 public GenPolynomial<BigInteger> eval(GenPolynomial<C> c) {
175 return PolyUtil.<C> integerFromModularCoefficients(fac, c);
176 }
177 });
178 }
179
180
181 /**
182 * BigInteger from ModInteger coefficients, positive. Represent as
183 * polynomial with BigInteger coefficients by removing the modules.
184 * @param fac result polynomial factory.
185 * @param A polynomial with ModInteger coefficients to be converted.
186 * @return polynomial with BigInteger coefficients.
187 */
188 public static <C extends RingElem<C> & Modular> GenPolynomial<BigInteger> integerFromModularCoefficientsPositive(
189 GenPolynomialRing<BigInteger> fac, GenPolynomial<C> A) {
190 return PolyUtil.<C, BigInteger> map(fac, A, new ModToInt<C>());
191 }
192
193
194 /**
195 * BigInteger from BigRational coefficients. Represent as polynomial with
196 * BigInteger coefficients by multiplication with the lcm of the numerators
197 * of the BigRational coefficients.
198 * @param fac result polynomial factory.
199 * @param A polynomial with BigRational coefficients to be converted.
200 * @return polynomial with BigInteger coefficients.
201 */
202 public static GenPolynomial<BigInteger> integerFromRationalCoefficients(
203 GenPolynomialRing<BigInteger> fac, GenPolynomial<BigRational> A) {
204 if (A == null || A.isZERO()) {
205 return fac.getZERO();
206 }
207 java.math.BigInteger c = null;
208 int s = 0;
209 // lcm of denominators
210 for (BigRational y : A.val.values()) {
211 java.math.BigInteger x = y.denominator();
212 // c = lcm(c,x)
213 if (c == null) {
214 c = x;
215 s = x.signum();
216 } else {
217 java.math.BigInteger d = c.gcd(x);
218 c = c.multiply(x.divide(d));
219 }
220 }
221 if (s < 0) {
222 c = c.negate();
223 }
224 return PolyUtil.<BigRational, BigInteger> map(fac, A, new RatToInt(c));
225 }
226
227
228 /**
229 * BigInteger from BigRational coefficients. Represent as polynomial with
230 * BigInteger coefficients by multiplication with the gcd of the numerators
231 * and the lcm of the denominators of the BigRational coefficients. <br
232 * /><b>Author:</b> Axel Kramer
233 * @param fac result polynomial factory.
234 * @param A polynomial with BigRational coefficients to be converted.
235 * @return Object[] with 3 entries: [0]->gcd [1]->lcm and [2]->polynomial
236 * with BigInteger coefficients.
237 */
238 public static Object[] integerFromRationalCoefficientsFactor(GenPolynomialRing<BigInteger> fac,
239 GenPolynomial<BigRational> A) {
240 Object[] result = new Object[3];
241 if (A == null || A.isZERO()) {
242 result[0] = java.math.BigInteger.ONE;
243 result[1] = java.math.BigInteger.ZERO;
244 result[2] = fac.getZERO();
245 return result;
246 }
247 java.math.BigInteger gcd = null;
248 java.math.BigInteger lcm = null;
249 int sLCM = 0;
250 int sGCD = 0;
251 // lcm of denominators
252 for (BigRational y : A.val.values()) {
253 java.math.BigInteger numerator = y.numerator();
254 java.math.BigInteger denominator = y.denominator();
255 // lcm = lcm(lcm,x)
256 if (lcm == null) {
257 lcm = denominator;
258 sLCM = denominator.signum();
259 } else {
260 java.math.BigInteger d = lcm.gcd(denominator);
261 lcm = lcm.multiply(denominator.divide(d));
262 }
263 // gcd = gcd(gcd,x)
264 if (gcd == null) {
265 gcd = numerator;
266 sGCD = numerator.signum();
267 } else {
268 gcd = gcd.gcd(numerator);
269 }
270 }
271 if (sLCM < 0) {
272 lcm = lcm.negate();
273 }
274 if (sGCD < 0) {
275 gcd = gcd.negate();
276 }
277 result[0] = gcd;
278 result[1] = lcm;
279 result[2] = PolyUtil.<BigRational, BigInteger> map(fac, A, new RatToIntFactor(gcd, lcm));
280 return result;
281 }
282
283
284 /**
285 * BigInteger from BigRational coefficients. Represent as list of
286 * polynomials with BigInteger coefficients by multiplication with the lcm
287 * of the numerators of the BigRational coefficients of each polynomial.
288 * @param fac result polynomial factory.
289 * @param L list of polynomials with BigRational coefficients to be
290 * converted.
291 * @return polynomial list with BigInteger coefficients.
292 */
293 public static List<GenPolynomial<BigInteger>> integerFromRationalCoefficients(
294 GenPolynomialRing<BigInteger> fac, List<GenPolynomial<BigRational>> L) {
295 return ListUtil.<GenPolynomial<BigRational>, GenPolynomial<BigInteger>> map(L, new RatToIntPoly(fac));
296 }
297
298
299 /**
300 * From BigInteger coefficients. Represent as polynomial with type C
301 * coefficients, e.g. ModInteger or BigRational.
302 * @param <C> coefficient type.
303 * @param fac result polynomial factory.
304 * @param A polynomial with BigInteger coefficients to be converted.
305 * @return polynomial with type C coefficients.
306 */
307 public static <C extends RingElem<C>> GenPolynomial<C> fromIntegerCoefficients(GenPolynomialRing<C> fac,
308 GenPolynomial<BigInteger> A) {
309 return PolyUtil.<BigInteger, C> map(fac, A, new FromInteger<C>(fac.coFac));
310 }
311
312
313 /**
314 * From BigInteger coefficients. Represent as list of polynomials with type
315 * C coefficients, e.g. ModInteger or BigRational.
316 * @param <C> coefficient type.
317 * @param fac result polynomial factory.
318 * @param L list of polynomials with BigInteger coefficients to be
319 * converted.
320 * @return list of polynomials with type C coefficients.
321 */
322 public static <C extends RingElem<C>> List<GenPolynomial<C>> fromIntegerCoefficients(
323 GenPolynomialRing<C> fac, List<GenPolynomial<BigInteger>> L) {
324 return ListUtil.<GenPolynomial<BigInteger>, GenPolynomial<C>> map(L, new FromIntegerPoly<C>(fac));
325 }
326
327
328 /**
329 * Convert to decimal coefficients.
330 * @param fac result polynomial factory.
331 * @param A polynomial with Rational coefficients to be converted.
332 * @return polynomial with BigDecimal coefficients.
333 */
334 public static <C extends RingElem<C> & Rational> GenPolynomial<BigDecimal> decimalFromRational(
335 GenPolynomialRing<BigDecimal> fac, GenPolynomial<C> A) {
336 return PolyUtil.<C, BigDecimal> map(fac, A, new RatToDec<C>());
337 }
338
339
340 /**
341 * Convert to complex decimal coefficients.
342 * @param fac result polynomial factory.
343 * @param A polynomial with complex Rational coefficients to be converted.
344 * @return polynomial with Complex BigDecimal coefficients.
345 */
346 public static <C extends RingElem<C> & Rational> GenPolynomial<Complex<BigDecimal>> complexDecimalFromRational(
347 GenPolynomialRing<Complex<BigDecimal>> fac, GenPolynomial<Complex<C>> A) {
348 return PolyUtil.<Complex<C>, Complex<BigDecimal>> map(fac, A, new CompRatToDec<C>(fac.coFac));
349 }
350
351
352 /**
353 * Real part.
354 * @param fac result polynomial factory.
355 * @param A polynomial with BigComplex coefficients to be converted.
356 * @return polynomial with real part of the coefficients.
357 */
358 public static GenPolynomial<BigRational> realPart(GenPolynomialRing<BigRational> fac,
359 GenPolynomial<BigComplex> A) {
360 return PolyUtil.<BigComplex, BigRational> map(fac, A, new RealPart());
361 }
362
363
364 /**
365 * Imaginary part.
366 * @param fac result polynomial factory.
367 * @param A polynomial with BigComplex coefficients to be converted.
368 * @return polynomial with imaginary part of coefficients.
369 */
370 public static GenPolynomial<BigRational> imaginaryPart(GenPolynomialRing<BigRational> fac,
371 GenPolynomial<BigComplex> A) {
372 return PolyUtil.<BigComplex, BigRational> map(fac, A, new ImagPart());
373 }
374
375
376 /**
377 * Real part.
378 * @param fac result polynomial factory.
379 * @param A polynomial with BigComplex coefficients to be converted.
380 * @return polynomial with real part of the coefficients.
381 */
382 public static <C extends RingElem<C>> GenPolynomial<C> realPartFromComplex(GenPolynomialRing<C> fac,
383 GenPolynomial<Complex<C>> A) {
384 return PolyUtil.<Complex<C>, C> map(fac, A, new RealPartComplex<C>());
385 }
386
387
388 /**
389 * Imaginary part.
390 * @param fac result polynomial factory.
391 * @param A polynomial with BigComplex coefficients to be converted.
392 * @return polynomial with imaginary part of coefficients.
393 */
394 public static <C extends RingElem<C>> GenPolynomial<C> imaginaryPartFromComplex(GenPolynomialRing<C> fac,
395 GenPolynomial<Complex<C>> A) {
396 return PolyUtil.<Complex<C>, C> map(fac, A, new ImagPartComplex<C>());
397 }
398
399
400 /**
401 * Complex from real polynomial.
402 * @param fac result polynomial factory.
403 * @param A polynomial with C coefficients to be converted.
404 * @return polynomial with Complex<C> coefficients.
405 */
406 public static <C extends RingElem<C>> GenPolynomial<Complex<C>> toComplex(
407 GenPolynomialRing<Complex<C>> fac, GenPolynomial<C> A) {
408 return PolyUtil.<C, Complex<C>> map(fac, A, new ToComplex<C>(fac.coFac));
409 }
410
411
412 /**
413 * Complex from rational coefficients.
414 * @param fac result polynomial factory.
415 * @param A polynomial with BigRational coefficients to be converted.
416 * @return polynomial with BigComplex coefficients.
417 */
418 public static GenPolynomial<BigComplex> complexFromRational(GenPolynomialRing<BigComplex> fac,
419 GenPolynomial<BigRational> A) {
420 return PolyUtil.<BigRational, BigComplex> map(fac, A, new RatToCompl());
421 }
422
423
424 /**
425 * Complex from ring element coefficients.
426 * @param fac result polynomial factory.
427 * @param A polynomial with RingElem coefficients to be converted.
428 * @return polynomial with Complex coefficients.
429 */
430 public static <C extends GcdRingElem<C>> GenPolynomial<Complex<C>> complexFromAny(
431 GenPolynomialRing<Complex<C>> fac, GenPolynomial<C> A) {
432 ComplexRing<C> cr = (ComplexRing<C>) fac.coFac;
433 return PolyUtil.<C, Complex<C>> map(fac, A, new AnyToComplex<C>(cr));
434 }
435
436
437 /**
438 * From AlgebraicNumber coefficients. Represent as polynomial with type
439 * GenPolynomial<C> coefficients, e.g. ModInteger or BigRational.
440 * @param rfac result polynomial factory.
441 * @param A polynomial with AlgebraicNumber coefficients to be converted.
442 * @return polynomial with type GenPolynomial<C> coefficients.
443 */
444 public static <C extends GcdRingElem<C>> GenPolynomial<GenPolynomial<C>> fromAlgebraicCoefficients(
445 GenPolynomialRing<GenPolynomial<C>> rfac, GenPolynomial<AlgebraicNumber<C>> A) {
446 return PolyUtil.<AlgebraicNumber<C>, GenPolynomial<C>> map(rfac, A, new AlgToPoly<C>());
447 }
448
449
450 /**
451 * Convert to AlgebraicNumber coefficients. Represent as polynomial with
452 * AlgebraicNumber<C> coefficients, C is e.g. ModInteger or BigRational.
453 * @param pfac result polynomial factory.
454 * @param A polynomial with C coefficients to be converted.
455 * @return polynomial with AlgebraicNumber<C> coefficients.
456 */
457 public static <C extends GcdRingElem<C>> GenPolynomial<AlgebraicNumber<C>> convertToAlgebraicCoefficients(
458 GenPolynomialRing<AlgebraicNumber<C>> pfac, GenPolynomial<C> A) {
459 AlgebraicNumberRing<C> afac = (AlgebraicNumberRing<C>) pfac.coFac;
460 return PolyUtil.<C, AlgebraicNumber<C>> map(pfac, A, new CoeffToAlg<C>(afac));
461 }
462
463
464 /**
465 * Convert to recursive AlgebraicNumber coefficients. Represent as
466 * polynomial with recursive AlgebraicNumber<C> coefficients, C is e.g.
467 * ModInteger or BigRational.
468 * @param depth recursion depth of AlgebraicNumber coefficients.
469 * @param pfac result polynomial factory.
470 * @param A polynomial with C coefficients to be converted.
471 * @return polynomial with AlgebraicNumber<C> coefficients.
472 */
473 public static <C extends GcdRingElem<C>> GenPolynomial<AlgebraicNumber<C>> convertToRecAlgebraicCoefficients(
474 int depth, GenPolynomialRing<AlgebraicNumber<C>> pfac, GenPolynomial<C> A) {
475 AlgebraicNumberRing<C> afac = (AlgebraicNumberRing<C>) pfac.coFac;
476 return PolyUtil.<C, AlgebraicNumber<C>> map(pfac, A, new CoeffToRecAlg<C>(depth, afac));
477 }
478
479
480 /**
481 * Convert to AlgebraicNumber coefficients. Represent as polynomial with
482 * AlgebraicNumber<C> coefficients, C is e.g. ModInteger or BigRational.
483 * @param pfac result polynomial factory.
484 * @param A recursive polynomial with GenPolynomial<BigInteger>
485 * coefficients to be converted.
486 * @return polynomial with AlgebraicNumber<C> coefficients.
487 */
488 public static <C extends GcdRingElem<C>> GenPolynomial<AlgebraicNumber<C>> convertRecursiveToAlgebraicCoefficients(
489 GenPolynomialRing<AlgebraicNumber<C>> pfac, GenPolynomial<GenPolynomial<C>> A) {
490 AlgebraicNumberRing<C> afac = (AlgebraicNumberRing<C>) pfac.coFac;
491 return PolyUtil.<GenPolynomial<C>, AlgebraicNumber<C>> map(pfac, A, new PolyToAlg<C>(afac));
492 }
493
494
495 /**
496 * Complex from algebraic coefficients.
497 * @param fac result polynomial factory.
498 * @param A polynomial with AlgebraicNumber coefficients Q(i) to be
499 * converted.
500 * @return polynomial with Complex coefficients.
501 */
502 public static <C extends GcdRingElem<C>> GenPolynomial<Complex<C>> complexFromAlgebraic(
503 GenPolynomialRing<Complex<C>> fac, GenPolynomial<AlgebraicNumber<C>> A) {
504 ComplexRing<C> cfac = (ComplexRing<C>) fac.coFac;
505 return PolyUtil.<AlgebraicNumber<C>, Complex<C>> map(fac, A, new AlgebToCompl<C>(cfac));
506 }
507
508
509 /**
510 * AlgebraicNumber from complex coefficients.
511 * @param fac result polynomial factory over Q(i).
512 * @param A polynomial with Complex coefficients to be converted.
513 * @return polynomial with AlgebraicNumber coefficients.
514 */
515 public static <C extends GcdRingElem<C>> GenPolynomial<AlgebraicNumber<C>> algebraicFromComplex(
516 GenPolynomialRing<AlgebraicNumber<C>> fac, GenPolynomial<Complex<C>> A) {
517 AlgebraicNumberRing<C> afac = (AlgebraicNumberRing<C>) fac.coFac;
518 return PolyUtil.<Complex<C>, AlgebraicNumber<C>> map(fac, A, new ComplToAlgeb<C>(afac));
519 }
520
521
522 /**
523 * ModInteger chinese remainder algorithm on coefficients.
524 * @param fac GenPolynomial<ModInteger> result factory with
525 * A.coFac.modul*B.coFac.modul = C.coFac.modul.
526 * @param A GenPolynomial<ModInteger>.
527 * @param B other GenPolynomial<ModInteger>.
528 * @param mi inverse of A.coFac.modul in ring B.coFac.
529 * @return S = cra(A,B), with S mod A.coFac.modul == A and S mod
530 * B.coFac.modul == B.
531 */
532 public static <C extends RingElem<C> & Modular> GenPolynomial<C> chineseRemainder(
533 GenPolynomialRing<C> fac, GenPolynomial<C> A, C mi, GenPolynomial<C> B) {
534 ModularRingFactory<C> cfac = (ModularRingFactory<C>) fac.coFac; // get RingFactory
535 GenPolynomial<C> S = fac.getZERO().clone();
536 GenPolynomial<C> Ap = A.clone();
537 SortedMap<ExpVector, C> av = Ap.val; //getMap();
538 SortedMap<ExpVector, C> bv = B.getMap();
539 SortedMap<ExpVector, C> sv = S.val; //getMap();
540 C c = null;
541 for (ExpVector e : bv.keySet()) {
542 C x = av.get(e);
543 C y = bv.get(e); // assert y != null
544 if (x != null) {
545 av.remove(e);
546 c = cfac.chineseRemainder(x, mi, y);
547 if (!c.isZERO()) { // 0 cannot happen
548 sv.put(e, c);
549 }
550 } else {
551 //c = cfac.fromInteger( y.getVal() );
552 c = cfac.chineseRemainder(A.ring.coFac.getZERO(), mi, y);
553 if (!c.isZERO()) { // 0 cannot happen
554 sv.put(e, c); // c != null
555 }
556 }
557 }
558 // assert bv is empty = done
559 for (ExpVector e : av.keySet()) { // rest of av
560 C x = av.get(e); // assert x != null
561 //c = cfac.fromInteger( x.getVal() );
562 c = cfac.chineseRemainder(x, mi, B.ring.coFac.getZERO());
563 if (!c.isZERO()) { // 0 cannot happen
564 sv.put(e, c); // c != null
565 }
566 }
567 return S;
568 }
569
570
571 /**
572 * GenPolynomial monic, i.e. leadingBaseCoefficient == 1. If
573 * leadingBaseCoefficient is not invertible returns this unmodified.
574 * @param <C> coefficient type.
575 * @param p recursive GenPolynomial<GenPolynomial<C>>.
576 * @return monic(p).
577 */
578 public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> monic(
579 GenPolynomial<GenPolynomial<C>> p) {
580 if (p == null || p.isZERO()) {
581 return p;
582 }
583 C lc = p.leadingBaseCoefficient().leadingBaseCoefficient();
584 if (!lc.isUnit()) {
585 return p;
586 }
587 C lm = lc.inverse();
588 GenPolynomial<C> L = p.ring.coFac.getONE();
589 L = L.multiply(lm);
590 return p.multiply(L);
591 }
592
593
594 /**
595 * Polynomial list monic.
596 * @param <C> coefficient type.
597 * @param L list of polynomials with field coefficients.
598 * @return list of polynomials with leading coefficient 1.
599 */
600 public static <C extends RingElem<C>> List<GenPolynomial<C>> monic(List<GenPolynomial<C>> L) {
601 return ListUtil.<GenPolynomial<C>, GenPolynomial<C>> map(L,
602 new UnaryFunctor<GenPolynomial<C>, GenPolynomial<C>>() {
603
604
605 public GenPolynomial<C> eval(GenPolynomial<C> c) {
606 if (c == null) {
607 return null;
608 } else {
609 return c.monic();
610 }
611 }
612 });
613 }
614
615
616 /**
617 * Polynomial list leading exponent vectors.
618 * @param <C> coefficient type.
619 * @param L list of polynomials.
620 * @return list of leading exponent vectors.
621 */
622 public static <C extends RingElem<C>> List<ExpVector> leadingExpVector(List<GenPolynomial<C>> L) {
623 return ListUtil.<GenPolynomial<C>, ExpVector> map(L, new UnaryFunctor<GenPolynomial<C>, ExpVector>() {
624
625
626 public ExpVector eval(GenPolynomial<C> c) {
627 if (c == null) {
628 return null;
629 } else {
630 return c.leadingExpVector();
631 }
632 }
633 });
634 }
635
636
637 /**
638 * Extend coefficient variables. Extend all coefficient ExpVectors by i
639 * elements and multiply by x_j^k.
640 * @param pfac extended polynomial ring factory (by i variables in the
641 * coefficients).
642 * @param j index of variable to be used for multiplication.
643 * @param k exponent for x_j.
644 * @return extended polynomial.
645 */
646 public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> extendCoefficients(
647 GenPolynomialRing<GenPolynomial<C>> pfac, GenPolynomial<GenPolynomial<C>> A, int j, long k) {
648 GenPolynomial<GenPolynomial<C>> Cp = pfac.getZERO().clone();
649 if (A.isZERO()) {
650 return Cp;
651 }
652 GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) pfac.coFac;
653 GenPolynomialRing<C> acfac = (GenPolynomialRing<C>) A.ring.coFac;
654 int i = cfac.nvar - acfac.nvar;
655 Map<ExpVector, GenPolynomial<C>> CC = Cp.val; //getMap();
656 for (Map.Entry<ExpVector, GenPolynomial<C>> y : A.val.entrySet()) {
657 ExpVector e = y.getKey();
658 GenPolynomial<C> a = y.getValue();
659 GenPolynomial<C> f = a.extend(cfac, j, k);
660 CC.put(e, f);
661 }
662 return Cp;
663 }
664
665
666 /**
667 * To recursive representation. Represent as polynomial in i+r variables
668 * with coefficients in i variables. Works for arbitrary term orders.
669 * @param <C> coefficient type.
670 * @param rfac recursive polynomial ring factory.
671 * @param A polynomial to be converted.
672 * @return Recursive represenations of this in the ring rfac.
673 */
674 public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> toRecursive(
675 GenPolynomialRing<GenPolynomial<C>> rfac, GenPolynomial<C> A) {
676
677 GenPolynomial<GenPolynomial<C>> B = rfac.getZERO().clone();
678 if (A.isZERO()) {
679 return B;
680 }
681 int i = rfac.nvar;
682 GenPolynomial<C> zero = rfac.getZEROCoefficient();
683 GenPolynomial<C> one = rfac.getONECoefficient();
684 Map<ExpVector, GenPolynomial<C>> Bv = B.val; //getMap();
685 for (Monomial<C> m : A) {
686 ExpVector e = m.e;
687 C a = m.c;
688 GenPolynomial<C> p = one.multiply(a);
689 Bv.put(e, p);
690 }
691 return B;
692 }
693
694
695 /**
696 * GenPolynomial coefficient wise remainder.
697 * @param <C> coefficient type.
698 * @param P GenPolynomial.
699 * @param s nonzero coefficient.
700 * @return coefficient wise remainder.
701 * @see edu.jas.poly.GenPolynomial#remainder(edu.jas.poly.GenPolynomial).
702 */
703 public static <C extends RingElem<C>> GenPolynomial<C> baseRemainderPoly(GenPolynomial<C> P, C s) {
704 if (s == null || s.isZERO()) {
705 throw new ArithmeticException(P.getClass().getName() + " division by zero");
706 }
707 GenPolynomial<C> h = P.ring.getZERO().clone();
708 Map<ExpVector, C> hm = h.val; //getMap();
709 for (Map.Entry<ExpVector, C> m : P.getMap().entrySet()) {
710 ExpVector f = m.getKey();
711 C a = m.getValue();
712 C x = a.remainder(s);
713 hm.put(f, x);
714 }
715 return h;
716 }
717
718
719 /**
720 * GenPolynomial sparse pseudo remainder. For univariate polynomials.
721 * @param <C> coefficient type.
722 * @param P GenPolynomial.
723 * @param S nonzero GenPolynomial.
724 * @return remainder with ldcf(S)<sup>m'</sup> P = quotient * S + remainder.
725 * @see edu.jas.poly.GenPolynomial#remainder(edu.jas.poly.GenPolynomial).
726 */
727 public static <C extends RingElem<C>> GenPolynomial<C> basePseudoRemainder(GenPolynomial<C> P,
728 GenPolynomial<C> S) {
729 if (S == null || S.isZERO()) {
730 throw new ArithmeticException(P.getClass().getName() + " division by zero");
731 }
732 if (P.isZERO()) {
733 return P;
734 }
735 if (S.isONE()) {
736 return P.ring.getZERO();
737 }
738 C c = S.leadingBaseCoefficient();
739 ExpVector e = S.leadingExpVector();
740 GenPolynomial<C> h;
741 GenPolynomial<C> r = P;
742 while (!r.isZERO()) {
743 ExpVector f = r.leadingExpVector();
744 if (f.multipleOf(e)) {
745 C a = r.leadingBaseCoefficient();
746 f = f.subtract(e);
747 C x = a.remainder(c);
748 if (x.isZERO()) {
749 C y = a.divide(c);
750 h = S.multiply(y, f); // coeff a
751 } else {
752 r = r.multiply(c); // coeff ac
753 h = S.multiply(a, f); // coeff ac
754 }
755 r = r.subtract(h);
756 } else {
757 break;
758 }
759 }
760 return r;
761 }
762
763
764 /**
765 * GenPolynomial pseudo divide. For univariate polynomials or exact
766 * division.
767 * @param <C> coefficient type.
768 * @param P GenPolynomial.
769 * @param S nonzero GenPolynomial.
770 * @return quotient with ldcf(S)<sup>m'</sup> P = quotient * S + remainder.
771 * @see edu.jas.poly.GenPolynomial#divide(edu.jas.poly.GenPolynomial).
772 */
773 public static <C extends RingElem<C>> GenPolynomial<C> basePseudoDivide(GenPolynomial<C> P,
774 GenPolynomial<C> S) {
775 if (S == null || S.isZERO()) {
776 throw new ArithmeticException(P.getClass().getName() + " division by zero");
777 }
778 if (S.ring.nvar != 1) {
779 // ok if exact division
780 // throw new RuntimeException(this.getClass().getName()
781 // + " univariate polynomials only");
782 }
783 if (P.isZERO() || S.isONE()) {
784 return P;
785 }
786 C c = S.leadingBaseCoefficient();
787 ExpVector e = S.leadingExpVector();
788 GenPolynomial<C> h;
789 GenPolynomial<C> r = P;
790 GenPolynomial<C> q = S.ring.getZERO().clone();
791
792 while (!r.isZERO()) {
793 ExpVector f = r.leadingExpVector();
794 if (f.multipleOf(e)) {
795 C a = r.leadingBaseCoefficient();
796 f = f.subtract(e);
797 C x = a.remainder(c);
798 if (x.isZERO()) {
799 C y = a.divide(c);
800 q = q.sum(y, f);
801 h = S.multiply(y, f); // coeff a
802 } else {
803 q = q.sum(a, f);
804 q = q.multiply(c);
805 r = r.multiply(c); // coeff ac
806 h = S.multiply(a, f); // coeff ac
807 }
808 r = r.subtract(h);
809 } else {
810 break;
811 }
812 }
813 return q;
814 }
815
816
817 /**
818 * GenPolynomial pseudo quotient and remainder. For univariate polynomials
819 * or exact division.
820 * @param <C> coefficient type.
821 * @param P GenPolynomial.
822 * @param S nonzero GenPolynomial.
823 * @return [ quotient, remainder ] with ldcf(S)<sup>m'</sup> P = quotient *
824 * S + remainder.
825 * @see edu.jas.poly.GenPolynomial#divide(edu.jas.poly.GenPolynomial).
826 */
827 @SuppressWarnings("unchecked")
828 public static <C extends RingElem<C>> GenPolynomial<C>[] basePseudoQuotientRemainder(GenPolynomial<C> P,
829 GenPolynomial<C> S) {
830 if (S == null || S.isZERO()) {
831 throw new ArithmeticException(P.getClass().getName() + " division by zero");
832 }
833 if (S.ring.nvar != 1) {
834 // ok if exact division
835 // throw new RuntimeException(this.getClass().getName()
836 // + " univariate polynomials only");
837 }
838 GenPolynomial<C>[] ret = new GenPolynomial[2];
839 ret[0] = null;
840 ret[1] = null;
841 if (P.isZERO() || S.isONE()) {
842 ret[0] = P;
843 ret[1] = S.ring.getZERO();
844 return ret;
845 }
846 C c = S.leadingBaseCoefficient();
847 ExpVector e = S.leadingExpVector();
848 GenPolynomial<C> h;
849 GenPolynomial<C> r = P;
850 GenPolynomial<C> q = S.ring.getZERO().clone();
851
852 while (!r.isZERO()) {
853 ExpVector f = r.leadingExpVector();
854 if (f.multipleOf(e)) {
855 C a = r.leadingBaseCoefficient();
856 f = f.subtract(e);
857 C x = a.remainder(c);
858 if (x.isZERO()) {
859 C y = a.divide(c);
860 q = q.sum(y, f);
861 h = S.multiply(y, f); // coeff a
862 } else {
863 q = q.sum(a, f);
864 q = q.multiply(c);
865 r = r.multiply(c); // coeff ac
866 h = S.multiply(a, f); // coeff ac
867 }
868 r = r.subtract(h);
869 } else {
870 break;
871 }
872 }
873 ret[0] = q;
874 ret[1] = r;
875 return ret;
876 }
877
878
879 /**
880 * GenPolynomial pseudo divide. For recursive polynomials. Division by
881 * coefficient ring element.
882 * @param <C> coefficient type.
883 * @param P recursive GenPolynomial.
884 * @param s GenPolynomial.
885 * @return this/s.
886 */
887 public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> recursiveDivide(
888 GenPolynomial<GenPolynomial<C>> P, GenPolynomial<C> s) {
889 if (s == null || s.isZERO()) {
890 throw new ArithmeticException(P.getClass().getName() + " division by zero " + P + ", " + s);
891 }
892 if (P.isZERO()) {
893 return P;
894 }
895 if (s.isONE()) {
896 return P;
897 }
898 GenPolynomial<GenPolynomial<C>> p = P.ring.getZERO().clone();
899 SortedMap<ExpVector, GenPolynomial<C>> pv = p.val; //getMap();
900 for (Map.Entry<ExpVector, GenPolynomial<C>> m1 : P.getMap().entrySet()) {
901 GenPolynomial<C> c1 = m1.getValue();
902 ExpVector e1 = m1.getKey();
903 GenPolynomial<C> c = PolyUtil.<C> basePseudoDivide(c1, s);
904 if (!c.isZERO()) {
905 pv.put(e1, c); // or m1.setValue( c )
906 } else {
907 System.out.println("pu, c1 = " + c1);
908 System.out.println("pu, s = " + s);
909 System.out.println("pu, c = " + c);
910 throw new RuntimeException("something is wrong");
911 }
912 }
913 return p;
914 }
915
916
917 /**
918 * GenPolynomial base divide. For recursive polynomials. Division by
919 * coefficient ring element.
920 * @param <C> coefficient type.
921 * @param P recursive GenPolynomial.
922 * @param s coefficient.
923 * @return this/s.
924 */
925 public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> baseRecursiveDivide(
926 GenPolynomial<GenPolynomial<C>> P, C s) {
927 if (s == null || s.isZERO()) {
928 throw new ArithmeticException(P.getClass().getName() + " division by zero " + P + ", " + s);
929 }
930 if (P.isZERO()) {
931 return P;
932 }
933 if (s.isONE()) {
934 return P;
935 }
936 GenPolynomial<GenPolynomial<C>> p = P.ring.getZERO().clone();
937 SortedMap<ExpVector, GenPolynomial<C>> pv = p.val; //getMap();
938 for (Map.Entry<ExpVector, GenPolynomial<C>> m1 : P.getMap().entrySet()) {
939 GenPolynomial<C> c1 = m1.getValue();
940 ExpVector e1 = m1.getKey();
941 GenPolynomial<C> c = PolyUtil.<C> coefficientBasePseudoDivide(c1, s);
942 if (!c.isZERO()) {
943 pv.put(e1, c); // or m1.setValue( c )
944 } else {
945 System.out.println("pu, c1 = " + c1);
946 System.out.println("pu, s = " + s);
947 System.out.println("pu, c = " + c);
948 throw new RuntimeException("something is wrong");
949 }
950 }
951 return p;
952 }
953
954
955 /**
956 * GenPolynomial sparse pseudo remainder. For recursive polynomials.
957 * @param <C> coefficient type.
958 * @param P recursive GenPolynomial.
959 * @param S nonzero recursive GenPolynomial.
960 * @return remainder with ldcf(S)<sup>m'</sup> P = quotient * S + remainder.
961 * @see edu.jas.poly.GenPolynomial#remainder(edu.jas.poly.GenPolynomial).
962 */
963 public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> recursivePseudoRemainder(
964 GenPolynomial<GenPolynomial<C>> P, GenPolynomial<GenPolynomial<C>> S) {
965 if (S == null || S.isZERO()) {
966 throw new ArithmeticException(P.getClass().getName() + " division by zero");
967 }
968 if (P == null || P.isZERO()) {
969 return P;
970 }
971 if (S.isONE()) {
972 return P.ring.getZERO();
973 }
974 GenPolynomial<C> c = S.leadingBaseCoefficient();
975 ExpVector e = S.leadingExpVector();
976 GenPolynomial<GenPolynomial<C>> h;
977 GenPolynomial<GenPolynomial<C>> r = P;
978 while (!r.isZERO()) {
979 ExpVector f = r.leadingExpVector();
980 if (f.multipleOf(e)) {
981 GenPolynomial<C> a = r.leadingBaseCoefficient();
982 f = f.subtract(e);
983 GenPolynomial<C> x = c; //test basePseudoRemainder(a,c);
984 if (x.isZERO()) {
985 GenPolynomial<C> y = PolyUtil.<C> basePseudoDivide(a, c);
986 h = S.multiply(y, f); // coeff a
987 } else {
988 r = r.multiply(c); // coeff ac
989 h = S.multiply(a, f); // coeff ac
990 }
991 r = r.subtract(h);
992 } else {
993 break;
994 }
995 }
996 return r;
997 }
998
999
1000 /**
1001 * GenPolynomial pseudo divide. For recursive polynomials.
1002 * @param <C> coefficient type.
1003 * @param P recursive GenPolynomial.
1004 * @param S nonzero recursive GenPolynomial.
1005 * @return quotient with ldcf(S)<sup>m</sup> P = quotient * S + remainder.
1006 * @see edu.jas.poly.GenPolynomial#remainder(edu.jas.poly.GenPolynomial).
1007 */
1008 public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> recursivePseudoDivide(
1009 GenPolynomial<GenPolynomial<C>> P, GenPolynomial<GenPolynomial<C>> S) {
1010 if (S == null || S.isZERO()) {
1011 throw new ArithmeticException(P.getClass().getName() + " division by zero");
1012 }
1013 if (S.ring.nvar != 1) {
1014 // ok if exact division
1015 // throw new RuntimeException(this.getClass().getName()
1016 // + " univariate polynomials only");
1017 }
1018 if (P == null || P.isZERO()) {
1019 return P;
1020 }
1021 if (S.isONE()) {
1022 return P;
1023 }
1024 GenPolynomial<C> c = S.leadingBaseCoefficient();
1025 ExpVector e = S.leadingExpVector();
1026 GenPolynomial<GenPolynomial<C>> h;
1027 GenPolynomial<GenPolynomial<C>> r = P;
1028 GenPolynomial<GenPolynomial<C>> q = S.ring.getZERO().clone();
1029 while (!r.isZERO()) {
1030 ExpVector f = r.leadingExpVector();
1031 if (f.multipleOf(e)) {
1032 GenPolynomial<C> a = r.leadingBaseCoefficient();
1033 f = f.subtract(e);
1034 GenPolynomial<C> x = PolyUtil.<C> basePseudoRemainder(a, c);
1035 if (x.isZERO()) {
1036 GenPolynomial<C> y = PolyUtil.<C> basePseudoDivide(a, c);
1037 q = q.sum(y, f);
1038 h = S.multiply(y, f); // coeff a
1039 } else {
1040 q = q.sum(a, f);
1041 q = q.multiply(c);
1042 r = r.multiply(c); // coeff ac
1043 h = S.multiply(a, f); // coeff ac
1044 }
1045 r = r.subtract(h);
1046 } else {
1047 break;
1048 }
1049 }
1050 return q;
1051 }
1052
1053
1054 /**
1055 * GenPolynomial pseudo divide. For recursive polynomials.
1056 * @param <C> coefficient type.
1057 * @param P recursive GenPolynomial.
1058 * @param s nonzero GenPolynomial.
1059 * @return quotient with ldcf(s)<sup>m</sup> P = quotient * s + remainder.
1060 * @see edu.jas.poly.GenPolynomial#remainder(edu.jas.poly.GenPolynomial).
1061 */
1062 public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> coefficientPseudoDivide(
1063 GenPolynomial<GenPolynomial<C>> P, GenPolynomial<C> s) {
1064 if (s == null || s.isZERO()) {
1065 throw new ArithmeticException(" division by zero");
1066 }
1067 if (P.isZERO()) {
1068 return P;
1069 }
1070 GenPolynomial<GenPolynomial<C>> p = P.ring.getZERO().clone();
1071 SortedMap<ExpVector, GenPolynomial<C>> pv = p.val;
1072 for (Map.Entry<ExpVector, GenPolynomial<C>> m : P.getMap().entrySet()) {
1073 ExpVector e = m.getKey();
1074 GenPolynomial<C> c1 = m.getValue();
1075 GenPolynomial<C> c = basePseudoDivide(c1, s);
1076 if (false) {
1077 GenPolynomial<C> x = c1.remainder(s);
1078 if (!x.isZERO()) {
1079 System.out.println("divide x = " + x);
1080 throw new ArithmeticException(" no exact division: " + c1 + "/" + s);
1081 }
1082 }
1083 if (c.isZERO()) {
1084 System.out.println(" no exact division: " + c1 + "/" + s);
1085 //throw new ArithmeticException(" no exact division: " + c1 + "/" + s);
1086 } else {
1087 pv.put(e, c); // or m1.setValue( c )
1088 }
1089 }
1090 return p;
1091 }
1092
1093
1094 /**
1095 * GenPolynomial pseudo divide. For polynomials.
1096 * @param <C> coefficient type.
1097 * @param P GenPolynomial.
1098 * @param s nonzero coefficient.
1099 * @return quotient with ldcf(s)<sup>m</sup> P = quotient * s + remainder.
1100 * @see edu.jas.poly.GenPolynomial#remainder(edu.jas.poly.GenPolynomial).
1101 */
1102 public static <C extends RingElem<C>> GenPolynomial<C> coefficientBasePseudoDivide(GenPolynomial<C> P, C s) {
1103 if (s == null || s.isZERO()) {
1104 throw new ArithmeticException(" division by zero");
1105 }
1106 if (P.isZERO()) {
1107 return P;
1108 }
1109 GenPolynomial<C> p = P.ring.getZERO().clone();
1110 SortedMap<ExpVector, C> pv = p.val;
1111 for (Map.Entry<ExpVector, C> m : P.getMap().entrySet()) {
1112 ExpVector e = m.getKey();
1113 C c1 = m.getValue();
1114 C c = c1.divide(s);
1115 if (false) {
1116 C x = c1.remainder(s);
1117 if (!x.isZERO()) {
1118 System.out.println("divide x = " + x);
1119 throw new ArithmeticException(" no exact division: " + c1 + "/" + s);
1120 }
1121 }
1122 if (c.isZERO()) {
1123 System.out.println(" no exact division: " + c1 + "/" + s);
1124 //throw new ArithmeticException(" no exact division: " + c1 + "/" + s);
1125 } else {
1126 pv.put(e, c); // or m1.setValue( c )
1127 }
1128 }
1129 return p;
1130 }
1131
1132
1133 /**
1134 * GenPolynomial polynomial derivative main variable.
1135 * @param <C> coefficient type.
1136 * @param P GenPolynomial.
1137 * @return deriviative(P).
1138 */
1139 public static <C extends RingElem<C>> GenPolynomial<C> baseDeriviative(GenPolynomial<C> P) {
1140 if (P == null || P.isZERO()) {
1141 return P;
1142 }
1143 GenPolynomialRing<C> pfac = P.ring;
1144 if (pfac.nvar > 1) {
1145 // baseContent not possible by return type
1146 throw new IllegalArgumentException(P.getClass().getName() + " only for univariate polynomials");
1147 }
1148 RingFactory<C> rf = pfac.coFac;
1149 GenPolynomial<C> d = pfac.getZERO().clone();
1150 Map<ExpVector, C> dm = d.val; //getMap();
1151 for (Map.Entry<ExpVector, C> m : P.getMap().entrySet()) {
1152 ExpVector f = m.getKey();
1153 long fl = f.getVal(0);
1154 if (fl > 0) {
1155 C cf = rf.fromInteger(fl);
1156 C a = m.getValue();
1157 C x = a.multiply(cf);
1158 if (x != null && !x.isZERO()) {
1159 ExpVector e = ExpVector.create(1, 0, fl - 1L);
1160 dm.put(e, x);
1161 }
1162 }
1163 }
1164 return d;
1165 }
1166
1167
1168 /**
1169 * GenPolynomial polynomial partial derivative variable r.
1170 * @param <C> coefficient type.
1171 * @param P GenPolynomial.
1172 * @param r variable for partial deriviate.
1173 * @return deriviative(P,r).
1174 */
1175 public static <C extends RingElem<C>> GenPolynomial<C> baseDeriviative(GenPolynomial<C> P, int r) {
1176 if (P == null || P.isZERO()) {
1177 return P;
1178 }
1179 GenPolynomialRing<C> pfac = P.ring;
1180 if (r < 0 || pfac.nvar <= r) {
1181 throw new IllegalArgumentException(P.getClass().getName() + " deriviative variable out of bound "
1182 + r);
1183 }
1184 int rp = pfac.nvar - 1 - r;
1185 RingFactory<C> rf = pfac.coFac;
1186 GenPolynomial<C> d = pfac.getZERO().clone();
1187 Map<ExpVector, C> dm = d.val; //getMap();
1188 for (Map.Entry<ExpVector, C> m : P.getMap().entrySet()) {
1189 ExpVector f = m.getKey();
1190 long fl = f.getVal(rp);
1191 if (fl > 0) {
1192 C cf = rf.fromInteger(fl);
1193 C a = m.getValue();
1194 C x = a.multiply(cf);
1195 if (x != null && !x.isZERO()) {
1196 ExpVector e = f.subst(rp, fl - 1L);
1197 dm.put(e, x);
1198 }
1199 }
1200 }
1201 return d;
1202 }
1203
1204
1205 /**
1206 * GenPolynomial polynomial integral main variable.
1207 * @param <C> coefficient type.
1208 * @param P GenPolynomial.
1209 * @return integral(P).
1210 */
1211 public static <C extends RingElem<C>> GenPolynomial<C> baseIntegral(GenPolynomial<C> P) {
1212 if (P == null || P.isZERO()) {
1213 return P;
1214 }
1215 GenPolynomialRing<C> pfac = P.ring;
1216 if (pfac.nvar > 1) {
1217 // baseContent not possible by return type
1218 throw new IllegalArgumentException(P.getClass().getName() + " only for univariate polynomials");
1219 }
1220 RingFactory<C> rf = pfac.coFac;
1221 GenPolynomial<C> d = pfac.getZERO().clone();
1222 Map<ExpVector, C> dm = d.val; //getMap();
1223 for (Map.Entry<ExpVector, C> m : P.getMap().entrySet()) {
1224 ExpVector f = m.getKey();
1225 long fl = f.getVal(0);
1226 fl++;
1227 C cf = rf.fromInteger(fl);
1228 C a = m.getValue();
1229 C x = a.divide(cf);
1230 if (x != null && !x.isZERO()) {
1231 ExpVector e = ExpVector.create(1, 0, fl);
1232 dm.put(e, x);
1233 }
1234 }
1235 return d;
1236 }
1237
1238
1239 /**
1240 * GenPolynomial recursive polynomial derivative main variable.
1241 * @param <C> coefficient type.
1242 * @param P recursive GenPolynomial.
1243 * @return deriviative(P).
1244 */
1245 public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> recursiveDeriviative(
1246 GenPolynomial<GenPolynomial<C>> P) {
1247 if (P == null || P.isZERO()) {
1248 return P;
1249 }
1250 GenPolynomialRing<GenPolynomial<C>> pfac = P.ring;
1251 if (pfac.nvar > 1) {
1252 // baseContent not possible by return type
1253 throw new IllegalArgumentException(P.getClass().getName() + " only for univariate polynomials");
1254 }
1255 GenPolynomialRing<C> pr = (GenPolynomialRing<C>) pfac.coFac;
1256 RingFactory<C> rf = pr.coFac;
1257 GenPolynomial<GenPolynomial<C>> d = pfac.getZERO().clone();
1258 Map<ExpVector, GenPolynomial<C>> dm = d.val; //getMap();
1259 for (Map.Entry<ExpVector, GenPolynomial<C>> m : P.getMap().entrySet()) {
1260 ExpVector f = m.getKey();
1261 long fl = f.getVal(0);
1262 if (fl > 0) {
1263 C cf = rf.fromInteger(fl);
1264 GenPolynomial<C> a = m.getValue();
1265 GenPolynomial<C> x = a.multiply(cf);
1266 if (x != null && !x.isZERO()) {
1267 ExpVector e = ExpVector.create(1, 0, fl - 1L);
1268 dm.put(e, x);
1269 }
1270 }
1271 }
1272 return d;
1273 }
1274
1275
1276 /**
1277 * Factor coefficient bound. See SACIPOL.IPFCB: the product of all maxNorms
1278 * of potential factors is less than or equal to 2**b times the maxNorm of
1279 * A.
1280 * @param e degree vector of a GenPolynomial A.
1281 * @return 2**b.
1282 */
1283 public static BigInteger factorBound(ExpVector e) {
1284 int n = 0;
1285 java.math.BigInteger p = java.math.BigInteger.ONE;
1286 java.math.BigInteger v;
1287 if (e == null || e.isZERO()) {
1288 return BigInteger.ONE;
1289 }
1290 for (int i = 0; i < e.length(); i++) {
1291 if (e.getVal(i) > 0) {
1292 n += (2 * e.getVal(i) - 1);
1293 v = new java.math.BigInteger("" + (e.getVal(i) - 1));
1294 p = p.multiply(v);
1295 }
1296 }
1297 n += (p.bitCount() + 1); // log2(p)
1298 n /= 2;
1299 v = new java.math.BigInteger("" + 2);
1300 v = v.shiftLeft(n);
1301 BigInteger N = new BigInteger(v);
1302 return N;
1303 }
1304
1305
1306 /**
1307 * Evaluate at main variable.
1308 * @param <C> coefficient type.
1309 * @param cfac coefficent polynomial ring factory.
1310 * @param A recursive polynomial to be evaluated.
1311 * @param a value to evaluate at.
1312 * @return A( x_1, ..., x_{n-1}, a ).
1313 */
1314 public static <C extends RingElem<C>> GenPolynomial<C> evaluateMainRecursive(GenPolynomialRing<C> cfac,
1315 GenPolynomial<GenPolynomial<C>> A, C a) {
1316 if (A == null || A.isZERO()) {
1317 return cfac.getZERO();
1318 }
1319 if (A.ring.nvar != 1) { // todo assert
1320 throw new IllegalArgumentException("evaluateMain no univariate polynomial");
1321 }
1322 if (a == null || a.isZERO()) {
1323 return A.trailingBaseCoefficient();
1324 }
1325 // assert decending exponents, i.e. compatible term order
1326 Map<ExpVector, GenPolynomial<C>> val = A.getMap();
1327 GenPolynomial<C> B = null;
1328 long el1 = -1; // undefined
1329 long el2 = -1;
1330 for (ExpVector e : val.keySet()) {
1331 el2 = e.getVal(0);
1332 if (B == null /*el1 < 0*/) { // first turn
1333 B = val.get(e);
1334 } else {
1335 for (long i = el2; i < el1; i++) {
1336 B = B.multiply(a);
1337 }
1338 B = B.sum(val.get(e));
1339 }
1340 el1 = el2;
1341 }
1342 for (long i = 0; i < el2; i++) {
1343 B = B.multiply(a);
1344 }
1345 return B;
1346 }
1347
1348
1349 /**
1350 * Evaluate at main variable.
1351 * @param <C> coefficient type.
1352 * @param cfac coefficent polynomial ring factory.
1353 * @param A distributed polynomial to be evaluated.
1354 * @param a value to evaluate at.
1355 * @return A( x_1, ..., x_{n-1}, a ).
1356 */
1357 public static <C extends RingElem<C>> GenPolynomial<C> evaluateMain(GenPolynomialRing<C> cfac,
1358 GenPolynomial<C> A, C a) {
1359 if (A == null || A.isZERO()) {
1360 return cfac.getZERO();
1361 }
1362 GenPolynomialRing<GenPolynomial<C>> rfac = new GenPolynomialRing<GenPolynomial<C>>(cfac, 1);
1363 if (rfac.nvar + cfac.nvar != A.ring.nvar) {
1364 throw new IllegalArgumentException("evaluateMain number of variabes mismatch");
1365 }
1366 GenPolynomial<GenPolynomial<C>> Ap = recursive(rfac, A);
1367 return PolyUtil.<C> evaluateMainRecursive(cfac, Ap, a);
1368 }
1369
1370
1371 /**
1372 * Evaluate at main variable.
1373 * @param <C> coefficient type.
1374 * @param cfac coefficent ring factory.
1375 * @param L list of univariate polynomials to be evaluated.
1376 * @param a value to evaluate at.
1377 * @return list( A( x_1, ..., x_{n-1}, a ) ) for A in L.
1378 */
1379 public static <C extends RingElem<C>> List<GenPolynomial<C>>
1380 evaluateMain(GenPolynomialRing<C> cfac, List<GenPolynomial<C>> L, C a) {
1381 return ListUtil.<GenPolynomial<C>, GenPolynomial<C>> map(L, new EvalMainPol<C>(cfac, a));
1382 }
1383
1384
1385 /**
1386 * Evaluate at main variable.
1387 * @param <C> coefficient type.
1388 * @param cfac coefficent ring factory.
1389 * @param A univariate polynomial to be evaluated.
1390 * @param a value to evaluate at.
1391 * @return A( a ).
1392 */
1393 public static <C extends RingElem<C>> C evaluateMain(RingFactory<C> cfac, GenPolynomial<C> A, C a) {
1394 if (A == null || A.isZERO()) {
1395 return cfac.getZERO();
1396 }
1397 if (A.ring.nvar != 1) { // todo assert
1398 throw new IllegalArgumentException("evaluateMain no univariate polynomial");
1399 }
1400 if (a == null || a.isZERO()) {
1401 return A.trailingBaseCoefficient();
1402 }
1403 // assert decreasing exponents, i.e. compatible term order
1404 Map<ExpVector, C> val = A.getMap();
1405 C B = null;
1406 long el1 = -1; // undefined
1407 long el2 = -1;
1408 for (ExpVector e : val.keySet()) {
1409 el2 = e.getVal(0);
1410 if (B == null /*el1 < 0*/) { // first turn
1411 B = val.get(e);
1412 } else {
1413 for (long i = el2; i < el1; i++) {
1414 B = B.multiply(a);
1415 }
1416 B = B.sum(val.get(e));
1417 }
1418 el1 = el2;
1419 }
1420 for (long i = 0; i < el2; i++) {
1421 B = B.multiply(a);
1422 }
1423 return B;
1424 }
1425
1426
1427 /**
1428 * Evaluate at main variable.
1429 * @param <C> coefficient type.
1430 * @param cfac coefficent ring factory.
1431 * @param L list of univariate polynomial to be evaluated.
1432 * @param a value to evaluate at.
1433 * @return list( A( a ) ) for A in L.
1434 */
1435 public static <C extends RingElem<C>> List<C> evaluateMain(RingFactory<C> cfac, List<GenPolynomial<C>> L,
1436 C a) {
1437 return ListUtil.<GenPolynomial<C>, C> map(L, new EvalMain<C>(cfac, a));
1438 }
1439
1440
1441 /**
1442 * Evaluate at k-th variable.
1443 * @param <C> coefficient type.
1444 * @param cfac coefficient polynomial ring in k variables C[x_1, ..., x_k]
1445 * factory.
1446 * @param rfac coefficient polynomial ring C[x_1, ..., x_{k-1}] [x_k]
1447 * factory, a recursive polynomial ring in 1 variable with
1448 * coefficients in k-1 variables.
1449 * @param nfac polynomial ring in n-1 varaibles C[x_1, ..., x_{k-1}]
1450 * [x_{k+1}, ..., x_n] factory, a recursive polynomial ring in
1451 * n-k+1 variables with coefficients in k-1 variables.
1452 * @param dfac polynomial ring in n-1 variables. C[x_1, ..., x_{k-1},
1453 * x_{k+1}, ..., x_n] factory.
1454 * @param A polynomial to be evaluated.
1455 * @param a value to evaluate at.
1456 * @return A( x_1, ..., x_{k-1}, a, x_{k+1}, ..., x_n).
1457 */
1458 public static <C extends RingElem<C>> GenPolynomial<C> evaluate(GenPolynomialRing<C> cfac,
1459 GenPolynomialRing<GenPolynomial<C>> rfac, GenPolynomialRing<GenPolynomial<C>> nfac,
1460 GenPolynomialRing<C> dfac, GenPolynomial<C> A, C a) {
1461 if (rfac.nvar != 1) { // todo assert
1462 throw new IllegalArgumentException("evaluate coefficient ring not univariate");
1463 }
1464 if (A == null || A.isZERO()) {
1465 return cfac.getZERO();
1466 }
1467 Map<ExpVector, GenPolynomial<C>> Ap = A.contract(cfac);
1468 GenPolynomialRing<C> rcf = (GenPolynomialRing<C>) rfac.coFac;
1469 GenPolynomial<GenPolynomial<C>> Ev = nfac.getZERO().clone();
1470 Map<ExpVector, GenPolynomial<C>> Evm = Ev.val; //getMap();
1471 for (Map.Entry<ExpVector, GenPolynomial<C>> m : Ap.entrySet()) {
1472 ExpVector e = m.getKey();
1473 GenPolynomial<C> b = m.getValue();
1474 GenPolynomial<GenPolynomial<C>> c = recursive(rfac, b);
1475 GenPolynomial<C> d = evaluateMainRecursive(rcf, c, a);
1476 if (d != null && !d.isZERO()) {
1477 Evm.put(e, d);
1478 }
1479 }
1480 GenPolynomial<C> B = distribute(dfac, Ev);
1481 return B;
1482 }
1483
1484
1485 /**
1486 * Evaluate at first (lowest) variable.
1487 * @param <C> coefficient type.
1488 * @param cfac coefficient polynomial ring in first variable C[x_1] factory.
1489 * @param dfac polynomial ring in n-1 variables. C[x_2, ..., x_n] factory.
1490 * @param A polynomial to be evaluated.
1491 * @param a value to evaluate at.
1492 * @return A( a, x_2, ..., x_n).
1493 */
1494 public static <C extends RingElem<C>> GenPolynomial<C> evaluateFirst(GenPolynomialRing<C> cfac,
1495 GenPolynomialRing<C> dfac, GenPolynomial<C> A, C a) {
1496 if (A == null || A.isZERO()) {
1497 return dfac.getZERO();
1498 }
1499 Map<ExpVector, GenPolynomial<C>> Ap = A.contract(cfac);
1500 //RingFactory<C> rcf = cfac.coFac; // == dfac.coFac
1501
1502 GenPolynomial<C> B = dfac.getZERO().clone();
1503 Map<ExpVector, C> Bm = B.val; //getMap();
1504
1505 for (Map.Entry<ExpVector, GenPolynomial<C>> m : Ap.entrySet()) {
1506 ExpVector e = m.getKey();
1507 GenPolynomial<C> b = m.getValue();
1508 C d = evaluateMain(cfac.coFac, b, a);
1509 if (d != null && !d.isZERO()) {
1510 Bm.put(e, d);
1511 }
1512 }
1513 return B;
1514 }
1515
1516
1517 /**
1518 * Evaluate at first (lowest) variable.
1519 * @param <C> coefficient type. Could also be called evaluateFirst(), but
1520 * type erasure of A parameter does not allow same name.
1521 * @param cfac coefficient polynomial ring in first variable C[x_1] factory.
1522 * @param dfac polynomial ring in n-1 variables. C[x_2, ..., x_n] factory.
1523 * @param A recursive polynomial to be evaluated.
1524 * @param a value to evaluate at.
1525 * @return A( a, x_2, ..., x_n).
1526 */
1527 public static <C extends RingElem<C>> GenPolynomial<C> evaluateFirstRec(GenPolynomialRing<C> cfac,
1528 GenPolynomialRing<C> dfac, GenPolynomial<GenPolynomial<C>> A, C a) {
1529 if (A == null || A.isZERO()) {
1530 return dfac.getZERO();
1531 }
1532 Map<ExpVector, GenPolynomial<C>> Ap = A.getMap();
1533 GenPolynomial<C> B = dfac.getZERO().clone();
1534 Map<ExpVector, C> Bm = B.val; //getMap();
1535 for (Map.Entry<ExpVector, GenPolynomial<C>> m : Ap.entrySet()) {
1536 ExpVector e = m.getKey();
1537 GenPolynomial<C> b = m.getValue();
1538 C d = evaluateMain(cfac.coFac, b, a);
1539 if (d != null && !d.isZERO()) {
1540 Bm.put(e, d);
1541 }
1542 }
1543 return B;
1544 }
1545
1546
1547 /**
1548 * Evaluate all variables.
1549 * @param <C> coefficient type.
1550 * @param cfac coefficient ring factory.
1551 * @param dfac polynomial ring in n variables. C[x_1, x_2, ..., x_n]
1552 * factory.
1553 * @param A polynomial to be evaluated.
1554 * @param a = ( a_1, a_2, ..., a_n) a tuple of values to evaluate at.
1555 * @return A( a_1, a_2, ..., a_n).
1556 */
1557 public static <C extends RingElem<C>> C evaluateAll(RingFactory<C> cfac, GenPolynomialRing<C> dfac,
1558 GenPolynomial<C> A, List<C> a) {
1559 if (A == null || A.isZERO()) {
1560 return cfac.getZERO();
1561 }
1562 if (a == null || a.size() != dfac.nvar) {
1563 throw new IllegalArgumentException("evaluate tuple size not equal to number of variables");
1564 }
1565 if (dfac.nvar == 0) {
1566 return A.trailingBaseCoefficient();
1567 }
1568 if (dfac.nvar == 1) {
1569 return evaluateMain(cfac, A, a.get(0));
1570 }
1571 C b = cfac.getZERO();
1572 GenPolynomial<C> Ap = A;
1573 for (int k = 0; k < dfac.nvar - 1; k++) {
1574 C ap = a.get(k);
1575 GenPolynomialRing<C> c1fac = new GenPolynomialRing<C>(cfac, 1);
1576 GenPolynomialRing<C> cnfac = new GenPolynomialRing<C>(cfac, dfac.nvar - 1 - k);
1577 GenPolynomial<C> Bp = evaluateFirst(c1fac, cnfac, Ap, ap);
1578 if (Bp.isZERO()) {
1579 return b;
1580 }
1581 Ap = Bp;
1582 //System.out.println("Ap = " + Ap);
1583 }
1584 C ap = a.get(dfac.nvar - 1);
1585 b = evaluateMain(cfac, Ap, ap);
1586 return b;
1587 }
1588
1589
1590 /**
1591 * Substitute main variable.
1592 * @param A univariate polynomial.
1593 * @param s polynomial for substitution.
1594 * @return polynomial A(x <- s).
1595 */
1596 public static <C extends RingElem<C>> GenPolynomial<C> substituteMain(GenPolynomial<C> A,
1597 GenPolynomial<C> s) {
1598 return substituteUnivariate(A, s);
1599 }
1600
1601
1602 /**
1603 * Substitute univariate polynomial.
1604 * @param f univariate polynomial.
1605 * @param t polynomial for substitution.
1606 * @return polynomial A(x <- t).
1607 */
1608 public static <C extends RingElem<C>> GenPolynomial<C> substituteUnivariate(GenPolynomial<C> f,
1609 GenPolynomial<C> t) {
1610 if (f == null || t == null) {
1611 return null;
1612 }
1613 GenPolynomialRing<C> fac = f.ring;
1614 if (fac.nvar > 1) {
1615 throw new IllegalArgumentException("only for univariate polynomial f");
1616 }
1617 if (f.isZERO() || f.isConstant()) {
1618 return f;
1619 }
1620 if (t.ring.nvar > 1) {
1621 fac = t.ring;
1622 }
1623 // assert decending exponents, i.e. compatible term order
1624 Map<ExpVector, C> val = f.getMap();
1625 GenPolynomial<C> s = null;
1626 long el1 = -1; // undefined
1627 long el2 = -1;
1628 for (ExpVector e : val.keySet()) {
1629 el2 = e.getVal(0);
1630 if (s == null /*el1 < 0*/) { // first turn
1631 s = fac.getZERO().sum(val.get(e));
1632 } else {
1633 for (long i = el2; i < el1; i++) {
1634 s = s.multiply(t);
1635 }
1636 s = s.sum(val.get(e));
1637 }
1638 el1 = el2;
1639 }
1640 for (long i = 0; i < el2; i++) {
1641 s = s.multiply(t);
1642 }
1643 //System.out.println("s = " + s);
1644 return s;
1645 }
1646
1647
1648 /**
1649 * Taylor series for polynomial.
1650 * @param f univariate polynomial.
1651 * @param a expansion point.
1652 * @return Taylor series (a polynomial) of f at a.
1653 */
1654 public static <C extends RingElem<C>> GenPolynomial<C> seriesOfTaylor(GenPolynomial<C> f, C a) {
1655 if (f == null) {
1656 return null;
1657 }
1658 GenPolynomialRing<C> fac = f.ring;
1659 if (fac.nvar > 1) {
1660 throw new IllegalArgumentException("only for univariate polynomials");
1661 }
1662 if (f.isZERO() || f.isConstant()) {
1663 return f;
1664 }
1665 GenPolynomial<C> s = fac.getZERO();
1666 C fa = PolyUtil.<C> evaluateMain(fac.coFac, f, a);
1667 s = s.sum(fa);
1668 long n = 1;
1669 long i = 0;
1670 GenPolynomial<C> g = PolyUtil.<C> baseDeriviative(f);
1671 GenPolynomial<C> p = fac.getONE();
1672 while (!g.isZERO()) {
1673 i++;
1674 n *= i;
1675 fa = PolyUtil.<C> evaluateMain(fac.coFac, g, a);
1676 GenPolynomial<C> q = fac.univariate(0, i); //p;
1677 q = q.multiply(fa);
1678 q = q.divide(fac.fromInteger(n));
1679 s = s.sum(q);
1680 g = PolyUtil.<C> baseDeriviative(g);
1681 }
1682 //System.out.println("s = " + s);
1683 return s;
1684 }
1685
1686
1687 /**
1688 * ModInteger interpolate on first variable.
1689 * @param <C> coefficient type.
1690 * @param fac GenPolynomial<C> result factory.
1691 * @param A GenPolynomial.
1692 * @param M GenPolynomial interpolation modul of A.
1693 * @param mi inverse of M(am) in ring fac.coFac.
1694 * @param B evaluation of other GenPolynomial.
1695 * @param am evaluation point (interpolation modul) of B, i.e. P(am) = B.
1696 * @return S, with S mod M == A and S(am) == B.
1697 */
1698 public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> interpolate(
1699 GenPolynomialRing<GenPolynomial<C>> fac, GenPolynomial<GenPolynomial<C>> A,
1700 GenPolynomial<C> M, C mi, GenPolynomial<C> B, C am) {
1701 GenPolynomial<GenPolynomial<C>> S = fac.getZERO().clone();
1702 GenPolynomial<GenPolynomial<C>> Ap = A.clone();
1703 SortedMap<ExpVector, GenPolynomial<C>> av = Ap.val; //getMap();
1704 SortedMap<ExpVector, C> bv = B.getMap();
1705 SortedMap<ExpVector, GenPolynomial<C>> sv = S.val; //getMap();
1706 GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) fac.coFac;
1707 RingFactory<C> bfac = cfac.coFac;
1708 GenPolynomial<C> c = null;
1709 for (ExpVector e : bv.keySet()) {
1710 GenPolynomial<C> x = av.get(e);
1711 C y = bv.get(e); // assert y != null
1712 if (x != null) {
1713 av.remove(e);
1714 c = PolyUtil.<C> interpolate(cfac, x, M, mi, y, am);
1715 if (!c.isZERO()) { // 0 cannot happen
1716 sv.put(e, c);
1717 }
1718 } else {
1719 c = PolyUtil.<C> interpolate(cfac, cfac.getZERO(), M, mi, y, am);
1720 if (!c.isZERO()) { // 0 cannot happen
1721 sv.put(e, c); // c != null
1722 }
1723 }
1724 }
1725 // assert bv is empty = done
1726 for (ExpVector e : av.keySet()) { // rest of av
1727 GenPolynomial<C> x = av.get(e); // assert x != null
1728 c = PolyUtil.<C> interpolate(cfac, x, M, mi, bfac.getZERO(), am);
1729 if (!c.isZERO()) { // 0 cannot happen
1730 sv.put(e, c); // c != null
1731 }
1732 }
1733 return S;
1734 }
1735
1736
1737 /**
1738 * Univariate polynomial interpolation.
1739 * @param <C> coefficient type.
1740 * @param fac GenPolynomial<C> result factory.
1741 * @param A GenPolynomial.
1742 * @param M GenPolynomial interpolation modul of A.
1743 * @param mi inverse of M(am) in ring fac.coFac.
1744 * @param a evaluation of other GenPolynomial.
1745 * @param am evaluation point (interpolation modul) of a, i.e. P(am) = a.
1746 * @return S, with S mod M == A and S(am) == a.
1747 */
1748 public static <C extends RingElem<C>> GenPolynomial<C> interpolate(GenPolynomialRing<C> fac,
1749 GenPolynomial<C> A, GenPolynomial<C> M, C mi, C a, C am) {
1750 GenPolynomial<C> s;
1751 C b = PolyUtil.<C> evaluateMain(fac.coFac, A, am);
1752 // A mod a.modul
1753 C d = a.subtract(b); // a-A mod a.modul
1754 if (d.isZERO()) {
1755 return A;
1756 }
1757 b = d.multiply(mi); // b = (a-A)*mi mod a.modul
1758 // (M*b)+A mod M = A mod M =
1759 // (M*mi*(a-A)+A) mod a.modul = a mod a.modul
1760 s = M.multiply(b);
1761 s = s.sum(A);
1762 return s;
1763 }
1764
1765
1766 /**
1767 * Recursive GenPolynomial switch varaible blocks.
1768 * @param <C> coefficient type.
1769 * @param P recursive GenPolynomial in R[X,Y].
1770 * @return this in R[Y,X].
1771 */
1772 public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> switchVariables(
1773 GenPolynomial<GenPolynomial<C>> P) {
1774 if (P == null) {
1775 throw new IllegalArgumentException("P == null");
1776 }
1777 GenPolynomialRing<GenPolynomial<C>> rfac1 = P.ring;
1778 GenPolynomialRing<C> cfac1 = (GenPolynomialRing<C>) rfac1.coFac;
1779 GenPolynomialRing<C> cfac2 = new GenPolynomialRing<C>(cfac1.coFac, rfac1);
1780 GenPolynomial<C> zero = cfac2.getZERO();
1781 GenPolynomialRing<GenPolynomial<C>> rfac2 = new GenPolynomialRing<GenPolynomial<C>>(cfac2, cfac1);
1782 GenPolynomial<GenPolynomial<C>> B = rfac2.getZERO().clone();
1783 if (P.isZERO()) {
1784 return B;
1785 }
1786 for (Monomial<GenPolynomial<C>> mr : P) {
1787 GenPolynomial<C> cr = mr.c;
1788 for (Monomial<C> mc : cr) {
1789 GenPolynomial<C> c = zero.sum(mc.c, mr.e);
1790 B = B.sum(c, mc.e);
1791 }
1792 }
1793 return B;
1794 }
1795
1796
1797 /**
1798 * Maximal degree of leading terms of a polynomial list.
1799 * @return maximum degree of the leading terms of a polynomial list.
1800 */
1801 public static <C extends RingElem<C>> long totalDegreeLeadingTerm(List<GenPolynomial<C>> P){
1802 long degree = 0;
1803 for(GenPolynomial<C> g : P){
1804 long total = g.leadingExpVector().totalDeg();
1805 if ( degree < total ) {
1806 degree = total;
1807 }
1808 }
1809 return degree;
1810 }
1811
1812
1813 /**
1814 * Maximal degree of polynomial list.
1815 * @return maximum degree of the polynomial list.
1816 */
1817 public static <C extends RingElem<C>> long totalDegree(List<GenPolynomial<C>> P){
1818 long degree = 0;
1819 for(GenPolynomial<C> g : P){
1820 long total = g.degree();
1821 if ( degree < total ) {
1822 degree = total;
1823 }
1824 }
1825 return degree;
1826 }
1827
1828
1829 /**
1830 * Maximal degree in the coefficient polynomials.
1831 * @param <C> coefficient type.
1832 * @return maximal degree in the coefficients.
1833 */
1834 public static <C extends RingElem<C>> long coeffMaxDegree(GenPolynomial<GenPolynomial<C>> A) {
1835 if (A.isZERO()) {
1836 return 0; // 0 or -1 ?;
1837 }
1838 long deg = 0;
1839 for (GenPolynomial<C> a : A.getMap().values()) {
1840 long d = a.degree();
1841 if (d > deg) {
1842 deg = d;
1843 }
1844 }
1845 return deg;
1846 }
1847
1848
1849 /**
1850 * Map a unary function to the coefficients.
1851 * @param ring result polynomial ring factory.
1852 * @param p polynomial.
1853 * @param f evaluation functor.
1854 * @return new polynomial with coefficients f(p(e)).
1855 */
1856 public static <C extends RingElem<C>, D extends RingElem<D>> GenPolynomial<D> map(
1857 GenPolynomialRing<D> ring, GenPolynomial<C> p, UnaryFunctor<C, D> f) {
1858 GenPolynomial<D> n = ring.getZERO().clone();
1859 SortedMap<ExpVector, D> nv = n.val;
1860 for (Monomial<C> m : p) {
1861 D c = f.eval(m.c);
1862 if (c != null && !c.isZERO()) {
1863 nv.put(m.e, c);
1864 }
1865 }
1866 return n;
1867 }
1868
1869
1870 /**
1871 * Product representation.
1872 * @param <C> coefficient type.
1873 * @param pfac polynomial ring factory.
1874 * @param L list of polynomials to be represented.
1875 * @return Product represenation of L in the polynomial ring pfac.
1876 */
1877 public static <C extends GcdRingElem<C>> List<GenPolynomial<Product<C>>> toProductGen(
1878 GenPolynomialRing<Product<C>> pfac, List<GenPolynomial<C>> L) {
1879
1880 List<GenPolynomial<Product<C>>> list = new ArrayList<GenPolynomial<Product<C>>>();
1881 if (L == null || L.size() == 0) {
1882 return list;
1883 }
1884 for (GenPolynomial<C> a : L) {
1885 GenPolynomial<Product<C>> b = toProductGen(pfac, a);
1886 list.add(b);
1887 }
1888 return list;
1889 }
1890
1891
1892 /**
1893 * Product representation.
1894 * @param <C> coefficient type.
1895 * @param pfac polynomial ring factory.
1896 * @param A polynomial to be represented.
1897 * @return Product represenation of A in the polynomial ring pfac.
1898 */
1899 public static <C extends GcdRingElem<C>> GenPolynomial<Product<C>> toProductGen(
1900 GenPolynomialRing<Product<C>> pfac, GenPolynomial<C> A) {
1901
1902 GenPolynomial<Product<C>> P = pfac.getZERO().clone();
1903 if (A == null || A.isZERO()) {
1904 return P;
1905 }
1906 RingFactory<Product<C>> rpfac = pfac.coFac;
1907 ProductRing<C> rfac = (ProductRing<C>) rpfac;
1908 for (Map.Entry<ExpVector, C> y : A.getMap().entrySet()) {
1909 ExpVector e = y.getKey();
1910 C a = y.getValue();
1911 Product<C> p = toProductGen(rfac, a);
1912 if (p != null && !p.isZERO()) {
1913 P.doPutToMap(e, p);
1914 }
1915 }
1916 return P;
1917 }
1918
1919
1920 /**
1921 * Product representation.
1922 * @param <C> coefficient type.
1923 * @param pfac product ring factory.
1924 * @param c coefficient to be represented.
1925 * @return Product represenation of c in the ring pfac.
1926 */
1927 public static <C extends GcdRingElem<C>> Product<C> toProductGen(ProductRing<C> pfac, C c) {
1928
1929 SortedMap<Integer, C> elem = new TreeMap<Integer, C>();
1930 for (int i = 0; i < pfac.length(); i++) {
1931 RingFactory<C> rfac = pfac.getFactory(i);
1932 C u = rfac.copy(c);
1933 if (u != null && !u.isZERO()) {
1934 elem.put(i, u);
1935 }
1936 }
1937 return new Product<C>(pfac, elem);
1938 }
1939
1940
1941 /**
1942 * Product representation.
1943 * @param <C> coefficient type.
1944 * @param pfac product polynomial ring factory.
1945 * @param c coefficient to be used.
1946 * @param e exponent vector.
1947 * @return Product represenation of c X^e in the ring pfac.
1948 */
1949 public static <C extends RingElem<C>> Product<GenPolynomial<C>> toProduct(
1950 ProductRing<GenPolynomial<C>> pfac, C c, ExpVector e) {
1951 SortedMap<Integer, GenPolynomial<C>> elem = new TreeMap<Integer, GenPolynomial<C>>();
1952 for (int i = 0; i < e.length(); i++) {
1953 RingFactory<GenPolynomial<C>> rfac = pfac.getFactory(i);
1954 GenPolynomialRing<C> fac = (GenPolynomialRing<C>) rfac;
1955 //GenPolynomialRing<C> cfac = fac.ring;
1956 long a = e.getVal(i);
1957 GenPolynomial<C> u;
1958 if (a == 0) {
1959 u = fac.getONE();
1960 } else {
1961 u = fac.univariate(0, a);
1962 }
1963 u = u.multiply(c);
1964 elem.put(i, u);
1965 }
1966 return new Product<GenPolynomial<C>>(pfac, elem);
1967 }
1968
1969
1970 /**
1971 * Product representation.
1972 * @param <C> coefficient type.
1973 * @param pfac product polynomial ring factory.
1974 * @param A polynomial.
1975 * @return Product represenation of the terms of A in the ring pfac.
1976 */
1977 public static <C extends RingElem<C>> Product<GenPolynomial<C>> toProduct(
1978 ProductRing<GenPolynomial<C>> pfac, GenPolynomial<C> A) {
1979 Product<GenPolynomial<C>> P = pfac.getZERO();
1980 if (A == null || A.isZERO()) {
1981 return P;
1982 }
1983 for (Map.Entry<ExpVector, C> y : A.getMap().entrySet()) {
1984 ExpVector e = y.getKey();
1985 C a = y.getValue();
1986 Product<GenPolynomial<C>> p = toProduct(pfac, a, e);
1987 P = P.sum(p);
1988 }
1989 return P;
1990 }
1991
1992
1993 /**
1994 * Product representation.
1995 * @param pfac product ring factory.
1996 * @param c coefficient to be represented.
1997 * @return Product represenation of c in the ring pfac.
1998 */
1999 public static Product<ModInteger> toProduct(ProductRing<ModInteger> pfac, BigInteger c) {
2000
2001 SortedMap<Integer, ModInteger> elem = new TreeMap<Integer, ModInteger>();
2002 for (int i = 0; i < pfac.length(); i++) {
2003 RingFactory<ModInteger> rfac = pfac.getFactory(i);
2004 ModIntegerRing fac = (ModIntegerRing) rfac;
2005 ModInteger u = fac.fromInteger(c.getVal());
2006 if (u != null && !u.isZERO()) {
2007 elem.put(i, u);
2008 }
2009 }
2010 return new Product<ModInteger>(pfac, elem);
2011 }
2012
2013
2014 /**
2015 * Product representation.
2016 * @param pfac polynomial ring factory.
2017 * @param A polynomial to be represented.
2018 * @return Product represenation of A in the polynomial ring pfac.
2019 */
2020 public static GenPolynomial<Product<ModInteger>> toProduct(GenPolynomialRing<Product<ModInteger>> pfac,
2021 GenPolynomial<BigInteger> A) {
2022
2023 GenPolynomial<Product<ModInteger>> P = pfac.getZERO().clone();
2024 if (A == null || A.isZERO()) {
2025 return P;
2026 }
2027 RingFactory<Product<ModInteger>> rpfac = pfac.coFac;
2028 ProductRing<ModInteger> fac = (ProductRing<ModInteger>) rpfac;
2029 for (Map.Entry<ExpVector, BigInteger> y : A.getMap().entrySet()) {
2030 ExpVector e = y.getKey();
2031 BigInteger a = y.getValue();
2032 Product<ModInteger> p = toProduct(fac, a);
2033 if (p != null && !p.isZERO()) {
2034 P.doPutToMap(e, p);
2035 }
2036 }
2037 return P;
2038 }
2039
2040
2041 /**
2042 * Product representation.
2043 * @param pfac polynomial ring factory.
2044 * @param L list of polynomials to be represented.
2045 * @return Product represenation of L in the polynomial ring pfac.
2046 */
2047 public static List<GenPolynomial<Product<ModInteger>>> toProduct(
2048 GenPolynomialRing<Product<ModInteger>> pfac, List<GenPolynomial<BigInteger>> L) {
2049
2050 List<GenPolynomial<Product<ModInteger>>> list = new ArrayList<GenPolynomial<Product<ModInteger>>>();
2051 if (L == null || L.size() == 0) {
2052 return list;
2053 }
2054 for (GenPolynomial<BigInteger> a : L) {
2055 GenPolynomial<Product<ModInteger>> b = toProduct(pfac, a);
2056 list.add(b);
2057 }
2058 return list;
2059 }
2060
2061
2062 /**
2063 * Remove all upper variables, which do not occur in polynomial.
2064 * @param p polynomial.
2065 * @return polynomial with removed variables
2066 */
2067 public static <C extends RingElem<C>> GenPolynomial<C> removeUnusedUpperVariables(GenPolynomial<C> p) {
2068 GenPolynomialRing<C> fac = p.ring;
2069 if (fac.nvar <= 1) { // univariate
2070 return p;
2071 }
2072 int[] dep = p.degreeVector().dependencyOnVariables();
2073 if (fac.nvar == dep.length) { // all variables appear
2074 return p;
2075 }
2076 if (dep.length == 0) { // no variables
2077 return p;
2078 }
2079 int l = dep[0]; // higher variable
2080 int r = dep[dep.length - 1]; // lower variable
2081 if (l == 0 /*|| l == fac.nvar-1*/) { // upper variable appears
2082 return p;
2083 }
2084 int n = l;
2085 GenPolynomialRing<C> facr = fac.contract(n);
2086 Map<ExpVector, GenPolynomial<C>> mpr = p.contract(facr);
2087 if (mpr.size() != 1) {
2088 System.out.println("upper ex, l = " + l + ", r = " + r + ", p = " + p + ", fac = "
2089 + fac.toScript());
2090 throw new RuntimeException("this should not happen " + mpr);
2091 }
2092 GenPolynomial<C> pr = mpr.values().iterator().next();
2093 n = fac.nvar - 1 - r;
2094 if (n == 0) {
2095 return pr;
2096 } // else case not implemented
2097 return pr;
2098 }
2099
2100
2101 /**
2102 * Remove all lower variables, which do not occur in polynomial.
2103 * @param p polynomial.
2104 * @return polynomial with removed variables
2105 */
2106 public static <C extends RingElem<C>> GenPolynomial<C> removeUnusedLowerVariables(GenPolynomial<C> p) {
2107 GenPolynomialRing<C> fac = p.ring;
2108 if (fac.nvar <= 1) { // univariate
2109 return p;
2110 }
2111 int[] dep = p.degreeVector().dependencyOnVariables();
2112 if (fac.nvar == dep.length) { // all variables appear
2113 return p;
2114 }
2115 if (dep.length == 0) { // no variables
2116 return p;
2117 }
2118 int l = dep[0]; // higher variable
2119 int r = dep[dep.length - 1]; // lower variable
2120 if (r == fac.nvar - 1) { // lower variable appears
2121 return p;
2122 }
2123 int n = r + 1;
2124 GenPolynomialRing<GenPolynomial<C>> rfac = fac.recursive(n);
2125 GenPolynomial<GenPolynomial<C>> mpr = recursive(rfac, p);
2126 if (mpr.length() != p.length()) {
2127 System.out.println("lower ex, l = " + l + ", r = " + r + ", p = " + p + ", fac = "
2128 + fac.toScript());
2129 throw new RuntimeException("this should not happen " + mpr);
2130 }
2131 RingFactory<C> cf = fac.coFac;
2132 GenPolynomialRing<C> facl = new GenPolynomialRing<C>(cf, rfac);
2133 GenPolynomial<C> pr = facl.getZERO().clone();
2134 for (Monomial<GenPolynomial<C>> m : mpr) {
2135 ExpVector e = m.e;
2136 GenPolynomial<C> a = m.c;
2137 if (!a.isConstant()) {
2138 throw new RuntimeException("this can not happen " + a);
2139 }
2140 C c = a.leadingBaseCoefficient();
2141 pr.doPutToMap(e, c);
2142 }
2143 return pr;
2144 }
2145
2146
2147 /**
2148 * Select polynomial with univariate leading term in variable i.
2149 * @param i variable index.
2150 * @return polynomial with head term in variable i
2151 */
2152 public static <C extends RingElem<C>> GenPolynomial<C> selectWithVariable(List<GenPolynomial<C>> P, int i) {
2153 for (GenPolynomial<C> p : P) {
2154 int[] dep = p.leadingExpVector().dependencyOnVariables();
2155 if (dep.length == 1 && dep[0] == i) {
2156 return p;
2157 }
2158 }
2159 return null; // not found
2160 }
2161
2162 }
2163
2164
2165 /**
2166 * Conversion of distributive to recursive representation.
2167 */
2168 class DistToRec<C extends RingElem<C>> implements
2169 UnaryFunctor<GenPolynomial<C>, GenPolynomial<GenPolynomial<C>>> {
2170
2171
2172 GenPolynomialRing<GenPolynomial<C>> fac;
2173
2174
2175 public DistToRec(GenPolynomialRing<GenPolynomial<C>> fac) {
2176 this.fac = fac;
2177 }
2178
2179
2180 public GenPolynomial<GenPolynomial<C>> eval(GenPolynomial<C> c) {
2181 if (c == null) {
2182 return fac.getZERO();
2183 } else {
2184 return PolyUtil.<C> recursive(fac, c);
2185 }
2186 }
2187 }
2188
2189
2190 /**
2191 * Conversion of recursive to distributive representation.
2192 */
2193 class RecToDist<C extends RingElem<C>> implements
2194 UnaryFunctor<GenPolynomial<GenPolynomial<C>>, GenPolynomial<C>> {
2195
2196
2197 GenPolynomialRing<C> fac;
2198
2199
2200 public RecToDist(GenPolynomialRing<C> fac) {
2201 this.fac = fac;
2202 }
2203
2204
2205 public GenPolynomial<C> eval(GenPolynomial<GenPolynomial<C>> c) {
2206 if (c == null) {
2207 return fac.getZERO();
2208 } else {
2209 return PolyUtil.<C> distribute(fac, c);
2210 }
2211 }
2212 }
2213
2214
2215 /**
2216 * BigRational numerator functor.
2217 */
2218 class RatNumer implements UnaryFunctor<BigRational, BigInteger> {
2219
2220
2221 public BigInteger eval(BigRational c) {
2222 if (c == null) {
2223 return new BigInteger();
2224 } else {
2225 return new BigInteger(c.numerator());
2226 }
2227 }
2228 }
2229
2230
2231 /**
2232 * Conversion of symmetric ModInteger to BigInteger functor.
2233 */
2234 class ModSymToInt<C extends RingElem<C> & Modular> implements UnaryFunctor<C, BigInteger> {
2235
2236
2237 public BigInteger eval(C c) {
2238 if (c == null) {
2239 return new BigInteger();
2240 } else {
2241 return c.getSymmetricInteger();
2242 }
2243 }
2244 }
2245
2246
2247 /**
2248 * Conversion of ModInteger to BigInteger functor.
2249 */
2250 class ModToInt<C extends RingElem<C> & Modular> implements UnaryFunctor<C, BigInteger> {
2251
2252
2253 public BigInteger eval(C c) {
2254 if (c == null) {
2255 return new BigInteger();
2256 } else {
2257 return c.getInteger();
2258 }
2259 }
2260 }
2261
2262
2263 /**
2264 * Conversion of BigRational to BigInteger with division by lcm functor. result
2265 * = num*(lcm/denom).
2266 */
2267 class RatToInt implements UnaryFunctor<BigRational, BigInteger> {
2268
2269
2270 java.math.BigInteger lcm;
2271
2272
2273 public RatToInt(java.math.BigInteger lcm) {
2274 this.lcm = lcm; //.getVal();
2275 }
2276
2277
2278 public BigInteger eval(BigRational c) {
2279 if (c == null) {
2280 return new BigInteger();
2281 } else {
2282 // p = num*(lcm/denom)
2283 java.math.BigInteger b = lcm.divide(c.denominator());
2284 return new BigInteger(c.numerator().multiply(b));
2285 }
2286 }
2287 }
2288
2289
2290 /**
2291 * * Conversion of BigRational to BigInteger. result = (num/gcd)*(lcm/denom).
2292 */
2293 class RatToIntFactor implements UnaryFunctor<BigRational, BigInteger> {
2294
2295
2296 final java.math.BigInteger lcm;
2297
2298
2299 final java.math.BigInteger gcd;
2300
2301
2302 public RatToIntFactor(java.math.BigInteger gcd, java.math.BigInteger lcm) {
2303 this.gcd = gcd;
2304 this.lcm = lcm; // .getVal();
2305 }
2306
2307
2308 public BigInteger eval(BigRational c) {
2309 if (c == null) {
2310 return new BigInteger();
2311 } else {
2312 if (gcd.equals(java.math.BigInteger.ONE)) {
2313 // p = num*(lcm/denom)
2314 java.math.BigInteger b = lcm.divide(c.denominator());
2315 return new BigInteger(c.numerator().multiply(b));
2316 } else {
2317 // p = (num/gcd)*(lcm/denom)
2318 java.math.BigInteger a = c.numerator().divide(gcd);
2319 java.math.BigInteger b = lcm.divide(c.denominator());
2320 return new BigInteger(a.multiply(b));
2321 }
2322 }
2323 }
2324 }
2325
2326
2327 /**
2328 * Conversion of Rational to BigDecimal. result = decimal(r).
2329 */
2330 class RatToDec<C extends Element<C> & Rational> implements UnaryFunctor<C, BigDecimal> {
2331
2332
2333 public BigDecimal eval(C c) {
2334 if (c == null) {
2335 return new BigDecimal();
2336 } else {
2337 return new BigDecimal(c.getRational());
2338 }
2339 }
2340 }
2341
2342
2343 /**
2344 * Conversion of Complex Rational to Complex BigDecimal. result = decimal(r).
2345 */
2346 class CompRatToDec<C extends RingElem<C> & Rational> implements UnaryFunctor<Complex<C>, Complex<BigDecimal>> {
2347
2348
2349 ComplexRing<BigDecimal> ring;
2350
2351
2352 public CompRatToDec(RingFactory<Complex<BigDecimal>> ring) {
2353 this.ring = (ComplexRing<BigDecimal>) ring;
2354 }
2355
2356
2357 public Complex<BigDecimal> eval(Complex<C> c) {
2358 if (c == null) {
2359 return ring.getZERO();
2360 } else {
2361 BigDecimal r = new BigDecimal(c.getRe().getRational());
2362 BigDecimal i = new BigDecimal(c.getIm().getRational());
2363 return new Complex<BigDecimal>(ring, r, i);
2364 }
2365 }
2366 }
2367
2368
2369 /**
2370 * Conversion from BigInteger functor.
2371 */
2372 class FromInteger<D extends RingElem<D>> implements UnaryFunctor<BigInteger, D> {
2373
2374
2375 RingFactory<D> ring;
2376
2377
2378 public FromInteger(RingFactory<D> ring) {
2379 this.ring = ring;
2380 }
2381
2382
2383 public D eval(BigInteger c) {
2384 if (c == null) {
2385 return ring.getZERO();
2386 } else {
2387 return ring.fromInteger(c.getVal());
2388 }
2389 }
2390 }
2391
2392
2393 /**
2394 * Conversion from GenPolynomial<BigInteger> functor.
2395 */
2396 class FromIntegerPoly<D extends RingElem<D>> implements
2397 UnaryFunctor<GenPolynomial<BigInteger>, GenPolynomial<D>> {
2398
2399
2400 GenPolynomialRing<D> ring;
2401
2402
2403 FromInteger<D> fi;
2404
2405
2406 public FromIntegerPoly(GenPolynomialRing<D> ring) {
2407 if (ring == null) {
2408 throw new IllegalArgumentException("ring must not be null");
2409 }
2410 this.ring = ring;
2411 fi = new FromInteger<D>(ring.coFac);
2412 }
2413
2414
2415 public GenPolynomial<D> eval(GenPolynomial<BigInteger> c) {
2416 if (c == null) {
2417 return ring.getZERO();
2418 } else {
2419 return PolyUtil.<BigInteger, D> map(ring, c, fi);
2420 }
2421 }
2422 }
2423
2424
2425 /**
2426 * Conversion from GenPolynomial<BigRational> to GenPolynomial<BigInteger>
2427 * functor.
2428 */
2429 class RatToIntPoly implements UnaryFunctor<GenPolynomial<BigRational>, GenPolynomial<BigInteger>> {
2430
2431
2432 GenPolynomialRing<BigInteger> ring;
2433
2434
2435 public RatToIntPoly(GenPolynomialRing<BigInteger> ring) {
2436 if (ring == null) {
2437 throw new IllegalArgumentException("ring must not be null");
2438 }
2439 this.ring = ring;
2440 }
2441
2442
2443 public GenPolynomial<BigInteger> eval(GenPolynomial<BigRational> c) {
2444 if (c == null) {
2445 return ring.getZERO();
2446 } else {
2447 return PolyUtil.integerFromRationalCoefficients(ring, c);
2448 }
2449 }
2450 }
2451
2452
2453 /**
2454 * Real part functor.
2455 */
2456 class RealPart implements UnaryFunctor<BigComplex, BigRational> {
2457
2458
2459 public BigRational eval(BigComplex c) {
2460 if (c == null) {
2461 return new BigRational();
2462 } else {
2463 return c.getRe();
2464 }
2465 }
2466 }
2467
2468
2469 /**
2470 * Imaginary part functor.
2471 */
2472 class ImagPart implements UnaryFunctor<BigComplex, BigRational> {
2473
2474
2475 public BigRational eval(BigComplex c) {
2476 if (c == null) {
2477 return new BigRational();
2478 } else {
2479 return c.getIm();
2480 }
2481 }
2482 }
2483
2484
2485 /**
2486 * Real part functor.
2487 */
2488 class RealPartComplex<C extends RingElem<C>> implements UnaryFunctor<Complex<C>, C> {
2489
2490
2491 public C eval(Complex<C> c) {
2492 if (c == null) {
2493 return null;
2494 } else {
2495 return c.getRe();
2496 }
2497 }
2498 }
2499
2500
2501 /**
2502 * Imaginary part functor.
2503 */
2504 class ImagPartComplex<C extends RingElem<C>> implements UnaryFunctor<Complex<C>, C> {
2505
2506
2507 public C eval(Complex<C> c) {
2508 if (c == null) {
2509 return null;
2510 } else {
2511 return c.getIm();
2512 }
2513 }
2514 }
2515
2516
2517 /**
2518 * Rational to complex functor.
2519 */
2520 class ToComplex<C extends RingElem<C>> implements UnaryFunctor<C, Complex<C>> {
2521
2522
2523 final protected ComplexRing<C> cfac;
2524
2525
2526 @SuppressWarnings("unchecked")
2527 public ToComplex(RingFactory<Complex<C>> fac) {
2528 if (fac == null) {
2529 throw new IllegalArgumentException("fac must not be null");
2530 }
2531 cfac = (ComplexRing<C>) fac;
2532 }
2533
2534
2535 public Complex<C> eval(C c) {
2536 if (c == null) {
2537 return cfac.getZERO();
2538 } else {
2539 return new Complex<C>(cfac, c);
2540 }
2541 }
2542 }
2543
2544
2545 /**
2546 * Rational to complex functor.
2547 */
2548 class RatToCompl implements UnaryFunctor<BigRational, BigComplex> {
2549
2550
2551 public BigComplex eval(BigRational c) {
2552 if (c == null) {
2553 return new BigComplex();
2554 } else {
2555 return new BigComplex(c);
2556 }
2557 }
2558 }
2559
2560
2561 /**
2562 * Any ring element to generic complex functor.
2563 */
2564 class AnyToComplex<C extends GcdRingElem<C>> implements UnaryFunctor<C, Complex<C>> {
2565
2566
2567 final protected ComplexRing<C> cfac;
2568
2569
2570 public AnyToComplex(ComplexRing<C> fac) {
2571 if (fac == null) {
2572 throw new IllegalArgumentException("fac must not be null");
2573 }
2574 cfac = fac;
2575 }
2576
2577
2578 public AnyToComplex(RingFactory<C> fac) {
2579 this(new ComplexRing<C>(fac));
2580 }
2581
2582
2583 public Complex<C> eval(C a) {
2584 if (a == null || a.isZERO()) { // should not happen
2585 return cfac.getZERO();
2586 } else if (a.isONE()) {
2587 return cfac.getONE();
2588 } else {
2589 return new Complex<C>(cfac, a);
2590 }
2591 }
2592 }
2593
2594
2595 /**
2596 * Algebraic to generic complex functor.
2597 */
2598 class AlgebToCompl<C extends GcdRingElem<C>> implements UnaryFunctor<AlgebraicNumber<C>, Complex<C>> {
2599
2600
2601 final protected ComplexRing<C> cfac;
2602
2603
2604 public AlgebToCompl(ComplexRing<C> fac) {
2605 if (fac == null) {
2606 throw new IllegalArgumentException("fac must not be null");
2607 }
2608 cfac = fac;
2609 }
2610
2611
2612 public Complex<C> eval(AlgebraicNumber<C> a) {
2613 if (a == null || a.isZERO()) { // should not happen
2614 return cfac.getZERO();
2615 } else if (a.isONE()) {
2616 return cfac.getONE();
2617 } else {
2618 GenPolynomial<C> p = a.getVal();
2619 C real = cfac.ring.getZERO();
2620 C imag = cfac.ring.getZERO();
2621 for (Monomial<C> m : p) {
2622 if (m.exponent().getVal(0) == 1L) {
2623 imag = m.coefficient();
2624 } else if (m.exponent().getVal(0) == 0L) {
2625 real = m.coefficient();
2626 } else {
2627 throw new IllegalArgumentException("unexpected monomial " + m);
2628 }
2629 }
2630 //Complex<C> c = new Complex<C>(cfac,real,imag);
2631 return new Complex<C>(cfac, real, imag);
2632 }
2633 }
2634 }
2635
2636
2637 /**
2638 * Ceneric complex to algebraic number functor.
2639 */
2640 class ComplToAlgeb<C extends GcdRingElem<C>> implements UnaryFunctor<Complex<C>, AlgebraicNumber<C>> {
2641
2642
2643 final protected AlgebraicNumberRing<C> afac;
2644
2645
2646 final protected AlgebraicNumber<C> I;
2647
2648
2649 public ComplToAlgeb(AlgebraicNumberRing<C> fac) {
2650 if (fac == null) {
2651 throw new IllegalArgumentException("fac must not be null");
2652 }
2653 afac = fac;
2654 I = afac.getGenerator();
2655 }
2656
2657
2658 public AlgebraicNumber<C> eval(Complex<C> c) {
2659 if (c == null || c.isZERO()) { // should not happen
2660 return afac.getZERO();
2661 } else if (c.isONE()) {
2662 return afac.getONE();
2663 } else if (c.isIMAG()) {
2664 return I;
2665 } else {
2666 return I.multiply(c.getIm()).sum(c.getRe());
2667 }
2668 }
2669 }
2670
2671
2672 /**
2673 * Algebraic to polynomial functor.
2674 */
2675 class AlgToPoly<C extends GcdRingElem<C>> implements UnaryFunctor<AlgebraicNumber<C>, GenPolynomial<C>> {
2676
2677
2678 public GenPolynomial<C> eval(AlgebraicNumber<C> c) {
2679 if (c == null) {
2680 return null;
2681 } else {
2682 return c.val;
2683 }
2684 }
2685 }
2686
2687
2688 /**
2689 * Polynomial to algebriac functor.
2690 */
2691 class PolyToAlg<C extends GcdRingElem<C>> implements UnaryFunctor<GenPolynomial<C>, AlgebraicNumber<C>> {
2692
2693
2694 final protected AlgebraicNumberRing<C> afac;
2695
2696
2697 public PolyToAlg(AlgebraicNumberRing<C> fac) {
2698 if (fac == null) {
2699 throw new IllegalArgumentException("fac must not be null");
2700 }
2701 afac = fac;
2702 }
2703
2704
2705 public AlgebraicNumber<C> eval(GenPolynomial<C> c) {
2706 if (c == null) {
2707 return afac.getZERO();
2708 } else {
2709 return new AlgebraicNumber<C>(afac, c);
2710 }
2711 }
2712 }
2713
2714
2715 /**
2716 * Coefficient to algebriac functor.
2717 */
2718 class CoeffToAlg<C extends GcdRingElem<C>> implements UnaryFunctor<C, AlgebraicNumber<C>> {
2719
2720
2721 final protected AlgebraicNumberRing<C> afac;
2722
2723
2724 final protected GenPolynomial<C> zero;
2725
2726
2727 public CoeffToAlg(AlgebraicNumberRing<C> fac) {
2728 if (fac == null) {
2729 throw new IllegalArgumentException("fac must not be null");
2730 }
2731 afac = fac;
2732 GenPolynomialRing<C> pfac = afac.ring;
2733 zero = pfac.getZERO();
2734 }
2735
2736
2737 public AlgebraicNumber<C> eval(C c) {
2738 if (c == null) {
2739 return afac.getZERO();
2740 } else {
2741 return new AlgebraicNumber<C>(afac, zero.sum(c));
2742 }
2743 }
2744 }
2745
2746
2747 /**
2748 * Coefficient to recursive algebriac functor.
2749 */
2750 class CoeffToRecAlg<C extends GcdRingElem<C>> implements UnaryFunctor<C, AlgebraicNumber<C>> {
2751
2752
2753 final protected List<AlgebraicNumberRing<C>> lfac;
2754
2755
2756 final int depth;
2757
2758
2759 @SuppressWarnings("unchecked")
2760 public CoeffToRecAlg(int depth, AlgebraicNumberRing<C> fac) {
2761 if (fac == null) {
2762 throw new IllegalArgumentException("fac must not be null");
2763 }
2764 AlgebraicNumberRing<C> afac = fac;
2765 this.depth = depth;
2766 lfac = new ArrayList<AlgebraicNumberRing<C>>(depth);
2767 lfac.add(fac);
2768 for (int i = 1; i < depth; i++) {
2769 RingFactory<C> rf = afac.ring.coFac;
2770 if (!(rf instanceof AlgebraicNumberRing)) {
2771 throw new IllegalArgumentException("fac depth to low");
2772 }
2773 afac = (AlgebraicNumberRing<C>) (Object) rf;
2774 lfac.add(afac);
2775 }
2776 }
2777
2778
2779 @SuppressWarnings("unchecked")
2780 public AlgebraicNumber<C> eval(C c) {
2781 if (c == null) {
2782 return lfac.get(0).getZERO();
2783 }
2784 C ac = c;
2785 AlgebraicNumberRing<C> af = lfac.get(lfac.size() - 1);
2786 GenPolynomial<C> zero = af.ring.getZERO();
2787 AlgebraicNumber<C> an = new AlgebraicNumber<C>(af, zero.sum(ac));
2788 for (int i = lfac.size() - 2; i >= 0; i--) {
2789 af = lfac.get(i);
2790 zero = af.ring.getZERO();
2791 ac = (C) (Object) an;
2792 an = new AlgebraicNumber<C>(af, zero.sum(ac));
2793 }
2794 return an;
2795 }
2796 }
2797
2798
2799 /**
2800 * Evaluate main variable functor.
2801 */
2802 class EvalMain<C extends RingElem<C>> implements UnaryFunctor<GenPolynomial<C>, C> {
2803
2804
2805 final RingFactory<C> cfac;
2806
2807
2808 final C a;
2809
2810
2811 public EvalMain(RingFactory<C> cfac, C a) {
2812 this.cfac = cfac;
2813 this.a = a;
2814 }
2815
2816
2817 public C eval(GenPolynomial<C> c) {
2818 if (c == null) {
2819 return cfac.getZERO();
2820 } else {
2821 return PolyUtil.<C> evaluateMain(cfac, c, a);
2822 }
2823 }
2824 }
2825
2826
2827 /**
2828 * Evaluate main variable functor.
2829 */
2830 class EvalMainPol<C extends RingElem<C>> implements UnaryFunctor<GenPolynomial<C>, GenPolynomial<C>> {
2831
2832
2833 final GenPolynomialRing<C> cfac;
2834
2835
2836 final C a;
2837
2838
2839 public EvalMainPol(GenPolynomialRing<C> cfac, C a) {
2840 this.cfac = cfac;
2841 this.a = a;
2842 }
2843
2844
2845 public GenPolynomial<C> eval(GenPolynomial<C> c) {
2846 if (c == null) {
2847 return cfac.getZERO();
2848 } else {
2849 return PolyUtil.<C> evaluateMain(cfac, c, a);
2850 }
2851 }
2852 }