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