001/*
002 * $Id: SolvableSyzygyTest.java 5272 2015-07-27 20:54:14Z kredel $
003 */
004
005package edu.jas.gbufd;
006
007
008import java.io.IOException;
009import java.io.Reader;
010import java.io.StringReader;
011import java.util.ArrayList;
012import java.util.List;
013
014import junit.framework.Test;
015import junit.framework.TestCase;
016import junit.framework.TestSuite;
017
018import org.apache.log4j.BasicConfigurator;
019// import org.apache.log4j.Logger;
020
021
022
023import edu.jas.arith.BigRational;
024import edu.jas.gb.SolvableGroebnerBaseAbstract;
025import edu.jas.gb.SolvableGroebnerBase;
026import edu.jas.gb.SolvableGroebnerBaseSeq;
027import edu.jas.gbufd.SGBFactory;
028import edu.jas.gbufd.SolvableSyzygyAbstract;
029import edu.jas.gbufd.SolvableSyzygySeq;
030import edu.jas.poly.GenPolynomialTokenizer;
031import edu.jas.poly.GenSolvablePolynomial;
032import edu.jas.poly.GenSolvablePolynomialRing;
033import edu.jas.poly.ModuleList;
034import edu.jas.poly.PolynomialList;
035import edu.jas.poly.RelationGenerator;
036import edu.jas.poly.RelationTable;
037import edu.jas.poly.TermOrder;
038import edu.jas.poly.WeylRelations;
039
040
041/**
042 * SolvableSyzygy tests with JUnit.
043 * @author Heinz Kredel.
044 */
045
046public class SolvableSyzygyTest extends TestCase {
047
048
049    /**
050     * main.
051     */
052    public static void main(String[] args) {
053        BasicConfigurator.configure();
054        junit.textui.TestRunner.run(suite());
055    }
056
057
058    /**
059     * Constructs a <CODE>SolvableSyzygyTest</CODE> object.
060     * @param name String.
061     */
062    public SolvableSyzygyTest(String name) {
063        super(name);
064    }
065
066
067    /**
068     */
069    public static Test suite() {
070        TestSuite suite = new TestSuite(SolvableSyzygyTest.class);
071        return suite;
072    }
073
074
075    int port = 4711;
076
077
078    String host = "localhost";
079
080
081    BigRational cfac;
082
083
084    GenSolvablePolynomialRing<BigRational> fac;
085
086
087    PolynomialList<BigRational> F;
088
089
090    List<GenSolvablePolynomial<BigRational>> G;
091
092
093    GenSolvablePolynomial<BigRational> a, b, c, d, e;
094
095
096    GenSolvablePolynomial<BigRational> zero, one;
097
098
099    TermOrder tord;
100
101
102    RelationTable table;
103
104
105    List<GenSolvablePolynomial<BigRational>> L;
106
107
108    List<List<GenSolvablePolynomial<BigRational>>> K;
109
110
111    List<GenSolvablePolynomial<BigRational>> V;
112
113
114    List<List<GenSolvablePolynomial<BigRational>>> W;
115
116
117    ModuleList<BigRational> M, N, Z;
118
119
120    SolvableGroebnerBaseAbstract<BigRational> sbb;
121
122
123    SolvableGroebnerBase<BigRational> msbb;
124
125
126    SolvableSyzygyAbstract<BigRational> ssz;
127
128
129    int rl = 4; //4; //3; 
130
131
132    int kl = 3;
133
134
135    int ll = 7;
136
137
138    int el = 2;
139
140
141    float q = 0.3f; //0.4f
142
143
144    @Override
145    protected void setUp() {
146        cfac = new BigRational(1);
147        tord = new TermOrder();
148        fac = new GenSolvablePolynomialRing<BigRational>(cfac, rl, tord);
149        //RelationGenerator<BigRational> wl = new WeylRelations<BigRational>();
150        //wl.generate(fac);
151        table = fac.table;
152        a = b = c = d = e = null;
153        L = null;
154        K = null;
155        V = null;
156        do {
157            a = fac.random(kl, ll, el, q);
158        } while (a.isZERO());
159        do {
160            b = fac.random(kl, ll, el, q);
161        } while (b.isZERO());
162        do {
163            c = fac.random(kl, ll, el, q);
164        } while (c.isZERO());
165        do {
166            d = fac.random(kl, ll, el, q);
167        } while (d.isZERO());
168        e = d; //fac.random(kl, ll, el, q );
169        one = fac.getONE();
170        zero = fac.getZERO();
171        sbb = SGBFactory.getImplementation(cfac);
172        msbb = new SolvableGroebnerBaseSeq<BigRational>(); //cfac);
173        ssz = new SolvableSyzygySeq<BigRational>(cfac);
174    }
175
176
177    @Override
178    protected void tearDown() {
179        a = b = c = d = e = null;
180        L = null;
181        K = null;
182        V = null;
183        fac = null;
184        tord = null;
185        table = null;
186        sbb = null;
187        msbb = null;
188        ssz = null;
189    }
190
191
192    /**
193     * Test sequential SolvableSyzygy.
194     */
195    public void testSequentialSolvableSyzygy() {
196        L = new ArrayList<GenSolvablePolynomial<BigRational>>();
197
198        assertTrue("not isZERO( a )", !a.isZERO());
199        L.add(a);
200        assertTrue("isGB( { a } )", sbb.isLeftGB(L));
201        K = ssz.leftZeroRelations(L);
202        assertTrue("is ZR( { a } )", ssz.isLeftZeroRelation(K, L));
203
204        assertTrue("not isZERO( b )", !b.isZERO());
205        L.add(b);
206        L = sbb.leftGB(L);
207        assertTrue("isGB( { a, b } )", sbb.isLeftGB(L));
208        //System.out.println("\nL = " + L );
209        K = ssz.leftZeroRelations(L);
210        //System.out.println("\nK = " + K );
211        assertTrue("is ZR( { a, b } )", ssz.isLeftZeroRelation(K, L));
212
213        assertTrue("not isZERO( c )", !c.isZERO());
214        L.add(c);
215        L = sbb.leftGB(L);
216        //System.out.println("\nL = " + L );
217        assertTrue("isGB( { a, b, c } )", sbb.isLeftGB(L));
218        K = ssz.leftZeroRelations(L);
219        //System.out.println("\nK = " + K );
220        assertTrue("is ZR( { a, b, c } )", ssz.isLeftZeroRelation(K, L));
221
222        assertTrue("not isZERO( d )", !d.isZERO());
223        L.add(d);
224        L = sbb.leftGB(L);
225        //System.out.println("\nL = " + L );
226        assertTrue("isGB( { a, b, c, d } )", sbb.isLeftGB(L));
227        K = ssz.leftZeroRelations(L);
228        //System.out.println("\nK = " + K );
229        assertTrue("is ZR( { a, b, c, d } )", ssz.isLeftZeroRelation(K, L));
230    }
231
232
233    /**
234     * Test sequential Weyl SolvableSyzygy.
235     */
236    public void testSequentialWeylSolvableSyzygy() {
237        int rloc = 4;
238        fac = new GenSolvablePolynomialRing<BigRational>(cfac, rloc);
239
240        RelationGenerator<BigRational> wl = new WeylRelations<BigRational>();
241        wl.generate(fac);
242        table = fac.table;
243
244        a = fac.random(kl, ll, el, q);
245        b = fac.random(kl, ll, el, q);
246        c = fac.random(kl, ll, el, q);
247        d = fac.random(kl, ll, el, q);
248        e = d; //fac.random(kl, ll, el, q );
249
250        L = new ArrayList<GenSolvablePolynomial<BigRational>>();
251
252        assertTrue("not isZERO( a )", !a.isZERO());
253        L.add(a);
254        assertTrue("isGB( { a } )", sbb.isLeftGB(L));
255        K = ssz.leftZeroRelations(L);
256        assertTrue("is ZR( { a } )", ssz.isLeftZeroRelation(K, L));
257
258        assertTrue("not isZERO( b )", !b.isZERO());
259        L.add(b);
260        L = sbb.leftGB(L);
261        assertTrue("isGB( { a, b } )", sbb.isLeftGB(L));
262        //System.out.println("\nL = " + L );
263        K = ssz.leftZeroRelations(L);
264        //System.out.println("\nK = " + K );
265        assertTrue("is ZR( { a, b } )", ssz.isLeftZeroRelation(K, L));
266
267        // useless since 1 in GB
268        assertTrue("not isZERO( c )", !c.isZERO());
269        L.add(c);
270        L = sbb.leftGB(L);
271        //System.out.println("\nL = " + L );
272        assertTrue("isGB( { a, b, c } )", sbb.isLeftGB(L));
273        K = ssz.leftZeroRelations(L);
274        //System.out.println("\nK = " + K );
275        assertTrue("is ZR( { a, b, c } )", ssz.isLeftZeroRelation(K, L));
276
277        // useless since 1 in GB
278        assertTrue("not isZERO( d )", !d.isZERO());
279        L.add(d);
280        L = sbb.leftGB(L);
281        //System.out.println("\nL = " + L );
282        assertTrue("isGB( { a, b, c, d } )", sbb.isLeftGB(L));
283        K = ssz.leftZeroRelations(L);
284        //System.out.println("\nK = " + K );
285        assertTrue("is ZR( { a, b, c, d } )", ssz.isLeftZeroRelation(K, L));
286    }
287
288
289    /**
290     * Test sequential module SolvableSyzygy.
291     */
292    public void testSequentialModSolvableSyzygy() {
293        W = new ArrayList<List<GenSolvablePolynomial<BigRational>>>();
294
295        assertTrue("not isZERO( a )", !a.isZERO());
296        V = new ArrayList<GenSolvablePolynomial<BigRational>>();
297        V.add(a);
298        V.add(zero);
299        V.add(one);
300        W.add(V);
301        M = new ModuleList<BigRational>(fac, W);
302        assertTrue("isGB( { (a,0,1) } )", msbb.isLeftGB(M));
303
304        N = msbb.leftGB(M);
305        assertTrue("isGB( { (a,0,1) } )", msbb.isLeftGB(N));
306
307        Z = ssz.leftZeroRelations(N);
308        //System.out.println("Z = " + Z);
309        assertTrue("is ZR( { a) } )", ssz.isLeftZeroRelation(Z, N));
310
311        assertTrue("not isZERO( b )", !b.isZERO());
312        V = new ArrayList<GenSolvablePolynomial<BigRational>>();
313        V.add(b);
314        V.add(one);
315        V.add(zero);
316        W.add(V);
317        M = new ModuleList<BigRational>(fac, W);
318        //System.out.println("W = " + W.size() );
319
320        N = msbb.leftGB(M);
321        assertTrue("isGB( { a, b } )", msbb.isLeftGB(N));
322
323        Z = ssz.leftZeroRelations(N);
324        //System.out.println("Z = " + Z);
325        assertTrue("is ZR( { a, b } )", ssz.isLeftZeroRelation(Z, N));
326
327        assertTrue("not isZERO( c )", !c.isZERO());
328        V = new ArrayList<GenSolvablePolynomial<BigRational>>();
329        V.add(c);
330        V.add(one);
331        V.add(zero);
332        W.add(V);
333        M = new ModuleList<BigRational>(fac, W);
334        //System.out.println("W = " + W.size() );
335
336        N = msbb.leftGB(M);
337        //System.out.println("GB(M) = " + N);
338        assertTrue("isGB( { a,b,c) } )", msbb.isLeftGB(N));
339
340        Z = ssz.leftZeroRelations(N);
341        //System.out.println("Z = " + Z);
342        //boolean b = ssz.isLeftZeroRelation(Z,N);
343        //System.out.println("boolean = " + b);
344        assertTrue("is ZR( { a,b,c } )", ssz.isLeftZeroRelation(Z, N));
345    }
346
347
348    /**
349     * Test sequential arbitrary base Syzygy.
350     */
351    public void testSequentialArbitrarySyzygy() {
352        L = new ArrayList<GenSolvablePolynomial<BigRational>>();
353
354        assertTrue("not isZERO( a )", !a.isZERO());
355        L.add(a);
356        assertTrue("isGB( { a } )", sbb.isLeftGB(L));
357        K = ssz.leftZeroRelationsArbitrary(L);
358        assertTrue("is ZR( { a } )", ssz.isLeftZeroRelation(K, L));
359
360        assertTrue("not isZERO( b )", !b.isZERO());
361        L.add(b);
362        K = ssz.leftZeroRelationsArbitrary(L);
363        //System.out.println("\nN = " + N );
364        assertTrue("is ZR( { a, b } )", ssz.isLeftZeroRelation(K, L));
365
366        assertTrue("not isZERO( c )", !c.isZERO());
367        L.add(c);
368        K = ssz.leftZeroRelationsArbitrary(L);
369        //System.out.println("\nN = " + N );
370        assertTrue("is ZR( { a, b, c } )", ssz.isLeftZeroRelation(K, L));
371
372        assertTrue("not isZERO( d )", !d.isZERO());
373        L.add(d);
374        K = ssz.leftZeroRelationsArbitrary(L);
375        //System.out.println("\nN = " + N );
376        assertTrue("is ZR( { a, b, c, d } )", ssz.isLeftZeroRelation(K, L));
377    }
378
379
380    /**
381     * Test sequential arbitrary base Syzygy, ex CLO 2, p 214 ff.
382     */
383    @SuppressWarnings("cast")
384    public void testSequentialArbitrarySyzygyCLO() {
385        PolynomialList<BigRational> F = null;
386
387        String exam = "Rat(x,y) G " + "( " + "( x y + x ), " + "( y^2 + 1 ) " + ") ";
388        Reader source = new StringReader(exam);
389        GenPolynomialTokenizer parser = new GenPolynomialTokenizer(source);
390        try {
391            F = (PolynomialList<BigRational>) parser.nextSolvablePolynomialSet();
392        } catch (ClassCastException e) {
393            fail("" + e);
394        } catch (IOException e) {
395            fail("" + e);
396        }
397        //System.out.println("F = " + F);
398
399        L = F.castToSolvableList();
400        K = ssz.leftZeroRelationsArbitrary(L);
401        assertTrue("is ZR( { a, b } )", ssz.isLeftZeroRelation(K, L));
402    }
403
404
405    /**
406     * Test sequential arbitrary base Syzygy, ex WA_32.
407     */
408    @SuppressWarnings("cast")
409    public void testSequentialArbitrarySyzygyWA32() {
410        PolynomialList<BigRational> F = null;
411
412        String exam = "Rat(e1,e2,e3) L " + "RelationTable " + "( " + " ( e3 ), ( e1 ), ( e1 e3 - e1 ), "
413                        + " ( e3 ), ( e2 ), ( e2 e3 - e2 ) " + ")" + "( " + " ( e1 e3^3 + e2^2 ), "
414                        + " ( e1^3 e2^2 + e3 ), " + " ( e3^3 + e3^2 ) " + ") ";
415        Reader source = new StringReader(exam);
416        GenPolynomialTokenizer parser = new GenPolynomialTokenizer(source);
417        try {
418            F = (PolynomialList<BigRational>) parser.nextSolvablePolynomialSet();
419        } catch (ClassCastException e) {
420            fail("" + e);
421        } catch (IOException e) {
422            fail("" + e);
423        }
424        //System.out.println("F = " + F);
425
426        L = F.castToSolvableList();
427        K = ssz.leftZeroRelationsArbitrary(L);
428        assertTrue("is ZR( { a, b } )", ssz.isLeftZeroRelation(K, L));
429    }
430
431
432    /**
433     * Test sequential arbitrary module SolvableSyzygy.
434     */
435    public void testSequentialArbitraryModSolvableSyzygy() {
436        W = new ArrayList<List<GenSolvablePolynomial<BigRational>>>();
437
438        assertTrue("not isZERO( a )", !a.isZERO());
439        V = new ArrayList<GenSolvablePolynomial<BigRational>>();
440        V.add(a);
441        V.add(zero);
442        V.add(one);
443        W.add(V);
444        M = new ModuleList<BigRational>(fac, W);
445        assertTrue("isGB( { (a,0,1) } )", msbb.isLeftGB(M));
446
447        Z = ssz.leftZeroRelationsArbitrary(M);
448        //System.out.println("Z = " + Z);
449        assertTrue("is ZR( { a) } )", ssz.isLeftZeroRelation(Z, M));
450
451        assertTrue("not isZERO( b )", !b.isZERO());
452        V = new ArrayList<GenSolvablePolynomial<BigRational>>();
453        V.add(b);
454        V.add(one);
455        V.add(zero);
456        W.add(V);
457        M = new ModuleList<BigRational>(fac, W);
458        //System.out.println("W = " + W.size() );
459
460        Z = ssz.leftZeroRelationsArbitrary(M);
461        //System.out.println("Z = " + Z);
462        assertTrue("is ZR( { a, b } )", ssz.isLeftZeroRelation(Z, M));
463
464        assertTrue("not isZERO( c )", !c.isZERO());
465        V = new ArrayList<GenSolvablePolynomial<BigRational>>();
466        V.add(c);
467        V.add(one);
468        V.add(zero);
469        W.add(V);
470        M = new ModuleList<BigRational>(fac, W);
471        //System.out.println("W = " + W.size() );
472
473        Z = ssz.leftZeroRelationsArbitrary(M);
474        //System.out.println("Z = " + Z);
475        //boolean b = ssz.isLeftZeroRelation(Z,N);
476        //System.out.println("boolean = " + b);
477        assertTrue("is ZR( { a,b,c } )", ssz.isLeftZeroRelation(Z, M));
478    }
479
480
481    /**
482     * Test Ore conditions.
483     */
484    public void testOreConditions() {
485        RelationGenerator<BigRational> wl = new WeylRelations<BigRational>();
486        wl.generate(fac);
487        do {
488            a = fac.random(kl, ll - 1, el, q);
489        } while (a.isZERO());
490        do {
491            b = fac.random(kl, ll - 1, el, q);
492        } while (b.isZERO());
493        //System.out.println("a = " + a);
494        //System.out.println("b = " + b);
495
496        GenSolvablePolynomial<BigRational>[] oc = ssz.leftOreCond(a, b);
497        //System.out.println("oc[0] = " + oc[0]);
498        //System.out.println("oc[1] = " + oc[1]);
499        c = oc[0].multiply(a);
500        d = oc[1].multiply(b);
501        //System.out.println("c = " + c);
502        //System.out.println("d = " + d);
503        assertEquals("c_0 * a = c_1 * b: ", c, d);
504        assertTrue("left Ore condition: ", ssz.isLeftOreCond(a, b, oc));
505
506        oc = ssz.rightOreCond(a, b);
507        //System.out.println("oc[0] = " + oc[0]);
508        //System.out.println("oc[1] = " + oc[1]);
509        c = a.multiply(oc[0]);
510        d = b.multiply(oc[1]);
511        //System.out.println("c = " + c);
512        //System.out.println("d = " + d);
513        assertEquals("a * c_0 = b * c_1: ", c, d);
514        assertTrue("right Ore condition: ", ssz.isRightOreCond(a, b, oc));
515    }
516
517
518    /**
519     * Test Ore conditions for residues.
520     */
521    public void testResidueOreConditions() {
522        RelationGenerator<BigRational> wl = new WeylRelations<BigRational>();
523        wl.generate(fac);
524
525        // construct ideal { x_i^2 - i, ... } for generators x_i
526        F = new PolynomialList<BigRational>(fac, fac.generators());
527        //System.out.println("F = " + F);
528        List<GenSolvablePolynomial<BigRational>> gens = F.castToSolvableList();
529        //System.out.println("gens = " + gens);
530        L = new ArrayList<GenSolvablePolynomial<BigRational>>(gens.size() - 1);
531        long i = 2;
532        for (GenSolvablePolynomial<BigRational> g : gens) {
533            if (g.isONE()) {
534                continue;
535            }
536            GenSolvablePolynomial<BigRational> p = g.multiply(g);
537            p = (GenSolvablePolynomial<BigRational>) p.subtract(fac.fromInteger(i++));
538            L.add(p);
539        }
540        //System.out.println("L = " + L);
541
542        do {
543            a = fac.random(kl, ll - 2, el, q);
544        } while (a.isZERO());
545        do {
546            b = fac.random(kl, ll - 2, el, q);
547        } while (b.isZERO());
548        //System.out.println("a = " + a);
549        //System.out.println("b = " + b);
550
551        GenSolvablePolynomial<BigRational>[] oc = ssz.leftOreCond(a, b);
552        //System.out.println("oc[0] = " + oc[0]);
553        //System.out.println("oc[1] = " + oc[1]);
554        c = oc[0].multiply(a);
555        d = oc[1].multiply(b);
556        //System.out.println("c = " + c);
557        //System.out.println("d = " + d);
558        assertEquals("c_0 * a = c_1 * b: ", c, d);
559        assertTrue("left Ore condition: ", ssz.isLeftOreCond(a, b, oc));
560
561        // now mod ideal(L):
562        GenSolvablePolynomial<BigRational> ar, br, cr, dr, or0, or1;
563        ar = sbb.sred.leftNormalform(L, a);
564        br = sbb.sred.leftNormalform(L, b);
565        //System.out.println("ar = " + ar);
566        //System.out.println("br = " + br);
567        cr = oc[0].multiply(ar);
568        dr = oc[1].multiply(br);
569        //System.out.println("cr = " + cr);
570        //System.out.println("dr = " + dr);
571        //this is not true: assertEquals("c_0 * a = c_1 * b: ", cr, dr);
572        cr = sbb.sred.leftNormalform(L, cr);
573        dr = sbb.sred.leftNormalform(L, dr);
574        //System.out.println("cr = " + cr);
575        //System.out.println("dr = " + dr);
576        assertEquals("cr_0 * ar = cr_1 * br: ", cr, dr);
577
578        or0 = sbb.sred.leftNormalform(L, oc[0]);
579        or1 = sbb.sred.leftNormalform(L, oc[1]);
580        //System.out.println("oc0 = " + oc[0]);
581        //System.out.println("oc1 = " + oc[1]);
582        //System.out.println("or0 = " + or0);
583        //System.out.println("or1 = " + or1);
584        cr = or0.multiply(ar);
585        dr = or1.multiply(br);
586        //okay w/o: cr = sbb.sred.leftNormalform(L,cr);
587        //okay w/o: dr = sbb.sred.leftNormalform(L,dr);
588        //System.out.println("cr = " + cr);
589        //System.out.println("dr = " + dr);
590        //not okay: assertEquals("cr_0 * ar = cr_1 * br: ", cr, dr);
591        oc[0] = or0;
592        oc[1] = or1;
593        //not okay: assertTrue("left Ore condition: ", ssz.isLeftOreCond(ar,br,oc));
594
595        //System.out.println("new Ore Condition:");
596        oc = ssz.leftOreCond(ar, br);
597        //System.out.println("oc[0] = " + oc[0]);
598        //System.out.println("oc[1] = " + oc[1]);
599        cr = oc[0].multiply(ar);
600        dr = oc[1].multiply(br);
601        //System.out.println("cr = " + cr);
602        //System.out.println("dr = " + dr);
603        //this is true:
604        assertEquals("c_0 * a = c_1 * b: ", cr, dr);
605        cr = sbb.sred.leftNormalform(L, cr);
606        dr = sbb.sred.leftNormalform(L, dr);
607        //System.out.println("cr = " + cr);
608        //System.out.println("dr = " + dr);
609        assertEquals("cr_0 * ar = cr_1 * br: ", cr, dr);
610
611        /* not okay:
612        or0 = sbb.sred.leftNormalform(L,oc[0]);
613        or1 = sbb.sred.leftNormalform(L,oc[1]);
614        //System.out.println("oc0 = " + oc[0]);
615        //System.out.println("oc1 = " + oc[1]);
616        //System.out.println("or0 = " + or0);
617        //System.out.println("or1 = " + or1);
618        cr = or0.multiply(ar);
619        dr = or1.multiply(br);
620        //okay w/o: cr = sbb.sred.leftNormalform(L,cr);
621        //okay w/o: dr = sbb.sred.leftNormalform(L,dr);
622        //System.out.println("cr = " + cr);
623        //System.out.println("dr = " + dr);
624        assertEquals("cr_0 * ar = cr_1 * br: ", cr, dr);
625        oc[0] = or0;
626        oc[1] = or1;
627        assertTrue("left Ore condition: ", ssz.isLeftOreCond(ar,br,oc));
628        */
629    }
630
631}