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}