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}