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}