Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.application;
006
007
008import java.util.ArrayList;
009import java.util.List;
010
011
012
013import edu.jas.arith.BigRational;
014import edu.jas.fd.FDUtil;
015import edu.jas.fd.GreatestCommonDivisorAbstract;
016import edu.jas.fd.GreatestCommonDivisorSimple;
017import edu.jas.kern.ComputerThreads;
018import edu.jas.kern.PrettyPrint;
019import edu.jas.poly.GenSolvablePolynomial;
020import edu.jas.poly.GenSolvablePolynomialRing;
021import edu.jas.poly.RelationGenerator;
022import edu.jas.poly.TermOrder;
023import edu.jas.poly.TermOrderByName;
024import edu.jas.poly.WeylRelations;
025
026import junit.framework.Test;
027import junit.framework.TestCase;
028import junit.framework.TestSuite;
029
030
031/**
032 * SolvableLocalResidue over BigRational GenSolvablePolynomial tests with JUnit.
033 * @author Heinz Kredel
034 */
035public class SolvableLocalResidueTest extends TestCase {
036
037
038    /**
039     * main.
040     */
041    public static void main(String[] args) {
042        
043        junit.textui.TestRunner.run(suite());
044        ComputerThreads.terminate();
045    }
046
047
048    /**
049     * Constructs a <code>SolvableLocalResidueTest</code> object.
050     * @param name String.
051     */
052    public SolvableLocalResidueTest(String name) {
053        super(name);
054    }
055
056
057    /**
058     * suite.
059     */
060    public static Test suite() {
061        TestSuite suite = new TestSuite(SolvableLocalResidueTest.class);
062        return suite;
063    }
064
065
066    SolvableLocalResidueRing<BigRational> efac;
067
068
069    GenSolvablePolynomialRing<BigRational> mfac;
070
071
072    SolvableIdeal<BigRational> id;
073
074
075    SolvableLocalResidue<BigRational> a, b, c, d, e;
076
077
078    SolvableLocalResidue<BigRational> az, bz, cz, dz, ez;
079
080
081    int rl = 4;
082
083
084    int kl = 2;
085
086
087    int ll = 3; //6;
088
089
090    int el = 2;
091
092
093    float q = 0.15f;
094
095
096    int il = (rl == 1 ? 1 : 2);
097
098
099    @Override
100    protected void setUp() {
101        a = b = c = d = e = null;
102        TermOrder to = TermOrderByName.INVLEX;
103        String[] vars = new String[] { "w", "x", "y", "z" };
104        mfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), rl, to, vars);
105        RelationGenerator<BigRational> wl = new WeylRelations<BigRational>();
106        wl.generate(mfac);
107        if (!mfac.isAssociative()) {
108            System.out.println("ring not associative: " + mfac);
109        }
110        //id = genRandomIdeal();
111        //id = genIdealA();
112        id = genPrimeIdealA();
113        //System.out.println("id = " + id);
114        assert !id.isONE() : "id = " + id;
115        efac = new SolvableLocalResidueRing<BigRational>(id);
116        //System.out.println("efac = " + efac.toScript());
117    }
118
119
120    protected SolvableIdeal<BigRational> genRandomIdeal() {
121        List<GenSolvablePolynomial<BigRational>> F;
122        do {
123            F = new ArrayList<GenSolvablePolynomial<BigRational>>(il);
124            for (int i = 0; i < il; i++) {
125                GenSolvablePolynomial<BigRational> mo = mfac.random(kl, ll, el + 1, q);
126                while (mo.isConstant()) {
127                    mo = mfac.random(kl, ll, el + 1, q);
128                }
129                F.add(mo);
130            }
131            SolvableIdeal<BigRational> id = new SolvableIdeal<BigRational>(mfac, F);
132            id.doGB();
133        } while (id.isONE());
134        return id;
135    }
136
137
138    protected SolvableIdeal<BigRational> genIdealA() {
139        GenSolvablePolynomial<BigRational> p;
140        List<GenSolvablePolynomial<BigRational>> F;
141        F = new ArrayList<GenSolvablePolynomial<BigRational>>(il);
142        p = mfac.parse("y^2 - 42/5");
143        F.add(p);
144        //p = mfac.parse("z^2");
145        p = mfac.parse("x^2");
146        F.add(p);
147        //p = mfac.parse("x^2 - w^2 ");
148        //F.add( p );
149        SolvableIdeal<BigRational> id = new SolvableIdeal<BigRational>(mfac, F);
150        id.doGB();
151        return id;
152    }
153
154
155    protected SolvableIdeal<BigRational> genIdealB() {
156        GenSolvablePolynomial<BigRational> p;
157        List<GenSolvablePolynomial<BigRational>> rel;
158        rel = new ArrayList<GenSolvablePolynomial<BigRational>>(il);
159        List<GenSolvablePolynomial<BigRational>> F;
160        F = new ArrayList<GenSolvablePolynomial<BigRational>>(il);
161
162        String[] vars = new String[] { "x", "y", "z", "t" };
163        mfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), TermOrderByName.INVLEX, vars);
164
165        // add relations
166        //z, y,  y * z + x,
167        p = mfac.parse("z");
168        rel.add(p);
169        p = mfac.parse("y");
170        rel.add(p);
171        p = mfac.parse("y * z + x");
172        rel.add(p);
173
174        //t, y,  y * t + y,
175        p = mfac.parse("t");
176        rel.add(p);
177        p = mfac.parse("y");
178        rel.add(p);
179        p = mfac.parse("y * t + y");
180        rel.add(p);
181
182        //t, z,  z * t - z
183        p = mfac.parse("t");
184        rel.add(p);
185        p = mfac.parse("z");
186        rel.add(p);
187        p = mfac.parse("z * t - z");
188        rel.add(p);
189
190        mfac.addSolvRelations(rel);
191        //System.out.println("mfac = " + mfac.toScript());
192
193        // construct ideal from polynomial t^2 + z^2 + y^2 + x^2 + 1
194        p = mfac.parse("t^2 + z^2 + y^2 + x^2 + 1");
195        F.add(p);
196        SolvableIdeal<BigRational> id;
197        id = new SolvableIdeal<BigRational>(mfac, F, SolvableIdeal.Side.twosided);
198        id.doGB();
199        //System.out.println("ideal = " + id.toScript());
200        return id;
201    }
202
203
204    protected SolvableIdeal<BigRational> genPrimeIdealA() { // well, almost
205        GenSolvablePolynomial<BigRational> p;
206        List<GenSolvablePolynomial<BigRational>> F;
207        F = new ArrayList<GenSolvablePolynomial<BigRational>>(il);
208        p = mfac.parse("y^2 + 5");
209        F.add(p);
210        p = mfac.parse("x^2 + 3");
211        F.add(p);
212        SolvableIdeal<BigRational> id = new SolvableIdeal<BigRational>(mfac, F);
213        id.doGB();
214        return id;
215    }
216
217
218    @Override
219    protected void tearDown() {
220        a = b = c = d = e = null;
221        //efac.terminate();
222        efac = null;
223        ComputerThreads.terminate();
224    }
225
226
227    /**
228     * Test constructor and toString.
229     */
230    public void testConstruction() {
231        c = efac.getONE();
232        //System.out.println("c = " + c);
233        //System.out.println("c.val = " + c.val);
234        assertTrue("length( c ) = 1", c.num.length() == 1);
235        assertTrue("isZERO( c )", !c.isZERO());
236        assertTrue("isONE( c )", c.isONE());
237
238        d = efac.getZERO();
239        //System.out.println("d = " + d);
240        //System.out.println("d.val = " + d.val);
241        assertTrue("length( d ) = 0", d.num.length() == 0);
242        assertTrue("isZERO( d )", d.isZERO());
243        assertTrue("isONE( d )", !d.isONE());
244
245        for (SolvableLocalResidue<BigRational> g : efac.generators()) {
246            //System.out.println("g = " + g);
247            assertFalse("not isZERO( g )", g.isZERO());
248        }
249        //wrong, solved: 
250        assertTrue("isAssociative: ", efac.isAssociative());
251    }
252
253
254    /**
255     * Test random polynomial.
256     */
257    public void testRandom() {
258        for (int i = 0; i < 4; i++) {
259            //a = efac.random(ll+i);
260            a = efac.random(kl + i, ll + 1, el, q);
261            //System.out.println("a = " + a);
262            if (a.isZERO() || a.isONE()) {
263                continue;
264            }
265            assertTrue("length( a" + i + " ) <> 0", a.num.length() >= 0);
266            assertTrue(" not isZERO( a" + i + " )", !a.isZERO());
267            assertTrue(" not isONE( a" + i + " )", !a.isONE());
268            assertEquals("a == a: ", a, a);
269        }
270    }
271
272
273    /**
274     * Test addition.
275     */
276    public void testAddition() {
277        a = efac.random(kl, ll, el, q);
278        b = efac.random(kl, ll, el, q);
279        //a = efac.parse("{ 1  | w * x + 25/28  }");
280        //b = efac.parse("{ x - 35/18  | x + 2 w - 6  }");
281        //!a = efac.parse("{ x - 1/7  | y * z + 7/10  }");
282        //!b = efac.parse("{ 1  | w + 3  }");
283        //a = efac.parse("{ 1  | y * z + 7/10 }");
284        //b = efac.parse("{ x - 1/7 | w + 3  }");
285        //a = efac.parse("{ ( -21/10 ) z - 5/4 x | x * z - 1/2 x + 1/2 }");
286        //b = efac.parse("{ 1 | z^2 - 63/5 }");
287        //a = efac.parse("{ 1  | z - 92/105 }");
288        //b = efac.parse("{ 1  | x }"); // when not prime
289        //a = efac.parse("{ x - 3 | z + 5 }");
290        //b = efac.parse("{ w + 2 | z - x * y }");
291        //b = new SolvableLocalResidue<BigRational>(efac,efac.ideal.getList().get(0));
292        //b = a.negate();
293        //System.out.println("a = " + a);
294        //System.out.println("b = " + b);
295
296        c = a.sum(efac.getZERO());
297        d = a.subtract(efac.getZERO());
298        assertEquals("a+0 = a-0", c, d);
299
300        c = efac.getZERO().sum(a);
301        d = efac.getZERO().subtract(a.negate());
302        assertEquals("0+a = 0-(-a)", c, d);
303
304        c = a.sum(b);
305        d = b.sum(a);
306        //System.out.println("c = " + c);
307        //System.out.println("d = " + d);
308        assertEquals("a+b = b+a", c, d);
309
310        c = a.sum(b);
311        //System.out.println("c = " + c);
312        d = c.subtract(b);
313        //System.out.println("d = " + d);
314        //System.out.println("a = " + a);
315        assertEquals("(a+b)-b = a: b = " + b, a, d);
316
317        c = efac.random(kl, ll, el, q);
318        //c = new SolvableLocalResidue<BigRational>(efac, mfac.univariate(1, 2));
319        //c = efac.parse("{ 42/5 }");
320        //System.out.println("c = " + c);
321        d = c.sum(a.sum(b));
322        e = c.sum(a).sum(b);
323        //System.out.println("d = " + d);
324        //System.out.println("e = " + e);
325        //System.out.println("d-e = " + d.subtract(e));
326        assertEquals("c+(a+b) = (c+a)+b: a = " + a + ", b = " + b + ", c = " + c, d, e);
327    }
328
329
330    /**
331     * Test multiplication.
332     */
333    public void testMultiplication() {
334        a = efac.random(kl, ll, el, q);
335        b = efac.random(kl, ll, el, q);
336        //System.out.println("a = " + a);
337        //System.out.println("b = " + b);
338
339        c = a.multiply(efac.getONE());
340        d = efac.getONE().multiply(a);
341        //System.out.println("c = " + c);
342        //System.out.println("d = " + d);
343        assertEquals("a*1 = 1*a", c, a);
344        assertEquals("a*1 = 1*a", c, d);
345
346        c = b.multiply(a);
347        d = a.multiply(b);
348        //System.out.println("c = " + c);
349        //System.out.println("d = " + d);
350        //non-com 
351        assertTrue("a*b != b*a", !c.equals(d) || c.equals(d) );
352
353        //c = efac.random(kl,ll,el,q);
354        c = new SolvableLocalResidue<BigRational>(efac, mfac.univariate(1, 2));
355        //System.out.println("c = " + c);
356        d = a.multiply(b.multiply(c));
357        //System.out.println("d = " + d);
358        e = (a.multiply(b)).multiply(c);
359        //System.out.println("e = " + e);
360        assertEquals("a(bc) = (ab)c", d, e);
361    }
362
363
364    /**
365     * Test inverse.
366     */
367    public void testInverse() {
368        a = efac.random(kl, ll + 1, el + 1, q * 1.15f);
369        //System.out.println("a = " + a);
370        b = new SolvableLocalResidue<BigRational>(efac, mfac.getONE(), mfac.univariate(1, 2));
371        //System.out.println("b = " + b);
372        a = a.multiply(b);
373        //System.out.println("a = " + a);
374
375        if (a.isUnit()) { // true if != 0
376            c = a.inverse();
377            //System.out.println("c = " + c);
378            d = c.multiply(a);
379            //d = a.multiply(c);
380            //System.out.println("d = " + d);
381            assertTrue("1/a * a = 1", d.isONE());
382            d = c.inverse();
383            //System.out.println("d = " + d);
384            //System.out.println("a = " + a);
385            //System.out.println("c = " + c);
386            //System.out.println("a-d = " + a.subtract(d));
387            assertEquals("1/(1/a) = a", a, d);
388        }
389    }
390
391
392    /**
393     * Test roots (eval mod ideal).
394     */
395    public void testRoot() {
396        c = efac.parse("y");
397        //System.out.println("c = " + c);
398        d = efac.parse("5");
399        //System.out.println("d = " + d);
400        e = c.multiply(c).sum(d);
401        //System.out.println("e = " + e);
402        assertTrue("e == 0 mod ideal", e.isZERO());
403        for (GenSolvablePolynomial<BigRational> p : efac.ideal.getList()) {
404            String s = p.toString();
405            //System.out.println("s = " + s);
406            e = efac.parse(s); // eval mod ideal
407            //System.out.println("e = " + e);
408            assertTrue("e == 0 mod ideal", e.isZERO());
409        }
410    }
411
412
413    /**
414     * Test parse.
415     */
416    public void testParse() {
417        a = efac.random(kl, ll, el, q);
418        //PrettyPrint.setInternal();
419        //System.out.println("a = " + a);
420        PrettyPrint.setPretty();
421        //System.out.println("a = " + a);
422        String p = a.toString();
423        //System.out.println("p = " + p);
424        b = efac.parse(p);
425        //System.out.println("b = " + b);
426        assertEquals("parse(a.toSting()) = a", a, b);
427    }
428
429
430    /**
431     * Test example ideal for ICMS-2016.
432     */
433    public void testExamIdeal() {
434        id = genIdealB();
435        //System.out.println("id = " + id);
436        assert !id.isONE() : "id = " + id;
437        efac = new SolvableLocalResidueRing<BigRational>(id);
438        //System.out.println("efac = " + efac.toScript());
439
440        SolvableLocalResidue<BigRational> a, b, c, d, e, f;
441        GenSolvablePolynomial<BigRational> p, q, r;
442
443        p = mfac.parse("t + x + y + 1");
444        a = new SolvableLocalResidue<BigRational>(efac, p);
445        //System.out.println("a = " + a.toScript());
446
447        p = mfac.parse("z**2+x+1");
448        b = new SolvableLocalResidue<BigRational>(efac, p);
449        //System.out.println("b = " + b.toScript());
450
451        c = a.inverse();
452        //System.out.println("c = " + c.toScript());
453        d = b.inverse();
454        //System.out.println("d = " + d.toScript());
455
456        d = c.multiply(a);
457        //System.out.println("d = " + d.toScript());
458        e = d.inverse();
459        //System.out.println("e = " + e.toScript());
460
461        e = b.multiply(c);
462        //System.out.println("e = " + e.toScript());
463        f = c.multiply(b);
464        //System.out.println("f = " + f.toScript());
465
466        d = a.multiply(f);
467        //System.out.println("d = " + d.toScript());
468
469        d = e.multiply(a); // b * 1/a * a == b
470        //System.out.println("d = " + d.toScript());
471        //System.out.println("b == d: " + b.equals(d));
472        assertEquals("b.equals(d): ", b, d);
473        //System.out.println("#b: " + (b.num.length()+b.den.length()));
474        //System.out.println("#d: " + (d.num.length()+d.den.length()));
475
476        GreatestCommonDivisorAbstract<BigRational> engine = new GreatestCommonDivisorSimple<BigRational>(
477                        new BigRational());
478        p = engine.leftGcd(d.num, d.den);
479        //System.out.println("p = " + p.toScript());
480
481        GenSolvablePolynomial<BigRational>[] qr;
482        // right division
483        qr = FDUtil.<BigRational> rightBasePseudoQuotientRemainder(d.num, p);
484        //System.out.println("q_rn = " + qr[0].toScript());
485        //System.out.println("r_rn = " + qr[1].toScript());
486        r = qr[0];
487        assertTrue("rem == 0: ", qr[1].isZERO());
488
489        qr = FDUtil.<BigRational> rightBasePseudoQuotientRemainder(d.den, p);
490        //System.out.println("q_rn = " + qr[0].toScript());
491        //System.out.println("r_rn = " + qr[1].toScript());
492        q = qr[0];
493        assertTrue("rem == 0: ", qr[1].isZERO());
494
495        e = new SolvableLocalResidue<BigRational>(efac, r, q);
496        //System.out.println("b = " + b.toScript());
497        //System.out.println("e = " + e.toScript());
498        //System.out.println("b == e: " + b.equals(e));
499        assertEquals("b == e: ", b, e);
500
501        //qr = FDUtil.<BigRational> leftGcdCofactors(id.getRing(), d.num, d.den);
502        //System.out.println("left qr = " + Arrays.toString(qr));
503
504        //qr = FDUtil.<BigRational> rightGcdCofactors(id.getRing(), d.num, d.den);
505        //System.out.println("right qr = " + Arrays.toString(qr));
506    }
507
508}