001/* 002 * $Id$ 003 */ 004 005package edu.jas.ufd; 006 007 008import java.util.ArrayList; 009import java.util.Collection; 010import java.util.List; 011import java.util.Map; 012import java.util.SortedMap; 013import java.util.TreeMap; 014 015import org.apache.logging.log4j.LogManager; 016import org.apache.logging.log4j.Logger; 017 018import edu.jas.arith.BigInteger; 019import edu.jas.arith.BigRational; 020import edu.jas.poly.AlgebraicNumber; 021import edu.jas.poly.AlgebraicNumberRing; 022import edu.jas.poly.ExpVector; 023import edu.jas.poly.GenExteriorPolynomial; 024import edu.jas.poly.GenExteriorPolynomialRing; 025import edu.jas.poly.GenPolynomial; 026import edu.jas.poly.GenPolynomialRing; 027import edu.jas.poly.IndexFactory; 028import edu.jas.poly.IndexList; 029import edu.jas.poly.PolyUtil; 030import edu.jas.poly.TermOrderByName; 031import edu.jas.ps.TaylorFunction; 032import edu.jas.ps.UnivPowerSeries; 033import edu.jas.ps.UnivPowerSeriesRing; 034import edu.jas.structure.GcdRingElem; 035import edu.jas.structure.NotInvertibleException; 036import edu.jas.structure.Power; 037import edu.jas.structure.RingElem; 038import edu.jas.structure.RingFactory; 039import edu.jas.structure.UnaryFunctor; 040import edu.jas.util.ListUtil; 041 042 043/** 044 * Polynomial ufd utilities. For example conversion between different 045 * representations and Kronecker substitution. 046 * @author Heinz Kredel 047 */ 048 049public class PolyUfdUtil { 050 051 052 private static final Logger logger = LogManager.getLogger(PolyUfdUtil.class); 053 054 055 private static final boolean debug = logger.isDebugEnabled(); 056 057 058 /** 059 * Derivation of a univariate rational function. 060 * @param r rational function 061 * @return dr/dx 062 */ 063 public static <C extends GcdRingElem<C>> Quotient<C> derivative(Quotient<C> r) { 064 if (r == null || r.isZERO()) { 065 return r; 066 } 067 GenPolynomial<C> num = r.num; 068 GenPolynomial<C> den = r.den; 069 GenPolynomial<C> nump = PolyUtil.<C> baseDerivative(num); 070 if (den.isONE()) { 071 return new Quotient<C>(r.ring, nump); 072 } 073 GenPolynomial<C> denp = PolyUtil.<C> baseDerivative(den); 074 075 // (n/d)' = (n' d - n d')/ d**2 076 GenPolynomial<C> n = den.multiply(nump).subtract(num.multiply(denp)); 077 GenPolynomial<C> d = den.multiply(den); 078 Quotient<C> der = new Quotient<C>(r.ring, n, d); 079 //System.out.println("der = " + der); 080 return der; 081 } 082 083 084 /** 085 * Polynomial quotient partial derivative variable r. 086 * @param <C> coefficient type. 087 * @param Q Quotient. 088 * @param r variable for partial deriviate. 089 * @return dq/dx_r = derivative(Q,r). 090 */ 091 public static <C extends GcdRingElem<C>> Quotient<C> derivative(Quotient<C> Q, int r) { 092 if (Q == null || Q.isZERO()) { 093 return Q; 094 } 095 QuotientRing<C> qfac = Q.ring; 096 if (r < 0 || qfac.ring.nvar <= r) { 097 throw new IllegalArgumentException("derivative variable out of bound " + r); 098 } 099 GenPolynomial<C> num = Q.num; 100 GenPolynomial<C> den = Q.den; 101 GenPolynomial<C> nump = PolyUtil.<C> baseDerivative(num, r); 102 if (den.isONE()) { 103 return new Quotient<C>(Q.ring, nump); 104 } 105 GenPolynomial<C> denp = PolyUtil.<C> baseDerivative(den, r); 106 107 // (n/d)' = (n' d - n d')/ d**2 108 GenPolynomial<C> n = den.multiply(nump).subtract(num.multiply(denp)); 109 GenPolynomial<C> d = den.multiply(den); 110 Quotient<C> der = new Quotient<C>(Q.ring, n, d); 111 return der; 112 } 113 114 115 /** 116 * GenExteriorPolynomial over polynomial quotient exterior derivative. 117 * @param <C> coefficient type. 118 * @param P GenExteriorPolynomial<Quotient>. 119 * @return exteriorDerivative(P). 120 */ 121 public static <C extends GcdRingElem<C>> GenExteriorPolynomial<Quotient<C>> exteriorDerivativeQuot( 122 GenExteriorPolynomial<Quotient<C>> P) { 123 if (P == null || P.isZERO()) { 124 return P; 125 } 126 GenExteriorPolynomialRing<Quotient<C>> pfac = P.ring; 127 IndexFactory ifac = pfac.ixfac; 128 int im = ifac.imaxlength; 129 if (im == 0) { 130 return pfac.getZERO(); 131 } 132 //RingFactory<Quotient<C>> rf = pfac.coFac; 133 GenExteriorPolynomial<Quotient<C>> d = pfac.getZERO().copy(); 134 //Map<IndexList, Quotient<C>> dm = d.getMap(); 135 for (Map.Entry<IndexList, Quotient<C>> m : P.getMap().entrySet()) { 136 //if (P.length() == 1) { 137 //Map.Entry<IndexList, C> m = P.leadingMonomial(); 138 Quotient<C> a = m.getValue(); 139 IndexList il = m.getKey(); 140 Quotient<C> b; 141 IndexList bi; 142 for (int i = 1; i <= im; i++) { 143 IndexList di = new IndexList(ifac, new int[] { i }); 144 bi = di.multiply(il); 145 if (bi.signum() == 0) { 146 continue; 147 } 148 b = PolyUfdUtil.<C> derivative(a, i - 1); //a.derivative(); 149 //System.out.println("baseDerivative a = " + a + ", i-1 = " + (i-1) + ", b = " + b); 150 if (b.isZERO()) { 151 continue; 152 } 153 if (bi.signum() < 0) { 154 bi = bi.negate(); 155 b = b.negate(); 156 } 157 d.doPutToMap(bi, b); 158 } 159 } 160 return d; 161 } 162 163 164 /** 165 * Evaluate at main variable. 166 * @param <C> coefficient type. 167 * @param cfac coefficient polynomial ring factory. 168 * @param A polynomial quotient to be evaluated. 169 * @param a value to evaluate at. 170 * @return A( x_1, ..., x_{n-1}, a ). 171 */ 172 public static <C extends GcdRingElem<C>> C evaluateMain(RingFactory<C> cfac, Quotient<C> A, C a) { 173 if (A == null || A.isZERO()) { 174 return cfac.getZERO(); 175 } 176 C num = PolyUtil.<C> evaluateMain(cfac, A.num, a); 177 C den = PolyUtil.<C> evaluateMain(cfac, A.den, a); 178 if (den.isZERO()) { 179 throw new NotInvertibleException("den == 0"); 180 } 181 return num.divide(den); 182 } 183 184 185 /** 186 * Evaluate all variables. 187 * @param <C> coefficient type. 188 * @param cfac coefficient ring factory. 189 * @param A polynomial quotient to be evaluated. 190 * @param a = (a_1, a_2, ..., a_n) a tuple of values to evaluate at. 191 * @return A(a_1, a_2, ..., a_n). 192 */ 193 public static <C extends GcdRingElem<C>> C evaluateAll(RingFactory<C> cfac, Quotient<C> A, List<C> a) { 194 if (A == null || A.isZERO()) { 195 return cfac.getZERO(); 196 } 197 C num = PolyUtil.<C> evaluateAll(cfac, A.num, a); 198 C den = PolyUtil.<C> evaluateAll(cfac, A.den, a); 199 if (den.isZERO()) { 200 throw new NotInvertibleException("den == 0"); 201 } 202 return num.divide(den); 203 } 204 205 206 /** 207 * Pade approximant [m/n] of function f. Computed using Taylor power series 208 * expansion of f. 209 * @see https://en.wikipedia.org/wiki/Pad%C3%A9_approximant 210 * @param upr univariate power series ring. 211 * @param f function. 212 * @param a expansion point. 213 * @param m degree of approximant numerator. 214 * @param n degree of approximant denominator. 215 * @return Pade approximation of f. 216 */ 217 public static <C extends GcdRingElem<C>> Quotient<C> approximantOfPade(final UnivPowerSeriesRing<C> upr, 218 final TaylorFunction<C> f, final C a, int m, int n) { 219 int mn = m + n; 220 GenPolynomialRing<C> pfac = upr.polyRing(); 221 QuotientRing<C> qfac = new QuotientRing<C>(pfac); 222 223 UnivPowerSeries<C> tps = upr.seriesOfTaylor(f, a); 224 int t = mn + 1; 225 if (tps.truncate() != t) { 226 tps.setTruncate(t); 227 //System.out.println("t = " + t + ", default = " + tps.ring.DEFAULT_TRUNCATE); 228 } 229 if (tps.isZERO()) { 230 throw new IllegalArgumentException("Taylor series may not be zero: " + tps); 231 } 232 //System.out.println("tps = " + tps); 233 GenPolynomial<C> Tmn = tps.asPolynomial(); 234 GenPolynomial<C> Xmn1 = pfac.univariate(0, mn + 1); 235 //System.out.println("Tmn = " + Tmn); 236 //System.out.println("Xmn1 = " + Xmn1); 237 238 GenPolynomial<C>[] exg = PolyUfdUtil.<C> agcd(Tmn, Xmn1, n); 239 GenPolynomial<C> p = exg[0]; 240 GenPolynomial<C> q = exg[1]; 241 //System.out.println("a = " + exg[2]); 242 Quotient<C> pa = new Quotient<C>(qfac, p, q); 243 return pa; 244 } 245 246 247 /** 248 * GenPolynomial approximate common divisor. Only for univariate polynomials 249 * over fields. 250 * @param R GenPolynomial. 251 * @param S GenPolynomial. 252 * @param n maximal degree of a. 253 * @return [ agcd(R,S), a ] with a*R + b*S = agcd(R,S) and deg(a) ≤ n. 254 */ 255 @SuppressWarnings("unchecked") 256 public static <C extends GcdRingElem<C>> GenPolynomial<C>[] agcd(GenPolynomial<C> R, GenPolynomial<C> S, 257 int n) { 258 GenPolynomial<C>[] ret = new GenPolynomial[2]; 259 ret[0] = null; 260 ret[1] = null; 261 if (R == null) { 262 return ret; 263 } 264 GenPolynomialRing<C> ring = R.ring; 265 if (R.isZERO()) { 266 ret[0] = S; 267 ret[1] = ring.getZERO(); 268 //ret[2] = ring.getONE(); 269 return ret; 270 } 271 if (S == null || S.isZERO()) { 272 ret[0] = R; 273 ret[1] = ring.getONE(); 274 //ret[2] = ring.getZERO(); 275 return ret; 276 } 277 if (ring.nvar != 1) { 278 throw new IllegalArgumentException("not univariate polynomials" + ring); 279 } 280 if (R.isConstant() && S.isConstant()) { 281 C t = R.leadingBaseCoefficient(); 282 C s = S.leadingBaseCoefficient(); 283 C[] gg = t.egcd(s); 284 //System.out.println("coeff gcd = " + Arrays.toString(gg)); 285 GenPolynomial<C> z = R.ring.getZERO(); 286 ret[0] = z.sum(gg[0]); 287 ret[1] = z.sum(gg[1]); 288 //ret[2] = z.sum(gg[2]); 289 return ret; 290 } 291 GenPolynomial<C>[] qr; 292 GenPolynomial<C> q = R; 293 GenPolynomial<C> r = S; 294 GenPolynomial<C> c1 = ring.getONE().copy(); 295 GenPolynomial<C> d1 = ring.getZERO().copy(); 296 GenPolynomial<C> c2 = ring.getZERO().copy(); 297 GenPolynomial<C> d2 = ring.getONE().copy(); 298 GenPolynomial<C> x1; 299 GenPolynomial<C> x2; 300 GenPolynomial<C> num = ring.getONE(); 301 GenPolynomial<C> den = ring.getONE(); 302 while (!r.isZERO()) { 303 qr = q.quotientRemainder(r); 304 q = qr[0]; 305 x1 = c1.subtract(q.multiply(d1)); 306 x2 = c2.subtract(q.multiply(d2)); 307 c1 = d1; 308 c2 = d2; 309 d1 = x1; 310 d2 = x2; 311 q = r; 312 r = qr[1]; 313 //System.out.println("q = " + q + ", c1 = " + c1); 314 if (c1.degree() <= n) { 315 num = q; 316 den = c1; 317 } else { 318 break; 319 } 320 } 321 // normalize ldcf(q) to 1, i.e. make monic 322 C g = num.leadingBaseCoefficient(); 323 if (g.isUnit()) { 324 C h = g.inverse(); 325 num = num.multiply(h); 326 den = den.multiply(h); 327 c2 = c2.multiply(h); 328 } 329 //System.out.println("num = " + num); 330 //System.out.println("den = " + den); 331 //assert ( ((c1.multiply(R)).sum( c2.multiply(S)).equals(q) )); 332 ret[0] = num; //q; 333 ret[1] = den; //c1; 334 //ret[2] = c2; 335 return ret; 336 } 337 338 339 /** 340 * Factors of Quotient rational function. 341 * @param A rational function to be factored. 342 * @return list of irreducible rational function parts. 343 */ 344 public static <C extends GcdRingElem<C>> SortedMap<Quotient<C>, Long> factors(Quotient<C> A) { 345 SortedMap<Quotient<C>, Long> factors = new TreeMap<Quotient<C>, Long>(); 346 if (A == null || A.isZERO()) { 347 return factors; 348 } 349 if (A.abs().isONE()) { 350 factors.put(A, 1L); 351 return factors; 352 } 353 QuotientRing<C> qfac = A.ring; 354 GenPolynomialRing<C> fac = qfac.ring; 355 FactorAbstract<C> eng = FactorFactory.<C> getImplementation(fac.coFac); 356 GenPolynomial<C> n = A.num; 357 SortedMap<GenPolynomial<C>, Long> numfactors = eng.factors(n); 358 for (Map.Entry<GenPolynomial<C>, Long> me : numfactors.entrySet()) { 359 GenPolynomial<C> f = me.getKey(); 360 Long e = me.getValue(); 361 Quotient<C> q = new Quotient<C>(qfac, f); 362 factors.put(q, e); 363 } 364 GenPolynomial<C> d = A.den; 365 if (d.isONE()) { 366 return factors; 367 } 368 GenPolynomial<C> one = fac.getONE(); 369 SortedMap<GenPolynomial<C>, Long> denfactors = eng.factors(d); 370 for (Map.Entry<GenPolynomial<C>, Long> me : denfactors.entrySet()) { 371 GenPolynomial<C> f = me.getKey(); 372 Long e = me.getValue(); 373 Quotient<C> q = new Quotient<C>(qfac, one, f); 374 factors.put(q, e); 375 } 376 return factors; 377 } 378 379 380 /** 381 * Quotient is (squarefree) factorization. 382 * @param P Quotient. 383 * @param F = [p_1 -> e_1, ..., p_k -> e_k]. 384 * @return true if P = prod_{i=1,...,k} p_i**e_i, else false. 385 */ 386 public static <C extends GcdRingElem<C>> boolean isFactorization(Quotient<C> P, 387 SortedMap<Quotient<C>, Long> F) { 388 if (P == null || F == null) { 389 throw new IllegalArgumentException("P and F may not be null"); 390 } 391 if (P.isZERO() && F.size() == 0) { 392 return true; 393 } 394 Quotient<C> t = P.ring.getONE(); 395 for (Map.Entry<Quotient<C>, Long> me : F.entrySet()) { 396 Quotient<C> f = me.getKey(); 397 Long E = me.getValue(); 398 long e = E.longValue(); 399 Quotient<C> g = f.power(e); 400 t = t.multiply(g); 401 } 402 boolean f = P.equals(t) || P.equals(t.negate()); 403 if (!f) { 404 P = P.monic(); 405 t = t.monic(); 406 f = P.equals(t) || P.equals(t.negate()); 407 if (f) { 408 return f; 409 } 410 logger.info("no factorization(map): F = {}, P = {}, t = {}", F, P, t); 411 } 412 return f; 413 } 414 415 416 /** 417 * Integral polynomial from rational function coefficients. Represent as 418 * polynomial with integral polynomial coefficients by multiplication with 419 * the lcm of the numerators of the rational function coefficients. 420 * @param fac result polynomial factory. 421 * @param A polynomial with rational function coefficients to be converted. 422 * @return polynomial with integral polynomial coefficients. 423 */ 424 public static <C extends GcdRingElem<C>> GenPolynomial<GenPolynomial<C>> integralFromQuotientCoefficients( 425 GenPolynomialRing<GenPolynomial<C>> fac, GenPolynomial<Quotient<C>> A) { 426 GenPolynomial<GenPolynomial<C>> B = fac.getZERO().copy(); 427 if (A == null || A.isZERO()) { 428 return B; 429 } 430 GenPolynomial<C> c = null; 431 GenPolynomial<C> d; 432 GenPolynomial<C> x; 433 GreatestCommonDivisor<C> ufd = new GreatestCommonDivisorSubres<C>(); 434 int s = 0; 435 // lcm of denominators 436 for (Quotient<C> y : A.getMap().values()) { 437 x = y.den; 438 // c = lcm(c,x) 439 if (c == null) { 440 c = x; 441 s = x.signum(); 442 } else { 443 d = ufd.gcd(c, x); 444 c = c.multiply(x.divide(d)); 445 } 446 } 447 if (s < 0) { 448 c = c.negate(); 449 } 450 for (Map.Entry<ExpVector, Quotient<C>> y : A.getMap().entrySet()) { 451 ExpVector e = y.getKey(); 452 Quotient<C> a = y.getValue(); 453 // p = n*(c/d) 454 GenPolynomial<C> b = c.divide(a.den); 455 GenPolynomial<C> p = a.num.multiply(b); 456 //B = B.sum( p, e ); // inefficient 457 B.doPutToMap(e, p); 458 } 459 return B; 460 } 461 462 463 /** 464 * Integral polynomial from rational function coefficients. Represent as 465 * polynomial with integral polynomial coefficients by multiplication with 466 * the lcm of the numerators of the rational function coefficients. 467 * @param fac result polynomial factory. 468 * @param L list of polynomial with rational function coefficients to be 469 * converted. 470 * @return list of polynomials with integral polynomial coefficients. 471 */ 472 public static <C extends GcdRingElem<C>> List<GenPolynomial<GenPolynomial<C>>> integralFromQuotientCoefficients( 473 GenPolynomialRing<GenPolynomial<C>> fac, Collection<GenPolynomial<Quotient<C>>> L) { 474 if (L == null) { 475 return null; 476 } 477 List<GenPolynomial<GenPolynomial<C>>> list = new ArrayList<GenPolynomial<GenPolynomial<C>>>(L.size()); 478 for (GenPolynomial<Quotient<C>> p : L) { 479 list.add(integralFromQuotientCoefficients(fac, p)); 480 } 481 return list; 482 } 483 484 485 /** 486 * Rational function from integral polynomial coefficients. Represent as 487 * polynomial with type Quotient<C> coefficients. 488 * @param fac result polynomial factory. 489 * @param A polynomial with integral polynomial coefficients to be 490 * converted. 491 * @return polynomial with type Quotient<C> coefficients. 492 */ 493 public static <C extends GcdRingElem<C>> GenPolynomial<Quotient<C>> quotientFromIntegralCoefficients( 494 GenPolynomialRing<Quotient<C>> fac, GenPolynomial<GenPolynomial<C>> A) { 495 GenPolynomial<Quotient<C>> B = fac.getZERO().copy(); 496 if (A == null || A.isZERO()) { 497 return B; 498 } 499 RingFactory<Quotient<C>> cfac = fac.coFac; 500 QuotientRing<C> qfac = (QuotientRing<C>) cfac; 501 for (Map.Entry<ExpVector, GenPolynomial<C>> y : A.getMap().entrySet()) { 502 ExpVector e = y.getKey(); 503 GenPolynomial<C> a = y.getValue(); 504 Quotient<C> p = new Quotient<C>(qfac, a); // can not be zero 505 if (!p.isZERO()) { 506 //B = B.sum( p, e ); // inefficient 507 B.doPutToMap(e, p); 508 } 509 } 510 return B; 511 } 512 513 514 /** 515 * Rational function from integral polynomial coefficients. Represent as 516 * polynomial with type Quotient<C> coefficients. 517 * @param fac result polynomial factory. 518 * @param L list of polynomials with integral polynomial coefficients to be 519 * converted. 520 * @return list of polynomials with type Quotient<C> coefficients. 521 */ 522 public static <C extends GcdRingElem<C>> List<GenPolynomial<Quotient<C>>> quotientFromIntegralCoefficients( 523 GenPolynomialRing<Quotient<C>> fac, Collection<GenPolynomial<GenPolynomial<C>>> L) { 524 if (L == null) { 525 return null; 526 } 527 List<GenPolynomial<Quotient<C>>> list = new ArrayList<GenPolynomial<Quotient<C>>>(L.size()); 528 for (GenPolynomial<GenPolynomial<C>> p : L) { 529 list.add(quotientFromIntegralCoefficients(fac, p)); 530 } 531 return list; 532 } 533 534 535 /** 536 * From BigInteger coefficients. Represent as polynomial with type 537 * GenPolynomial<C> coefficients, e.g. ModInteger or BigRational. 538 * @param fac result polynomial factory. 539 * @param A polynomial with GenPolynomial<BigInteger> coefficients to 540 * be converted. 541 * @return polynomial with type GenPolynomial<C> coefficients. 542 */ 543 public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> fromIntegerCoefficients( 544 GenPolynomialRing<GenPolynomial<C>> fac, GenPolynomial<GenPolynomial<BigInteger>> A) { 545 GenPolynomial<GenPolynomial<C>> B = fac.getZERO().copy(); 546 if (A == null || A.isZERO()) { 547 return B; 548 } 549 RingFactory<GenPolynomial<C>> cfac = fac.coFac; 550 GenPolynomialRing<C> rfac = (GenPolynomialRing<C>) cfac; 551 for (Map.Entry<ExpVector, GenPolynomial<BigInteger>> y : A.getMap().entrySet()) { 552 ExpVector e = y.getKey(); 553 GenPolynomial<BigInteger> a = y.getValue(); 554 GenPolynomial<C> p = PolyUtil.<C> fromIntegerCoefficients(rfac, a); 555 if (!p.isZERO()) { 556 //B = B.sum( p, e ); // inefficient 557 B.doPutToMap(e, p); 558 } 559 } 560 return B; 561 } 562 563 564 /** 565 * From BigInteger coefficients. Represent as polynomial with type 566 * GenPolynomial<C> coefficients, e.g. ModInteger or BigRational. 567 * @param fac result polynomial factory. 568 * @param L polynomial list with GenPolynomial<BigInteger> 569 * coefficients to be converted. 570 * @return polynomial list with polynomials with type GenPolynomial<C> 571 * coefficients. 572 */ 573 public static <C extends RingElem<C>> List<GenPolynomial<GenPolynomial<C>>> fromIntegerCoefficients( 574 GenPolynomialRing<GenPolynomial<C>> fac, 575 List<GenPolynomial<GenPolynomial<BigInteger>>> L) { 576 List<GenPolynomial<GenPolynomial<C>>> K = null; 577 if (L == null) { 578 return K; 579 } 580 K = new ArrayList<GenPolynomial<GenPolynomial<C>>>(L.size()); 581 if (L.size() == 0) { 582 return K; 583 } 584 for (GenPolynomial<GenPolynomial<BigInteger>> a : L) { 585 GenPolynomial<GenPolynomial<C>> b = fromIntegerCoefficients(fac, a); 586 K.add(b); 587 } 588 return K; 589 } 590 591 592 //------------------------------ 593 594 595 /** 596 * BigInteger from BigRational coefficients. Represent as polynomial with 597 * type GenPolynomial<BigInteger> coefficients. 598 * @param fac result polynomial factory. 599 * @param A polynomial with GenPolynomial<BigRational> coefficients to 600 * be converted. 601 * @return polynomial with type GenPolynomial<BigInteger> 602 * coefficients. 603 */ 604 public static GenPolynomial<GenPolynomial<BigInteger>> integerFromRationalCoefficients( 605 GenPolynomialRing<GenPolynomial<BigInteger>> fac, 606 GenPolynomial<GenPolynomial<BigRational>> A) { 607 GenPolynomial<GenPolynomial<BigInteger>> B = fac.getZERO().copy(); 608 if (A == null || A.isZERO()) { 609 return B; 610 } 611 java.math.BigInteger gcd = null; 612 java.math.BigInteger lcm = null; 613 int sLCM = 0; 614 int sGCD = 0; 615 // lcm of all denominators 616 for (GenPolynomial<BigRational> av : A.getMap().values()) { 617 for (BigRational y : av.getMap().values()) { 618 java.math.BigInteger numerator = y.numerator(); 619 java.math.BigInteger denominator = y.denominator(); 620 // lcm = lcm(lcm,x) 621 if (lcm == null) { 622 lcm = denominator; 623 sLCM = denominator.signum(); 624 } else { 625 java.math.BigInteger d = lcm.gcd(denominator); 626 lcm = lcm.multiply(denominator.divide(d)); 627 } 628 // gcd = gcd(gcd,x) 629 if (gcd == null) { 630 gcd = numerator; 631 sGCD = numerator.signum(); 632 } else { 633 gcd = gcd.gcd(numerator); 634 } 635 } 636 //System.out.println("gcd = " + gcd + ", lcm = " + lcm); 637 } 638 if (sLCM < 0) { 639 lcm = lcm.negate(); 640 } 641 if (sGCD < 0) { 642 gcd = gcd.negate(); 643 } 644 //System.out.println("gcd** = " + gcd + ", lcm = " + lcm); 645 RingFactory<GenPolynomial<BigInteger>> cfac = fac.coFac; 646 GenPolynomialRing<BigInteger> rfac = (GenPolynomialRing<BigInteger>) cfac; 647 for (Map.Entry<ExpVector, GenPolynomial<BigRational>> y : A.getMap().entrySet()) { 648 ExpVector e = y.getKey(); 649 GenPolynomial<BigRational> a = y.getValue(); 650 // common denominator over all coefficients 651 GenPolynomial<BigInteger> p = PolyUtil.integerFromRationalCoefficients(rfac, gcd, lcm, a); 652 if (!p.isZERO()) { 653 //B = B.sum( p, e ); // inefficient 654 B.doPutToMap(e, p); 655 } 656 } 657 return B; 658 } 659 660 661 /** 662 * BigInteger from BigRational coefficients. Represent as polynomial with 663 * type GenPolynomial<BigInteger> coefficients. 664 * @param fac result polynomial factory. 665 * @param L polynomial list with GenPolynomial<BigRational> 666 * coefficients to be converted. 667 * @return polynomial list with polynomials with type 668 * GenPolynomial<BigInteger> coefficients. 669 */ 670 public static List<GenPolynomial<GenPolynomial<BigInteger>>> integerFromRationalCoefficients( 671 GenPolynomialRing<GenPolynomial<BigInteger>> fac, 672 List<GenPolynomial<GenPolynomial<BigRational>>> L) { 673 List<GenPolynomial<GenPolynomial<BigInteger>>> K = null; 674 if (L == null) { 675 return K; 676 } 677 K = new ArrayList<GenPolynomial<GenPolynomial<BigInteger>>>(L.size()); 678 if (L.isEmpty()) { 679 return K; 680 } 681 for (GenPolynomial<GenPolynomial<BigRational>> a : L) { 682 GenPolynomial<GenPolynomial<BigInteger>> b = integerFromRationalCoefficients(fac, a); 683 K.add(b); 684 } 685 return K; 686 } 687 688 689 /** 690 * Introduce lower variable. Represent as polynomial with type 691 * GenPolynomial<C> coefficients. 692 * @param rfac result polynomial factory. 693 * @param A polynomial to be extended. 694 * @return polynomial with type GenPolynomial<C> coefficients. 695 */ 696 public static <C extends GcdRingElem<C>> GenPolynomial<GenPolynomial<C>> introduceLowerVariable( 697 GenPolynomialRing<GenPolynomial<C>> rfac, GenPolynomial<C> A) { 698 if (A == null || rfac == null) { 699 return null; 700 } 701 GenPolynomial<GenPolynomial<C>> Pc = rfac.getONE().multiply(A); 702 if (Pc.isZERO()) { 703 return Pc; 704 } 705 Pc = PolyUtil.<C> switchVariables(Pc); 706 return Pc; 707 } 708 709 710 /** 711 * From AlgebraicNumber coefficients. Represent as polynomial with type 712 * GenPolynomial<C> coefficients, e.g. ModInteger or BigRational. 713 * @param rfac result polynomial factory. 714 * @param A polynomial with AlgebraicNumber coefficients to be converted. 715 * @param k for (y-k x) substitution. 716 * @return polynomial with type GenPolynomial<C> coefficients. 717 */ 718 public static <C extends GcdRingElem<C>> GenPolynomial<GenPolynomial<C>> substituteFromAlgebraicCoefficients( 719 GenPolynomialRing<GenPolynomial<C>> rfac, GenPolynomial<AlgebraicNumber<C>> A, long k) { 720 if (A == null || rfac == null) { 721 return null; 722 } 723 if (A.isZERO()) { 724 return rfac.getZERO(); 725 } 726 // setup x - k alpha 727 GenPolynomialRing<AlgebraicNumber<C>> apfac = A.ring; 728 GenPolynomial<AlgebraicNumber<C>> x = apfac.univariate(0); 729 AlgebraicNumberRing<C> afac = (AlgebraicNumberRing<C>) A.ring.coFac; 730 AlgebraicNumber<C> alpha = afac.getGenerator(); 731 AlgebraicNumber<C> ka = afac.fromInteger(k); 732 GenPolynomial<AlgebraicNumber<C>> s = x.subtract(ka.multiply(alpha)); // x - k alpha 733 //System.out.println("x - k alpha = " + s); 734 //System.out.println("s.ring = " + s.ring.toScript()); 735 if (debug) { 736 logger.info("x - k alpha: {}", s); 737 } 738 // substitute, convert and switch 739 //System.out.println("Asubs = " + A); 740 GenPolynomial<AlgebraicNumber<C>> B; 741 if (s.ring.nvar <= 1) { 742 B = PolyUtil.<AlgebraicNumber<C>> substituteMain(A, s); 743 } else { 744 B = PolyUtil.<AlgebraicNumber<C>> substituteUnivariateMult(A, s); 745 } 746 //System.out.println("Bsubs = " + B); 747 GenPolynomial<GenPolynomial<C>> Pc = PolyUtil.<C> fromAlgebraicCoefficients(rfac, B); // Q[alpha][x] 748 //System.out.println("Pc[a,x] = " + Pc); 749 Pc = PolyUtil.<C> switchVariables(Pc); // Q[x][alpha] 750 //System.out.println("Pc[x,a] = " + Pc); 751 return Pc; 752 } 753 754 755 /** 756 * Convert to AlgebraicNumber coefficients. Represent as polynomial with 757 * AlgebraicNumber<C> coefficients, C is e.g. ModInteger or BigRational. 758 * @param pfac result polynomial factory. 759 * @param A polynomial with GenPolynomial<BigInteger> coefficients to 760 * be converted. 761 * @param k for (y-k x) substitution. 762 * @return polynomial with AlgebraicNumber<C> coefficients. 763 */ 764 public static <C extends GcdRingElem<C>> GenPolynomial<AlgebraicNumber<C>> substituteConvertToAlgebraicCoefficients( 765 GenPolynomialRing<AlgebraicNumber<C>> pfac, GenPolynomial<C> A, long k) { 766 if (A == null || pfac == null) { 767 return null; 768 } 769 if (A.isZERO()) { 770 return pfac.getZERO(); 771 } 772 // convert to Q(alpha)[x] 773 GenPolynomial<AlgebraicNumber<C>> B = PolyUtil.<C> convertToAlgebraicCoefficients(pfac, A); 774 // setup x .+. k alpha for back substitution 775 GenPolynomial<AlgebraicNumber<C>> x = pfac.univariate(0); 776 AlgebraicNumberRing<C> afac = (AlgebraicNumberRing<C>) pfac.coFac; 777 AlgebraicNumber<C> alpha = afac.getGenerator(); 778 AlgebraicNumber<C> ka = afac.fromInteger(k); 779 GenPolynomial<AlgebraicNumber<C>> s = x.sum(ka.multiply(alpha)); // x + k alpha 780 // substitute 781 //System.out.println("s.ring = " + s.ring.toScript()); 782 GenPolynomial<AlgebraicNumber<C>> N; 783 if (s.ring.nvar <= 1) { 784 N = PolyUtil.<AlgebraicNumber<C>> substituteMain(B, s); 785 } else { 786 N = PolyUtil.<AlgebraicNumber<C>> substituteUnivariateMult(B, s); 787 } 788 return N; 789 } 790 791 792 /** 793 * Norm of a polynomial with AlgebraicNumber coefficients. 794 * @param A uni or multivariate polynomial from 795 * GenPolynomial<AlgebraicNumber<C>>. 796 * @param k for (y - k x) substitution. 797 * @return norm(A) = res_x(A(x,y),m(x)) in GenPolynomialRing<C>. 798 */ 799 public static <C extends GcdRingElem<C>> GenPolynomial<C> norm(GenPolynomial<AlgebraicNumber<C>> A, 800 long k) { 801 if (A == null) { 802 return null; 803 } 804 GenPolynomialRing<AlgebraicNumber<C>> pfac = A.ring; // Q(alpha)[x] 805 //if (pfac.nvar > 1) { 806 // throw new IllegalArgumentException("only for univariate polynomials"); 807 //} 808 AlgebraicNumberRing<C> afac = (AlgebraicNumberRing<C>) pfac.coFac; 809 GenPolynomial<C> agen = afac.modul; 810 GenPolynomialRing<C> cfac = afac.ring; 811 if (A.isZERO()) { 812 return cfac.getZERO(); 813 } 814 AlgebraicNumber<C> ldcf = A.leadingBaseCoefficient(); 815 if (!ldcf.isONE()) { 816 A = A.monic(); 817 } 818 GenPolynomialRing<GenPolynomial<C>> rfac = new GenPolynomialRing<GenPolynomial<C>>(cfac, pfac); 819 //System.out.println("rfac = " + rfac.toScript()); 820 821 // transform minimal polynomial to bi-variate polynomial 822 GenPolynomial<GenPolynomial<C>> Ac = PolyUfdUtil.<C> introduceLowerVariable(rfac, agen); 823 824 // transform to bi-variate polynomial, 825 // switching variable sequence from Q[alpha][x] to Q[X][alpha] 826 GenPolynomial<GenPolynomial<C>> Pc = PolyUfdUtil.<C> substituteFromAlgebraicCoefficients(rfac, A, k); 827 Pc = PolyUtil.<C> monic(Pc); 828 //System.out.println("Pc = " + Pc.toScript() + " :: " + Pc.ring.toScript()); 829 830 GreatestCommonDivisorSubres<C> engine = new GreatestCommonDivisorSubres<C>( /*cfac.coFac*/); 831 // = (GreatestCommonDivisorAbstract<C>)GCDFactory.<C>getImplementation( cfac.coFac ); 832 833 GenPolynomial<GenPolynomial<C>> Rc = engine.recursiveUnivariateResultant(Pc, Ac); 834 //System.out.println("Rc = " + Rc.toScript()); 835 GenPolynomial<C> res = Rc.leadingBaseCoefficient(); 836 res = res.monic(); 837 return res; 838 } 839 840 841 /** 842 * Norm of a polynomial with AlgebraicNumber coefficients. 843 * @param A polynomial from GenPolynomial<AlgebraicNumber<C>>. 844 * @return norm(A) = resultant_x( A(x,y), m(x) ) in K[y]. 845 */ 846 public static <C extends GcdRingElem<C>> GenPolynomial<C> norm(GenPolynomial<AlgebraicNumber<C>> A) { 847 return norm(A, 0L); 848 } 849 850 851 /** 852 * Ensure that the field property is determined. Checks if modul is 853 * irreducible and modifies the algebraic number ring. 854 * @param afac algebraic number ring. 855 */ 856 public static <C extends GcdRingElem<C>> void ensureFieldProperty(AlgebraicNumberRing<C> afac) { 857 if (afac.getField() != -1) { 858 return; 859 } 860 if (!afac.ring.coFac.isField()) { 861 afac.setField(false); 862 return; 863 } 864 Factorization<C> mf = FactorFactory.<C> getImplementation(afac.ring); 865 if (mf.isIrreducible(afac.modul)) { 866 afac.setField(true); 867 } else { 868 afac.setField(false); 869 } 870 } 871 872 873 /** 874 * Construct a random irreducible univariate polynomial of degree d. 875 * @param cfac coefficient polynomial ring. 876 * @param degree of random polynomial. 877 * @return irreducible univariate polynomial. 878 */ 879 public static <C extends GcdRingElem<C>> GenPolynomial<C> randomIrreduciblePolynomial(RingFactory<C> cfac, 880 int degree) { 881 if (!cfac.isField()) { 882 throw new IllegalArgumentException("coefficient ring must be a field " + cfac); 883 } 884 GenPolynomialRing<C> ring = new GenPolynomialRing<C>(cfac, 1, TermOrderByName.INVLEX); 885 return randomIrreduciblePolynomial(ring, degree); 886 } 887 888 889 /** 890 * Construct a random irreducible univariate polynomial of degree d. 891 * @param ring coefficient ring. 892 * @param degree of random polynomial. 893 * @return irreducible univariate polynomial. 894 */ 895 public static <C extends GcdRingElem<C>> GenPolynomial<C> randomIrreduciblePolynomial( 896 GenPolynomialRing<C> ring, int degree) { 897 if (!ring.coFac.isField()) { 898 throw new IllegalArgumentException("coefficient ring must be a field " + ring.coFac); 899 } 900 Factorization<C> eng = FactorFactory.<C> getImplementation(ring); 901 GenPolynomial<C> mod = ring.getZERO(); 902 int k = ring.coFac.characteristic().bitLength(); // log 903 if (k < 3) { 904 k = 7; 905 } 906 int l = degree / 2 + 2; 907 int d = degree + 1; 908 float q = 0.55f; 909 for (;;) { 910 mod = ring.random(k, l, d, q).monic(); 911 if (mod.degree() != degree) { 912 mod = mod.sum(ring.univariate(0, degree)); 913 } 914 if (mod.trailingBaseCoefficient().isZERO()) { 915 mod = mod.sum(ring.getONE()); 916 } 917 //System.out.println("algebriacNumberField: mod = " + mod + ", k = " + k); 918 if (eng.isIrreducible(mod)) { 919 break; 920 } 921 } 922 return mod; 923 } 924 925 926 /** 927 * Construct an algebraic number field of degree d. Uses a random 928 * irreducible polynomial of degree d as modulus of the algebraic number 929 * ring. 930 * @param cfac coefficient ring. 931 * @param degree of random polynomial. 932 * @return algebraic number field. 933 */ 934 public static <C extends GcdRingElem<C>> AlgebraicNumberRing<C> algebraicNumberField(RingFactory<C> cfac, 935 int degree) { 936 GenPolynomial<C> mod = randomIrreduciblePolynomial(cfac, degree); 937 AlgebraicNumberRing<C> afac = new AlgebraicNumberRing<C>(mod, true); 938 return afac; 939 } 940 941 942 /** 943 * Construct an algebraic number field of degree d. Uses a random 944 * irreducible polynomial of degree d as modulus of the algebraic number 945 * ring. 946 * @param ring coefficient polynomial ring. 947 * @param degree of random polynomial. 948 * @return algebraic number field. 949 */ 950 public static <C extends GcdRingElem<C>> AlgebraicNumberRing<C> algebraicNumberField( 951 GenPolynomialRing<C> ring, int degree) { 952 GenPolynomial<C> mod = randomIrreduciblePolynomial(ring, degree); 953 AlgebraicNumberRing<C> afac = new AlgebraicNumberRing<C>(mod, true); 954 return afac; 955 } 956 957 958 /** 959 * Construct Berlekamp Q matrix. 960 * @param A univariate modular polynomial. 961 * @return Q matrix. 962 */ 963 public static <C extends GcdRingElem<C>> ArrayList<ArrayList<C>> constructQmatrix(GenPolynomial<C> A) { 964 ArrayList<ArrayList<C>> Q = new ArrayList<ArrayList<C>>(); 965 if (A == null || A.isZERO()) { 966 return Q; 967 } 968 GenPolynomialRing<C> pfac = A.ring; 969 //System.out.println("pfac = " + pfac.toScript()); 970 java.math.BigInteger q = pfac.coFac.characteristic(); //.longValueExact(); 971 int lq = q.bitLength(); //Power.logarithm(2, q); 972 if (pfac.coFac instanceof AlgebraicNumberRing) { 973 lq = (int) ((AlgebraicNumberRing) pfac.coFac).extensionDegree(); 974 q = q.pow(lq); //Power.power(q, lq); 975 } 976 logger.info("Q matrix for cfac = {}", q); 977 long d = A.degree(0); 978 GenPolynomial<C> x = pfac.univariate(0); 979 //System.out.println("x = " + x.toScript()); 980 GenPolynomial<C> r = pfac.getONE(); 981 //System.out.println("r = " + r.toScript()); 982 List<GenPolynomial<C>> Qp = new ArrayList<GenPolynomial<C>>(); 983 Qp.add(r); 984 GenPolynomial<C> pow = Power.<GenPolynomial<C>> modPositivePower(x, q, A); 985 //System.out.println("pow = " + pow.toScript()); 986 Qp.add(pow); 987 r = pow; 988 for (int i = 2; i < d; i++) { 989 r = r.multiply(pow).remainder(A); 990 Qp.add(r); 991 } 992 //System.out.println("Qp = " + Qp); 993 UnivPowerSeriesRing<C> psfac = new UnivPowerSeriesRing<C>(pfac); 994 //System.out.println("psfac = " + psfac.toScript()); 995 for (GenPolynomial<C> p : Qp) { 996 UnivPowerSeries<C> ps = psfac.fromPolynomial(p); 997 //System.out.println("ps = " + ps.toScript()); 998 ArrayList<C> pr = new ArrayList<C>(); 999 for (int i = 0; i < d; i++) { 1000 C c = ps.coefficient(i); 1001 pr.add(c); 1002 } 1003 Q.add(pr); 1004 } 1005 //System.out.println("Q = " + Q); 1006 return Q; 1007 } 1008 1009 1010 /** 1011 * Polynomial suitable evaluation points. deg(B) = deg(A(x_1,...)) and B is 1012 * also squarefree. 1013 * @param A squarefree polynomial in r variables. 1014 * @return L list of evaluation points and a squarefree univariate 1015 * Polynomial B = A(x_1,L_1,...L_{r-2}). 1016 * @see "sacring.SACPFAC.mi#IPCEVP from SAC2/MAS" 1017 */ 1018 @SuppressWarnings("unchecked") 1019 public static <C extends GcdRingElem<C>> EvalPoints<C> evaluationPoints(GenPolynomial<C> A) { 1020 ArrayList<C> L = new ArrayList<C>(); 1021 if (A == null) { 1022 throw new IllegalArgumentException("A is null"); 1023 } 1024 GenPolynomialRing<C> pfac = A.ring; 1025 if (pfac.nvar <= 1) { 1026 return new EvalPoints<C>(A, A, L); 1027 } 1028 GenPolynomial<C> B = A; 1029 if (A.isZERO() || A.isONE()) { 1030 return new EvalPoints<C>(A, A, L); 1031 } 1032 SquarefreeAbstract<C> sengine = SquarefreeFactory.<C> getImplementation(pfac.coFac); 1033 //long dega = A.degree(0); 1034 GenPolynomialRing<C> rpfac = pfac; 1035 GenPolynomial<C> ape = A; 1036 C one = pfac.coFac.getONE(); 1037 C ll = pfac.coFac.getZERO(); 1038 //logger.info("ape = {}, squarefree: {}", ape, sengine.isSquarefree(ape)); 1039 for (int i = pfac.nvar; i > 1; i--) { 1040 //System.out.println("rpfac = " + rpfac.toScript()); 1041 GenPolynomialRing<GenPolynomial<C>> rfac = rpfac.recursive(1); 1042 GenPolynomialRing<C> cpfac = (GenPolynomialRing) rfac.coFac; 1043 GenPolynomial<GenPolynomial<C>> ap = PolyUtil.<C> recursive(rfac, ape); 1044 //System.out.println("ap = " + ap); 1045 long degd = ape.degree(rpfac.nvar - 2); 1046 boolean unlucky = true; 1047 long s = 0; 1048 C Vi = null; 1049 while (unlucky) { 1050 //System.out.println("ll = " + ll); 1051 Vi = ll; 1052 if (ll.signum() > 0) { 1053 ll = ll.negate(); 1054 } else { 1055 ll = one.subtract(ll); 1056 } 1057 ape = PolyUtil.<C> evaluateMainRecursive(cpfac, ap, Vi); 1058 //logger.info("loop: ap, Vi, ape = {}, {}, {}, squarefree: {}", ap, Vi, ape, sengine.isSquarefree(ape)); 1059 //long degp = ape.degree(0); 1060 long degc = ape.degree(cpfac.nvar - 1); 1061 //System.out.println("degc = " + degc + ", degd = " + degd); 1062 if (degd != degc) { 1063 continue; 1064 } 1065 if (!sengine.isSquarefree(ape)) { 1066 if (s++ > 30l) { 1067 throw new RuntimeException(s + " evaluations not squarefree: " + Vi + ", " + ape 1068 + ", squarefree(A): " + sengine.isSquarefree(A)); 1069 } 1070 //System.out.println("not squarefree"); 1071 continue; 1072 } 1073 //System.out.println("isSquarefree"); 1074 //ap = ape; 1075 unlucky = false; 1076 } 1077 L.add(Vi); 1078 rpfac = cpfac; 1079 } 1080 B = ape; 1081 return new EvalPoints<C>(A, B, L); 1082 } 1083 1084 1085 /** 1086 * Kronecker substitution. Substitute x_i by x**d**(i-1) to construct a 1087 * univariate polynomial. 1088 * @param A polynomial to be converted. 1089 * @return a univariate polynomial. 1090 */ 1091 public static <C extends GcdRingElem<C>> GenPolynomial<C> substituteKronecker(GenPolynomial<C> A) { 1092 if (A == null) { 1093 return A; 1094 } 1095 long d = A.degree() + 1L; 1096 return substituteKronecker(A, d); 1097 } 1098 1099 1100 /** 1101 * Kronecker substitution. Substitute x_i by x**d**(i-1) to construct a 1102 * univariate polynomial. 1103 * @param A polynomial to be converted. 1104 * @return a univariate polynomial. 1105 */ 1106 public static <C extends GcdRingElem<C>> GenPolynomial<C> substituteKronecker(GenPolynomial<C> A, 1107 long d) { 1108 if (A == null) { 1109 return A; 1110 } 1111 RingFactory<C> cfac = A.ring.coFac; 1112 GenPolynomialRing<C> ufac = new GenPolynomialRing<C>(cfac, 1); 1113 GenPolynomial<C> B = ufac.getZERO().copy(); 1114 if (A.isZERO()) { 1115 return B; 1116 } 1117 for (Map.Entry<ExpVector, C> y : A.getMap().entrySet()) { 1118 ExpVector e = y.getKey(); 1119 C a = y.getValue(); 1120 long f = 0L; 1121 long h = 1L; 1122 for (int i = 0; i < e.length(); i++) { 1123 long j = e.getVal(i) * h; 1124 f += j; 1125 h *= d; 1126 } 1127 ExpVector g = ExpVector.create(1, 0, f); 1128 B.doPutToMap(g, a); 1129 } 1130 return B; 1131 } 1132 1133 1134 /** 1135 * Kronecker substitution. Substitute x_i by x**d**(i-1) to construct 1136 * univariate polynomials. 1137 * @param A list of polynomials to be converted. 1138 * @return a list of univariate polynomials. 1139 */ 1140 public static <C extends GcdRingElem<C>> List<GenPolynomial<C>> substituteKronecker( 1141 List<GenPolynomial<C>> A, int d) { 1142 if (A == null || A.get(0) == null) { 1143 return null; 1144 } 1145 return ListUtil.<GenPolynomial<C>, GenPolynomial<C>> map(A, new SubstKronecker<C>(d)); 1146 } 1147 1148 1149 /** 1150 * Kronecker back substitution. Substitute x**d**(i-1) to x_i to construct a 1151 * multivariate polynomial. 1152 * @param A polynomial to be converted. 1153 * @param fac result polynomial factory. 1154 * @return a multivariate polynomial. 1155 */ 1156 public static <C extends GcdRingElem<C>> GenPolynomial<C> backSubstituteKronecker( 1157 GenPolynomialRing<C> fac, GenPolynomial<C> A, long d) { 1158 if (A == null) { 1159 return A; 1160 } 1161 if (fac == null) { 1162 throw new IllegalArgumentException("null factory not allowed "); 1163 } 1164 int n = fac.nvar; 1165 GenPolynomial<C> B = fac.getZERO().copy(); 1166 if (A.isZERO()) { 1167 return B; 1168 } 1169 for (Map.Entry<ExpVector, C> y : A.getMap().entrySet()) { 1170 ExpVector e = y.getKey(); 1171 C a = y.getValue(); 1172 long f = e.getVal(0); 1173 ExpVector g = ExpVector.create(n); 1174 for (int i = 0; i < n; i++) { 1175 long j = f % d; 1176 f /= d; 1177 g = g.subst(i, j); 1178 } 1179 B.doPutToMap(g, a); 1180 } 1181 return B; 1182 } 1183 1184 1185 /** 1186 * Kronecker back substitution. Substitute x**d**(i-1) to x_i to construct 1187 * multivariate polynomials. 1188 * @param A list of polynomials to be converted. 1189 * @param fac result polynomial factory. 1190 * @return a list of multivariate polynomials. 1191 */ 1192 public static <C extends GcdRingElem<C>> List<GenPolynomial<C>> backSubstituteKronecker( 1193 GenPolynomialRing<C> fac, List<GenPolynomial<C>> A, long d) { 1194 return ListUtil.<GenPolynomial<C>, GenPolynomial<C>> map(A, new BackSubstKronecker<C>(fac, d)); 1195 } 1196 1197} 1198 1199 1200/** 1201 * Kronecker substitutuion functor. 1202 */ 1203class SubstKronecker<C extends GcdRingElem<C>> implements UnaryFunctor<GenPolynomial<C>, GenPolynomial<C>> { 1204 1205 1206 final long d; 1207 1208 1209 public SubstKronecker(long d) { 1210 this.d = d; 1211 } 1212 1213 1214 public GenPolynomial<C> eval(GenPolynomial<C> c) { 1215 if (c == null) { 1216 return null; 1217 } 1218 return PolyUfdUtil.<C> substituteKronecker(c, d); 1219 } 1220} 1221 1222 1223/** 1224 * Kronecker back substitutuion functor. 1225 */ 1226class BackSubstKronecker<C extends GcdRingElem<C>> 1227 implements UnaryFunctor<GenPolynomial<C>, GenPolynomial<C>> { 1228 1229 1230 final long d; 1231 1232 1233 final GenPolynomialRing<C> fac; 1234 1235 1236 public BackSubstKronecker(GenPolynomialRing<C> fac, long d) { 1237 this.d = d; 1238 this.fac = fac; 1239 } 1240 1241 1242 public GenPolynomial<C> eval(GenPolynomial<C> c) { 1243 if (c == null) { 1244 return null; 1245 } 1246 return PolyUfdUtil.<C> backSubstituteKronecker(fac, c, d); 1247 } 1248}