Source code

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