Source code

001
002/*
003 * $Id$
004 */
005
006package edu.jas.ufd;
007
008
009import java.util.List;
010import java.util.SortedMap;
011
012import edu.jas.arith.BigRational;
013import edu.jas.kern.ComputerThreads;
014import edu.jas.kern.PrettyPrint;
015import edu.jas.poly.GenPolynomialRing;
016import edu.jas.poly.TermOrder;
017import edu.jas.vector.GenMatrix;
018import edu.jas.vector.GenMatrixRing;
019import edu.jas.vector.LinAlg;
020
021import junit.framework.Test;
022import junit.framework.TestCase;
023import junit.framework.TestSuite;
024
025
026/**
027 * Quotient over BigRational GenPolynomial tests with JUnit.
028 * @author Heinz Kredel
029 */
030
031public class QuotientRatTest extends TestCase {
032
033
034    /**
035     * main.
036     */
037    public static void main(String[] args) {
038        junit.textui.TestRunner.run(suite());
039    }
040
041
042    /**
043     * Constructs a <CODE>QuotientRatTest</CODE> object.
044     * @param name String.
045     */
046    public QuotientRatTest(String name) {
047        super(name);
048    }
049
050
051    /**
052     * suite.
053     */
054    public static Test suite() {
055        TestSuite suite = new TestSuite(QuotientRatTest.class);
056        return suite;
057    }
058
059
060    //private final static int bitlen = 100;
061
062    QuotientRing<BigRational> zFac, efac;
063
064
065    GenPolynomialRing<BigRational> mfac;
066
067
068    Quotient<BigRational> a, b, c, d, e;
069
070
071    Quotient<BigRational> az, bz, cz, dz, ez;
072
073
074    int rl = 3;
075
076
077    int kl = 5;
078
079
080    int ll = 3; //6;
081
082
083    int el = 2;
084
085
086    float q = 0.4f;
087
088
089    @Override
090    protected void setUp() {
091        a = b = c = d = e = null;
092        TermOrder to = new TermOrder(TermOrder.INVLEX);
093        mfac = new GenPolynomialRing<BigRational>(new BigRational(1), rl, to);
094        efac = new QuotientRing<BigRational>(mfac);
095        zFac = new QuotientRing<BigRational>(mfac, false);
096    }
097
098
099    @Override
100    protected void tearDown() {
101        a = b = c = d = e = null;
102        //efac.terminate();
103        efac = null;
104        zFac = null;
105        ComputerThreads.terminate();
106    }
107
108
109    /**
110     * Test constructor and toString.
111     */
112    public void testConstruction() {
113        c = efac.getONE();
114        //System.out.println("c = " + c);
115        //System.out.println("c.val = " + c.val);
116        assertTrue("length( c ) = 1", c.num.length() == 1);
117        assertTrue("isZERO( c )", !c.isZERO());
118        assertTrue("isONE( c )", c.isONE());
119
120        d = efac.getZERO();
121        //System.out.println("d = " + d);
122        //System.out.println("d.val = " + d.val);
123        assertTrue("length( d ) = 0", d.num.length() == 0);
124        assertTrue("isZERO( d )", d.isZERO());
125        assertTrue("isONE( d )", !d.isONE());
126    }
127
128
129    /**
130     * Test random polynomial.
131     */
132    public void testRandom() {
133        for (int i = 0; i < 7; i++) {
134            //a = efac.random(ll+i);
135            a = efac.random(kl * (i + 1), ll + 2 + 2 * i, el, q);
136            //System.out.println("a = " + a);
137            if (a.isZERO() || a.isONE()) {
138                continue;
139            }
140            assertTrue("length( a" + i + " ) <> 0", a.num.length() >= 0);
141            assertTrue(" not isZERO( a" + i + " )", !a.isZERO());
142            assertTrue(" not isONE( a" + i + " )", !a.isONE());
143        }
144    }
145
146
147    /**
148     * Test addition.
149     */
150    public void testAddition() {
151        a = efac.random(kl, ll, el, q);
152        b = efac.random(kl, ll, el, q);
153        //System.out.println("a = " + a);
154        //System.out.println("b = " + b);
155
156        c = a.sum(b);
157        d = c.subtract(b);
158        //System.out.println("c = " + c);
159        //System.out.println("d = " + d);
160        d = d.monic();
161        //System.out.println("d = " + d);
162        assertEquals("a+b-b = a", a, d);
163
164        c = a.sum(b);
165        d = b.sum(a);
166        //System.out.println("c = " + c);
167        //System.out.println("d = " + d);
168        assertEquals("a+b = b+a", c, d);
169
170        //System.out.println("monic(d) = " + d.monic());
171
172        c = efac.random(kl, ll, el, q);
173        //System.out.println("c = " + c);
174        d = c.sum(a.sum(b));
175        e = c.sum(a).sum(b);
176        //System.out.println("d = " + d);
177        //System.out.println("e = " + e);
178        assertEquals("c+(a+b) = (c+a)+b", d, e);
179
180
181        c = a.sum(efac.getZERO());
182        d = a.subtract(efac.getZERO());
183        assertEquals("a+0 = a-0", c, d);
184
185        c = efac.getZERO().sum(a);
186        d = efac.getZERO().subtract(a.negate());
187        assertEquals("0+a = 0+(-a)", c, d);
188    }
189
190
191    /**
192     * Test object multiplication.
193     */
194    public void testMultiplication() {
195        a = efac.random(kl, ll, el, q);
196        //assertTrue("not isZERO( a )", !a.isZERO() );
197
198        b = efac.random(kl, ll, el, q);
199        //assertTrue("not isZERO( b )", !b.isZERO() );
200
201        c = b.multiply(a);
202        d = a.multiply(b);
203        //assertTrue("not isZERO( c )", !c.isZERO() );
204        //assertTrue("not isZERO( d )", !d.isZERO() );
205
206        //System.out.println("a = " + a);
207        //System.out.println("b = " + b);
208        e = d.subtract(c);
209        assertTrue("isZERO( a*b-b*a ) " + e, e.isZERO());
210
211        assertTrue("a*b = b*a", c.equals(d));
212        assertEquals("a*b = b*a", c, d);
213
214        c = efac.random(kl, ll, el, q);
215        //System.out.println("c = " + c);
216        d = a.multiply(b.multiply(c));
217        e = (a.multiply(b)).multiply(c);
218
219        //System.out.println("d = " + d);
220        //System.out.println("e = " + e);
221
222        //System.out.println("d-e = " + d.subtract(c) );
223
224        assertEquals("a(bc) = (ab)c", d, e);
225        assertTrue("a(bc) = (ab)c", d.equals(e));
226
227        c = a.multiply(efac.getONE());
228        d = efac.getONE().multiply(a);
229        assertEquals("a*1 = 1*a", c, d);
230
231        if (a.isUnit()) {
232            c = a.inverse();
233            d = c.multiply(a);
234            //System.out.println("a = " + a);
235            //System.out.println("c = " + c);
236            //System.out.println("d = " + d);
237            assertTrue("a*1/a = 1", d.isONE());
238        }
239    }
240
241
242    /**
243     * Test addition with syzygy gcd and euclids gcd.
244     */
245    public void xtestAdditionGcd() {
246        long te, tz;
247
248        a = efac.random(kl, ll, el, q);
249        b = efac.random(kl, ll, el, q);
250        //System.out.println("a = " + a);
251        //System.out.println("b = " + b);
252
253        az = new Quotient<BigRational>(zFac, a.num, a.den, true);
254        bz = new Quotient<BigRational>(zFac, b.num, b.den, true);
255
256        te = System.currentTimeMillis();
257        c = a.sum(b);
258        d = c.subtract(b);
259        d = d.monic();
260        te = System.currentTimeMillis() - te;
261        assertEquals("a+b-b = a", a, d);
262
263        tz = System.currentTimeMillis();
264        cz = az.sum(bz);
265        dz = cz.subtract(bz);
266        dz = dz.monic();
267        tz = System.currentTimeMillis() - tz;
268        assertEquals("a+b-b = a", az, dz);
269
270        System.out.println("te = " + te);
271        System.out.println("tz = " + tz);
272
273        c = a.sum(b);
274        d = b.sum(a);
275        //System.out.println("c = " + c);
276        //System.out.println("d = " + d);
277        assertEquals("a+b = b+a", c, d);
278
279        c = efac.random(kl, ll, el, q);
280        cz = new Quotient<BigRational>(zFac, c.num, c.den, true);
281
282
283        te = System.currentTimeMillis();
284        d = c.sum(a.sum(b));
285        e = c.sum(a).sum(b);
286        te = System.currentTimeMillis() - te;
287        assertEquals("c+(a+b) = (c+a)+b", d, e);
288
289        tz = System.currentTimeMillis();
290        dz = cz.sum(az.sum(bz));
291        ez = cz.sum(az).sum(bz);
292        tz = System.currentTimeMillis() - tz;
293        assertEquals("c+(a+b) = (c+a)+b", dz, ez);
294
295        System.out.println("te = " + te);
296        System.out.println("tz = " + tz);
297
298        c = a.sum(efac.getZERO());
299        d = a.subtract(efac.getZERO());
300        assertEquals("a+0 = a-0", c, d);
301
302        c = efac.getZERO().sum(a);
303        d = efac.getZERO().subtract(a.negate());
304        assertEquals("0+a = 0+(-a)", c, d);
305    }
306
307
308    /**
309     * Test parse().
310     */
311    public void testParse() {
312        a = efac.random(kl * 2, ll * 2, el * 2, q * 2);
313        //assertTrue("not isZERO( a )", !a.isZERO() );
314
315        //PrettyPrint.setInternal();
316        //System.out.println("a = " + a);
317        PrettyPrint.setPretty();
318        //System.out.println("a = " + a);
319        String p = a.toString();
320        //System.out.println("p = " + p);
321        b = efac.parse(p);
322        //System.out.println("b = " + b);
323
324        //c = a.subtract(b);
325        //System.out.println("c = " + c);
326        assertEquals("parse(a.toSting()) = a", a, b);
327    }
328
329
330    /**
331     * Test factorization.
332     */
333    public void testFactors() {
334        a = efac.random(kl, ll, el, q);
335        b = efac.random(kl, ll, el, q);
336        b = b.multiply(b);
337        //System.out.println("a = " + a);
338        //System.out.println("b = " + b);
339
340        c = a.multiply(b);
341        //System.out.println("c = " + c);
342
343        SortedMap<Quotient<BigRational>, Long> factors = PolyUfdUtil.<BigRational> factors(c);
344        //System.out.println("factors = " + factors);
345
346        boolean t = PolyUfdUtil.<BigRational> isFactorization(c, factors);
347        //System.out.println("t = " + t);
348        assertTrue("c == prod(factors): " + c + ", " + factors, t);
349    }
350
351
352    /**
353     * Test symbolic row echelon form and LU decomposition. Using an example
354     * from
355     * <a href="https://github.com/kredel/java-algebra-system/issues/21">Issue
356     * #21</a>.
357     */
358    public void testLinAlg() {
359        BigRational cfac = new BigRational(11);
360        GenPolynomialRing<BigRational> pfac = new GenPolynomialRing<BigRational>(cfac, new String[] { "a" });
361        //System.out.println("pfac = " + pfac.toScript());
362        QuotientRing<BigRational> qfac = new QuotientRing<BigRational>(pfac);
363        //System.out.println("qfac = " + qfac.toScript());
364        Quotient<BigRational> a = new Quotient<BigRational>(qfac, pfac.univariate(0));
365        //System.out.println("a: " + a.toScript());
366        int n = 3;
367        GenMatrixRing<Quotient<BigRational>> mfac = new GenMatrixRing<Quotient<BigRational>>(qfac, n, n);
368        //System.out.println("mfac = " + mfac.toScript());
369        GenMatrixRing<Quotient<BigRational>> tfac = mfac.transpose();
370        @SuppressWarnings("unchecked")
371        Quotient<BigRational>[][] mm = new Quotient[n][n];
372        // ( {{1, a, 2}, {0, 1, 1}, {-1, 1, 1}} )
373        mm[0][0] = qfac.fromInteger(1);
374        mm[0][1] = a;
375        mm[0][2] = qfac.fromInteger(2);
376
377        mm[1][0] = qfac.getZERO();
378        mm[1][1] = qfac.fromInteger(1);
379        mm[1][2] = qfac.fromInteger(1);
380
381        mm[2][0] = qfac.fromInteger(-1);
382        mm[2][1] = qfac.fromInteger(1);
383        mm[2][2] = qfac.fromInteger(1);
384
385        GenMatrix<Quotient<BigRational>> A = new GenMatrix<Quotient<BigRational>>(mfac, mm);
386        //System.out.println("A:   " + A);
387
388        LinAlg<Quotient<BigRational>> lu = new LinAlg<Quotient<BigRational>>();
389
390        // test rowEchelonForm and rowEchelonFormSparse
391        GenMatrix<Quotient<BigRational>> B = lu.rowEchelonForm(A);
392        //System.out.println("B:   " + B);
393        long r = lu.rankRE(B);
394        GenMatrix<Quotient<BigRational>> D = lu.rowEchelonFormSparse(B);
395        //System.out.println("D:   " + D);
396        assertTrue("rank1 == rank2: ", lu.rankRE(D) == r);
397
398        // test LU decomposition
399        A = new GenMatrix<Quotient<BigRational>>(mfac, mm);
400        List<Integer> P = lu.decompositionLU(A);
401        //System.out.println("P  :   " + P);
402        //System.out.println("A  :   " + A.toScript());
403        //System.out.println("U  :   " + A.getUpper().toScript());
404
405        // test LU inverse
406        GenMatrix<Quotient<BigRational>> I = lu.inverseLU(A, P);
407        //System.out.println("I  :   " + I.toScript());
408
409        GenMatrix<Quotient<BigRational>> C = new GenMatrix<Quotient<BigRational>>(mfac, mm);
410        GenMatrix<Quotient<BigRational>> CI = C.multiply(I);
411        //System.out.println("C*I:   " + CI.toScript());
412        assertTrue("C*I == 1: ", CI.isONE());
413
414        GenMatrix<Quotient<BigRational>> C2 = C.sum(C);
415        GenMatrix<Quotient<BigRational>> CA = A.divide(C2);
416        GenMatrix<Quotient<BigRational>> AC = A.divideLeft(C2);
417        //System.out.println("C/A :    " + CA);
418        //System.out.println("A\\C :   " + AC);
419        assertFalse("C/A != A\\C: ", CA.equals(AC));
420    }
421
422}