001/* 002 * $Id: Examples.java 3879 2012-02-05 16:51:04Z kredel $ 003 */ 004 005package edu.jas.application; 006 007 008import java.io.IOException; 009import java.io.Reader; 010import java.io.StringReader; 011import java.util.ArrayList; 012import java.util.List; 013 014import org.apache.log4j.BasicConfigurator; 015 016import edu.jas.arith.BigDecimal; 017import edu.jas.arith.BigInteger; 018import edu.jas.arith.BigRational; 019import edu.jas.arith.ModInteger; 020import edu.jas.arith.ModIntegerRing; 021import edu.jas.arith.Product; 022import edu.jas.arith.ProductRing; 023import edu.jas.gb.GroebnerBase; 024import edu.jas.gbufd.GBFactory; 025import edu.jas.gbufd.RGroebnerBasePseudoSeq; 026import edu.jas.gbufd.RReductionSeq; 027import edu.jas.kern.ComputerThreads; 028import edu.jas.poly.GenPolynomial; 029import edu.jas.poly.GenPolynomialRing; 030import edu.jas.poly.GenPolynomialTokenizer; 031import edu.jas.poly.PolynomialList; 032import edu.jas.poly.TermOrder; 033 034 035/** 036 * Examples for application usage. 037 * @author Christoph Zengler. 038 * @author Heinz Kredel. 039 */ 040 041public class Examples { 042 043 044 /** 045 * main. 046 */ 047 public static void main(String[] args) { 048 BasicConfigurator.configure(); 049 if (args.length > 0) { 050 example1(); 051 example2(); 052 example3(); 053 example4(); 054 } 055 example5(); 056 example6(); 057 ComputerThreads.terminate(); 058 } 059 060 061 /** 062 * example1. cyclic n-th roots polynomial systems. 063 */ 064 public static void example1() { 065 int n = 4; 066 067 BigInteger fac = new BigInteger(); 068 GenPolynomialRing<BigInteger> ring = new GenPolynomialRing<BigInteger>(fac, n); //,var); 069 System.out.println("ring = " + ring + "\n"); 070 071 List<GenPolynomial<BigInteger>> cp = new ArrayList<GenPolynomial<BigInteger>>(n); 072 for (int i = 1; i <= n; i++) { 073 GenPolynomial<BigInteger> p = cyclicPoly(ring, n, i); 074 cp.add(p); 075 System.out.println("p[" + i + "] = " + p); 076 System.out.println(); 077 } 078 System.out.println("cp = " + cp + "\n"); 079 080 List<GenPolynomial<BigInteger>> gb; 081 //GroebnerBase<BigInteger> sgb = new GroebnerBaseSeq<BigInteger>(); 082 GroebnerBase<BigInteger> sgb = GBFactory.getImplementation(fac); 083 gb = sgb.GB(cp); 084 System.out.println("gb = " + gb); 085 086 } 087 088 089 static GenPolynomial<BigInteger> cyclicPoly(GenPolynomialRing<BigInteger> ring, int n, int i) { 090 091 List<? extends GenPolynomial<BigInteger>> X = /*(List<GenPolynomial<BigInteger>>)*/ring 092 .univariateList(); 093 094 GenPolynomial<BigInteger> p = ring.getZERO(); 095 for (int j = 1; j <= n; j++) { 096 GenPolynomial<BigInteger> pi = ring.getONE(); 097 for (int k = j; k < j + i; k++) { 098 pi = pi.multiply(X.get(k % n)); 099 } 100 p = p.sum(pi); 101 if (i == n) { 102 p = p.subtract(ring.getONE()); 103 break; 104 } 105 } 106 return p; 107 } 108 109 110 /** 111 * example2. abtract types: 112 * List<GenPolynomial<Product<Residue<BigRational>>>>. 113 */ 114 public static void example2() { 115 List<GenPolynomial<Product<Residue<BigRational>>>> L = null; 116 L = new ArrayList<GenPolynomial<Product<Residue<BigRational>>>>(); 117 118 BigRational bfac = new BigRational(1); 119 GenPolynomialRing<BigRational> pfac = null; 120 pfac = new GenPolynomialRing<BigRational>(bfac, 3); 121 122 List<GenPolynomial<BigRational>> F = null; 123 F = new ArrayList<GenPolynomial<BigRational>>(); 124 125 GenPolynomial<BigRational> p = null; 126 for (int i = 0; i < 2; i++) { 127 p = pfac.random(5, 4, 3, 0.4f); 128 if (!p.isConstant()) { 129 F.add(p); 130 } 131 } 132 //System.out.println("F = " + F); 133 134 Ideal<BigRational> id = new Ideal<BigRational>(pfac, F); 135 id.doGB(); 136 if (id.isONE() || id.isZERO()) { 137 System.out.println("id zero or one = " + id); 138 return; 139 } 140 ResidueRing<BigRational> rr = new ResidueRing<BigRational>(id); 141 System.out.println("rr = " + rr); 142 143 ProductRing<Residue<BigRational>> pr = null; 144 pr = new ProductRing<Residue<BigRational>>(rr, 3); 145 146 String[] vars = new String[] { "a", "b" }; 147 GenPolynomialRing<Product<Residue<BigRational>>> fac; 148 fac = new GenPolynomialRing<Product<Residue<BigRational>>>(pr, 2, vars); 149 150 GenPolynomial<Product<Residue<BigRational>>> pp; 151 for (int i = 0; i < 1; i++) { 152 pp = fac.random(2, 4, 4, 0.4f); 153 if (!pp.isConstant()) { 154 L.add(pp); 155 } 156 } 157 System.out.println("L = " + L); 158 159 //PolynomialList<Product<Residue<BigRational>>> Lp = null; 160 //Lp = new PolynomialList<Product<Residue<BigRational>>>(fac,L); 161 //System.out.println("Lp = " + Lp); 162 163 GroebnerBase<Product<Residue<BigRational>>> bb = new RGroebnerBasePseudoSeq<Product<Residue<BigRational>>>( 164 pr); 165 166 System.out.println("isGB(L) = " + bb.isGB(L)); 167 168 List<GenPolynomial<Product<Residue<BigRational>>>> G = null; 169 170 G = bb.GB(L); 171 System.out.println("G = " + G); 172 System.out.println("isGB(G) = " + bb.isGB(G)); 173 } 174 175 176 /** 177 * example3. abtract types: GB of List<GenPolynomial<Residue<BigRational>>>. 178 */ 179 public static void example3() { 180 List<GenPolynomial<Residue<BigRational>>> L = null; 181 L = new ArrayList<GenPolynomial<Residue<BigRational>>>(); 182 183 BigRational bfac = new BigRational(1); 184 GenPolynomialRing<BigRational> pfac = null; 185 pfac = new GenPolynomialRing<BigRational>(bfac, 2); 186 187 List<GenPolynomial<BigRational>> F = null; 188 F = new ArrayList<GenPolynomial<BigRational>>(); 189 190 GenPolynomial<BigRational> p = null; 191 for (int i = 0; i < 2; i++) { 192 p = pfac.random(5, 5, 5, 0.4f); 193 //p = pfac.parse("x0^2 -2" ); 194 if (!p.isConstant()) { 195 F.add(p); 196 } 197 } 198 //System.out.println("F = " + F); 199 200 Ideal<BigRational> id = new Ideal<BigRational>(pfac, F); 201 id.doGB(); 202 if (id.isONE() || id.isZERO()) { 203 System.out.println("id zero or one = " + id); 204 return; 205 } 206 ResidueRing<BigRational> rr = new ResidueRing<BigRational>(id); 207 System.out.println("rr = " + rr); 208 209 String[] vars = new String[] { "a", "b" }; 210 GenPolynomialRing<Residue<BigRational>> fac; 211 fac = new GenPolynomialRing<Residue<BigRational>>(rr, 2, vars); 212 213 GenPolynomial<Residue<BigRational>> pp; 214 for (int i = 0; i < 2; i++) { 215 pp = fac.random(2, 4, 6, 0.2f); 216 if (!pp.isConstant()) { 217 L.add(pp); 218 } 219 } 220 System.out.println("L = " + L); 221 222 GroebnerBase<Residue<BigRational>> bb; 223 //bb = new GroebnerBasePseudoSeq<Residue<BigRational>>(rr); 224 bb = GBFactory.getImplementation(rr); 225 226 System.out.println("isGB(L) = " + bb.isGB(L)); 227 228 List<GenPolynomial<Residue<BigRational>>> G = null; 229 230 G = bb.GB(L); 231 System.out.println("G = " + G); 232 System.out.println("isGB(G) = " + bb.isGB(G)); 233 } 234 235 236 /** 237 * example4. abtract types: comprehensive GB of 238 * List<GenPolynomial<GenPolynomial<BigRational>>>. 239 */ 240 public static void example4() { 241 int kl = 2; 242 int ll = 3; 243 int el = 3; 244 float q = 0.2f; //0.4f 245 GenPolynomialRing<BigRational> cfac; 246 GenPolynomialRing<GenPolynomial<BigRational>> fac; 247 248 List<GenPolynomial<GenPolynomial<BigRational>>> L; 249 250 ComprehensiveGroebnerBaseSeq<BigRational> bb; 251 252 GenPolynomial<GenPolynomial<BigRational>> a; 253 GenPolynomial<GenPolynomial<BigRational>> b; 254 GenPolynomial<GenPolynomial<BigRational>> c; 255 256 BigRational coeff = new BigRational(kl); 257 String[] cv = { "a", "b" }; 258 cfac = new GenPolynomialRing<BigRational>(coeff, 2, cv); 259 String[] v = { "x", "y" }; 260 fac = new GenPolynomialRing<GenPolynomial<BigRational>>(cfac, 2, v); 261 bb = new ComprehensiveGroebnerBaseSeq<BigRational>(coeff); 262 263 L = new ArrayList<GenPolynomial<GenPolynomial<BigRational>>>(); 264 265 a = fac.random(kl, ll, el, q); 266 b = fac.random(kl, ll, el, q); 267 c = a; //c = fac.random(kl, ll, el, q ); 268 269 if (a.isZERO() || b.isZERO() || c.isZERO()) { 270 return; 271 } 272 273 L.add(a); 274 System.out.println("CGB exam L = " + L); 275 L = bb.GB(L); 276 System.out.println("CGB( L ) = " + L); 277 System.out.println("isCGB( L ) = " + bb.isGB(L)); 278 279 L.add(b); 280 System.out.println("CGB exam L = " + L); 281 L = bb.GB(L); 282 System.out.println("CGB( L ) = " + L); 283 System.out.println("isCGB( L ) = " + bb.isGB(L)); 284 285 L.add(c); 286 System.out.println("CGB exam L = " + L); 287 L = bb.GB(L); 288 System.out.println("CGB( L ) = " + L); 289 System.out.println("isCGB( L ) = " + bb.isGB(L)); 290 } 291 292 293 /** 294 * example5. comprehensive GB of 295 * List<GenPolynomial<GenPolynomial<BigRational>>> and GB for regular ring. 296 */ 297 public static void example5() { 298 int kl = 2; 299 int ll = 4; 300 int el = 3; 301 float q = 0.3f; //0.4f 302 GenPolynomialRing<BigRational> cfac; 303 GenPolynomialRing<GenPolynomial<BigRational>> fac; 304 305 List<GenPolynomial<GenPolynomial<BigRational>>> L; 306 307 ComprehensiveGroebnerBaseSeq<BigRational> bb; 308 309 GenPolynomial<GenPolynomial<BigRational>> a; 310 GenPolynomial<GenPolynomial<BigRational>> b; 311 GenPolynomial<GenPolynomial<BigRational>> c; 312 313 BigRational coeff = new BigRational(kl); 314 String[] cv = { "a", "b" }; 315 cfac = new GenPolynomialRing<BigRational>(coeff, 2, cv); 316 String[] v = { "x", "y" }; 317 fac = new GenPolynomialRing<GenPolynomial<BigRational>>(cfac, 2, v); 318 bb = new ComprehensiveGroebnerBaseSeq<BigRational>(coeff); 319 320 L = new ArrayList<GenPolynomial<GenPolynomial<BigRational>>>(); 321 322 a = fac.random(kl, ll, el, q); 323 b = fac.random(kl, ll, el, q); 324 c = a; //c = fac.random(kl, ll, el, q ); 325 326 if (a.isZERO() || b.isZERO() || c.isZERO()) { 327 return; 328 } 329 330 L.add(a); 331 L.add(b); 332 L.add(c); 333 System.out.println("CGB exam L = " + L); 334 GroebnerSystem<BigRational> sys = bb.GBsys(L); 335 boolean ig = bb.isGB(sys.getCGB()); 336 System.out.println("CGB( L ) = " + sys.getCGB()); 337 System.out.println("isCGB( L ) = " + ig); 338 339 List<GenPolynomial<Product<Residue<BigRational>>>> Lr, bLr; 340 RReductionSeq<Product<Residue<BigRational>>> res = new RReductionSeq<Product<Residue<BigRational>>>(); 341 342 Lr = PolyUtilApp.<BigRational> toProductRes(sys.list); 343 bLr = res.booleanClosure(Lr); 344 345 System.out.println("booleanClosed(Lr) = " + bLr); 346 347 if (bLr.size() > 0) { 348 GroebnerBase<Product<Residue<BigRational>>> rbb = new RGroebnerBasePseudoSeq<Product<Residue<BigRational>>>( 349 bLr.get(0).ring.coFac); 350 System.out.println("isRegularGB(Lr) = " + rbb.isGB(bLr)); 351 } 352 } 353 354 355 /** 356 * Example GBase and real root. 357 */ 358 @SuppressWarnings("unchecked") 359 public static void example6() { 360 BigRational coeff = new BigRational(); 361 GroebnerBase<BigRational> gb = GBFactory.getImplementation(coeff); 362 363 String exam = "(x,y,z) L " + "( " + "( x^2 - 2 ), ( y^2 - 3 ), ( z^2 + x * y )" + ") "; 364 Reader source = new StringReader(exam); 365 GenPolynomialTokenizer parser = new GenPolynomialTokenizer(source); 366 PolynomialList<BigRational> F = null; 367 368 try { 369 F = (PolynomialList<BigRational>) parser.nextPolynomialSet(); 370 } catch (ClassCastException e) { 371 e.printStackTrace(); 372 return; 373 } catch (IOException e) { 374 e.printStackTrace(); 375 return; 376 } 377 System.out.println("F = " + F); 378 379 List<GenPolynomial<BigRational>> G = gb.GB(F.list); 380 381 PolynomialList<BigRational> Gp = new PolynomialList<BigRational>(F.ring, G); 382 System.out.println("G = " + Gp); 383 384 // compute real roots of the ideal 385 Ideal<BigRational> I = new Ideal<BigRational>(Gp); 386 List<IdealWithRealAlgebraicRoots<BigRational>> Ir = PolyUtilApp.<BigRational> realAlgebraicRoots(I); 387 for (IdealWithRealAlgebraicRoots<BigRational> R : Ir) { 388 R.doDecimalApproximation(); 389 for (List<BigDecimal> Dr : R.decimalApproximation()) { 390 System.out.println(Dr.toString()); 391 } 392 System.out.println(); 393 } 394 } 395 396 397 /** 398 * example7. Coefficients in Boolean residue class ring. 399 */ 400 public static void example7() { 401 String[] vars = { "v3", "v2", "v1" }; 402 403 ModIntegerRing z2 = new ModIntegerRing(2); 404 GenPolynomialRing<ModInteger> z2p = new GenPolynomialRing<ModInteger>(z2, vars.length, new TermOrder( 405 TermOrder.INVLEX), vars); 406 List<GenPolynomial<ModInteger>> fieldPolynomials = new ArrayList<GenPolynomial<ModInteger>>(); 407 408 //add v1^2 + v1, v2^2 + v2, v3^2 + v3 to fieldPolynomials 409 for (int i = 0; i < vars.length; i++) { 410 GenPolynomial<ModInteger> var = z2p.univariate(i); 411 fieldPolynomials.add(var.multiply(var).sum(var)); 412 } 413 414 415 Ideal<ModInteger> fieldPolys = new Ideal<ModInteger>(z2p, fieldPolynomials); 416 ResidueRing<ModInteger> ring = new ResidueRing<ModInteger>(fieldPolys); 417 String[] mvars = { "mv3", "mv2", "mv1" }; 418 GenPolynomialRing<Residue<ModInteger>> ringp = new GenPolynomialRing<Residue<ModInteger>>(ring, 419 mvars.length, mvars); 420 421 List<GenPolynomial<Residue<ModInteger>>> polynomials = new ArrayList<GenPolynomial<Residue<ModInteger>>>(); 422 423 GenPolynomial<Residue<ModInteger>> v1 = ringp.univariate(0); 424 GenPolynomial<Residue<ModInteger>> v2 = ringp.univariate(1); 425 GenPolynomial<Residue<ModInteger>> v3 = ringp.univariate(2); 426 GenPolynomial<Residue<ModInteger>> notV1 = v1.sum(ringp.ONE); 427 GenPolynomial<Residue<ModInteger>> notV2 = v2.sum(ringp.ONE); 428 GenPolynomial<Residue<ModInteger>> notV3 = v3.sum(ringp.ONE); 429 430 //v1*v2 431 GenPolynomial<Residue<ModInteger>> p1 = v1.multiply(v2); 432 433 //v1*v2 + v1 + v2 + 1 434 GenPolynomial<Residue<ModInteger>> p2 = notV1.multiply(notV2); 435 436 //v1*v3 + v1 + v3 + 1 437 GenPolynomial<Residue<ModInteger>> p3 = notV1.multiply(notV3); 438 439 polynomials.add(p1); 440 polynomials.add(p2); 441 polynomials.add(p3); 442 443 //GroebnerBase<Residue<ModInteger>> gb = new GroebnerBasePseudoSeq<Residue<ModInteger>>(ring); 444 GroebnerBase<Residue<ModInteger>> gb = GBFactory.getImplementation(ring); 445 List<GenPolynomial<Residue<ModInteger>>> G = gb.GB(polynomials); 446 447 System.out.println(G); 448 } 449 450 451 /** 452 * example8. Coefficients in Boolean residue class ring with cuppling of 453 * variables. 454 */ 455 public static void example8() { 456 String[] vars = { "v3", "v2", "v1" }; 457 458 ModIntegerRing z2 = new ModIntegerRing(2); 459 GenPolynomialRing<ModInteger> z2p = new GenPolynomialRing<ModInteger>(z2, vars.length, new TermOrder( 460 TermOrder.INVLEX), vars); 461 List<GenPolynomial<ModInteger>> fieldPolynomials = new ArrayList<GenPolynomial<ModInteger>>(); 462 463 //add v1^2 + v1, v2^2 + v2, v3^2 + v3 to fieldPolynomials 464 for (int i = 0; i < vars.length; i++) { 465 GenPolynomial<ModInteger> var = z2p.univariate(i); 466 fieldPolynomials.add(var.multiply(var).sum(var)); 467 } 468 469 470 Ideal<ModInteger> fieldPolys = new Ideal<ModInteger>(z2p, fieldPolynomials); 471 ResidueRing<ModInteger> ring = new ResidueRing<ModInteger>(fieldPolys); 472 String[] mvars = { "mv3", "mv2", "mv1" }; 473 GenPolynomialRing<Residue<ModInteger>> ringp = new GenPolynomialRing<Residue<ModInteger>>(ring, 474 mvars.length, mvars); 475 476 List<GenPolynomial<Residue<ModInteger>>> polynomials = new ArrayList<GenPolynomial<Residue<ModInteger>>>(); 477 478 GenPolynomial<Residue<ModInteger>> v1 = ringp.univariate(0); 479 GenPolynomial<Residue<ModInteger>> v2 = ringp.univariate(1); 480 GenPolynomial<Residue<ModInteger>> v3 = ringp.univariate(2); 481 GenPolynomial<Residue<ModInteger>> notV1 = v1.sum(ringp.ONE); 482 GenPolynomial<Residue<ModInteger>> notV2 = v2.sum(ringp.ONE); 483 GenPolynomial<Residue<ModInteger>> notV3 = v3.sum(ringp.ONE); 484 485 //v1*v2 486 GenPolynomial<Residue<ModInteger>> p1 = v1.multiply(v2); 487 488 //v1*v2 + v1 + v2 + 1 489 GenPolynomial<Residue<ModInteger>> p2 = notV1.multiply(notV2); 490 491 //v1*v3 + v1 + v3 + 1 492 GenPolynomial<Residue<ModInteger>> p3 = notV1.multiply(notV3); 493 494 polynomials.add(p1); 495 polynomials.add(p2); 496 polynomials.add(p3); 497 498 List<Residue<ModInteger>> gens = ring.generators(); 499 System.out.println("gens = " + gens); 500 GenPolynomial<Residue<ModInteger>> mv3v3 = v3.subtract(gens.get(1)); 501 GenPolynomial<Residue<ModInteger>> mv2v2 = v2.subtract(gens.get(2)); 502 GenPolynomial<Residue<ModInteger>> mv1v1 = v1.subtract(gens.get(3)); 503 504 System.out.println("mv3v3 = " + mv3v3); 505 System.out.println("mv2v2 = " + mv2v2); 506 System.out.println("mv1v1 = " + mv1v1); 507 508 polynomials.add(mv3v3); 509 polynomials.add(mv2v2); 510 polynomials.add(mv1v1); 511 512 //GroebnerBase<Residue<ModInteger>> gb = new GroebnerBasePseudoSeq<Residue<ModInteger>>(ring); 513 GroebnerBase<Residue<ModInteger>> gb = GBFactory.getImplementation(ring); 514 515 List<GenPolynomial<Residue<ModInteger>>> G = gb.GB(polynomials); 516 517 System.out.println(G); 518 } 519 520 521 /** 522 * example9. Groebner base and dimension. 523 */ 524 public static void example9() { 525 String[] vars = { "d1", "d2", "d3", "p1a", "p1b", "p1c", "p2a", "p2b", "p2c", "p3a", "p3b", "p3c", 526 "p4a", "p4b", "p4c", "A", "B", "C", "D" }; 527 528 BigRational br = new BigRational(); 529 GenPolynomialRing<BigRational> pring = new GenPolynomialRing<BigRational>(br, vars); 530 //GenPolynomialRing<BigRational> pring = new GenPolynomialRing<BigRational>(br, vars.length, new TermOrder(TermOrder.INVLEX), vars); 531 532 GenPolynomial<BigRational> e1 = pring.parse("A*p1a+B*p1b+C*p1c+D"); // (1) 533 GenPolynomial<BigRational> e2 = pring.parse("A*p2a+B*p2b+C*p2c+D"); // (2) 534 GenPolynomial<BigRational> e3 = pring.parse("A*p3a+B*p3b+C*p3c+D"); // (3) 535 GenPolynomial<BigRational> e4 = pring.parse("A*p4a+B*p4b+C*p4c+D"); // (4) 536 GenPolynomial<BigRational> e5 = pring.parse("p2a-p3a"); // (5) 537 GenPolynomial<BigRational> e6 = pring.parse("p2b-p3b"); // (6) 538 GenPolynomial<BigRational> e7 = pring.parse("p2c-p3c"); // (7) 539 GenPolynomial<BigRational> e8 = pring.parse("(p2a-p1a)^2+(p2b-p1b)^2+(p2c-p1c)^2-d1^2"); // (8) 540 GenPolynomial<BigRational> e9 = pring.parse("(p4a-p3a)^2+(p4b-p3b)^2+(p4c-p3c)^2-d2^2"); // (9) 541 542 List<GenPolynomial<BigRational>> cp = new ArrayList<GenPolynomial<BigRational>>(9); 543 cp.add(e1); 544 cp.add(e2); 545 cp.add(e3); 546 cp.add(e4); 547 cp.add(e5); 548 cp.add(e6); 549 cp.add(e7); 550 cp.add(e8); 551 cp.add(e9); 552 553 GenPolynomial<BigRational> e10 = pring.parse("(p4a-p1a)^2+(p4b-p1b)^2+(p4c-p1c)^2-d3^2"); // (10) 554 cp.add(e10); 555 556 List<GenPolynomial<BigRational>> gb; 557 GroebnerBase<BigRational> sgb = GBFactory.getImplementation(br); 558 gb = sgb.GB(cp); 559 //System.out.println("gb = " + gb); 560 561 PolynomialList<BigRational> pl = new PolynomialList<BigRational>(pring, gb); 562 Ideal<BigRational> id = new Ideal<BigRational>(pl, true); 563 System.out.println("cp = " + cp); 564 System.out.println("id = " + id); 565 566 Dimension dim = id.dimension(); 567 System.out.println("dim = " + dim); 568 } 569 570}