001/* 002 * $Id: CharSetTest.java 4071 2012-07-27 19:59:38Z kredel $ 003 */ 004 005package edu.jas.gbufd; 006 007 008import java.util.ArrayList; 009import java.util.List; 010 011import junit.framework.Test; 012import junit.framework.TestCase; 013import junit.framework.TestSuite; 014 015import org.apache.log4j.BasicConfigurator; 016 017import edu.jas.arith.BigRational; 018import edu.jas.kern.ComputerThreads; 019import edu.jas.poly.GenPolynomial; 020import edu.jas.poly.GenPolynomialRing; 021import edu.jas.poly.TermOrder; 022 023 024/** 025 * Chararacteristic set tests with JUnit. 026 * @author Heinz Kredel. 027 */ 028public class CharSetTest extends TestCase { 029 030 031 /** 032 * main. 033 */ 034 public static void main(String[] args) { 035 BasicConfigurator.configure(); 036 junit.textui.TestRunner.run(suite()); 037 ComputerThreads.terminate(); 038 } 039 040 041 /** 042 * Constructs a <CODE>CharSetTest</CODE> object. 043 * @param name String. 044 */ 045 public CharSetTest(String name) { 046 super(name); 047 } 048 049 050 /** 051 */ 052 public static Test suite() { 053 TestSuite suite = new TestSuite(CharSetTest.class); 054 return suite; 055 } 056 057 058 CharacteristicSet<BigRational> cs; 059 060 061 //TermOrder to = new TermOrder(TermOrder.INVLEX); 062 TermOrder to = new TermOrder(TermOrder.IGRLEX); 063 064 065 int rl = 3; 066 067 068 int kl = 3; 069 070 071 int ll = 4; 072 073 074 int el = 3; 075 076 077 float q = 0.29f; 078 079 080 @Override 081 protected void setUp() { 082 cs = new CharacteristicSetWu<BigRational>(); 083 } 084 085 086 @Override 087 protected void tearDown() { 088 cs = null; 089 } 090 091 092 /** 093 * Test random characteristic set simple. 094 */ 095 public void testCharacteristicSet() { 096 CharacteristicSet<BigRational> css = new CharacteristicSetSimple<BigRational>(); 097 GenPolynomialRing<BigRational> dfac; 098 BigRational br = new BigRational(); 099 to = new TermOrder(TermOrder.INVLEX); 100 dfac = new GenPolynomialRing<BigRational>(br, rl, to); 101 //System.out.println("dfac = " + dfac); 102 103 GenPolynomial<BigRational> a, b, c, d, e; 104 List<GenPolynomial<BigRational>> F, G, W; 105 106 F = new ArrayList<GenPolynomial<BigRational>>(); 107 a = dfac.random(kl, ll, el, q * 1.1f); 108 b = dfac.random(kl, ll + 2, el, q); 109 c = dfac.random(kl, ll, el, q); 110 F.add(a); 111 F.add(b); 112 F.add(c); 113 while (F.size() <= rl) { 114 F.add(dfac.getZERO()); // make false cs 115 } 116 //F.add(dfac.fromInteger(17)); // test 1 117 //System.out.println("F = " + F); 118 assertFalse("isCharacteristicSet: " + F, css.isCharacteristicSet(F)); 119 120 G = css.characteristicSet(F); 121 //System.out.println("G = " + G); 122 assertTrue("isCharacteristicSet: " + G, css.isCharacteristicSet(G)); 123 124 e = PolyGBUtil.<BigRational> topPseudoRemainder(G, a); 125 //System.out.println("a = " + a + ", deg_1 = " + a.degree(rl-1)); 126 //System.out.println("e = " + e + ", deg_1 = " + e.degree(rl-1)); 127 assertTrue("a rem G: " + e, e.isZERO() || e.degree(rl - 1) < a.degree(rl - 1)); // not always true 128 129 e = PolyGBUtil.<BigRational> topPseudoRemainder(G, G.get(0)); 130 //System.out.println("e = " + e); 131 assertTrue("a rem G: " + e + ", G = " + G, e.isZERO()); 132 133 e = css.characteristicSetReduction(G, a); 134 //System.out.println("a = " + a); 135 //System.out.println("e = " + e); 136 assertTrue("a mod G: " + e, e.isZERO() || e.degree(rl - 1) < a.degree(rl - 1)); // not always true 137 138 d = dfac.getONE(); 139 if (!G.contains(d)) { 140 d = dfac.random(kl, ll, el, q).sum(d); 141 //System.out.println("d = " + d); 142 e = PolyGBUtil.<BigRational> topPseudoRemainder(G, d); 143 //System.out.println("e = " + e); 144 assertFalse("a rem G: " + e, e.isZERO()); 145 e = css.characteristicSetReduction(G, d); 146 //System.out.println("e = " + e); 147 assertFalse("a mod G: " + e, e.isZERO()); 148 } 149 150 // now with Wu 151 W = cs.characteristicSet(F); 152 //System.out.println("F = " + F); 153 //System.out.println("W = " + W); 154 assertTrue("isCharacteristicSet: " + W, cs.isCharacteristicSet(W)); 155 156 e = PolyGBUtil.<BigRational> topPseudoRemainder(W, a); 157 //System.out.println("a = " + a + ", deg = " + a.degree(rl-1)); 158 //System.out.println("e = " + e + ", deg = " + e.degree(rl-1)); 159 assertTrue("a rem W: " + e, e.isZERO() || e.degree(rl - 1) < a.degree(rl - 1)); // not always true 160 161 e = PolyGBUtil.<BigRational> topPseudoRemainder(W, W.get(0)); 162 //System.out.println("e = " + e); 163 assertTrue("a rem G: " + e + ", W = " + W, e.isZERO()); 164 165 e = cs.characteristicSetReduction(W, W.get(W.size() - 1)); 166 //System.out.println("e = " + e); 167 assertTrue("a mod W: " + e, e.isZERO()); 168 169 e = cs.characteristicSetReduction(W, a); 170 //System.out.println("a = " + a); 171 //System.out.println("e = " + e); 172 assertTrue("a mod W: " + e, e.isZERO() || e.degree(rl - 1) < a.degree(rl - 1)); // not always true 173 } 174 175 176 /** 177 * Test random characteristic set Wu. 178 */ 179 public void testCharacteristicSetWu() { 180 GenPolynomialRing<BigRational> dfac; 181 BigRational br = new BigRational(); 182 to = new TermOrder(TermOrder.INVLEX); 183 dfac = new GenPolynomialRing<BigRational>(br, rl, to); 184 //System.out.println("dfac = " + dfac); 185 186 GenPolynomial<BigRational> a, b, c, d, e; 187 List<GenPolynomial<BigRational>> F, G; 188 189 F = new ArrayList<GenPolynomial<BigRational>>(); 190 a = dfac.random(kl, ll, el, q * 1.1f); 191 b = dfac.random(kl, ll + 2, el, q); 192 c = dfac.random(kl, ll, el, q); 193 F.add(a); 194 F.add(b); 195 F.add(c); 196 while (F.size() <= rl) { 197 F.add(dfac.getZERO()); // make false cs 198 } 199 //F.add(dfac.fromInteger(19)); // test 1 200 //System.out.println("F = " + F); 201 assertFalse("isCharacteristicSet: " + F, cs.isCharacteristicSet(F)); 202 203 G = cs.characteristicSet(F); 204 //System.out.println("G = " + G); 205 assertTrue("isCharacteristicSet: " + G, cs.isCharacteristicSet(G)); 206 207 e = PolyGBUtil.<BigRational> topPseudoRemainder(G, a); 208 //System.out.println("e = " + e); 209 assertTrue("a rem G: " + e, e.isZERO() || e.degree(rl - 1) < a.degree(rl - 1)); // not always true 210 211 e = cs.characteristicSetReduction(G, G.get(G.size() - 1)); 212 //System.out.println("e = " + e); 213 assertTrue("a mod G: " + e, e.isZERO()); 214 215 e = cs.characteristicSetReduction(G, G.get(0)); 216 //System.out.println("e = " + e); 217 assertTrue("a mod G: " + e, e.isZERO()); 218 219 e = cs.characteristicSetReduction(G, a); 220 //System.out.println("e = " + e); 221 assertTrue("a mod G: " + e + ", G = " + G, e.isZERO() || e.degree(rl - 1) < a.degree(rl - 1)); // not always true 222 223 d = dfac.getONE(); 224 if (!G.contains(d)) { 225 d = dfac.random(kl, ll, el, q).sum(d); 226 //System.out.println("d = " + d); 227 e = PolyGBUtil.<BigRational> topPseudoRemainder(G, d); 228 //System.out.println("e = " + e); 229 assertFalse("a rem G: " + e, e.isZERO()); 230 e = cs.characteristicSetReduction(G, d); 231 //System.out.println("e = " + e); 232 assertFalse("a mod G: " + e, e.isZERO()); 233 } 234 } 235 236 237 /** 238 * Test characteristic set, example Circle of Apollonius, from CLO IVA, 239 * 1992. 240 */ 241 public void testCharacteristicSetExample() { 242 GenPolynomialRing<BigRational> dfac; 243 BigRational br = new BigRational(); 244 to = new TermOrder(TermOrder.INVLEX); 245 String[] vars = new String[] { "u1", "u2", "x1", "x2", "x3", "x4", "x5", "x6", "x7", "x8" }; 246 dfac = new GenPolynomialRing<BigRational>(br, to, vars); 247 //System.out.println("dfac = " + dfac); 248 249 GenPolynomial<BigRational> h1, h2, h3, h4, h5, h6, h7, h8, g, e; 250 List<GenPolynomial<BigRational>> F, G; 251 252 F = new ArrayList<GenPolynomial<BigRational>>(); 253 h1 = dfac.parse(" 2 x1 - u1 "); 254 h2 = dfac.parse(" 2 x2 - u2 "); 255 h3 = dfac.parse(" 2 x3 - u1 "); 256 h4 = dfac.parse(" 2 x4 - u2 "); 257 h5 = dfac.parse(" u2 x5 + u1 x6 - u1 u2 "); 258 h6 = dfac.parse(" u1 x5 - u2 x6 "); 259 h7 = dfac.parse(" x1^2 - x2^2 - 2 x1 x7 + 2 x2 x8 "); 260 h8 = dfac.parse(" x1^2 - 2 x1 x7 - x3^2 + 2 x3 x7 - x4^2 + 2 x4 x8 "); 261 262 F.add(h1); 263 F.add(h2); 264 F.add(h3); 265 F.add(h4); 266 F.add(h5); 267 F.add(h6); 268 F.add(h7); 269 F.add(h8); 270 271 //System.out.println("F = " + F); 272 assertFalse("isCharacteristicSet: " + F, cs.isCharacteristicSet(F)); 273 274 G = cs.characteristicSet(F); 275 //System.out.println("G = " + G); 276 assertTrue("isCharacteristicSet: " + G, cs.isCharacteristicSet(G)); 277 278 g = dfac.parse("( ( x5 - x7 )**2 + ( x6 - x8 )**2 - ( x1 - x7 )**2 - x8^2 )"); 279 //g = dfac.parse("-2 x6 * x8 - 2 x5 * x7 + 2 x1 * x7 + x6^2 + x5^2 - x1^2"); 280 //System.out.println("g = " + g); 281 282 e = cs.characteristicSetReduction(G, g); 283 //e = PolyGBUtil.<BigRational> topPseudoRemainder(G, g); 284 //System.out.println("e = " + e); 285 assertTrue("g mod G: " + e, e.isZERO()); // || true ?not always true 286 287 //GroebnerBaseAbstract<BigRational> bb = GBFactory.getImplementation(br); 288 //H = bb.GB(F); 289 //System.out.println(" H = " + H); 290 291 //Reduction<BigRational> red = bb.red; 292 //f = red.normalform(H, g); 293 //System.out.println("fg = " + f); 294 295 //k = red.normalform(H, e); 296 //System.out.println("fk' = " + k); 297 298 //System.out.println("fk' == f: " + k.equals(f)); 299 //System.out.println("fk' - f: " + k.subtract(f)); 300 301 //K = red.normalform(H, G); 302 //System.out.println("Kg = " + K); 303 //L = red.normalform(H, F); 304 //System.out.println("Lf = " + L); 305 //assertEquals("Kg == Kf: " + L, K, L); 306 } 307 308 309 /** 310 * Test characteristic set, example circum-center. 311 */ 312 public void ytestCharacteristicSetExampleCC() { 313 GenPolynomialRing<BigRational> dfac; 314 BigRational br = new BigRational(); 315 to = new TermOrder(TermOrder.INVLEX); 316 String[] vars = new String[] { "u1", "u2", "u3", "x1", "x2", "x3" }; 317 dfac = new GenPolynomialRing<BigRational>(br, to, vars); 318 //System.out.println("dfac = " + dfac); 319 320 GenPolynomial<BigRational> h1, h2, h3, g, e; 321 List<GenPolynomial<BigRational>> F, G; 322 323 F = new ArrayList<GenPolynomial<BigRational>>(); 324 // wrong: 325 h1 = dfac.parse(" 2 u1 x2 - u1^2 "); 326 h2 = dfac.parse(" 2 u2 x2 + 2 u3 x1 - u2^2 - u3^2 "); 327 h3 = dfac.parse(" 2 u3 x3 - 2 ( u2 - u1 ) x2 - u2^2 - u3^2 + u1^2 "); 328 329 F.add(h1); 330 F.add(h2); 331 F.add(h3); 332 333 System.out.println("F = " + F); 334 assertFalse("isCharacteristicSet: " + F, cs.isCharacteristicSet(F)); 335 336 G = cs.characteristicSet(F); 337 System.out.println("G = " + G); 338 assertTrue("isCharacteristicSet: " + G, cs.isCharacteristicSet(G)); 339 340 g = dfac.parse(" x3^2 - 2 x3 x1 + x1^2 "); 341 //g = dfac.parse(" x3 - x1 "); 342 System.out.println("g = " + g); 343 344 e = cs.characteristicSetReduction(G, g); 345 //e = PolyGBUtil.<BigRational> characteristicSetRemainder(G,g); 346 System.out.println("e = " + e); 347 assertTrue("g mod G: " + e, e.isZERO() || e.degree(rl - 1) < g.degree(rl - 1)); // not always true 348 } 349 350 351 /** 352 * Test characteristic set, example secant from wang. 353 */ 354 public void testCharacteristicSetExampleSec() { 355 GenPolynomialRing<BigRational> dfac; 356 BigRational br = new BigRational(); 357 to = new TermOrder(TermOrder.INVLEX); 358 String[] vars = new String[] { "u1", "u2", "u3", "u4", "y1", "y2", "y3" }; 359 dfac = new GenPolynomialRing<BigRational>(br, to, vars); 360 //System.out.println("dfac = " + dfac); 361 362 GenPolynomial<BigRational> h1, h2, h3, g, e; 363 List<GenPolynomial<BigRational>> F, G; 364 365 F = new ArrayList<GenPolynomial<BigRational>>(); 366 h1 = dfac.parse(" 2 u3 y1 - u2^2 + u1^2 - u3^2 "); 367 h2 = dfac.parse(" - y2^2 + 2 y1 y2 + u1^2 - u4^2 "); 368 h3 = dfac.parse(" - y2 y3 + u3 y3 + y2 u2 - u4 u3 "); 369 370 F.add(h1); 371 F.add(h2); 372 F.add(h3); 373 374 //System.out.println("F = " + F); 375 assertTrue("isCharacteristicSet: " + F, cs.isCharacteristicSet(F)); // already CS 376 377 G = cs.characteristicSet(F); 378 //System.out.println("G = " + G); 379 assertTrue("isCharacteristicSet: " + G, cs.isCharacteristicSet(G)); 380 381 g = dfac.parse("( (y3 + u1)^2 (y3 - u1)^2 - ( (y3 - u2)^2 + u3^2 ) ( (y3 - u4)^2 + y2^2 ) )"); 382 //g = dfac.parse(" x3 - x1 "); 383 //System.out.println("g = " + g); 384 385 e = cs.characteristicSetReduction(G, g); 386 //e = PolyGBUtil.<BigRational> characteristicSetRemainder(G,g); 387 //System.out.println("e = " + e); 388 assertTrue("g mod G: " + e, e.isZERO()); 389 } 390 391 392 /** 393 * Test characteristic set, example ??. 394 */ 395 public void testCharacteristicSetExampleT() { 396 GenPolynomialRing<BigRational> dfac; 397 BigRational br = new BigRational(); 398 to = new TermOrder(TermOrder.INVLEX); 399 String[] vars = new String[] { "x", "y", "z" }; 400 dfac = new GenPolynomialRing<BigRational>(br, to, vars); 401 //System.out.println("dfac = " + dfac); 402 403 GenPolynomial<BigRational> h1, h2, h3; 404 List<GenPolynomial<BigRational>> F, G; 405 406 F = new ArrayList<GenPolynomial<BigRational>>(); 407 h1 = dfac.parse(" x^2 + y + z - 1 "); 408 h2 = dfac.parse(" x + y^2 + z - 1 "); 409 h3 = dfac.parse(" x + y + z^2 - 1 "); 410 411 F.add(h1); 412 F.add(h2); 413 F.add(h3); 414 415 //System.out.println("F = " + F); 416 assertFalse("isCharacteristicSet: " + F, cs.isCharacteristicSet(F)); 417 418 G = cs.characteristicSet(F); 419 //System.out.println("G = " + G); 420 assertTrue("isCharacteristicSet: " + G, cs.isCharacteristicSet(G)); 421 } 422 423}