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