001 /*
002 * $Id: PolyUfdUtil.java 3634 2011-05-15 18:48:04Z kredel $
003 */
004
005 package edu.jas.ufd;
006
007
008 import java.util.ArrayList;
009 import java.util.Collection;
010 import java.util.List;
011 import java.util.Map;
012
013 import org.apache.log4j.Logger;
014
015 import edu.jas.arith.BigInteger;
016 import edu.jas.poly.AlgebraicNumber;
017 import edu.jas.poly.AlgebraicNumberRing;
018 import edu.jas.poly.ExpVector;
019 import edu.jas.poly.GenPolynomial;
020 import edu.jas.poly.GenPolynomialRing;
021 import edu.jas.poly.PolyUtil;
022 import edu.jas.structure.GcdRingElem;
023 import edu.jas.structure.RingElem;
024 import edu.jas.structure.RingFactory;
025 import edu.jas.structure.UnaryFunctor;
026 import edu.jas.util.ListUtil;
027
028
029 /**
030 * Polynomial ufd utilities, like conversion between different representations
031 * and Hensel lifting.
032 * @author Heinz Kredel
033 */
034
035 public class PolyUfdUtil {
036
037
038 private static final Logger logger = Logger.getLogger(PolyUfdUtil.class);
039
040
041 private static boolean debug = logger.isDebugEnabled();
042
043
044 /**
045 * Integral polynomial from rational function coefficients. Represent as
046 * polynomial with integral polynomial coefficients by multiplication with
047 * the lcm of the numerators of the rational function coefficients.
048 * @param fac result polynomial factory.
049 * @param A polynomial with rational function coefficients to be converted.
050 * @return polynomial with integral polynomial coefficients.
051 */
052 public static <C extends GcdRingElem<C>> GenPolynomial<GenPolynomial<C>> integralFromQuotientCoefficients(
053 GenPolynomialRing<GenPolynomial<C>> fac, GenPolynomial<Quotient<C>> A) {
054 GenPolynomial<GenPolynomial<C>> B = fac.getZERO().clone();
055 if (A == null || A.isZERO()) {
056 return B;
057 }
058 GenPolynomial<C> c = null;
059 GenPolynomial<C> d;
060 GenPolynomial<C> x;
061 GreatestCommonDivisor<C> ufd = new GreatestCommonDivisorSubres<C>();
062 int s = 0;
063 // lcm of denominators
064 for (Quotient<C> y : A.getMap().values()) {
065 x = y.den;
066 // c = lcm(c,x)
067 if (c == null) {
068 c = x;
069 s = x.signum();
070 } else {
071 d = ufd.gcd(c, x);
072 c = c.multiply(x.divide(d));
073 }
074 }
075 if (s < 0) {
076 c = c.negate();
077 }
078 for (Map.Entry<ExpVector, Quotient<C>> y : A.getMap().entrySet()) {
079 ExpVector e = y.getKey();
080 Quotient<C> a = y.getValue();
081 // p = n*(c/d)
082 GenPolynomial<C> b = c.divide(a.den);
083 GenPolynomial<C> p = a.num.multiply(b);
084 //B = B.sum( p, e ); // inefficient
085 B.doPutToMap(e, p);
086 }
087 return B;
088 }
089
090
091 /**
092 * Integral polynomial from rational function coefficients. Represent as
093 * polynomial with integral polynomial coefficients by multiplication with
094 * the lcm of the numerators of the rational function coefficients.
095 * @param fac result polynomial factory.
096 * @param L list of polynomial with rational function coefficients to be
097 * converted.
098 * @return list of polynomials with integral polynomial coefficients.
099 */
100 public static <C extends GcdRingElem<C>> List<GenPolynomial<GenPolynomial<C>>> integralFromQuotientCoefficients(
101 GenPolynomialRing<GenPolynomial<C>> fac, Collection<GenPolynomial<Quotient<C>>> L) {
102 if (L == null) {
103 return null;
104 }
105 List<GenPolynomial<GenPolynomial<C>>> list = new ArrayList<GenPolynomial<GenPolynomial<C>>>(L.size());
106 for (GenPolynomial<Quotient<C>> p : L) {
107 list.add(integralFromQuotientCoefficients(fac, p));
108 }
109 return list;
110 }
111
112
113 /**
114 * Rational function from integral polynomial coefficients. Represent as
115 * polynomial with type Quotient<C> coefficients.
116 * @param fac result polynomial factory.
117 * @param A polynomial with integral polynomial coefficients to be
118 * converted.
119 * @return polynomial with type Quotient<C> coefficients.
120 */
121 public static <C extends GcdRingElem<C>> GenPolynomial<Quotient<C>> quotientFromIntegralCoefficients(
122 GenPolynomialRing<Quotient<C>> fac, GenPolynomial<GenPolynomial<C>> A) {
123 GenPolynomial<Quotient<C>> B = fac.getZERO().clone();
124 if (A == null || A.isZERO()) {
125 return B;
126 }
127 RingFactory<Quotient<C>> cfac = fac.coFac;
128 QuotientRing<C> qfac = (QuotientRing<C>) cfac;
129 for (Map.Entry<ExpVector, GenPolynomial<C>> y : A.getMap().entrySet()) {
130 ExpVector e = y.getKey();
131 GenPolynomial<C> a = y.getValue();
132 Quotient<C> p = new Quotient<C>(qfac, a); // can not be zero
133 if (p != null && !p.isZERO()) {
134 //B = B.sum( p, e ); // inefficient
135 B.doPutToMap(e, p);
136 }
137 }
138 return B;
139 }
140
141
142 /**
143 * Rational function from integral polynomial coefficients. Represent as
144 * polynomial with type Quotient<C> coefficients.
145 * @param fac result polynomial factory.
146 * @param L list of polynomials with integral polynomial coefficients to be
147 * converted.
148 * @return list of polynomials with type Quotient<C> coefficients.
149 */
150 public static <C extends GcdRingElem<C>> List<GenPolynomial<Quotient<C>>> quotientFromIntegralCoefficients(
151 GenPolynomialRing<Quotient<C>> fac, Collection<GenPolynomial<GenPolynomial<C>>> L) {
152 if (L == null) {
153 return null;
154 }
155 List<GenPolynomial<Quotient<C>>> list = new ArrayList<GenPolynomial<Quotient<C>>>(L.size());
156 for (GenPolynomial<GenPolynomial<C>> p : L) {
157 list.add(quotientFromIntegralCoefficients(fac, p));
158 }
159 return list;
160 }
161
162
163 /**
164 * From BigInteger coefficients. Represent as polynomial with type
165 * GenPolynomial<C> coefficients, e.g. ModInteger or BigRational.
166 * @param fac result polynomial factory.
167 * @param A polynomial with GenPolynomial<BigInteger> coefficients to
168 * be converted.
169 * @return polynomial with type GenPolynomial<C> coefficients.
170 */
171 public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> fromIntegerCoefficients(
172 GenPolynomialRing<GenPolynomial<C>> fac, GenPolynomial<GenPolynomial<BigInteger>> A) {
173 GenPolynomial<GenPolynomial<C>> B = fac.getZERO().clone();
174 if (A == null || A.isZERO()) {
175 return B;
176 }
177 RingFactory<GenPolynomial<C>> cfac = fac.coFac;
178 GenPolynomialRing<C> rfac = (GenPolynomialRing<C>) cfac;
179 for (Map.Entry<ExpVector, GenPolynomial<BigInteger>> y : A.getMap().entrySet()) {
180 ExpVector e = y.getKey();
181 GenPolynomial<BigInteger> a = y.getValue();
182 GenPolynomial<C> p = PolyUtil.<C> fromIntegerCoefficients(rfac, a);
183 if (p != null && !p.isZERO()) {
184 //B = B.sum( p, e ); // inefficient
185 B.doPutToMap(e, p);
186 }
187 }
188 return B;
189 }
190
191
192 /**
193 * From BigInteger coefficients. Represent as polynomial with type
194 * GenPolynomial<C> coefficients, e.g. ModInteger or BigRational.
195 * @param fac result polynomial factory.
196 * @param L polynomial list with GenPolynomial<BigInteger>
197 * coefficients to be converted.
198 * @return polynomial list with polynomials with type GenPolynomial<C>
199 * coefficients.
200 */
201 public static <C extends RingElem<C>> List<GenPolynomial<GenPolynomial<C>>> fromIntegerCoefficients(
202 GenPolynomialRing<GenPolynomial<C>> fac, List<GenPolynomial<GenPolynomial<BigInteger>>> L) {
203 List<GenPolynomial<GenPolynomial<C>>> K = null;
204 if (L == null) {
205 return K;
206 }
207 K = new ArrayList<GenPolynomial<GenPolynomial<C>>>(L.size());
208 if (L.size() == 0) {
209 return K;
210 }
211 for (GenPolynomial<GenPolynomial<BigInteger>> a : L) {
212 GenPolynomial<GenPolynomial<C>> b = fromIntegerCoefficients(fac, a);
213 K.add(b);
214 }
215 return K;
216 }
217
218
219 /**
220 * Introduce lower variable. Represent as polynomial with type
221 * GenPolynomial<C> coefficients.
222 * @param rfac result polynomial factory.
223 * @param A polynomial to be extended.
224 * @return polynomial with type GenPolynomial<C> coefficients.
225 */
226 public static <C extends GcdRingElem<C>> GenPolynomial<GenPolynomial<C>> introduceLowerVariable(
227 GenPolynomialRing<GenPolynomial<C>> rfac, GenPolynomial<C> A) {
228 if (A == null || rfac == null) {
229 return null;
230 }
231 GenPolynomial<GenPolynomial<C>> Pc = rfac.getONE().multiply(A);
232 if (Pc.isZERO()) {
233 return Pc;
234 }
235 Pc = PolyUtil.<C> switchVariables(Pc);
236 return Pc;
237 }
238
239
240 /**
241 * From AlgebraicNumber coefficients. Represent as polynomial with type
242 * GenPolynomial<C> coefficients, e.g. ModInteger or BigRational.
243 * @param rfac result polynomial factory.
244 * @param A polynomial with AlgebraicNumber coefficients to be converted.
245 * @param k for (y-k x) substitution.
246 * @return polynomial with type GenPolynomial<C> coefficients.
247 */
248 public static <C extends GcdRingElem<C>> GenPolynomial<GenPolynomial<C>> substituteFromAlgebraicCoefficients(
249 GenPolynomialRing<GenPolynomial<C>> rfac, GenPolynomial<AlgebraicNumber<C>> A, long k) {
250 if (A == null || rfac == null) {
251 return null;
252 }
253 if (A.isZERO()) {
254 return rfac.getZERO();
255 }
256 // setup x - k alpha
257 GenPolynomialRing<AlgebraicNumber<C>> apfac = A.ring;
258 GenPolynomial<AlgebraicNumber<C>> x = apfac.univariate(0);
259 AlgebraicNumberRing<C> afac = (AlgebraicNumberRing<C>) A.ring.coFac;
260 AlgebraicNumber<C> alpha = afac.getGenerator();
261 AlgebraicNumber<C> ka = afac.fromInteger(k);
262 GenPolynomial<AlgebraicNumber<C>> s = x.subtract(ka.multiply(alpha)); // x - k alpha
263 // substitute, convert and switch
264 GenPolynomial<AlgebraicNumber<C>> B = PolyUtil.<AlgebraicNumber<C>> substituteMain(A, s);
265 GenPolynomial<GenPolynomial<C>> Pc = PolyUtil.<C> fromAlgebraicCoefficients(rfac, B); // Q[alpha][x]
266 Pc = PolyUtil.<C> switchVariables(Pc); // Q[x][alpha]
267 return Pc;
268 }
269
270
271 /**
272 * Convert to AlgebraicNumber coefficients. Represent as polynomial with
273 * AlgebraicNumber<C> coefficients, C is e.g. ModInteger or BigRational.
274 * @param pfac result polynomial factory.
275 * @param A polynomial with GenPolynomial<BigInteger> coefficients to
276 * be converted.
277 * @param k for (y-k x) substitution.
278 * @return polynomial with AlgebraicNumber<C> coefficients.
279 */
280 public static <C extends GcdRingElem<C>> GenPolynomial<AlgebraicNumber<C>> substituteConvertToAlgebraicCoefficients(
281 GenPolynomialRing<AlgebraicNumber<C>> pfac, GenPolynomial<C> A, long k) {
282 if (A == null || pfac == null) {
283 return null;
284 }
285 if (A.isZERO()) {
286 return pfac.getZERO();
287 }
288 // convert to Q(alpha)[x]
289 GenPolynomial<AlgebraicNumber<C>> B = PolyUtil.<C> convertToAlgebraicCoefficients(pfac, A);
290 // setup x .+. k alpha for back substitution
291 GenPolynomial<AlgebraicNumber<C>> x = pfac.univariate(0);
292 AlgebraicNumberRing<C> afac = (AlgebraicNumberRing<C>) pfac.coFac;
293 AlgebraicNumber<C> alpha = afac.getGenerator();
294 AlgebraicNumber<C> ka = afac.fromInteger(k);
295 GenPolynomial<AlgebraicNumber<C>> s = x.sum(ka.multiply(alpha)); // x + k alpha
296 // substitute
297 GenPolynomial<AlgebraicNumber<C>> N = PolyUtil.<AlgebraicNumber<C>> substituteMain(B, s);
298 return N;
299 }
300
301
302 /**
303 * Norm of a polynomial with AlgebraicNumber coefficients.
304 * @param A polynomial from GenPolynomial<AlgebraicNumber<C>>.
305 * @param k for (y - k x) substitution.
306 * @return norm(A) = res_x(A(x,y),m(x)) in GenPolynomialRing<C>.
307 */
308 public static <C extends GcdRingElem<C>> GenPolynomial<C> norm(GenPolynomial<AlgebraicNumber<C>> A, long k) {
309 if (A == null) {
310 return null;
311 }
312 GenPolynomialRing<AlgebraicNumber<C>> pfac = A.ring; // Q(alpha)[x]
313 if (pfac.nvar > 1) {
314 throw new IllegalArgumentException("only for univariate polynomials");
315 }
316 AlgebraicNumberRing<C> afac = (AlgebraicNumberRing<C>) pfac.coFac;
317 GenPolynomial<C> agen = afac.modul;
318 GenPolynomialRing<C> cfac = afac.ring;
319 if (A.isZERO()) {
320 return cfac.getZERO();
321 }
322 AlgebraicNumber<C> ldcf = A.leadingBaseCoefficient();
323 if (!ldcf.isONE()) {
324 A = A.monic();
325 }
326 GenPolynomialRing<GenPolynomial<C>> rfac = new GenPolynomialRing<GenPolynomial<C>>(cfac, pfac);
327
328 // transform minimal polynomial to bi-variate polynomial
329 GenPolynomial<GenPolynomial<C>> Ac = PolyUfdUtil.<C> introduceLowerVariable(rfac, agen);
330 //System.out.println("Ac = " + Ac.toScript());
331
332 // transform to bi-variate polynomial,
333 // switching varaible sequence from Q[alpha][x] to Q[X][alpha]
334 GenPolynomial<GenPolynomial<C>> Pc = PolyUfdUtil.<C> substituteFromAlgebraicCoefficients(rfac, A, k);
335 Pc = PolyUtil.<C> monic(Pc);
336 //System.out.println("Pc = " + Pc.toScript());
337
338 GreatestCommonDivisorSubres<C> engine = new GreatestCommonDivisorSubres<C>( /*cfac.coFac*/);
339 // = (GreatestCommonDivisorAbstract<C>)GCDFactory.<C>getImplementation( cfac.coFac );
340
341 GenPolynomial<GenPolynomial<C>> Rc = engine.recursiveResultant(Pc, Ac);
342 //System.out.println("Rc = " + Rc.toScript());
343 GenPolynomial<C> res = Rc.leadingBaseCoefficient();
344 res = res.monic();
345 return res;
346 }
347
348
349 /**
350 * Norm of a polynomial with AlgebraicNumber coefficients.
351 * @param A polynomial from GenPolynomial<AlgebraicNumber<C>>.
352 * @return norm(A) = resultant_x( A(x,y), m(x) ) in K[y].
353 */
354 public static <C extends GcdRingElem<C>> GenPolynomial<C> norm(GenPolynomial<AlgebraicNumber<C>> A) {
355 return norm(A, 0L);
356 }
357
358
359 /**
360 * Ensure that the field property is determined. Checks if modul is
361 * irreducible and modifies the algebraic number ring.
362 * @param afac algebraic number ring.
363 */
364 public static <C extends GcdRingElem<C>> void ensureFieldProperty(AlgebraicNumberRing<C> afac) {
365 if (afac.getField() != -1) {
366 return;
367 }
368 if (!afac.ring.coFac.isField()) {
369 afac.setField(false);
370 return;
371 }
372 Factorization<C> mf = FactorFactory.<C> getImplementation(afac.ring);
373 if (mf.isIrreducible(afac.modul)) {
374 afac.setField(true);
375 } else {
376 afac.setField(false);
377 }
378 }
379
380
381 /**
382 * Kronecker substitution. Substitute x_i by x**d**(i-1) to construct a
383 * univariate polynomial.
384 * @param A polynomial to be converted.
385 * @return a univariate polynomial.
386 */
387 public static <C extends GcdRingElem<C>> GenPolynomial<C> substituteKronecker(GenPolynomial<C> A) {
388 if (A == null) {
389 return A;
390 }
391 long d = A.degree() + 1L;
392 return substituteKronecker(A, d);
393 }
394
395
396 /**
397 * Kronecker substitution. Substitute x_i by x**d**(i-1) to construct a
398 * univariate polynomial.
399 * @param A polynomial to be converted.
400 * @return a univariate polynomial.
401 */
402 public static <C extends GcdRingElem<C>> GenPolynomial<C> substituteKronecker(GenPolynomial<C> A, long d) {
403 if (A == null) {
404 return A;
405 }
406 RingFactory<C> cfac = A.ring.coFac;
407 GenPolynomialRing<C> ufac = new GenPolynomialRing<C>(cfac, 1);
408 GenPolynomial<C> B = ufac.getZERO().clone();
409 if (A.isZERO()) {
410 return B;
411 }
412 for (Map.Entry<ExpVector, C> y : A.getMap().entrySet()) {
413 ExpVector e = y.getKey();
414 C a = y.getValue();
415 long f = 0L;
416 long h = 1L;
417 for (int i = 0; i < e.length(); i++) {
418 long j = e.getVal(i) * h;
419 f += j;
420 h *= d;
421 }
422 ExpVector g = ExpVector.create(1, 0, f);
423 B.doPutToMap(g, a);
424 }
425 return B;
426 }
427
428
429 /**
430 * Kronecker substitution. Substitute x_i by x**d**(i-1) to construct a
431 * univariate polynomials.
432 * @param A list of polynomials to be converted.
433 * @return a list of univariate polynomials.
434 */
435 public static <C extends GcdRingElem<C>> List<GenPolynomial<C>> substituteKronecker(
436 List<GenPolynomial<C>> A, int d) {
437 if (A == null || A.get(0) == null) {
438 return null;
439 }
440 return ListUtil.<GenPolynomial<C>, GenPolynomial<C>> map(A, new SubstKronecker<C>(d));
441 }
442
443
444 /**
445 * Kronecker back substitution. Substitute x**d**(i-1) to x_i to construct a
446 * multivariate polynomial.
447 * @param A polynomial to be converted.
448 * @param fac result polynomial factory.
449 * @return a multivariate polynomial.
450 */
451 public static <C extends GcdRingElem<C>> GenPolynomial<C> backSubstituteKronecker(
452 GenPolynomialRing<C> fac, GenPolynomial<C> A, long d) {
453 if (A == null) {
454 return A;
455 }
456 if (fac == null) {
457 throw new IllegalArgumentException("null factory not allowed ");
458 }
459 int n = fac.nvar;
460 GenPolynomial<C> B = fac.getZERO().clone();
461 if (A.isZERO()) {
462 return B;
463 }
464 for (Map.Entry<ExpVector, C> y : A.getMap().entrySet()) {
465 ExpVector e = y.getKey();
466 C a = y.getValue();
467 long f = e.getVal(0);
468 ExpVector g = ExpVector.create(n);
469 for (int i = 0; i < n; i++) {
470 long j = f % d;
471 f /= d;
472 g = g.subst(i, j);
473 }
474 B.doPutToMap(g, a);
475 }
476 return B;
477 }
478
479
480 /**
481 * Kronecker back substitution. Substitute x**d**(i-1) to x_i to construct a
482 * multivariate polynomials.
483 * @param A list of polynomials to be converted.
484 * @param fac result polynomial factory.
485 * @return a list of multivariate polynomials.
486 */
487 public static <C extends GcdRingElem<C>> List<GenPolynomial<C>> backSubstituteKronecker(
488 GenPolynomialRing<C> fac, List<GenPolynomial<C>> A, long d) {
489 return ListUtil.<GenPolynomial<C>, GenPolynomial<C>> map(A, new BackSubstKronecker<C>(fac, d));
490 }
491
492 }
493
494
495 /**
496 * Kronecker substitutuion functor.
497 */
498 class SubstKronecker<C extends GcdRingElem<C>> implements UnaryFunctor<GenPolynomial<C>, GenPolynomial<C>> {
499
500
501 final long d;
502
503
504 public SubstKronecker(long d) {
505 this.d = d;
506 }
507
508
509 public GenPolynomial<C> eval(GenPolynomial<C> c) {
510 if (c == null) {
511 return null;
512 } else {
513 return PolyUfdUtil.<C> substituteKronecker(c, d);
514 }
515 }
516 }
517
518
519 /**
520 * Kronecker back substitutuion functor.
521 */
522 class BackSubstKronecker<C extends GcdRingElem<C>> implements
523 UnaryFunctor<GenPolynomial<C>, GenPolynomial<C>> {
524
525
526 final long d;
527
528
529 final GenPolynomialRing<C> fac;
530
531
532 public BackSubstKronecker(GenPolynomialRing<C> fac, long d) {
533 this.d = d;
534 this.fac = fac;
535 }
536
537
538 public GenPolynomial<C> eval(GenPolynomial<C> c) {
539 if (c == null) {
540 return null;
541 } else {
542 return PolyUfdUtil.<C> backSubstituteKronecker(fac, c, d);
543 }
544 }
545 }