001 /*
002 * $Id: ReductionTest.java 3425 2010-12-24 12:53:29Z kredel $
003 */
004
005 package edu.jas.gb;
006
007 import java.util.List;
008 import java.util.ArrayList;
009 import java.util.Map;
010
011 import junit.framework.Test;
012 import junit.framework.TestCase;
013 import junit.framework.TestSuite;
014
015 import org.apache.log4j.BasicConfigurator;
016
017 import edu.jas.structure.RingFactory;
018 import edu.jas.arith.BigInteger;
019 import edu.jas.arith.BigRational;
020 import edu.jas.arith.BigComplex;
021 import edu.jas.arith.Product;
022 import edu.jas.arith.ProductRing;
023 import edu.jas.poly.ExpVector;
024 import edu.jas.poly.GenPolynomial;
025 import edu.jas.poly.GenPolynomialRing;
026 import edu.jas.poly.PolynomialList;
027
028
029 /**
030 * Reduction tests with JUnit.
031 * @author Heinz Kredel.
032 */
033
034 public 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 assertFalse("lcm(lt(a),lt(b)) != lt(e) ", ce.equals( e ) );
203
204
205 L = new ArrayList<GenPolynomial<BigRational>>();
206 L.add( a );
207 assertTrue("isTopRed( a )", red.isTopReducible(L,a) );
208 assertTrue("isRed( a )", red.isReducible(L,a) );
209 b = fac.random(kl, ll, el, q );
210 L.add( b );
211 assertTrue("isTopRed( b )", red.isTopReducible(L,b) );
212 assertTrue("isRed( b )", red.isReducible(L,b) );
213 c = fac.random(kl, ll, el, q );
214 e = red.normalform( L, c );
215 assertTrue("isNF( e )", red.isNormalform(L,e) );
216 }
217
218
219 /**
220 * Test rational coefficient parallel reduction.
221 *
222 */
223 public void testRatReductionPar() {
224
225 a = fac.random(kl, ll, el, q );
226 b = fac.random(kl, ll, el, q );
227
228 assertTrue("not isZERO( a )", !a.isZERO() );
229
230 L = new ArrayList<GenPolynomial<BigRational>>();
231 L.add(a);
232
233 e = redpar.normalform( L, a );
234 assertTrue("isZERO( e )", e.isZERO() );
235
236 assertTrue("not isZERO( b )", !b.isZERO() );
237
238 L.add(b);
239 e = redpar.normalform( L, a );
240 assertTrue("isZERO( e ) some times", e.isZERO() );
241
242 L = new ArrayList<GenPolynomial<BigRational>>();
243 L.add( a );
244 assertTrue("isTopRed( a )", redpar.isTopReducible(L,a) );
245 assertTrue("isRed( a )", redpar.isReducible(L,a) );
246 b = fac.random(kl, ll, el, q );
247 L.add( b );
248 assertTrue("isTopRed( b )", redpar.isTopReducible(L,b) );
249 assertTrue("isRed( b )", redpar.isReducible(L,b) );
250 c = fac.random(kl, ll, el, q );
251 e = redpar.normalform( L, c );
252 assertTrue("isNF( e )", redpar.isNormalform(L,e) );
253 }
254
255
256 /**
257 * Test complex coefficient reduction.
258 *
259 */
260 public void testComplexReduction() {
261
262 GenPolynomialRing<BigComplex> fac
263 = new GenPolynomialRing<BigComplex>( new BigComplex(0), rl );
264
265 Reduction<BigComplex> cred = new ReductionSeq<BigComplex>();
266
267 GenPolynomial<BigComplex> a = fac.random(kl, ll, el, q );
268 GenPolynomial<BigComplex> b = fac.random(kl, ll, el, q );
269 GenPolynomial<BigComplex> c;
270
271 assertTrue("not isZERO( a )", !a.isZERO() );
272
273 List<GenPolynomial<BigComplex>> L
274 = new ArrayList<GenPolynomial<BigComplex>>();
275 L.add(a);
276
277 GenPolynomial<BigComplex> e
278 = cred.normalform( L, a );
279 assertTrue("isZERO( e )", e.isZERO() );
280
281 assertTrue("not isZERO( b )", !b.isZERO() );
282
283 L.add(b);
284 e = cred.normalform( L, a );
285 assertTrue("isZERO( e ) some times", e.isZERO() );
286
287 L = new ArrayList<GenPolynomial<BigComplex>>();
288 L.add( a );
289 assertTrue("isTopRed( a )", cred.isTopReducible(L,a) );
290 assertTrue("isRed( a )", cred.isReducible(L,a) );
291 b = fac.random(kl, ll, el, q );
292 L.add( b );
293 assertTrue("isTopRed( b )", cred.isTopReducible(L,b) );
294 assertTrue("isRed( b )", cred.isReducible(L,b) );
295 c = fac.random(kl, ll, el, q );
296 e = cred.normalform( L, c );
297 assertTrue("isNF( e )", cred.isNormalform(L,e) );
298 }
299
300
301 /**
302 * Test rational coefficient reduction with recording.
303 *
304 */
305 public void testRatReductionRecording() {
306
307 List<GenPolynomial<BigRational>> row = null;
308
309
310 a = fac.random(kl, ll, el, q );
311 b = fac.random(kl, ll, el, q );
312 c = fac.random(kl, ll, el, q );
313 d = fac.random(kl, ll, el, q );
314
315 assertTrue("not isZERO( a )", !a.isZERO() );
316
317 L = new ArrayList<GenPolynomial<BigRational>>();
318
319 L.add(a);
320 row = new ArrayList<GenPolynomial<BigRational>>( L.size() );
321 for ( int m = 0; m < L.size(); m++ ) {
322 row.add(null);
323 }
324 e = red.normalform( row, L, a );
325 assertTrue("isZERO( e )", e.isZERO() );
326 assertTrue("not isZERO( b )", !b.isZERO() );
327 assertTrue("is Reduction ", red.isReductionNF(row,L,a,e) );
328
329 L.add(b);
330 row = new ArrayList<GenPolynomial<BigRational>>( L.size() );
331 for ( int m = 0; m < L.size(); m++ ) {
332 row.add(null);
333 }
334 e = red.normalform( row, L, b );
335 assertTrue("is Reduction ", red.isReductionNF(row,L,b,e) );
336
337 L.add(c);
338 row = new ArrayList<GenPolynomial<BigRational>>( L.size() );
339 for ( int m = 0; m < L.size(); m++ ) {
340 row.add(null);
341 }
342 e = red.normalform( row, L, c );
343 assertTrue("is Reduction ", red.isReductionNF(row,L,c,e) );
344
345 L.add(d);
346 row = new ArrayList<GenPolynomial<BigRational>>( L.size() );
347 for ( int m = 0; m < L.size(); m++ ) {
348 row.add(null);
349 }
350 e = red.normalform( row, L, d );
351 assertTrue("is Reduction ", red.isReductionNF(row,L,d,e) );
352 }
353
354
355 /**
356 * Test integer coefficient e-reduction.
357 *
358 */
359 public void testIntegerEReduction() {
360
361 BigInteger bi = new BigInteger(0);
362 GenPolynomialRing<BigInteger> fac
363 = new GenPolynomialRing<BigInteger>( bi, rl );
364
365 EReductionSeq<BigInteger> ered = new EReductionSeq<BigInteger>();
366
367 GenPolynomial<BigInteger> a = fac.random(kl, ll, el, q );
368 GenPolynomial<BigInteger> b = fac.random(kl, ll, el, q );
369
370 assertTrue("not isZERO( a )", !a.isZERO() );
371
372 List<GenPolynomial<BigInteger>> L
373 = new ArrayList<GenPolynomial<BigInteger>>();
374 L.add(a);
375
376 GenPolynomial<BigInteger> e
377 = ered.normalform( L, a );
378 //System.out.println("a = " + a);
379 //System.out.println("e = " + e);
380 assertTrue("isZERO( e )", e.isZERO() );
381
382 assertTrue("not isZERO( b )", !b.isZERO() );
383
384 L.add(b);
385 e = ered.normalform( L, a );
386 //System.out.println("b = " + b);
387 //System.out.println("e = " + e);
388 assertTrue("isZERO( e ) some times", e.isZERO() );
389
390 GenPolynomial<BigInteger> c = fac.getONE();
391 a = a.sum(c);
392 e = ered.normalform( L, a );
393 //System.out.println("b = " + b);
394 //System.out.println("e = " + e);
395 assertTrue("isONE( e ) some times", e.isONE() );
396
397 L = new ArrayList<GenPolynomial<BigInteger>>();
398 a = c.multiply( bi.fromInteger(4) );
399 b = c.multiply( bi.fromInteger(5) );
400 L.add( a );
401 e = ered.normalform( L, b );
402 //System.out.println("a = " + a);
403 //System.out.println("b = " + b);
404 //System.out.println("e = " + e);
405 assertTrue("isONE( e )", e.isONE() );
406
407 a = fac.random(kl, ll, el, q ); //.abs();
408 b = fac.random(kl, ll, el, q ); //.abs();
409 c = ered.GPolynomial( a, b );
410 e = ered.SPolynomial( a, b );
411 //System.out.println("a = " + a);
412 //System.out.println("b = " + b);
413 //System.out.println("c = " + c);
414 //System.out.println("e = " + e);
415
416 BigInteger ci = a.leadingBaseCoefficient().gcd( b.leadingBaseCoefficient() );
417 assertEquals("gcd(lbc(a),lbc(b)) = lbc(c) ", ci, c.leadingBaseCoefficient() );
418
419 ExpVector ce = a.leadingExpVector().lcm(b.leadingExpVector());
420 assertEquals("lcm(lt(a),lt(b)) == lt(c) ", ce, c.leadingExpVector() );
421 assertFalse("lcm(lt(a),lt(b)) != lt(e) ", ce.equals( e.leadingExpVector() ) );
422
423 L = new ArrayList<GenPolynomial<BigInteger>>();
424 L.add( a );
425 assertTrue("isTopRed( a )", ered.isTopReducible(L,a) );
426 assertTrue("isRed( a )", ered.isReducible(L,a) );
427 b = fac.random(kl, ll, el, q );
428 L.add( b );
429 assertTrue("isTopRed( b )", ered.isTopReducible(L,b) );
430 assertTrue("isRed( b )", ered.isReducible(L,b) );
431 c = fac.random(kl, ll, el, q );
432 e = ered.normalform( L, c );
433 assertTrue("isNF( e )", ered.isNormalform(L,e) );
434 }
435
436
437 /**
438 * Test integer coefficient d-reduction.
439 *
440 */
441 public void testIntegerDReduction() {
442
443 BigInteger bi = new BigInteger(0);
444 GenPolynomialRing<BigInteger> fac
445 = new GenPolynomialRing<BigInteger>( bi, rl );
446
447 DReductionSeq<BigInteger> dred = new DReductionSeq<BigInteger>();
448
449 GenPolynomial<BigInteger> a = fac.random(kl, ll, el, q );
450 GenPolynomial<BigInteger> b = fac.random(kl, ll, el, q );
451
452 assertTrue("not isZERO( a )", !a.isZERO() );
453
454 List<GenPolynomial<BigInteger>> L
455 = new ArrayList<GenPolynomial<BigInteger>>();
456 L.add(a);
457
458 GenPolynomial<BigInteger> e
459 = dred.normalform( L, a );
460 //System.out.println("a = " + a);
461 //System.out.println("e = " + e);
462 assertTrue("isZERO( e )", e.isZERO() );
463
464 assertTrue("not isZERO( b )", !b.isZERO() );
465
466 L.add(b);
467 e = dred.normalform( L, a );
468 //System.out.println("b = " + b);
469 //System.out.println("e = " + e);
470 assertTrue("isZERO( e ) some times", e.isZERO() );
471
472 GenPolynomial<BigInteger> c = fac.getONE();
473 a = a.sum(c);
474 e = dred.normalform( L, a );
475 //System.out.println("b = " + b);
476 //System.out.println("e = " + e);
477 assertTrue("isONE( e ) some times", e.isONE() );
478
479 L = new ArrayList<GenPolynomial<BigInteger>>();
480 a = c.multiply( bi.fromInteger(5) );
481 L.add( a );
482 b = c.multiply( bi.fromInteger(4) );
483 e = dred.normalform( L, b );
484 //System.out.println("a = " + a);
485 //System.out.println("b = " + b);
486 //System.out.println("e = " + e);
487 assertTrue("nf(b) = b ", e.equals(b) );
488
489 a = fac.random(kl, ll, el, q ); //.abs();
490 b = fac.random(kl, ll, el, q ); //.abs();
491 c = dred.GPolynomial( a, b );
492 e = dred.SPolynomial( a, b );
493 //System.out.println("a = " + a);
494 //System.out.println("b = " + b);
495 //System.out.println("c = " + c);
496 //System.out.println("e = " + e);
497
498 BigInteger ci = a.leadingBaseCoefficient().gcd( b.leadingBaseCoefficient() );
499 assertEquals("gcd(lbc(a),lbc(b)) = lbc(c) ", ci, c.leadingBaseCoefficient() );
500
501 ExpVector ce = a.leadingExpVector().lcm(b.leadingExpVector());
502 assertEquals("lcm(lt(a),lt(b)) == lt(c) ", ce, c.leadingExpVector() );
503 assertFalse("lcm(lt(a),lt(b)) != lt(e) ", ce.equals( e.leadingExpVector() ) );
504
505 L = new ArrayList<GenPolynomial<BigInteger>>();
506 L.add( a );
507 assertTrue("isTopRed( a )", dred.isTopReducible(L,a) );
508 assertTrue("isRed( a )", dred.isReducible(L,a) );
509 b = fac.random(kl, ll, el, q );
510 L.add( b );
511 assertTrue("isTopRed( b )", dred.isTopReducible(L,b) );
512 assertTrue("isRed( b )", dred.isReducible(L,b) );
513 c = fac.random(kl, ll, el, q );
514 e = dred.normalform( L, c );
515 assertTrue("isNF( e )", dred.isNormalform(L,e) );
516 }
517
518 }