001/* 002 * $Id: GCDSubresTest.java 3850 2011-12-30 18:29:00Z kredel $ 003 */ 004 005package edu.jas.ufd; 006 007 008//import java.util.Map; 009 010import junit.framework.Test; 011import junit.framework.TestCase; 012import junit.framework.TestSuite; 013 014import org.apache.log4j.BasicConfigurator; 015 016import edu.jas.arith.BigInteger; 017import edu.jas.arith.ModInteger; 018import edu.jas.poly.ExpVector; 019import edu.jas.poly.GenPolynomial; 020import edu.jas.poly.GenPolynomialRing; 021import edu.jas.poly.PolyUtil; 022import edu.jas.poly.TermOrder; 023 024 025/** 026 * GCD Subresultant PRS algorithm tests with JUnit. 027 * @author Heinz Kredel. 028 */ 029 030public class GCDSubresTest extends TestCase { 031 032 033 /** 034 * main. 035 */ 036 public static void main(String[] args) { 037 BasicConfigurator.configure(); 038 junit.textui.TestRunner.run(suite()); 039 } 040 041 042 /** 043 * Constructs a <CODE>GCDSubresTest</CODE> object. 044 * @param name String. 045 */ 046 public GCDSubresTest(String name) { 047 super(name); 048 } 049 050 051 /** 052 */ 053 public static Test suite() { 054 TestSuite suite = new TestSuite(GCDSubresTest.class); 055 return suite; 056 } 057 058 059 GreatestCommonDivisorAbstract<BigInteger> ufd; 060 061 062 TermOrder to = new TermOrder(TermOrder.INVLEX); 063 064 065 GenPolynomialRing<BigInteger> dfac; 066 067 068 GenPolynomialRing<BigInteger> cfac; 069 070 071 GenPolynomialRing<GenPolynomial<BigInteger>> rfac; 072 073 074 BigInteger ai; 075 076 077 BigInteger bi; 078 079 080 BigInteger ci; 081 082 083 BigInteger di; 084 085 086 BigInteger ei; 087 088 089 GenPolynomial<BigInteger> a; 090 091 092 GenPolynomial<BigInteger> b; 093 094 095 GenPolynomial<BigInteger> c; 096 097 098 GenPolynomial<BigInteger> d; 099 100 101 GenPolynomial<BigInteger> e; 102 103 104 GenPolynomial<GenPolynomial<BigInteger>> ar; 105 106 107 GenPolynomial<GenPolynomial<BigInteger>> br; 108 109 110 GenPolynomial<GenPolynomial<BigInteger>> cr; 111 112 113 GenPolynomial<GenPolynomial<BigInteger>> dr; 114 115 116 GenPolynomial<GenPolynomial<BigInteger>> er; 117 118 119 int rl = 5; 120 121 122 int kl = 4; 123 124 125 int ll = 5; 126 127 128 int el = 3; 129 130 131 float q = 0.3f; 132 133 134 @Override 135 protected void setUp() { 136 a = b = c = d = e = null; 137 ai = bi = ci = di = ei = null; 138 ar = br = cr = dr = er = null; 139 ufd = new GreatestCommonDivisorPrimitive<BigInteger>(); 140 String[] vars = ExpVector.STDVARS(rl); 141 String[] cvars = ExpVector.STDVARS(rl - 1); 142 String[] rvars = new String[] { vars[rl - 1] }; 143 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl, to, vars); 144 cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl - 1, to, cvars); 145 rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, to, rvars); 146 } 147 148 149 @Override 150 protected void tearDown() { 151 a = b = c = d = e = null; 152 ai = bi = ci = di = ei = null; 153 ar = br = cr = dr = er = null; 154 ufd = null; 155 dfac = null; 156 cfac = null; 157 rfac = null; 158 } 159 160 161 /** 162 * Test base gcd subresultant. 163 */ 164 public void testBaseGcdSubres() { 165 166 ufd = new GreatestCommonDivisorSubres<BigInteger>(); 167 168 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 1, to); 169 170 for (int i = 0; i < 1; i++) { 171 a = dfac.random(kl * (i + 2), ll + 2 * i, el + 2, q); 172 b = dfac.random(kl * (i + 2), ll + 2 * i, el + 2, q); 173 c = dfac.random(kl * (i + 2), ll + 2, el + 2, q); 174 c = c.multiply(dfac.univariate(0)); 175 if (c.isZERO()) { 176 // skip for this turn 177 continue; 178 } 179 //a = ufd.basePrimitivePart(a); 180 //b = ufd.basePrimitivePart(b); 181 c = ufd.basePrimitivePart(c).abs(); 182 183 //System.out.println("a = " + a); 184 //System.out.println("b = " + b); 185 //System.out.println("c = " + c); 186 187 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 188 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 189 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 190 191 a = a.multiply(c); 192 b = b.multiply(c); 193 194 d = ufd.baseGcd(a, b); 195 e = PolyUtil.<BigInteger> basePseudoRemainder(d, c); 196 //System.out.println("d = " + d); 197 //System.out.println("c = " + c); 198 assertTrue("c | gcd(ac,bc) " + e, e.isZERO()); 199 200 e = PolyUtil.<BigInteger> basePseudoRemainder(a, d); 201 //System.out.println("e = " + e); 202 assertTrue("gcd(a,b) | a" + e, e.isZERO()); 203 204 e = PolyUtil.<BigInteger> basePseudoRemainder(b, d); 205 //System.out.println("e = " + e); 206 assertTrue("gcd(a,b) | b" + e, e.isZERO()); 207 } 208 } 209 210 211 /** 212 * Test recursive gcd subresultant. 213 */ 214 public void testRecursiveGCDsubres() { 215 216 ufd = new GreatestCommonDivisorSubres<BigInteger>(); 217 218 di = new BigInteger(1); 219 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2, to); 220 cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2 - 1, to); 221 rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, to); 222 223 for (int i = 0; i < 5; i++) { 224 ar = rfac.random(kl, ll, el + i, q); 225 br = rfac.random(kl, ll, el, q); 226 cr = rfac.random(kl, ll, el, q); 227 cr = ufd.recursivePrimitivePart(cr).abs(); 228 //System.out.println("ar = " + ar); 229 //System.out.println("br = " + br); 230 //System.out.println("cr = " + cr); 231 232 if (ar.isZERO() || br.isZERO() || cr.isZERO()) { 233 // skip for this turn 234 continue; 235 } 236 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0); 237 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 238 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 239 240 ar = ar.multiply(cr); 241 br = br.multiply(cr); 242 //System.out.println("ar = " + ar); 243 //System.out.println("br = " + br); 244 //System.out.println("cr = " + cr); 245 246 dr = ufd.recursiveUnivariateGcd(ar, br); 247 //System.out.println("dr = " + dr); 248 249 er = PolyUtil.<BigInteger> recursivePseudoRemainder(dr, cr); 250 //System.out.println("er = " + er); 251 assertTrue("c | gcd(ac,bc) " + er, er.isZERO()); 252 253 er = PolyUtil.<BigInteger> recursivePseudoRemainder(ar, dr); 254 //System.out.println("er = " + er); 255 assertTrue("gcd(a,b) | a" + er, er.isZERO()); 256 257 er = PolyUtil.<BigInteger> recursivePseudoRemainder(br, dr); 258 //System.out.println("er = " + er); 259 assertTrue("gcd(a,b) | b" + er, er.isZERO()); 260 } 261 } 262 263 264 /** 265 * Test arbitrary recursive gcd subresultant. 266 */ 267 public void testArbitraryRecursiveGCDsubres() { 268 269 ufd = new GreatestCommonDivisorSubres<BigInteger>(); 270 271 di = new BigInteger(1); 272 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2, to); 273 cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2 - 1, to); 274 rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, to); 275 276 for (int i = 0; i < 5; i++) { 277 ar = rfac.random(kl, ll, el + i, q); 278 br = rfac.random(kl, ll, el, q); 279 cr = rfac.random(kl, ll, el, q); 280 cr = ufd.recursivePrimitivePart(cr).abs(); 281 //System.out.println("ar = " + ar); 282 //System.out.println("br = " + br); 283 //System.out.println("cr = " + cr); 284 285 if (ar.isZERO() || br.isZERO() || cr.isZERO()) { 286 // skip for this turn 287 continue; 288 } 289 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0); 290 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 291 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 292 293 ar = ar.multiply(cr); 294 br = br.multiply(cr); 295 //System.out.println("ar = " + ar); 296 //System.out.println("br = " + br); 297 //System.out.println("cr = " + cr); 298 299 dr = ufd.recursiveGcd(ar, br); 300 //System.out.println("dr = " + dr); 301 302 er = PolyUtil.<BigInteger> recursivePseudoRemainder(dr, cr); 303 //System.out.println("er = " + er); 304 assertTrue("c | gcd(ac,bc) " + er, er.isZERO()); 305 306 er = PolyUtil.<BigInteger> recursivePseudoRemainder(ar, dr); 307 //System.out.println("er = " + er); 308 assertTrue("gcd(a,b) | a" + er, er.isZERO()); 309 310 er = PolyUtil.<BigInteger> recursivePseudoRemainder(br, dr); 311 //System.out.println("er = " + er); 312 assertTrue("gcd(a,b) | b" + er, er.isZERO()); 313 } 314 } 315 316 317 /** 318 * Test gcd subresultant. 319 */ 320 public void testGCDsubres() { 321 322 //GreatestCommonDivisorAbstract<BigInteger> ufd_pp; 323 //ufd_pp = ufd; 324 325 ufd = new GreatestCommonDivisorSubres<BigInteger>(); 326 327 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 5, to); 328 329 for (int i = 0; i < 2; i++) { 330 a = dfac.random(kl, ll, el, q); 331 b = dfac.random(kl, ll, el, q); 332 c = dfac.random(kl, ll, el, q); 333 c = c.multiply(dfac.univariate(0)); 334 c = ufd.primitivePart(c).abs(); 335 //System.out.println("a = " + a); 336 //System.out.println("b = " + b); 337 //System.out.println("c = " + c); 338 339 if (a.isZERO() || b.isZERO() || c.isZERO()) { 340 // skip for this turn 341 continue; 342 } 343 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 344 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 345 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 346 347 a = a.multiply(c); 348 b = b.multiply(c); 349 //System.out.println("a = " + a); 350 //System.out.println("b = " + b); 351 //System.out.println("c = " + c); 352 353 d = ufd.gcd(a, b); 354 //System.out.println("c = " + c); 355 //System.out.println("d = " + d); 356 357 e = PolyUtil.<BigInteger> basePseudoRemainder(d, c); 358 //System.out.println("e = " + e); 359 assertTrue("c | gcd(ac,bc) " + e, e.isZERO()); 360 361 e = PolyUtil.<BigInteger> basePseudoRemainder(a, d); 362 //System.out.println("e = " + e); 363 assertTrue("gcd(a,b) | a " + e, e.isZERO()); 364 365 e = PolyUtil.<BigInteger> basePseudoRemainder(b, d); 366 //System.out.println("e = " + e); 367 assertTrue("gcd(a,b) | b " + e, e.isZERO()); 368 } 369 } 370 371 372 /** 373 * Test base subresultant. 374 */ 375 public void testBaseSubresultant() { 376 377 GreatestCommonDivisorSubres<BigInteger> ufd = new GreatestCommonDivisorSubres<BigInteger>(); 378 379 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 1, to); 380 381 for (int i = 0; i < 1; i++) { 382 a = dfac.random(kl * (i + 2), ll + 2 * i, el + 2, q); 383 b = dfac.random(kl * (i + 2), ll + 2 * i, el + 2, q); 384 c = dfac.random(kl, ll, 2, q); 385 //c = c.multiply( cfac.univariate(0) ); 386 //c = dfac.getONE(); 387 if (c.isZERO()) { 388 // skip for this turn 389 continue; 390 } 391 //System.out.println("a = " + a); 392 //System.out.println("b = " + b); 393 //System.out.println("c = " + c); 394 395 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 396 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 397 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 398 399 a = a.multiply(c); 400 b = b.multiply(c); 401 402 d = ufd.baseResultant(a, b); 403 e = ufd.baseGcd(a, b); 404 //System.out.println("d = " + d); 405 //System.out.println("c = " + c); 406 //System.out.println("e = " + e); 407 if (!e.isConstant()) { 408 assertTrue("res(a,b) == 0 " + d, d.isZERO()); 409 } else { 410 assertTrue("res(a,b) != 0 " + d, !d.isZERO()); 411 } 412 } 413 } 414 415 416 /** 417 * Test recursive subresultant. 418 */ 419 public void testRecursiveSubresultant() { 420 421 GreatestCommonDivisorSubres<BigInteger> ufd = new GreatestCommonDivisorSubres<BigInteger>(); 422 423 di = new BigInteger(1); 424 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2, to); 425 cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2 - 1, to); 426 rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, to); 427 428 for (int i = 0; i < 5; i++) { 429 ar = rfac.random(kl, ll, el + i, q); 430 br = rfac.random(kl, ll, el, q); 431 cr = rfac.random(kl, ll, 2, q); 432 //cr = rfac.getONE(); 433 //cr = ufd.recursivePrimitivePart(cr).abs(); 434 //cr = cr.multiply( rfac.univariate(0) ); 435 //System.out.println("ar = " + ar); 436 //System.out.println("br = " + br); 437 //System.out.println("cr = " + cr); 438 439 if (ar.isZERO() || br.isZERO() || cr.isZERO()) { 440 // skip for this turn 441 continue; 442 } 443 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0); 444 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 445 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 446 447 ar = ar.multiply(cr); 448 br = br.multiply(cr); 449 //System.out.println("ar = " + ar); 450 //System.out.println("br = " + br); 451 452 dr = ufd.recursiveUnivariateResultant(ar, br); 453 //System.out.println("cr = " + cr); 454 //System.out.println("dr = " + dr); 455 er = ufd.recursiveUnivariateGcd(ar, br); 456 //System.out.println("er = " + er); 457 458 if (er.isZERO()) { // cannot happen since a, b, c != 0 459 assertTrue("res(a,b) = 0 " + dr + " e = " + er, dr.isZERO()); 460 } 461 if (er.isConstant() && er.leadingBaseCoefficient().isConstant()) { 462 assertTrue("res(a,b) != 0 " + dr + ", e = " + er + ", a = " + ar + ", b = " + br, !dr 463 .isZERO()); 464 } else { 465 assertTrue("res(a,b) = 0 or not const " + dr + ", e = " + er + ", a = " + ar + ", b = " + br, 466 dr.isZERO() || !dr.isConstant() || !dr.leadingBaseCoefficient().isConstant()); 467 } 468 469 } 470 } 471 472 473 /** 474 * Test subresultant. 475 */ 476 public void testSubres() { 477 478 GreatestCommonDivisorSubres<BigInteger> ufd = new GreatestCommonDivisorSubres<BigInteger>(); 479 480 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 3, to); 481 482 for (int i = 0; i < 2; i++) { 483 a = dfac.random(kl, ll, el, q); 484 b = dfac.random(kl, ll, el, q); 485 c = dfac.random(kl, ll, 2, q); 486 //c = dfac.getONE(); 487 //c = c.multiply( dfac.univariate(0) ); 488 //c = ufd.primitivePart(c).abs(); 489 //System.out.println("a = " + a); 490 //System.out.println("b = " + b); 491 //System.out.println("c = " + c); 492 493 if (a.isZERO() || b.isZERO() || c.isZERO()) { 494 // skip for this turn 495 continue; 496 } 497 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 498 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 499 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 500 501 a = a.multiply(c); 502 b = b.multiply(c); 503 //System.out.println("a = " + a); 504 //System.out.println("b = " + b); 505 506 d = ufd.resultant(a, b); 507 e = ufd.gcd(a, b); 508 //System.out.println("c = " + c); 509 //System.out.println("d = " + d); 510 //System.out.println("e = " + e); 511 512 if (e.isZERO()) { // cannot happen since a, b, c != 0 513 assertTrue("res(a,b) = 0 " + d + " e = " + e, d.isZERO()); 514 } 515 if (e.isConstant()) { 516 assertTrue("res(a,b) != 0 " + d + ", e = " + e + ", a = " + a + ", b = " + b, !d.isZERO()); 517 } else { 518 assertTrue("res(a,b) = 0 or not const " + d + ", e = " + e + ", a = " + a + ", b = " + b, d 519 .isZERO() 520 || !d.isConstant()); 521 } 522 523 } 524 } 525 526 527 /** 528 * Test and compare resultant. 529 */ 530 public void testResultant() { 531 532 GreatestCommonDivisorAbstract<BigInteger> ufdm = new GreatestCommonDivisorModular<ModInteger>(true); 533 GreatestCommonDivisorSubres<BigInteger> ufds = new GreatestCommonDivisorSubres<BigInteger>(); 534 535 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 3, to); 536 537 for (int i = 0; i < 1; i++) { 538 a = dfac.random(kl+(i+1), ll, el, q); 539 b = dfac.random(kl+(i+2), ll, el, q); 540 c = dfac.random(kl, ll, 2, q); 541 //c = dfac.getONE(); 542 //c = c.multiply( dfac.univariate(0) ); 543 //c = ufd.primitivePart(c).abs(); 544 //System.out.println("a = " + a); 545 //System.out.println("b = " + b); 546 547 if (a.isZERO() || b.isZERO() || c.isZERO()) { 548 // skip for this turn 549 continue; 550 } 551 if (c.isConstant()) { 552 c = dfac.univariate(0,1); 553 } 554 //System.out.println("c = " + c); 555 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 556 557 d = ufdm.resultant(a, b); 558 //System.out.println("d = " + d); 559 e = ufds.resultant(a, b); 560 //System.out.println("e = " + e); 561 assertEquals("d == e: " + d.subtract(e), d.abs().signum(), e.abs().signum()); 562 //assertEquals("d == e: " + d.subtract(e), d, e); 563 564 GenPolynomial<BigInteger> ac = a.multiply(c); 565 GenPolynomial<BigInteger> bc = b.multiply(c); 566 //System.out.println("ac = " + ac); 567 //System.out.println("bc = " + bc); 568 569 d = ufdm.resultant(ac, bc); 570 //System.out.println("d = " + d); 571 //assertTrue("d == 0: " + d, d.isZERO()); 572 573 e = ufds.resultant(ac, bc); 574 //System.out.println("e = " + e); 575 //assertTrue("e == 0: " + e, e.isZERO()); 576 577 assertEquals("d == e: " + d.subtract(e), d.abs().signum(), e.abs().signum()); 578 } 579 } 580 581}