001/* 002 * $Id: Examples.java 4057 2012-07-26 20:35:44Z kredel $ 003 */ 004 005package edu.jas.poly; 006 007 008import java.util.ArrayList; 009import java.util.List; 010 011import edu.jas.arith.BigInteger; 012import edu.jas.arith.BigRational; 013import edu.jas.arith.ModInteger; 014import edu.jas.arith.ModIntegerRing; 015 016 017/** 018 * Examples for polynomials usage. 019 * @author Heinz Kredel. 020 */ 021 022public class Examples { 023 024 025 /** 026 * main. 027 */ 028 public static void main(String[] args) { 029 //example0(); 030 /* 031 example1(); 032 example2(); 033 example3(); 034 example4(); 035 example5(); 036 */ 037 //example6(); 038 example7(); 039 example7(); 040 //example8(); 041 //example9(); 042 //example10(); 043 //example11(); 044 //example12(); 045 } 046 047 048 /** 049 * example0. for PPPJ 2006. 050 */ 051 public static void example0() { 052 BigInteger z = new BigInteger(); 053 054 TermOrder to = new TermOrder(); 055 String[] vars = new String[] { "x1", "x2", "x3" }; 056 GenPolynomialRing<BigInteger> ring; 057 ring = new GenPolynomialRing<BigInteger>(z, 3, to, vars); 058 System.out.println("ring = " + ring); 059 060 GenPolynomial<BigInteger> pol; 061 pol = ring.parse("3 x1^2 x3^4 + 7 x2^5 - 61"); 062 System.out.println("pol = " + pol); 063 System.out.println("pol = " + pol.toString(ring.getVars())); 064 065 GenPolynomial<BigInteger> one; 066 one = ring.parse("1"); 067 System.out.println("one = " + one); 068 System.out.println("one = " + one.toString(ring.getVars())); 069 070 GenPolynomial<BigInteger> p; 071 p = pol.subtract(pol); 072 System.out.println("p = " + p); 073 System.out.println("p = " + p.toString(ring.getVars())); 074 075 p = pol.multiply(pol); 076 System.out.println("p = " + p); 077 System.out.println("p = " + p.toString(ring.getVars())); 078 } 079 080 081 /** 082 * example1. random polynomial with rational coefficients. Q[x_1,...x_7] 083 */ 084 public static void example1() { 085 System.out.println("\n\n example 1"); 086 087 BigRational cfac = new BigRational(); 088 System.out.println("cfac = " + cfac); 089 GenPolynomialRing<BigRational> fac; 090 fac = new GenPolynomialRing<BigRational>(cfac, 7); 091 //System.out.println("fac = " + fac); 092 System.out.println("fac = " + fac); 093 094 GenPolynomial<BigRational> a = fac.random(10); 095 System.out.println("a = " + a); 096 } 097 098 099 /** 100 * example2. random polynomial with coefficients of rational polynomials. 101 * Q[x_1,...x_7][y_1,...,y_3] 102 */ 103 public static void example2() { 104 System.out.println("\n\n example 2"); 105 106 BigRational cfac = new BigRational(); 107 System.out.println("cfac = " + cfac); 108 GenPolynomialRing<BigRational> fac; 109 fac = new GenPolynomialRing<BigRational>(cfac, 7); 110 System.out.println("fac = " + fac); 111 112 GenPolynomialRing<GenPolynomial<BigRational>> gfac; 113 gfac = new GenPolynomialRing<GenPolynomial<BigRational>>(fac, 3); 114 System.out.println("gfac = " + gfac); 115 116 GenPolynomial<GenPolynomial<BigRational>> a = gfac.random(10); 117 System.out.println("a = " + a); 118 } 119 120 121 /** 122 * example3. random rational algebraic number. Q(alpha) 123 */ 124 public static void example3() { 125 System.out.println("\n\n example 3"); 126 127 BigRational cfac = new BigRational(); 128 System.out.println("cfac = " + cfac); 129 130 GenPolynomialRing<BigRational> mfac; 131 mfac = new GenPolynomialRing<BigRational>(cfac, 1); 132 System.out.println("mfac = " + mfac); 133 134 GenPolynomial<BigRational> modul = mfac.random(8).monic(); 135 // assume !mo.isUnit() 136 System.out.println("modul = " + modul); 137 138 AlgebraicNumberRing<BigRational> fac; 139 fac = new AlgebraicNumberRing<BigRational>(modul); 140 System.out.println("fac = " + fac); 141 142 AlgebraicNumber<BigRational> a = fac.random(15); 143 System.out.println("a = " + a); 144 } 145 146 147 protected static long getPrime() { 148 long prime = 2; //2^60-93; // 2^30-35; //19; knuth (2,390) 149 for (int i = 1; i < 60; i++) { 150 prime *= 2; 151 } 152 prime -= 93; 153 //System.out.println("prime = " + prime); 154 return prime; 155 } 156 157 158 /** 159 * example4. random modular algebraic number. Z_p(alpha) 160 */ 161 public static void example4() { 162 System.out.println("\n\n example 4"); 163 164 long prime = getPrime(); 165 ModIntegerRing cfac = new ModIntegerRing(prime); 166 System.out.println("cfac = " + cfac); 167 168 GenPolynomialRing<ModInteger> mfac; 169 mfac = new GenPolynomialRing<ModInteger>(cfac, 1); 170 System.out.println("mfac = " + mfac); 171 172 GenPolynomial<ModInteger> modul = mfac.random(8).monic(); 173 // assume !modul.isUnit() 174 System.out.println("modul = " + modul); 175 176 AlgebraicNumberRing<ModInteger> fac; 177 fac = new AlgebraicNumberRing<ModInteger>(modul); 178 System.out.println("fac = " + fac); 179 180 AlgebraicNumber<ModInteger> a = fac.random(12); 181 System.out.println("a = " + a); 182 } 183 184 185 /** 186 * example5. random solvable polynomial with rational coefficients. 187 * Q{x_1,...x_6, {x_2 * x_1 = x_1 x_2 +1, ...} } 188 */ 189 public static void example5() { 190 System.out.println("\n\n example 5"); 191 192 BigRational cfac = new BigRational(); 193 System.out.println("cfac = " + cfac); 194 GenSolvablePolynomialRing<BigRational> sfac; 195 sfac = new GenSolvablePolynomialRing<BigRational>(cfac, 6); 196 //System.out.println("sfac = " + sfac); 197 198 WeylRelations<BigRational> wl = new WeylRelations<BigRational>(sfac); 199 wl.generate(); 200 System.out.println("sfac = " + sfac); 201 202 GenSolvablePolynomial<BigRational> a = sfac.random(5); 203 System.out.println("a = " + a); 204 System.out.println("a = " + a.toString(sfac.vars)); 205 206 GenSolvablePolynomial<BigRational> b = a.multiply(a); 207 System.out.println("b = " + b); 208 System.out.println("b = " + b.toString(sfac.vars)); 209 210 System.out.println("sfac = " + sfac); 211 } 212 213 214 /** 215 * example6. Fateman benchmark: p = (x+y+z)^20; q = p * (p+1) Z[z,y,x] 216 */ 217 public static void example6() { 218 System.out.println("\n\n example 6"); 219 220 BigInteger cfac = new BigInteger(); 221 System.out.println("cfac = " + cfac); 222 223 TermOrder to = new TermOrder(TermOrder.INVLEX); 224 System.out.println("to = " + to); 225 226 GenPolynomialRing<BigInteger> fac; 227 fac = new GenPolynomialRing<BigInteger>(cfac, 3, to); 228 System.out.println("fac = " + fac); 229 fac.setVars(new String[] { "z", "y", "x" }); 230 System.out.println("fac = " + fac); 231 232 GenPolynomial<BigInteger> x = fac.univariate(0); 233 GenPolynomial<BigInteger> y = fac.univariate(1); 234 GenPolynomial<BigInteger> z = fac.univariate(2); 235 236 System.out.println("x = " + x); 237 System.out.println("x = " + x.toString(fac.vars)); 238 System.out.println("y = " + y); 239 System.out.println("y = " + y.toString(fac.vars)); 240 System.out.println("z = " + z); 241 System.out.println("z = " + z.toString(fac.vars)); 242 243 GenPolynomial<BigInteger> p = x.sum(y).sum(z).sum(fac.getONE()); 244 //BigInteger f = cfac.fromInteger(10000000001L); 245 // p = p.multiply( f ); 246 System.out.println("p = " + p); 247 System.out.println("p = " + p.toString(fac.vars)); 248 249 GenPolynomial<BigInteger> q = p; 250 for (int i = 1; i < 20; i++) { 251 q = q.multiply(p); 252 } 253 //System.out.println("q = " + q.toString( fac.vars ) ); 254 System.out.println("q = " + q.length()); 255 256 GenPolynomial<BigInteger> q1 = q.sum(fac.getONE()); 257 258 GenPolynomial<BigInteger> q2; 259 long t = System.currentTimeMillis(); 260 q2 = q.multiply(q1); 261 t = System.currentTimeMillis() - t; 262 263 System.out.println("q2 = " + q2.length()); 264 System.out.println("time = " + t + " ms"); 265 } 266 267 268 /** 269 * example7. Fateman benchmark: p = (x+y+z)^20; q = p * (p+1) Q[z,y,x] 270 */ 271 public static void example7() { 272 System.out.println("\n\n example 7"); 273 274 BigRational cfac = new BigRational(); 275 System.out.println("cfac = " + cfac); 276 277 TermOrder to = new TermOrder(TermOrder.INVLEX); 278 System.out.println("to = " + to); 279 280 GenPolynomialRing<BigRational> fac; 281 fac = new GenPolynomialRing<BigRational>(cfac, 3, to); 282 System.out.println("fac = " + fac); 283 fac.setVars(new String[] { "z", "y", "x" }); 284 System.out.println("fac = " + fac); 285 286 long mi = 1L; 287 //long mi = Integer.MAX_VALUE; 288 GenPolynomial<BigRational> x = fac.univariate(0, mi); 289 GenPolynomial<BigRational> y = fac.univariate(1, mi); 290 GenPolynomial<BigRational> z = fac.univariate(2, mi); 291 292 // System.out.println("x = " + x); 293 System.out.println("x = " + x.toString(fac.vars)); 294 // System.out.println("y = " + y); 295 System.out.println("y = " + y.toString(fac.vars)); 296 // System.out.println("z = " + z); 297 System.out.println("z = " + z.toString(fac.vars)); 298 299 GenPolynomial<BigRational> p = x.sum(y).sum(z).sum(fac.getONE()); 300 //BigRational f = cfac.fromInteger(10000000001L); 301 // f = f.multiply( f ); 302 //p = p.multiply( f ); 303 // System.out.println("p = " + p); 304 System.out.println("p = " + p.toString(fac.vars)); 305 306 int mpow = 20; 307 System.out.println("mpow = " + mpow); 308 GenPolynomial<BigRational> q = p; 309 for (int i = 1; i < mpow; i++) { 310 q = q.multiply(p); 311 } 312 //System.out.println("q = " + q.toString( fac.vars ) ); 313 System.out.println("len(q) = " + q.length()); 314 System.out.println("deg(q) = " + q.degree()); 315 316 GenPolynomial<BigRational> q1 = q.sum(fac.getONE()); 317 318 GenPolynomial<BigRational> q2; 319 long t = System.currentTimeMillis(); 320 q2 = q.multiply(q1); 321 t = System.currentTimeMillis() - t; 322 323 System.out.println("len(q2) = " + q2.length()); 324 System.out.println("deg(q2) = " + q2.degree()); 325 System.out.println("LeadEV(q2) = " + q2.leadingExpVector()); 326 System.out.println("time = " + t + " ms"); 327 } 328 329 330 /** 331 * example8. Chebyshev polynomials 332 * 333 * T(0) = 1 T(1) = x T(n) = 2x * T(n-1) - T(n-2) 334 */ 335 public static void example8() { 336 int m = 10; 337 BigInteger fac = new BigInteger(); 338 String[] var = new String[] { "x" }; 339 340 GenPolynomialRing<BigInteger> ring = new GenPolynomialRing<BigInteger>(fac, 1, var); 341 342 List<GenPolynomial<BigInteger>> T = new ArrayList<GenPolynomial<BigInteger>>(m); 343 344 GenPolynomial<BigInteger> t, one, x, x2, x2b; 345 346 one = ring.getONE(); 347 x = ring.univariate(0); 348 //x2 = ring.parse("2 x"); 349 //x2a = x.multiply( fac.fromInteger(2) ); 350 x2b = x.multiply(new BigInteger(2)); 351 x2 = x2b; 352 353 T.add(one); 354 T.add(x); 355 for (int n = 2; n < m; n++) { 356 t = x2.multiply(T.get(n - 1)).subtract(T.get(n - 2)); 357 T.add(t); 358 } 359 for (int n = 0 /*m-2*/; n < m; n++) { 360 System.out.println("T[" + n + "] = " + T.get(n)); //.toString(var) ); 361 } 362 } 363 364 365 /** 366 * example9. Legendre polynomials 367 * 368 * P(0) = 1 P(1) = x P(n) = 1/n [ (2n-1) * x * P(n-1) - (n-1) * P(n-2) ] 369 */ 370 // P(n+1) = 1/(n+1) [ (2n+1) * x * P(n) - n * P(n-1) ] 371 public static void example9() { 372 int n = 10; 373 374 BigRational fac = new BigRational(); 375 String[] var = new String[] { "x" }; 376 377 GenPolynomialRing<BigRational> ring = new GenPolynomialRing<BigRational>(fac, 1, var); 378 379 List<GenPolynomial<BigRational>> P = new ArrayList<GenPolynomial<BigRational>>(n); 380 381 GenPolynomial<BigRational> t, one, x, xc; 382 BigRational n21, nn; 383 384 one = ring.getONE(); 385 x = ring.univariate(0); 386 387 P.add(one); 388 P.add(x); 389 for (int i = 2; i < n; i++) { 390 n21 = new BigRational(2 * i - 1); 391 xc = x.multiply(n21); 392 t = xc.multiply(P.get(i - 1)); 393 nn = new BigRational(i - 1); 394 xc = P.get(i - 2).multiply(nn); 395 t = t.subtract(xc); 396 nn = new BigRational(1, i); 397 t = t.multiply(nn); 398 P.add(t); 399 } 400 for (int i = 0; i < n; i++) { 401 System.out.println("P[" + i + "] = " + P.get(i).toString(var)); 402 System.out.println(); 403 } 404 } 405 406 407 /** 408 * example10. Hermite polynomials 409 * 410 * H(0) = 1 H(1) = 2 x H(n) = 2 * x * H(n-1) - 2 * (n-1) * H(n-2) 411 */ 412 // H(n+1) = 2 * x * H(n) - 2 * n * H(n-1) 413 public static void example10() { 414 int n = 100; 415 416 BigInteger fac = new BigInteger(); 417 String[] var = new String[] { "x" }; 418 419 GenPolynomialRing<BigInteger> ring = new GenPolynomialRing<BigInteger>(fac, 1, var); 420 421 List<GenPolynomial<BigInteger>> H = new ArrayList<GenPolynomial<BigInteger>>(n); 422 423 GenPolynomial<BigInteger> t, one, x2, xc, x; 424 BigInteger n2, nn; 425 426 one = ring.getONE(); 427 x = ring.univariate(0); 428 n2 = new BigInteger(2); 429 x2 = x.multiply(n2); 430 H.add(one); 431 H.add(x2); 432 for (int i = 2; i < n; i++) { 433 t = x2.multiply(H.get(i - 1)); 434 nn = new BigInteger(2 * (i - 1)); 435 xc = H.get(i - 2).multiply(nn); 436 t = t.subtract(xc); 437 H.add(t); 438 } 439 for (int i = n - 1; i < n; i++) { 440 System.out.println("H[" + i + "] = " + H.get(i).toString(var)); 441 System.out.println(); 442 } 443 } 444 445 446 /** 447 * example11. degree matrix; 448 * 449 */ 450 public static void example11() { 451 int n = 50; 452 BigRational fac = new BigRational(); 453 GenPolynomialRing<BigRational> ring = new GenPolynomialRing<BigRational>(fac, n); 454 System.out.println("ring = " + ring + "\n"); 455 456 GenPolynomial<BigRational> p = ring.random(5, 3, 6, 0.5f); 457 System.out.println("p = " + p + "\n"); 458 459 List<GenPolynomial<BigInteger>> dem = TermOrderOptimization.<BigRational> degreeMatrix(p); 460 461 System.out.println("dem = " + dem + "\n"); 462 463 List<GenPolynomial<BigRational>> polys = new ArrayList<GenPolynomial<BigRational>>(); 464 polys.add(p); 465 for (int i = 0; i < 5; i++) { 466 polys.add(ring.random(5, 3, 6, 0.1f)); 467 } 468 System.out.println("polys = " + polys + "\n"); 469 470 dem = TermOrderOptimization.<BigRational> degreeMatrix(polys); 471 System.out.println("dem = " + dem + "\n"); 472 473 List<Integer> perm; 474 perm = TermOrderOptimization.optimalPermutation(dem); 475 System.out.println("perm = " + perm + "\n"); 476 477 List<GenPolynomial<BigInteger>> pdem; 478 pdem = TermOrderOptimization.<GenPolynomial<BigInteger>> listPermutation(perm, dem); 479 System.out.println("pdem = " + pdem + "\n"); 480 481 GenPolynomialRing<BigRational> pring; 482 pring = TermOrderOptimization.<BigRational> permutation(perm, ring); 483 System.out.println("ring = " + ring); 484 System.out.println("pring = " + pring + "\n"); 485 486 List<GenPolynomial<BigRational>> ppolys; 487 ppolys = TermOrderOptimization.<BigRational> permutation(perm, pring, polys); 488 System.out.println("ppolys = " + ppolys + "\n"); 489 490 dem = TermOrderOptimization.<BigRational> degreeMatrix(ppolys); 491 //System.out.println("pdem = " + dem + "\n"); 492 493 perm = TermOrderOptimization.optimalPermutation(dem); 494 //System.out.println("pperm = " + perm + "\n"); 495 int i = 0; 496 for (Integer j : perm) { 497 if (i != (int) j) { 498 System.out.println("error = " + i + " != " + j + "\n"); 499 } 500 i++; 501 } 502 503 OptimizedPolynomialList<BigRational> op; 504 op = TermOrderOptimization.<BigRational> optimizeTermOrder(ring, polys); 505 System.out.println("op:\n" + op); 506 if (!op.equals(new PolynomialList<BigRational>(pring, ppolys))) { 507 System.out.println("error = " + "\n" + op); 508 } 509 } 510 511 512 /** 513 * example12. type games. 514 */ 515 public static void example12() { 516 System.out.println("\n\n example 12"); 517 518 BigRational t1 = new BigRational(); 519 System.out.println("t1 = " + t1); 520 521 BigInteger t2 = new BigInteger(); 522 System.out.println("t2 = " + t2); 523 524 System.out.println("t1.isAssignableFrom(t2) = " + t1.getClass().isAssignableFrom(t2.getClass())); 525 System.out.println("t2.isAssignableFrom(t1) = " + t2.getClass().isAssignableFrom(t1.getClass())); 526 527 GenPolynomialRing<BigInteger> t3 = new GenPolynomialRing<BigInteger>(t2, 3); 528 System.out.println("t3 = " + t3); 529 530 GenSolvablePolynomialRing<BigInteger> t4 = new GenSolvablePolynomialRing<BigInteger>(t2, 3); 531 System.out.println("t4 = " + t4); 532 533 System.out.println("t3.isAssignableFrom(t4) = " + t3.getClass().isAssignableFrom(t4.getClass())); 534 System.out.println("t4.isAssignableFrom(t3) = " + t4.getClass().isAssignableFrom(t3.getClass())); 535 536 537 GenPolynomialRing<BigRational> t5 = new GenPolynomialRing<BigRational>(t1, 3); 538 System.out.println("t5 = " + t5); 539 540 System.out.println("t3.isAssignableFrom(t5) = " + t3.getClass().isAssignableFrom(t5.getClass())); 541 System.out.println("t5.isAssignableFrom(t3) = " + t5.getClass().isAssignableFrom(t3.getClass())); 542 } 543 544}