001/*
002 * $Id: ReductionTest.java 4015 2012-07-22 12:05:38Z kredel $
003 */
004
005package edu.jas.gb;
006
007import java.util.List;
008import java.util.ArrayList;
009import java.util.Map;
010
011import junit.framework.Test;
012import junit.framework.TestCase;
013import junit.framework.TestSuite;
014
015import org.apache.log4j.BasicConfigurator;
016
017import edu.jas.structure.RingFactory;
018import edu.jas.arith.BigInteger;
019import edu.jas.arith.BigRational;
020import edu.jas.arith.BigComplex;
021import edu.jas.arith.Product;
022import edu.jas.arith.ProductRing;
023import edu.jas.poly.ExpVector;
024import edu.jas.poly.GenPolynomial;
025import edu.jas.poly.GenPolynomialRing;
026import edu.jas.poly.PolynomialList;
027
028
029/**
030 * Reduction tests with JUnit.
031 * @author Heinz Kredel.
032 */
033
034public class ReductionTest extends TestCase {
035
036    /**
037     * main
038     */
039    public static void main (String[] args) {
040        BasicConfigurator.configure();
041        junit.textui.TestRunner.run( suite() );
042    }
043
044    /**
045     * Constructs a <CODE>ReductionTest</CODE> object.
046     * @param name String
047     */
048    public ReductionTest(String name) {
049        super(name);
050    }
051
052    /**
053     * suite.
054     * @return a test suite.
055     */
056    public static Test suite() {
057        TestSuite suite= new TestSuite(ReductionTest.class);
058        return suite;
059    }
060
061    //private final static int bitlen = 100;
062
063    GenPolynomialRing<BigRational> fac;
064
065    GenPolynomial<BigRational> a;
066    GenPolynomial<BigRational> b;
067    GenPolynomial<BigRational> c;
068    GenPolynomial<BigRational> d;
069    GenPolynomial<BigRational> e;
070
071    List<GenPolynomial<BigRational>> L;
072    PolynomialList<BigRational> F;
073    PolynomialList<BigRational> G;
074
075    ReductionSeq<BigRational> red;
076    Reduction<BigRational> redpar;
077
078    int rl = 4; 
079    int kl = 10;
080    int ll = 11;
081    int el = 5;
082    float q = 0.6f;
083
084    protected void setUp() {
085        a = b = c = d = e = null;
086        fac = new GenPolynomialRing<BigRational>( new BigRational(0), rl );
087        red = new ReductionSeq<BigRational>();
088        redpar = new ReductionPar<BigRational>();
089    }
090
091    protected void tearDown() {
092        a = b = c = d = e = null;
093        fac = null;
094        red = null;
095        redpar = null;
096    }
097
098
099    /**
100     * Test constants and empty list reduction.
101     */
102    public void testRatReduction0() {
103        L = new ArrayList<GenPolynomial<BigRational>>();
104
105        a = fac.random(kl, ll, el, q );
106        c = fac.getONE();
107        d = fac.getZERO();
108
109        e = red.normalform( L, c );
110        assertTrue("isONE( e )", e.isONE() ); 
111
112        e = red.normalform( L, d );
113        assertTrue("isZERO( e )", e.isZERO() ); 
114
115
116        L.add( c );
117        e = red.normalform( L, c );
118        assertTrue("isZERO( e )", e.isZERO() ); 
119
120        e = red.normalform( L, a );
121        assertTrue("isZERO( e )", e.isZERO() ); 
122
123        e = red.normalform( L, d );
124        assertTrue("isZERO( e )", e.isZERO() ); 
125
126
127        L = new ArrayList<GenPolynomial<BigRational>>();
128        L.add( d );
129        e = red.normalform( L, c );
130        assertTrue("isONE( e )", e.isONE() ); 
131
132        e = red.normalform( L, d );
133        assertTrue("isZERO( e )", e.isZERO() ); 
134    }
135
136
137    /**
138     * Test parallel reduction with constants and empty list reduction.
139     */
140    public void testRatReductionPar0() {
141        L = new ArrayList<GenPolynomial<BigRational>>();
142
143        a = fac.random(kl, ll, el, q );
144        c = fac.getONE();
145        d = fac.getZERO();
146
147        e = redpar.normalform( L, c );
148        assertTrue("isONE( e )", e.isONE() ); 
149
150        e = redpar.normalform( L, d );
151        assertTrue("isZERO( e )", e.isZERO() ); 
152
153
154        L.add( c );
155        e = redpar.normalform( L, c );
156        assertTrue("isZERO( e )", e.isZERO() ); 
157
158        e = redpar.normalform( L, a );
159        assertTrue("isZERO( e )", e.isZERO() ); 
160
161        e = redpar.normalform( L, d );
162        assertTrue("isZERO( e )", e.isZERO() ); 
163
164
165        L = new ArrayList<GenPolynomial<BigRational>>();
166        L.add( d );
167        e = redpar.normalform( L, c );
168        assertTrue("isONE( e )", e.isONE() ); 
169
170        e = redpar.normalform( L, d );
171        assertTrue("isZERO( e )", e.isZERO() ); 
172    }
173
174
175    /**
176     * Test rational coefficient reduction.
177     * 
178     */
179    public void testRatReduction() {
180
181        a = fac.random(kl, ll, el, q );
182        b = fac.random(kl, ll, el, q );
183
184        assertTrue("not isZERO( a )", !a.isZERO() );
185
186        L = new ArrayList<GenPolynomial<BigRational>>();
187        L.add(a);
188
189        e = red.normalform( L, a );
190        assertTrue("isZERO( e )", e.isZERO() );
191
192        assertTrue("not isZERO( b )", !b.isZERO() );
193
194        L.add(b);
195        e = red.normalform( L, a );
196        assertTrue("isZERO( e ) some times", e.isZERO() ); 
197
198        e = red.SPolynomial( a, b );
199        //System.out.println("e = " + e);
200        ExpVector ce = a.leadingExpVector().lcm(b.leadingExpVector());
201        ExpVector ee = e.leadingExpVector();
202        assertTrue("lcm(lt(a),lt(b)) > lt(e) " + ce + " > " + ee, fac.tord.getAscendComparator().compare(ce,ee) > 0 ); // findbugs
203
204        L = new ArrayList<GenPolynomial<BigRational>>();
205        L.add( a );
206        assertTrue("isTopRed( a )", red.isTopReducible(L,a) ); 
207        assertTrue("isRed( a )", red.isReducible(L,a) ); 
208        b = fac.random(kl, ll, el, q );
209        L.add( b );
210        assertTrue("isTopRed( b )", red.isTopReducible(L,b) ); 
211        assertTrue("isRed( b )", red.isReducible(L,b) ); 
212        c = fac.random(kl, ll, el, q );
213        e = red.normalform( L, c );
214        assertTrue("isNF( e )", red.isNormalform(L,e) ); 
215    }
216
217
218    /**
219     * Test rational coefficient parallel reduction.
220     * 
221     */
222    public void testRatReductionPar() {
223
224        a = fac.random(kl, ll, el, q );
225        b = fac.random(kl, ll, el, q );
226     
227        assertTrue("not isZERO( a )", !a.isZERO() );
228
229        L = new ArrayList<GenPolynomial<BigRational>>();
230        L.add(a);
231
232        e = redpar.normalform( L, a );
233        assertTrue("isZERO( e )", e.isZERO() );
234
235        assertTrue("not isZERO( b )", !b.isZERO() );
236
237        L.add(b);
238        e = redpar.normalform( L, a );
239        assertTrue("isZERO( e ) some times", e.isZERO() ); 
240
241        L = new ArrayList<GenPolynomial<BigRational>>();
242        L.add( a );
243        assertTrue("isTopRed( a )", redpar.isTopReducible(L,a) ); 
244        assertTrue("isRed( a )", redpar.isReducible(L,a) ); 
245        b = fac.random(kl, ll, el, q );
246        L.add( b );
247        assertTrue("isTopRed( b )", redpar.isTopReducible(L,b) ); 
248        assertTrue("isRed( b )", redpar.isReducible(L,b) ); 
249        c = fac.random(kl, ll, el, q );
250        e = redpar.normalform( L, c );
251        assertTrue("isNF( e )", redpar.isNormalform(L,e) ); 
252    }
253
254
255    /**
256     * Test complex coefficient reduction.
257     * 
258     */
259    public void testComplexReduction() {
260
261        GenPolynomialRing<BigComplex> fac 
262            = new GenPolynomialRing<BigComplex>( new BigComplex(0), rl );
263
264        Reduction<BigComplex> cred = new ReductionSeq<BigComplex>();
265
266        GenPolynomial<BigComplex> a = fac.random(kl, ll, el, q );
267        GenPolynomial<BigComplex> b = fac.random(kl, ll, el, q );
268        GenPolynomial<BigComplex> c;
269
270        assertTrue("not isZERO( a )", !a.isZERO() );
271
272        List<GenPolynomial<BigComplex>> L 
273            = new ArrayList<GenPolynomial<BigComplex>>();
274        L.add(a);
275
276        GenPolynomial<BigComplex> e 
277            = cred.normalform( L, a );
278        assertTrue("isZERO( e )", e.isZERO() );
279
280        assertTrue("not isZERO( b )", !b.isZERO() );
281
282        L.add(b);
283        e = cred.normalform( L, a );
284        assertTrue("isZERO( e ) some times", e.isZERO() ); 
285
286        L = new ArrayList<GenPolynomial<BigComplex>>();
287        L.add( a );
288        assertTrue("isTopRed( a )", cred.isTopReducible(L,a) ); 
289        assertTrue("isRed( a )", cred.isReducible(L,a) ); 
290        b = fac.random(kl, ll, el, q );
291        L.add( b );
292        assertTrue("isTopRed( b )", cred.isTopReducible(L,b) ); 
293        assertTrue("isRed( b )", cred.isReducible(L,b) ); 
294        c = fac.random(kl, ll, el, q );
295        e = cred.normalform( L, c );
296        assertTrue("isNF( e )", cred.isNormalform(L,e) ); 
297    }
298
299
300    /**
301     * Test rational coefficient reduction with recording.
302     * 
303     */
304    public void testRatReductionRecording() {
305
306        List<GenPolynomial<BigRational>> row = null;
307
308
309        a = fac.random(kl, ll, el, q );
310        b = fac.random(kl, ll, el, q );
311        c = fac.random(kl, ll, el, q );
312        d = fac.random(kl, ll, el, q );
313
314        assertTrue("not isZERO( a )", !a.isZERO() );
315
316        L = new ArrayList<GenPolynomial<BigRational>>();
317
318        L.add(a);
319        row = new ArrayList<GenPolynomial<BigRational>>( L.size() );
320        for ( int m = 0; m < L.size(); m++ ) {
321            row.add(null);
322        }
323        e = red.normalform( row, L, a );
324        assertTrue("isZERO( e )", e.isZERO() );
325        assertTrue("not isZERO( b )", !b.isZERO() );
326        assertTrue("is Reduction ", red.isReductionNF(row,L,a,e) );
327
328        L.add(b);
329        row = new ArrayList<GenPolynomial<BigRational>>( L.size() );
330        for ( int m = 0; m < L.size(); m++ ) {
331            row.add(null);
332        }
333        e = red.normalform( row, L, b );
334        assertTrue("is Reduction ", red.isReductionNF(row,L,b,e) );
335
336        L.add(c);
337        row = new ArrayList<GenPolynomial<BigRational>>( L.size() );
338        for ( int m = 0; m < L.size(); m++ ) {
339            row.add(null);
340        }
341        e = red.normalform( row, L, c );
342        assertTrue("is Reduction ", red.isReductionNF(row,L,c,e) );
343
344        L.add(d);
345        row = new ArrayList<GenPolynomial<BigRational>>( L.size() );
346        for ( int m = 0; m < L.size(); m++ ) {
347            row.add(null);
348        }
349        e = red.normalform( row, L, d );
350        assertTrue("is Reduction ", red.isReductionNF(row,L,d,e) );
351    }
352
353
354    /**
355     * Test integer coefficient e-reduction.
356     * 
357     */
358    public void testIntegerEReduction() {
359
360        BigInteger bi = new BigInteger(0);
361        GenPolynomialRing<BigInteger> fac 
362            = new GenPolynomialRing<BigInteger>( bi, rl );
363
364        EReductionSeq<BigInteger> ered = new EReductionSeq<BigInteger>();
365
366        GenPolynomial<BigInteger> a = fac.random(kl, ll, el, q );
367        GenPolynomial<BigInteger> b = fac.random(kl, ll, el, q );
368
369        assertTrue("not isZERO( a )", !a.isZERO() );
370
371        List<GenPolynomial<BigInteger>> L 
372            = new ArrayList<GenPolynomial<BigInteger>>();
373        L.add(a);
374
375        GenPolynomial<BigInteger> e 
376            = ered.normalform( L, a );
377        //System.out.println("a = " + a);
378        //System.out.println("e = " + e);
379        assertTrue("isZERO( e )", e.isZERO() );
380
381        assertTrue("not isZERO( b )", !b.isZERO() );
382
383        L.add(b);
384        e = ered.normalform( L, a );
385        //System.out.println("b = " + b);
386        //System.out.println("e = " + e);
387        assertTrue("isZERO( e ) some times", e.isZERO() ); 
388
389        GenPolynomial<BigInteger> c = fac.getONE();
390        a = a.sum(c);
391        e = ered.normalform( L, a );
392        //System.out.println("b = " + b);
393        //System.out.println("e = " + e);
394        assertTrue("isONE( e ) some times", e.isONE() ); 
395
396        L = new ArrayList<GenPolynomial<BigInteger>>();
397        a = c.multiply( bi.fromInteger(4) );
398        b = c.multiply( bi.fromInteger(5) );
399        L.add( a );
400        e = ered.normalform( L, b );
401        //System.out.println("a = " + a);
402        //System.out.println("b = " + b);
403        //System.out.println("e = " + e);
404        assertTrue("isONE( e )", e.isONE() ); 
405
406        a = fac.random(kl, ll, el, q ); //.abs();
407        b = fac.random(kl, ll, el, q ); //.abs();
408        c = ered.GPolynomial( a, b );
409        e = ered.SPolynomial( a, b );
410        //System.out.println("a = " + a);
411        //System.out.println("b = " + b);
412        //System.out.println("c = " + c);
413        //System.out.println("e = " + e);
414
415        BigInteger ci = a.leadingBaseCoefficient().gcd( b.leadingBaseCoefficient() );
416        assertEquals("gcd(lbc(a),lbc(b)) = lbc(c) ", ci, c.leadingBaseCoefficient() ); 
417
418        ExpVector ce = a.leadingExpVector().lcm(b.leadingExpVector());
419        assertEquals("lcm(lt(a),lt(b)) == lt(c) ", ce, c.leadingExpVector() ); 
420        assertFalse("lcm(lt(a),lt(b)) != lt(e) ", ce.equals( e.leadingExpVector() ) ); 
421
422        L = new ArrayList<GenPolynomial<BigInteger>>();
423        L.add( a );
424        assertTrue("isTopRed( a )", ered.isTopReducible(L,a) ); 
425        assertTrue("isRed( a )", ered.isReducible(L,a) ); 
426        b = fac.random(kl, ll, el, q );
427        L.add( b );
428        assertTrue("isTopRed( b )", ered.isTopReducible(L,b) ); 
429        assertTrue("isRed( b )", ered.isReducible(L,b) ); 
430        c = fac.random(kl, ll, el, q );
431        e = ered.normalform( L, c );
432        assertTrue("isNF( e )", ered.isNormalform(L,e) ); 
433    }
434
435
436    /**
437     * Test integer coefficient d-reduction.
438     * 
439     */
440    public void testIntegerDReduction() {
441
442        BigInteger bi = new BigInteger(0);
443        GenPolynomialRing<BigInteger> fac 
444            = new GenPolynomialRing<BigInteger>( bi, rl );
445
446        DReductionSeq<BigInteger> dred = new DReductionSeq<BigInteger>();
447
448        GenPolynomial<BigInteger> a = fac.random(kl, ll, el, q );
449        GenPolynomial<BigInteger> b = fac.random(kl, ll, el, q );
450
451        assertTrue("not isZERO( a )", !a.isZERO() );
452
453        List<GenPolynomial<BigInteger>> L 
454            = new ArrayList<GenPolynomial<BigInteger>>();
455        L.add(a);
456
457        GenPolynomial<BigInteger> e 
458            = dred.normalform( L, a );
459        //System.out.println("a = " + a);
460        //System.out.println("e = " + e);
461        assertTrue("isZERO( e )", e.isZERO() );
462
463        assertTrue("not isZERO( b )", !b.isZERO() );
464
465        L.add(b);
466        e = dred.normalform( L, a );
467        //System.out.println("b = " + b);
468        //System.out.println("e = " + e);
469        assertTrue("isZERO( e ) some times", e.isZERO() ); 
470
471        GenPolynomial<BigInteger> c = fac.getONE();
472        a = a.sum(c);
473        e = dred.normalform( L, a );
474        //System.out.println("b = " + b);
475        //System.out.println("e = " + e);
476        assertTrue("isONE( e ) some times", e.isONE() ); 
477
478        L = new ArrayList<GenPolynomial<BigInteger>>();
479        a = c.multiply( bi.fromInteger(5) );
480        L.add( a );
481        b = c.multiply( bi.fromInteger(4) );
482        e = dred.normalform( L, b );
483        //System.out.println("a = " + a);
484        //System.out.println("b = " + b);
485        //System.out.println("e = " + e);
486        assertTrue("nf(b) = b ", e.equals(b) ); 
487
488        a = fac.random(kl, ll, el, q ); //.abs();
489        b = fac.random(kl, ll, el, q ); //.abs();
490        c = dred.GPolynomial( a, b );
491        e = dred.SPolynomial( a, b );
492        //System.out.println("a = " + a);
493        //System.out.println("b = " + b);
494        //System.out.println("c = " + c);
495        //System.out.println("e = " + e);
496
497        BigInteger ci = a.leadingBaseCoefficient().gcd( b.leadingBaseCoefficient() );
498        assertEquals("gcd(lbc(a),lbc(b)) = lbc(c) ", ci, c.leadingBaseCoefficient() ); 
499
500        ExpVector ce = a.leadingExpVector().lcm(b.leadingExpVector());
501        assertEquals("lcm(lt(a),lt(b)) == lt(c) ", ce, c.leadingExpVector() ); 
502        assertFalse("lcm(lt(a),lt(b)) != lt(e) ", ce.equals( e.leadingExpVector() ) ); 
503
504        L = new ArrayList<GenPolynomial<BigInteger>>();
505        L.add( a );
506        assertTrue("isTopRed( a )", dred.isTopReducible(L,a) ); 
507        assertTrue("isRed( a )", dred.isReducible(L,a) ); 
508        b = fac.random(kl, ll, el, q );
509        L.add( b );
510        assertTrue("isTopRed( b )", dred.isTopReducible(L,b) ); 
511        assertTrue("isRed( b )", dred.isReducible(L,b) ); 
512        c = fac.random(kl, ll, el, q );
513        e = dred.normalform( L, c );
514        assertTrue("isNF( e )", dred.isNormalform(L,e) ); 
515    }
516
517}