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