001 /*
002 * $Id: Examples.java 3564 2011-03-13 12:18:19Z kredel $
003 */
004
005 package edu.jas.application;
006
007
008 import java.io.IOException;
009 import java.io.Reader;
010 import java.io.StringReader;
011 import java.util.ArrayList;
012 import java.util.List;
013
014 import org.apache.log4j.BasicConfigurator;
015
016 import edu.jas.arith.BigDecimal;
017 import edu.jas.arith.BigInteger;
018 import edu.jas.arith.BigRational;
019 import edu.jas.arith.ModInteger;
020 import edu.jas.arith.ModIntegerRing;
021 import edu.jas.arith.Product;
022 import edu.jas.arith.ProductRing;
023 import edu.jas.gb.GroebnerBase;
024 import edu.jas.gbufd.GBFactory;
025 import edu.jas.gbufd.RGroebnerBasePseudoSeq;
026 import edu.jas.gbufd.RReductionSeq;
027 import edu.jas.kern.ComputerThreads;
028 import edu.jas.poly.GenPolynomial;
029 import edu.jas.poly.GenPolynomialRing;
030 import edu.jas.poly.GenPolynomialTokenizer;
031 import edu.jas.poly.PolynomialList;
032 import edu.jas.poly.TermOrder;
033
034
035 /**
036 * Examples for application usage.
037 * @author Christoph Zengler.
038 * @author Heinz Kredel.
039 */
040
041 public 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 } catch (IOException e) {
373 e.printStackTrace();
374 }
375 System.out.println("F = " + F);
376
377 List<GenPolynomial<BigRational>> G = gb.GB(F.list);
378
379 PolynomialList<BigRational> Gp = new PolynomialList<BigRational>(F.ring, G);
380 System.out.println("G = " + Gp);
381
382 // compute real roots of the ideal
383 Ideal<BigRational> I = new Ideal<BigRational>(Gp);
384 List<IdealWithRealAlgebraicRoots<BigRational, BigRational>> Ir = PolyUtilApp
385 .<BigRational, BigRational> realAlgebraicRoots(I);
386 for (IdealWithRealAlgebraicRoots<BigRational, BigRational> R : Ir) {
387 R.doDecimalApproximation();
388 for (List<BigDecimal> Dr : R.decimalApproximation()) {
389 System.out.println(Dr.toString());
390 }
391 System.out.println();
392 }
393 }
394
395
396 /**
397 * example7. Coefficients in Boolean residue class ring.
398 */
399 public static void example7() {
400 String[] vars = { "v3", "v2", "v1" };
401
402 ModIntegerRing z2 = new ModIntegerRing(2);
403 GenPolynomialRing<ModInteger> z2p = new GenPolynomialRing<ModInteger>(z2, vars.length, new TermOrder(
404 TermOrder.INVLEX), vars);
405 List<GenPolynomial<ModInteger>> fieldPolynomials = new ArrayList<GenPolynomial<ModInteger>>();
406
407 //add v1^2 + v1, v2^2 + v2, v3^2 + v3 to fieldPolynomials
408 for (int i = 0; i < vars.length; i++) {
409 GenPolynomial<ModInteger> var = z2p.univariate(i);
410 fieldPolynomials.add(var.multiply(var).sum(var));
411 }
412
413
414 Ideal<ModInteger> fieldPolys = new Ideal<ModInteger>(z2p, fieldPolynomials);
415 ResidueRing<ModInteger> ring = new ResidueRing<ModInteger>(fieldPolys);
416 String[] mvars = { "mv3", "mv2", "mv1" };
417 GenPolynomialRing<Residue<ModInteger>> ringp = new GenPolynomialRing<Residue<ModInteger>>(ring,
418 mvars.length, mvars);
419
420 List<GenPolynomial<Residue<ModInteger>>> polynomials = new ArrayList<GenPolynomial<Residue<ModInteger>>>();
421
422 GenPolynomial<Residue<ModInteger>> v1 = ringp.univariate(0);
423 GenPolynomial<Residue<ModInteger>> v2 = ringp.univariate(1);
424 GenPolynomial<Residue<ModInteger>> v3 = ringp.univariate(2);
425 GenPolynomial<Residue<ModInteger>> notV1 = v1.sum(ringp.ONE);
426 GenPolynomial<Residue<ModInteger>> notV2 = v2.sum(ringp.ONE);
427 GenPolynomial<Residue<ModInteger>> notV3 = v3.sum(ringp.ONE);
428
429 //v1*v2
430 GenPolynomial<Residue<ModInteger>> p1 = v1.multiply(v2);
431
432 //v1*v2 + v1 + v2 + 1
433 GenPolynomial<Residue<ModInteger>> p2 = notV1.multiply(notV2);
434
435 //v1*v3 + v1 + v3 + 1
436 GenPolynomial<Residue<ModInteger>> p3 = notV1.multiply(notV3);
437
438 polynomials.add(p1);
439 polynomials.add(p2);
440 polynomials.add(p3);
441
442 //GroebnerBase<Residue<ModInteger>> gb = new GroebnerBasePseudoSeq<Residue<ModInteger>>(ring);
443 GroebnerBase<Residue<ModInteger>> gb = GBFactory.getImplementation(ring);
444 List<GenPolynomial<Residue<ModInteger>>> G = gb.GB(polynomials);
445
446 System.out.println(G);
447 }
448
449
450 /**
451 * example8. Coefficients in Boolean residue class ring with cuppling of
452 * variables.
453 */
454 public static void example8() {
455 String[] vars = { "v3", "v2", "v1" };
456
457 ModIntegerRing z2 = new ModIntegerRing(2);
458 GenPolynomialRing<ModInteger> z2p = new GenPolynomialRing<ModInteger>(z2, vars.length, new TermOrder(
459 TermOrder.INVLEX), vars);
460 List<GenPolynomial<ModInteger>> fieldPolynomials = new ArrayList<GenPolynomial<ModInteger>>();
461
462 //add v1^2 + v1, v2^2 + v2, v3^2 + v3 to fieldPolynomials
463 for (int i = 0; i < vars.length; i++) {
464 GenPolynomial<ModInteger> var = z2p.univariate(i);
465 fieldPolynomials.add(var.multiply(var).sum(var));
466 }
467
468
469 Ideal<ModInteger> fieldPolys = new Ideal<ModInteger>(z2p, fieldPolynomials);
470 ResidueRing<ModInteger> ring = new ResidueRing<ModInteger>(fieldPolys);
471 String[] mvars = { "mv3", "mv2", "mv1" };
472 GenPolynomialRing<Residue<ModInteger>> ringp = new GenPolynomialRing<Residue<ModInteger>>(ring,
473 mvars.length, mvars);
474
475 List<GenPolynomial<Residue<ModInteger>>> polynomials = new ArrayList<GenPolynomial<Residue<ModInteger>>>();
476
477 GenPolynomial<Residue<ModInteger>> v1 = ringp.univariate(0);
478 GenPolynomial<Residue<ModInteger>> v2 = ringp.univariate(1);
479 GenPolynomial<Residue<ModInteger>> v3 = ringp.univariate(2);
480 GenPolynomial<Residue<ModInteger>> notV1 = v1.sum(ringp.ONE);
481 GenPolynomial<Residue<ModInteger>> notV2 = v2.sum(ringp.ONE);
482 GenPolynomial<Residue<ModInteger>> notV3 = v3.sum(ringp.ONE);
483
484 //v1*v2
485 GenPolynomial<Residue<ModInteger>> p1 = v1.multiply(v2);
486
487 //v1*v2 + v1 + v2 + 1
488 GenPolynomial<Residue<ModInteger>> p2 = notV1.multiply(notV2);
489
490 //v1*v3 + v1 + v3 + 1
491 GenPolynomial<Residue<ModInteger>> p3 = notV1.multiply(notV3);
492
493 polynomials.add(p1);
494 polynomials.add(p2);
495 polynomials.add(p3);
496
497 List<Residue<ModInteger>> gens = ring.generators();
498 System.out.println("gens = " + gens);
499 GenPolynomial<Residue<ModInteger>> mv3v3 = v3.subtract(gens.get(1));
500 GenPolynomial<Residue<ModInteger>> mv2v2 = v2.subtract(gens.get(2));
501 GenPolynomial<Residue<ModInteger>> mv1v1 = v1.subtract(gens.get(3));
502
503 System.out.println("mv3v3 = " + mv3v3);
504 System.out.println("mv2v2 = " + mv2v2);
505 System.out.println("mv1v1 = " + mv1v1);
506
507 polynomials.add(mv3v3);
508 polynomials.add(mv2v2);
509 polynomials.add(mv1v1);
510
511 //GroebnerBase<Residue<ModInteger>> gb = new GroebnerBasePseudoSeq<Residue<ModInteger>>(ring);
512 GroebnerBase<Residue<ModInteger>> gb = GBFactory.getImplementation(ring);
513
514 List<GenPolynomial<Residue<ModInteger>>> G = gb.GB(polynomials);
515
516 System.out.println(G);
517 }
518
519
520 /**
521 * example9. Groebner base and dimension.
522 */
523 public static void example9() {
524 String[] vars = { "d1", "d2", "d3",
525 "p1a", "p1b", "p1c", "p2a", "p2b", "p2c", "p3a", "p3b", "p3c", "p4a", "p4b", "p4c",
526 "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 }