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