Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.poly;
006
007
008import java.io.IOException;
009import java.io.StringReader;
010import java.util.ArrayList;
011import java.util.List;
012
013import edu.jas.arith.BigComplex;
014import edu.jas.arith.BigInteger;
015import edu.jas.arith.BigRational;
016import edu.jas.structure.RingElem;
017
018import junit.framework.Test;
019import junit.framework.TestCase;
020import junit.framework.TestSuite;
021
022
023/**
024 * GenWordPolynomial tests with JUnit.
025 * @author Heinz Kredel
026 */
027
028public class GenWordPolynomialTest extends TestCase {
029
030
031    /**
032     * main
033     */
034    public static void main(String[] args) {
035        junit.textui.TestRunner.run(suite());
036    }
037
038
039    /**
040     * Constructs a <CODE>GenWordPolynomialTest</CODE> object.
041     * @param name String.
042     */
043    public GenWordPolynomialTest(String name) {
044        super(name);
045    }
046
047
048    /**
049     * suite.
050     */
051    public static Test suite() {
052        TestSuite suite = new TestSuite(GenWordPolynomialTest.class);
053        return suite;
054    }
055
056
057    int rl = 6;
058
059
060    int kl = 10;
061
062
063    int ll = 7;
064
065
066    int el = 5;
067
068
069    @Override
070    protected void setUp() {
071    }
072
073
074    @Override
075    protected void tearDown() {
076    }
077
078
079    /**
080     * Test constructors and factory.
081     */
082    public void testConstructors() {
083        // integers
084        BigInteger rf = new BigInteger();
085        //System.out.println("rf = " + rf);
086
087        // non-commuting vars: abcdef
088        WordFactory wf = new WordFactory("abcdef");
089        //System.out.println("wf = " + wf);
090
091        // polynomials over integers
092        GenWordPolynomialRing<BigInteger> pf = new GenWordPolynomialRing<BigInteger>(rf, wf);
093        //System.out.println("pf = " + pf);
094        assertFalse("not commutative", pf.isCommutative());
095        assertTrue("associative", pf.isAssociative());
096        assertFalse("not field", pf.isField());
097
098        String s = pf.toScript();
099        //System.out.println("pf.toScript: " + s + ", " + s.length());
100        assertEquals("#s == 32: " + s, s.length(), 32);
101
102        s = pf.toString();
103        //System.out.println("pf.toString: " + s + ", " + s.length());
104        assertEquals("#s == 32: " + s, s.length(), 32);
105
106        GenWordPolynomial<BigInteger> p = pf.getONE();
107        //System.out.println("p = " + p);
108        assertTrue("p == 1", p.isONE());
109        p = pf.getZERO();
110        assertTrue("p == 0", p.isZERO());
111        //System.out.println("p = " + p);
112        //p = pf.random(9);
113        //System.out.println("p = " + p);
114
115        List<GenWordPolynomial<BigInteger>> gens = pf.generators();
116        //System.out.println("gens = " + gens);
117        assertTrue("#gens == 7", gens.size() == 7);
118
119        RingElem<GenWordPolynomial<BigInteger>> pe = new GenWordPolynomial<BigInteger>(pf);
120        //System.out.println("pe = " + pe);
121        //System.out.println("p.equals(pe) = " + p.equals(pe) );
122        //System.out.println("p.equals(p) = " + p.equals(p) );
123        assertTrue("p.equals(pe) = ", p.equals(pe));
124        assertTrue("p.equals(p) = ", p.equals(p));
125
126        pe = pe.sum(p);
127        //System.out.println("pe = " + pe);
128        assertTrue("pe.isZERO() = ", pe.isZERO());
129        p = pf.random(9);
130        p = p.subtract(p);
131        //System.out.println("p = " + p);
132        //System.out.println("p.isZERO() = " + p.isZERO());
133        assertTrue("p.isZERO() = ", p.isZERO());
134
135        // polynomials over (polynomials over integers)
136        // non-commuting vars: xyz
137        WordFactory wf2 = new WordFactory("xyz");
138        //System.out.println("wf2 = " + wf2);
139
140        GenWordPolynomialRing<GenWordPolynomial<BigInteger>> ppf = new GenWordPolynomialRing<GenWordPolynomial<BigInteger>>(
141                        pf, wf2);
142        //System.out.println("ppf = " + ppf);
143
144        GenWordPolynomial<GenWordPolynomial<BigInteger>> pp = ppf.getONE();
145        //System.out.println("pp = " + pp);
146        assertTrue("pp == 1", pp.isONE());
147        //pp = ppf.random(2);
148        //System.out.println("pp = " + pp);
149        pp = ppf.getZERO();
150        //System.out.println("pp = " + pp);
151        assertTrue("pp == 0", pp.isZERO());
152
153        List<GenWordPolynomial<GenWordPolynomial<BigInteger>>> pgens = ppf.generators();
154        //System.out.println("pgens = " + pgens);
155        assertTrue("#pgens == 7+3", pgens.size() == 10);
156
157        RingElem<GenWordPolynomial<GenWordPolynomial<BigInteger>>> ppe = new GenWordPolynomial<GenWordPolynomial<BigInteger>>(
158                        ppf);
159        //System.out.println("ppe = " + ppe);
160        //System.out.println("pp.equals(ppe) = " + pp.equals(ppe) );
161        //System.out.println("pp.equals(pp) = " + pp.equals(pp) );
162        assertTrue("pp.equals(ppe) = ", pp.equals(ppe));
163        assertTrue("pp.equals(pp) = ", pp.equals(pp));
164
165        ppe = ppe.sum(pp); // why not pp = pp.add(ppe) ?
166        //System.out.println("ppe = " + ppe);
167        assertTrue("ppe.isZERO() = ", ppe.isZERO());
168        pp = ppf.random(2);
169        pp = pp.subtract(pp);
170        //System.out.println("pp = " + pp);
171        //System.out.println("pp.isZERO() = " + pp.isZERO());
172        assertTrue("pp.isZERO() = ", pp.isZERO());
173
174        // polynomials over (polynomials over (polynomials over integers))
175        // non-commuting vars: uvw
176        WordFactory wf3 = new WordFactory("uvw");
177        //System.out.println("wf3 = " + wf3);
178        GenWordPolynomialRing<GenWordPolynomial<GenWordPolynomial<BigInteger>>> pppf = new GenWordPolynomialRing<GenWordPolynomial<GenWordPolynomial<BigInteger>>>(
179                        ppf, wf3);
180        //System.out.println("pppf = " + pppf);
181
182        GenWordPolynomial<GenWordPolynomial<GenWordPolynomial<BigInteger>>> ppp = pppf.getONE();
183        //System.out.println("ppp = " + ppp);
184        assertTrue("ppp == 1", ppp.isONE());
185        //ppp = pppf.random(2);
186        //System.out.println("ppp = " + ppp);
187        ppp = pppf.getZERO();
188        //System.out.println("ppp = " + ppp);
189        assertTrue("ppp == 0", ppp.isZERO());
190
191        List<GenWordPolynomial<GenWordPolynomial<GenWordPolynomial<BigInteger>>>> ppgens = pppf.generators();
192        //System.out.println("ppgens = " + ppgens);
193        assertTrue("#ppgens == 7+3+3", ppgens.size() == 13);
194
195        RingElem<GenWordPolynomial<GenWordPolynomial<GenWordPolynomial<BigInteger>>>> pppe = new GenWordPolynomial<GenWordPolynomial<GenWordPolynomial<BigInteger>>>(
196                        pppf);
197        //System.out.println("pppe = " + pppe);
198        // System.out.println("ppp.equals(pppe) = " + ppp.equals(pppe) );
199        // System.out.println("ppp.equals(ppp) = " + ppp.equals(ppp) );
200        assertTrue("ppp.equals(pppe) = ", ppp.equals(pppe));
201        assertTrue("ppp.equals(ppp) = ", ppp.equals(ppp));
202
203        pppe = pppe.sum(ppp);
204        //System.out.println("pppe = " + pppe);
205        assertTrue("pppe.isZERO() = ", pppe.isZERO());
206        //ppp = pppf.random(2);
207        ppp = ppp.subtract(ppp);
208        //System.out.println("ppp = " + ppp);
209        //System.out.println("ppp.isZERO() = " + ppp.isZERO());
210        assertTrue("ppp.isZERO() = ", ppp.isZERO());
211    }
212
213
214    /**
215     * Test accessors.
216     */
217    public void testAccessors() {
218        // integers
219        BigInteger rf = new BigInteger();
220        // System.out.println("rf = " + rf);
221
222        // non-commuting vars: abcdef
223        WordFactory wf = new WordFactory("abcdef");
224        //System.out.println("wf = " + wf);
225
226        // polynomials over integers
227        GenWordPolynomialRing<BigInteger> pf = new GenWordPolynomialRing<BigInteger>(rf, wf);
228        //System.out.println("pf = " + pf);
229
230        // test 1
231        GenWordPolynomial<BigInteger> p = pf.getONE();
232        //System.out.println("p = " + p);
233
234        Word e = p.leadingWord();
235        BigInteger c = p.leadingBaseCoefficient();
236
237        GenWordPolynomial<BigInteger> f = new GenWordPolynomial<BigInteger>(pf, c, e);
238        assertEquals("1 == 1 ", p, f);
239
240        GenWordPolynomial<BigInteger> r = p.reductum();
241        assertTrue("red(1) == 0 ", r.isZERO());
242
243        // test 0
244        p = pf.getZERO();
245        // System.out.println("p = " + p);
246        e = p.leadingWord();
247        c = p.leadingBaseCoefficient();
248
249        f = new GenWordPolynomial<BigInteger>(pf, c, e);
250        assertEquals("0 == 0 ", p, f);
251
252        r = p.reductum();
253        assertTrue("red(0) == 0 ", r.isZERO());
254
255        // test random
256        p = pf.random(kl, ll, el);
257        // System.out.println("p = " + p);
258        e = p.leadingWord();
259        c = p.leadingBaseCoefficient();
260        r = p.reductum();
261
262        f = new GenWordPolynomial<BigInteger>(pf, c, e);
263        f = r.sum(f);
264        assertEquals("p == lm(f)+red(f) ", p, f);
265
266        // test iteration over random
267        GenWordPolynomial<BigInteger> g;
268        g = p;
269        f = pf.getZERO();
270        while (!g.isZERO()) {
271            e = g.leadingWord();
272            c = g.leadingBaseCoefficient();
273            //System.out.println("c e = " + c + " " + e);
274            r = g.reductum();
275            f = f.sum(c, e);
276            g = r;
277        }
278        assertEquals("p == lm(f)+lm(red(f))+... ", p, f);
279    }
280
281
282    /**
283     * Test addition.
284     */
285    public void testAddition() {
286        // integers
287        BigInteger rf = new BigInteger();
288        // System.out.println("rf = " + rf);
289
290        // non-commuting vars: abcdef
291        WordFactory wf = new WordFactory("abcdef");
292        //System.out.println("wf = " + wf);
293
294        // polynomials over integers
295        GenWordPolynomialRing<BigInteger> fac = new GenWordPolynomialRing<BigInteger>(rf, wf);
296        //System.out.println("fac = " + fac);
297
298        GenWordPolynomial<BigInteger> a = fac.random(kl, ll, el);
299        GenWordPolynomial<BigInteger> b = fac.random(kl, ll, el);
300
301        GenWordPolynomial<BigInteger> c = a.sum(b);
302        GenWordPolynomial<BigInteger> d = c.subtract(b);
303        GenWordPolynomial<BigInteger> e;
304        assertEquals("a+b-b = a", a, d);
305        //System.out.println("a = " + a);
306        //System.out.println("b = " + b);
307        //System.out.println("c = " + c);
308        //System.out.println("d = " + d);
309        assertTrue("deg(a+b) >= deg(a)", c.degree() >= a.degree());
310        assertTrue("deg(a+b) >= deg(b)", c.degree() >= b.degree());
311
312        c = fac.random(kl, ll, el);
313        //System.out.println("\nc = " + c);
314        d = a.sum(b.sum(c));
315        e = (a.sum(b)).sum(c);
316
317        //System.out.println("d = " + d);
318        //System.out.println("e = " + e);
319        //System.out.println("d-e = " + d.subtract(e) );
320        assertEquals("a+(b+c) = (a+b)+c", d, e);
321
322        Word u = wf.random(rl);
323        BigInteger x = rf.random(kl);
324
325        b = new GenWordPolynomial<BigInteger>(fac, x, u);
326        c = a.sum(b);
327        d = a.sum(x, u);
328        assertEquals("a+p(x,u) = a+(x,u)", c, d);
329        //System.out.println("\nc = " + c);
330        //System.out.println("d = " + d);
331
332        c = a.subtract(b);
333        d = a.subtract(x, u);
334        assertEquals("a-p(x,u) = a-(x,u)", c, d);
335        //System.out.println("c = " + c);
336        //System.out.println("d = " + d);
337
338        //a = new GenWordPolynomial<BigInteger>(fac);
339        b = new GenWordPolynomial<BigInteger>(fac, x, u);
340        c = b.sum(a);
341        d = a.sum(x, u);
342        assertEquals("a+p(x,u) = a+(x,u)", c, d);
343        //System.out.println("a = " + a);
344        //System.out.println("b = " + b);
345        //System.out.println("c = " + c);
346        //System.out.println("d = " + d);
347
348        c = a.subtract(b);
349        d = a.subtract(x, u);
350        assertEquals("a-p(x,u) = a-(x,u)", c, d);
351        //System.out.println("c = " + c);
352        //System.out.println("d = " + d);
353    }
354
355
356    /**
357     * Test multiplication.
358     */
359    public void testMultiplication() {
360        // integers
361        BigInteger rf = new BigInteger();
362        // System.out.println("rf = " + rf);
363
364        // non-commuting vars: abcdef
365        WordFactory wf = new WordFactory("abcdef");
366        //System.out.println("wf = " + wf);
367
368        // polynomials over integers
369        GenWordPolynomialRing<BigInteger> fac = new GenWordPolynomialRing<BigInteger>(rf, wf);
370        //System.out.println("fac = " + fac);
371
372        GenWordPolynomial<BigInteger> a = fac.random(kl, ll, el);
373        GenWordPolynomial<BigInteger> b = fac.random(kl, ll, el);
374
375        GenWordPolynomial<BigInteger> c = a.multiply(b);
376        GenWordPolynomial<BigInteger> d = b.multiply(a);
377        GenWordPolynomial<BigInteger> e;
378        assertFalse("a*b != b*a", c.equals(d));
379        //System.out.println("a = " + a);
380        //System.out.println("b = " + b);
381        //System.out.println("c = " + c);
382        //System.out.println("d = " + d);
383        assertTrue("maxNorm(a*b) >= maxNorm(a)", c.maxNorm().compareTo(a.maxNorm()) >= 0);
384        assertTrue("maxNorm(a*b) >= maxNorm(b)", c.maxNorm().compareTo(b.maxNorm()) >= 0);
385
386        c = fac.random(kl, ll, el);
387        //System.out.println("c = " + c);
388        d = a.multiply(b.multiply(c));
389        e = (a.multiply(b)).multiply(c);
390
391        //System.out.println("d = " + d);
392        //System.out.println("e = " + e);
393        //System.out.println("d-e = " + d.subtract(c) );
394        assertEquals("a*(b*c) = (a*b)*c", d, e);
395
396        Word u = wf.random(rl);
397        BigInteger x = rf.random(kl);
398
399        b = new GenWordPolynomial<BigInteger>(fac, x, u);
400        c = a.multiply(b);
401        d = a.multiply(x, u);
402        assertEquals("a*p(x,u) = a*(x,u)", c, d);
403        //System.out.println("c = " + c);
404        //System.out.println("d = " + d);
405
406        //a = new GenWordPolynomial<BigInteger>(fac);
407        b = new GenWordPolynomial<BigInteger>(fac, x, u);
408        c = a.multiply(b);
409        d = a.multiply(x, u);
410        assertEquals("a*p(x,u) = a*(x,u)", c, d);
411        //System.out.println("a = " + a);
412        //System.out.println("b = " + b);
413        //System.out.println("c = " + c);
414        //System.out.println("d = " + d);
415
416        BigInteger y = rf.random(kl);
417        c = a.multiply(x, y);
418        //System.out.println("c = " + c);
419        d = a.multiply(y, x);
420        //System.out.println("d = " + d);
421        assertEquals("x a y = y a x", c, d);
422    }
423
424
425    /**
426     * Test distributive law.
427     */
428    public void testDistributive() {
429        // integers
430        BigInteger rf = new BigInteger();
431        // System.out.println("rf = " + rf);
432
433        // non-commuting vars: abcdef
434        WordFactory wf = new WordFactory("abcdef");
435        //System.out.println("wf = " + wf);
436
437        // polynomials over integers
438        GenWordPolynomialRing<BigInteger> fac = new GenWordPolynomialRing<BigInteger>(rf, wf);
439        //System.out.println("fac = " + fac);
440
441        GenWordPolynomial<BigInteger> a = fac.random(kl, ll, el);
442        GenWordPolynomial<BigInteger> b = fac.random(kl, ll, el);
443        GenWordPolynomial<BigInteger> c = fac.random(kl, ll, el);
444        GenWordPolynomial<BigInteger> d, e;
445
446        d = a.multiply(b.sum(c));
447        e = a.multiply(b).sum(a.multiply(c));
448
449        assertEquals("a(b+c) = ab+ac", d, e);
450    }
451
452
453    /**
454     * Test univariate division.
455     */
456    public void testUnivDivision() {
457        // rational numbers
458        BigRational rf = new BigRational();
459        //System.out.println("rf = " + rf);
460
461        // non-commuting vars: x
462        WordFactory wf = new WordFactory("x");
463        //System.out.println("wf = " + wf);
464
465        // polynomials over rational numbers
466        GenWordPolynomialRing<BigRational> fac = new GenWordPolynomialRing<BigRational>(rf, wf);
467        //System.out.println("fac = " + fac);
468
469        GenWordPolynomial<BigRational> a = fac.random(7, ll, el).monic();
470        GenWordPolynomial<BigRational> b = fac.random(7, ll, el).monic();
471
472        GenWordPolynomial<BigRational> c = a.multiply(b);
473        GenWordPolynomial<BigRational> d = b.multiply(a);
474        GenWordPolynomial<BigRational> e, f;
475        assertTrue("a*b == b*a", c.equals(d)); // since univariate
476        //System.out.println("a = " + a);
477        //System.out.println("b = " + b);
478        //System.out.println("c = " + c);
479        //System.out.println("d = " + d);
480
481        e = c.divide(a);
482        //System.out.println("e = " + e);
483        assertTrue("a*b/a == b", b.equals(e));
484        d = c.divide(b);
485        //System.out.println("d = " + d);
486        assertTrue("a*b/b == a", a.equals(d));
487
488        d = c.gcd(a);
489        //System.out.println("d = " + d);
490        assertTrue("gcd(a*b,a) == a", a.equals(d));
491
492        d = a.gcd(b);
493        //System.out.println("d = " + d);
494        if (d.isConstant()) {
495            assertTrue("gcd(b,a) == 1", d.isONE());
496        } else {
497            return;
498        }
499        d = a.modInverse(b);
500        //System.out.println("d = " + d);
501        e = d.multiply(a);
502        //System.out.println("e = " + e);
503        f = e.remainder(b);
504        //System.out.println("f = " + f);
505        assertTrue("d * a == 1 mod b ", f.isONE());
506
507        GenWordPolynomial<BigRational>[] egcd;
508        egcd = a.egcd(b);
509        d = egcd[0];
510        e = egcd[1];
511        f = egcd[2];
512        //System.out.println("d = " + d);
513        //System.out.println("e = " + e);
514        //System.out.println("f = " + f);
515        c = e.multiply(a).sum(f.multiply(b));
516        //System.out.println("d = " + d);
517        assertEquals("gcd(a,b) == e*a + f*b", c, d); // since univariate
518    }
519
520
521    /**
522     * Test multivariate 2 division.
523     */
524    public void testMulti2Division() {
525        // rational numbers
526        BigRational rf = new BigRational();
527        // System.out.println("rf = " + rf);
528
529        // non-commuting vars: xy
530        WordFactory wf = new WordFactory("xy");
531        //System.out.println("wf = " + wf);
532
533        // polynomials over rational numbers
534        GenWordPolynomialRing<BigRational> fac = new GenWordPolynomialRing<BigRational>(rf, wf);
535        //System.out.println("fac = " + fac);
536
537        GenWordPolynomial<BigRational> a = fac.random(7, ll, el).monic();
538        GenWordPolynomial<BigRational> b = fac.random(7, ll, el).monic();
539
540        GenWordPolynomial<BigRational> c = a.multiply(b);
541        GenWordPolynomial<BigRational> d = b.multiply(a);
542        GenWordPolynomial<BigRational> e, f;
543        assertFalse("a*b == b*a", c.equals(d));
544        //System.out.println("a = " + a);
545        //System.out.println("b = " + b);
546        //System.out.println("c = " + c);
547        //System.out.println("d = " + d);
548
549        e = c.divide(a);
550        //System.out.println("e = " + e);
551        assertTrue("a*b/a == b", b.equals(e));
552        f = d.divide(b);
553        //System.out.println("f = " + f);
554        assertTrue("a*b/b == a", a.equals(f));
555
556        try {
557            f = a.divide(b);
558            //System.out.println("f = " + f);
559        } catch (RuntimeException re) {
560            System.out.println("a divide b fail: " + a + ", " + b);
561            return;
562        }
563        WordFactory.WordComparator cmp = fac.alphabet.getDescendComparator();
564        f = a.remainder(b);
565        //System.out.println("a = " + a);
566        //System.out.println("f = " + f);
567        assertTrue("a rem2 b <= a", cmp.compare(a.leadingWord(), f.leadingWord()) <= 0);
568    }
569
570
571    /**
572     * Test multivariate 3 division.
573     */
574    public void testMulti3Division() {
575        // rational numbers
576        BigRational rf = new BigRational();
577        // System.out.println("rf = " + rf);
578
579        // non-commuting vars: xyz
580        WordFactory wf = new WordFactory("xyz");
581        //System.out.println("wf = " + wf);
582
583        // polynomials over rational numbers
584        GenWordPolynomialRing<BigRational> fac = new GenWordPolynomialRing<BigRational>(rf, wf);
585        //System.out.println("fac = " + fac);
586
587        GenWordPolynomial<BigRational> a = fac.random(7, ll, el).monic();
588        GenWordPolynomial<BigRational> b = fac.random(7, ll, el).monic();
589
590        GenWordPolynomial<BigRational> c = a.multiply(b);
591        GenWordPolynomial<BigRational> d = b.multiply(a);
592        GenWordPolynomial<BigRational> e, f;
593        assertFalse("a*b == b*a", c.equals(d));
594        //System.out.println("a = " + a);
595        //System.out.println("b = " + b);
596        //System.out.println("c = " + c);
597        //System.out.println("d = " + d);
598
599        e = c.divide(a);
600        //System.out.println("e = " + e);
601        assertTrue("a*b/a == b", b.equals(e));
602        f = d.divide(b);
603        //System.out.println("f = " + f);
604        assertTrue("a*b/b == a", a.equals(f));
605
606        try {
607            f = a.divide(b);
608            //System.out.println("f = " + f);
609        } catch (RuntimeException re) {
610            System.out.println("a divide b fail: " + a + ", " + b);
611            return;
612        }
613        WordFactory.WordComparator cmp = fac.alphabet.getDescendComparator();
614        f = a.remainder(b);
615        //System.out.println("a = " + a);
616        //System.out.println("f = " + f);
617        assertTrue("a rem3 b <= a: " + a.leadingWord() + ", " + f.leadingWord(),
618                        cmp.compare(a.leadingWord(), f.leadingWord()) <= 0);
619    }
620
621
622    /**
623     * Test polynomial and solvable coefficients.
624     */
625    public void testCoefficients() {
626        // integers
627        BigComplex rf = new BigComplex();
628        //System.out.println("rf = " + rf);
629
630        // commuting vars: uvw
631        String[] cvar = new String[] { "u", "v", "w" };
632        GenPolynomialRing<BigComplex> cf = new GenPolynomialRing<BigComplex>(rf, cvar);
633        //System.out.println("cf = " + cf);
634
635        // solvable vars: x1 x2 y1 y2
636        String[] svar = new String[] { "x1", "x2", "y1", "y2" };
637        GenSolvablePolynomialRing<GenPolynomial<BigComplex>> sf;
638        sf = new GenSolvablePolynomialRing<GenPolynomial<BigComplex>>(cf, svar);
639        //System.out.println("sf = " + sf);
640        RelationGenerator<GenPolynomial<BigComplex>> wr = new WeylRelations<GenPolynomial<BigComplex>>();
641        wr.generate(sf);
642        //System.out.println("sf = " + sf);
643
644        // non-commuting vars: abcdef
645        WordFactory wf = new WordFactory("abcdef");
646        //System.out.println("wf = " + wf);
647        // non-commuting polynomials over commuting and solvable coefficients
648        GenWordPolynomialRing<GenPolynomial<GenPolynomial<BigComplex>>> nf;
649        nf = new GenWordPolynomialRing<GenPolynomial<GenPolynomial<BigComplex>>>(sf, wf);
650        //want: GenWordPolynomialRing<GenSolvablePolynomial<GenPolynomial<BigComplex>>> nf;
651        //System.out.println("nf = " + nf.toScript());
652
653        assertFalse("not commutative", nf.isCommutative());
654        assertTrue("associative", nf.isAssociative());
655        assertFalse("not field", nf.isField());
656
657        GenWordPolynomial<GenPolynomial<GenPolynomial<BigComplex>>> p = nf.getONE();
658        //System.out.println("p = " + p);
659        assertTrue("p == 1", p.isONE());
660        p = nf.getZERO();
661        //System.out.println("p = " + p);
662        assertTrue("p == 0", p.isZERO());
663        p = nf.random(3);
664        //System.out.println("p = " + p);
665        //p = p.sum(p);
666        p = p.multiply(p);
667        //System.out.println("p = " + p);
668        p = p.subtract(p);
669        //System.out.println("p = " + p);
670        assertTrue("p == 0", p.isZERO());
671
672        List<GenWordPolynomial<GenPolynomial<GenPolynomial<BigComplex>>>> gens = nf.generators();
673        //System.out.println("gens = " + gens);
674        assertTrue("#gens == 2+3+4+6", gens.size() == 15);
675    }
676
677
678    /**
679     * Test contraction.
680     */
681    public void testContraction() {
682        // integers
683        BigInteger rf = new BigInteger();
684        //System.out.println("rf = " + rf);
685
686        // non-commuting vars: abcdef
687        WordFactory wf = new WordFactory("abcdef");
688        //System.out.println("wf = " + wf);
689        WordFactory wfs = new WordFactory("abc");
690        //System.out.println("wf = " + wf);
691
692        // polynomials over integers
693        GenWordPolynomialRing<BigInteger> pf = new GenWordPolynomialRing<BigInteger>(rf, wf);
694        //System.out.println("pf = " + pf);
695        GenWordPolynomialRing<BigInteger> pfs = new GenWordPolynomialRing<BigInteger>(rf, wfs);
696        //System.out.println("pfs = " + pfs);
697
698        List<GenWordPolynomial<BigInteger>> H = new ArrayList<GenWordPolynomial<BigInteger>>();
699
700        GenWordPolynomial<BigInteger> a = pf.random(5).abs();
701        //System.out.println("a = " + a);
702        GenWordPolynomial<BigInteger> as = pfs.random(5).abs();
703        //System.out.println("as = " + as);
704        GenWordPolynomial<BigInteger> asf = pf.valueOf(as);
705        H.add(asf);
706        H.add(asf.multiply(pf.valueOf(pfs.random(5).abs())));
707        H.add(pfs.random(5).abs());
708        //System.out.println("asf = " + asf);
709        GenWordPolynomial<BigInteger> asfc = asf.contract(pfs);
710        //System.out.println("asfc = " + asfc);
711        assertEquals("as == contract(extend(as)): ", as, asfc);
712
713        // mostly not contractable
714        GenWordPolynomial<BigInteger> ac = a.contract(pfs);
715        H.add(a);
716        //System.out.println("ac = " + ac);
717        assertTrue("contract(a) == 0: " + ac, ac.isZERO() || pf.valueOf(ac).equals(a));
718
719        // 1 always contractable
720        a = pf.getONE();
721        H.add(a);
722        ac = a.contract(pfs);
723        //System.out.println("ac = " + ac);
724        assertTrue("contract(1) == 1: ", ac.isONE());
725
726        // now contract lists of word polynomials
727        //System.out.println("H = " + H);
728        List<GenWordPolynomial<BigInteger>> M = PolyUtil.<BigInteger> intersect(pfs, H);
729        //System.out.println("M = " + M);
730        int i = 0;
731        for (GenWordPolynomial<BigInteger> h : H) {
732            if (!h.contract(pfs).isZERO()) {
733                assertEquals("extend(contract(h)) == h: " + h, h, pf.valueOf(M.get(i++)));
734            }
735        }
736    }
737
738
739    /**
740     * Test constructors and factory.
741     */
742    @SuppressWarnings("unchecked")
743    public void testParser() {
744        BigInteger rf = new BigInteger();
745        //System.out.println("rf = " + rf.toScriptFactory());
746
747        // non-commuting vars: abcdef
748        String[] sa = new String[] { "a", "b", "c", "d", "e", "f" };
749        WordFactory wf = new WordFactory(sa);
750        //System.out.println("wf = " + wf.toScript());
751
752        // word polynomials over integers
753        GenWordPolynomialRing<BigInteger> pf = new GenWordPolynomialRing<BigInteger>(rf, wf);
754        //System.out.println("pf = " + pf.toScript());
755        assertFalse("not commutative", pf.isCommutative());
756        assertTrue("associative", pf.isAssociative());
757        assertFalse("not field", pf.isField());
758
759        List<GenWordPolynomial<BigInteger>> gens = pf.generators();
760        //System.out.println("pf = " + gens);
761        GenWordPolynomial<BigInteger> ga, gb, crel;
762        ga = gens.get(1);
763        gb = gens.get(2);
764        //System.out.println("ga = " + ga + ", " + ga.toScript());
765        //System.out.println("gb = " + gb);
766        assertEquals("#s == 3: ", ga.toString().length(), 3);
767        assertEquals("#s == 1: ", ga.toScript().length(), 1);
768
769        crel = ga.multiply(gb).subtract(gb.multiply(ga));
770        //System.out.println("crel = " + crel);
771
772        StringReader sr = new StringReader("a b - b a, b c - c b");
773        GenPolynomialTokenizer tok = new GenPolynomialTokenizer(sr);
774
775        GenWordPolynomial<BigInteger> a;
776        // parse of tokenizer
777        try {
778            a = (GenWordPolynomial) tok.nextWordPolynomial(pf);
779        } catch (IOException e) {
780            a = null;
781            e.printStackTrace();
782        }
783        //System.out.println("a = " + a);
784        assertEquals("parse() == ab - ba: ", a, crel);
785
786        // now parse of factory
787        a = pf.parse("a b - b a");
788        //System.out.println("a = " + a);
789        assertEquals("parse() == ab - ba: ", a, crel);
790
791        // polynomials over integers
792        GenPolynomialRing<BigInteger> fac = new GenPolynomialRing<BigInteger>(rf, sa);
793        //System.out.println("fac = " + fac.toScript());
794        assertTrue("commutative", fac.isCommutative());
795        assertTrue("associative", fac.isAssociative());
796        assertFalse("not field", fac.isField());
797
798        sr = new StringReader("a b - b a, b c - c b");
799        tok = new GenPolynomialTokenizer(fac, sr);
800        // parse of tokenizer
801        try {
802            a = (GenWordPolynomial) tok.nextWordPolynomial();
803        } catch (IOException e) {
804            a = null;
805            e.printStackTrace();
806        }
807        //System.out.println("a = " + a);
808        assertEquals("parse() == ab - ba: ", a, crel);
809    }
810
811
812    /**
813     * Test iterators.
814     */
815    public void testIterators() {
816        // integers
817        BigInteger rf = new BigInteger();
818        //System.out.println("rf = " + rf);
819
820        // word polynomials over integral numbers
821        GenWordPolynomialRing<BigInteger> pf = new GenWordPolynomialRing<BigInteger>(rf, "abcdef");
822        //System.out.println("pf = " + pf);
823
824        // random polynomial
825        GenWordPolynomial<BigInteger> p = pf.random(kl, 2 * ll, el);
826        //System.out.println("p = " + p);
827
828        // test monomials
829        for (WordMonomial<BigInteger> m : p) {
830            //System.out.println("m = " + m);
831            assertFalse("m.c == 0 ", m.coefficient().isZERO());
832            assertFalse("m.e < (0) ", m.word().signum() < 0);
833        }
834    }
835
836}