Source code

001/*
002 * $Id: GCDPrimitiveTest.java 5267 2015-07-27 17:57:50Z kredel $
003 */
004
005package edu.jas.fd;
006
007
008import java.util.List;
009
010import junit.framework.Test;
011import junit.framework.TestCase;
012import junit.framework.TestSuite;
013
014import org.apache.log4j.BasicConfigurator;
015
016import edu.jas.arith.BigRational;
017import edu.jas.gbufd.QuotSolvablePolynomialRing;
018import edu.jas.gbufd.SolvableQuotient;
019import edu.jas.gbufd.SolvableQuotientRing;
020import edu.jas.poly.GenPolynomial;
021import edu.jas.poly.GenSolvablePolynomial;
022import edu.jas.poly.GenSolvablePolynomialRing;
023import edu.jas.poly.PolyUtil;
024import edu.jas.poly.PolynomialList;
025import edu.jas.poly.RecSolvablePolynomial;
026import edu.jas.poly.RecSolvablePolynomialRing;
027import edu.jas.poly.RelationGenerator;
028import edu.jas.poly.TermOrder;
029import edu.jas.poly.WeylRelationsIterated;
030
031
032/**
033 * GCD Primitive PRS algorithm tests with JUnit. <b>Note:</b> not in sync with
034 * implementation.
035 * @author Heinz Kredel.
036 */
037
038public class GCDPrimitiveTest extends TestCase {
039
040
041    /**
042     * main.
043     */
044    public static void main(String[] args) {
045        BasicConfigurator.configure();
046        junit.textui.TestRunner.run(suite());
047    }
048
049
050    /**
051     * Constructs a <CODE>GCDPrimitiveTest</CODE> object.
052     * @param name String.
053     */
054    public GCDPrimitiveTest(String name) {
055        super(name);
056    }
057
058
059    /**
060     */
061    public static Test suite() {
062        TestSuite suite = new TestSuite(GCDPrimitiveTest.class);
063        return suite;
064    }
065
066
067    GreatestCommonDivisorAbstract<BigRational> fd, fds;
068
069
070    TermOrder to = new TermOrder(TermOrder.INVLEX);
071
072
073    //TermOrder to = new TermOrder(TermOrder.IGRLEX);
074
075
076    GenSolvablePolynomialRing<BigRational> dfac;
077
078
079    //GenSolvablePolynomialRing<GenPolynomial<BigRational>> rfac;
080    RecSolvablePolynomialRing<BigRational> rfac;
081
082
083    GenSolvablePolynomial<BigRational> a, b, c, d, e, a1, b1;
084
085
086    GenSolvablePolynomial<GenPolynomial<BigRational>> ar, br, cr, dr, er, sr;
087
088
089    int rl = 4;
090
091
092    int kl = 2;
093
094
095    int ll = 2;
096
097
098    int el = 3;
099
100
101    float q = 0.25f;
102
103
104    @Override
105    protected void setUp() {
106        a = b = c = d = e = null;
107        ar = br = cr = dr = er = null;
108        String[] vars = new String[] { "a", "b", "c", "d" };
109        BigRational cf = new BigRational(1);
110        fd = new GreatestCommonDivisorPrimitive<BigRational>(cf);
111        fds = new GreatestCommonDivisorSimple<BigRational>(cf);
112        dfac = new GenSolvablePolynomialRing<BigRational>(cf, rl, to, vars);
113        RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>();
114        dfac.addRelations(wl);
115        rfac = (RecSolvablePolynomialRing<BigRational>) dfac.recursive(1);
116    }
117
118
119    @Override
120    protected void tearDown() {
121        a = b = c = d = e = null;
122        ar = br = cr = dr = er = null;
123        fd = null;
124        dfac = null;
125        rfac = null;
126    }
127
128
129    /**
130     * Test base gcd primitive.
131     */
132    public void xtestBaseGcdPrimitive() {
133        String[] uvars = new String[] { "x" };
134        dfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), 1, to, uvars);
135
136        for (int i = 0; i < 5; i++) {
137            a = dfac.random(kl * (i + 2), ll + 2 * i, el + 2, q);
138            b = dfac.random(kl * (i + 2), ll + 2 * i, el + 2, q);
139            c = dfac.random(kl * (i + 2), ll + 2, el + 2, q);
140            c = c.multiply(dfac.univariate(0));
141            if (c.isZERO()) {
142                // skip for this turn
143                continue;
144            }
145            //a = fd.basePrimitivePart(a);
146            //b = fd.basePrimitivePart(b);
147            c = (GenSolvablePolynomial<BigRational>) fd.leftBasePrimitivePart(c).abs();
148
149            //System.out.println("a  = " + a);
150            //System.out.println("b  = " + b);
151            //System.out.println("c  = " + c);
152            //assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
153
154            a = a.multiply(c);
155            b = b.multiply(c);
156
157            d = fd.leftBaseGcd(a, b);
158            e = (GenSolvablePolynomial<BigRational>) PolyUtil.<BigRational> basePseudoRemainder(d, c);
159            //System.out.println("d  = " + d);
160            //System.out.println("c  = " + c);
161            assertTrue("c | gcd(ac,bc): " + e, e.isZERO());
162
163            e = (GenSolvablePolynomial<BigRational>) PolyUtil.<BigRational> basePseudoRemainder(a, d);
164            //System.out.println("e = " + e);
165            assertTrue("gcd(a,b) | a: " + e, e.isZERO());
166
167            e = (GenSolvablePolynomial<BigRational>) PolyUtil.<BigRational> basePseudoRemainder(b, d);
168            //System.out.println("e = " + e);
169            assertTrue("gcd(a,b) | b " + e, e.isZERO());
170        }
171    }
172
173
174    /**
175     * Test univariate recursive gcd primitive.
176     */
177    @SuppressWarnings("cast")
178    public void xtestRecursiveGCDPrimitive() {
179        //String[] vars = new String[] { "a", "b", "c", "d" };
180        String[] vars = new String[] { "a", "b" };
181        dfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), to, vars);
182        RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>();
183        dfac.addRelations(wl);
184        //System.out.println("dfac = " + dfac.toScript());
185        rfac = (RecSolvablePolynomialRing<BigRational>) dfac.recursive(1);
186        //System.out.println("rfac = " + rfac.toScript());
187
188        RecSolvablePolynomialRing<BigRational> rrfacTemp = rfac;
189        GenSolvablePolynomialRing<GenPolynomial<BigRational>> rrfac = rfac;
190
191        GenSolvablePolynomialRing<BigRational> rcfac = (GenSolvablePolynomialRing<BigRational>) rfac.coFac;
192        SolvableQuotientRing<BigRational> qfac = new SolvableQuotientRing<BigRational>(rcfac);
193        QuotSolvablePolynomialRing<BigRational> rqfac = new QuotSolvablePolynomialRing<BigRational>(qfac,
194                        rrfac);
195        List<GenSolvablePolynomial<GenPolynomial<BigRational>>> rl = rrfacTemp.coeffTable.relationList();
196        List<GenPolynomial<GenPolynomial<BigRational>>> rlc = PolynomialList
197                        .<GenPolynomial<BigRational>> castToList(rl);
198        rqfac.polCoeff.coeffTable.addRelations(rlc);
199        //System.out.println("rrfac  = " + rrfac.toScript());
200        //System.out.println("rcfac  = " + rcfac.toScript());
201        //System.out.println("qfac   = " + qfac.toScript());
202        //System.out.println("rqfac  = " + rqfac.toScript());
203
204        //kl = 3; ll = 4; //
205        el = 2;
206
207        ar = rfac.random(kl, ll, el + 1, q);
208        br = rfac.random(kl, ll, el, q);
209        cr = rfac.random(kl, ll, el, q);
210        //cr = (RecSolvablePolynomial<BigRational>) cr.abs();
211        cr = (RecSolvablePolynomial<BigRational>) PolyUtil.<BigRational> monic(cr);
212        //cr = (RecSolvablePolynomial<BigRational>) fd.recursivePrimitivePart(cr).abs();
213        //cr = rfac.getONE();
214        //cr = rfac.parse("a+b+c+d");
215
216        //ar = rfac.parse("1/3 b^3 - 1/6");
217        //ar = rfac.parse("1/3 b^2 - 1/6");
218        //br = rfac.parse("( -1/2 ) b + 3 a");
219        //nok: cr = rfac.parse("b * a - 5 b");
220        //cr = rfac.parse("a - 5");
221
222        //System.out.println("ar = " + ar);
223        //System.out.println("br = " + br);
224        //System.out.println("cr = " + cr);
225
226        if (br.isZERO() || cr.isZERO()) {
227            br = rfac.parse("( -1/2 ) b + 3 a");
228            cr = rfac.parse("a * b - 5 b");
229        }
230
231        //ar = cr.multiply(ar); 
232        //br = cr.multiply(br);
233        ar = ar.multiply(cr);
234        br = br.multiply(cr);
235        //System.out.println("ar = " + ar);
236        //System.out.println("br = " + br);
237        //if (true) return;
238
239        long ts = System.currentTimeMillis();
240        //sr = rfac.getONE(); 
241        sr = fds.leftRecursiveUnivariateGcd(ar, br);
242        ts = System.currentTimeMillis() - ts;
243        //System.out.println("cr = " + cr);
244
245        long tp = System.currentTimeMillis();
246        dr = fd.leftRecursiveUnivariateGcd(ar, br);
247        tp = System.currentTimeMillis() - tp;
248        //System.out.println("cr = " + cr);
249        //System.out.println("dr = " + dr);
250        //System.out.println("sr = " + sr);
251        if (ts < tp) {
252            System.out.println("time: ts = " + ts + ", tp = " + tp);
253        }
254
255        er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(dr, cr);
256        //System.out.println("er = " + er);
257        assertTrue("c | gcd(ac,bc): " + er, er.isZERO());
258
259        er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(ar, dr);
260        //System.out.println("er = " + er);
261        assertTrue("gcd(a,b) | a: " + er, er.isZERO());
262
263        er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(br, dr);
264        //System.out.println("er = " + er);
265        assertTrue("gcd(a,b) | b: " + er, er.isZERO());
266
267        GenSolvablePolynomial<SolvableQuotient<BigRational>> ap, bp, cp, dp, gp, ep, apm, bpm, cpm, dpm, gpm;
268        ap = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, ar);
269        bp = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, br);
270        cp = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, cr);
271        dp = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, dr);
272        apm = ap.monic();
273        bpm = bp.monic();
274        cpm = cp.monic();
275        dpm = dp.monic();
276        //System.out.println("ap  = " + ap);
277        //System.out.println("apm = " + apm);
278        //System.out.println("bp  = " + bp);
279        //System.out.println("bpm = " + bpm);
280        //System.out.println("cp  = " + cp);
281        //System.out.println("cpm = " + cpm);
282        //System.out.println("dp  = " + dp);
283        //System.out.println("dpm = " + dpm);
284
285        GreatestCommonDivisorAbstract<SolvableQuotient<BigRational>> fdq = new GreatestCommonDivisorPrimitive<SolvableQuotient<BigRational>>(
286                        qfac);
287        gp = fdq.leftBaseGcd(ap, bp);
288        gpm = gp.monic();
289        //System.out.println("gp  = " + gp);
290        //System.out.println("gpm = " + gpm);
291
292        ep = FDUtil.<SolvableQuotient<BigRational>> leftBaseSparsePseudoRemainder(gp, dp);
293        //System.out.println("ep  = " + ep);
294        assertTrue("c | gcd(ac,bc): " + ep, ep.isZERO());
295
296        ep = FDUtil.<SolvableQuotient<BigRational>> leftBaseSparsePseudoRemainder(ap, gp);
297        //System.out.println("ep  = " + ep);
298        assertTrue("gcd(ac,bc)| ac): " + ep, ep.isZERO());
299
300        ep = FDUtil.<SolvableQuotient<BigRational>> leftBaseSparsePseudoRemainder(bp, gp);
301        //System.out.println("ep  = " + ep);
302        assertTrue("gcd(ac,bc)| bc): " + ep, ep.isZERO());
303
304        assertEquals("nonsense", apm, ap.monic());
305        assertEquals("nonsense", bpm, bp.monic());
306        assertEquals("nonsense", cpm, cp.monic());
307        assertEquals("nonsense", dpm, dp.monic());
308        assertEquals("nonsense", gpm, gp.monic());
309    }
310
311
312    /**
313     * Test arbitrary recursive gcd primitive.
314     */
315    @SuppressWarnings("cast")
316    public void xtestArbitraryRecursiveGCDPrimitive() {
317        String[] cvars = new String[] { "a", "b" };
318        String[] vars = new String[] { "c" };
319        dfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), to, cvars);
320        RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>();
321        dfac.addRelations(wl);
322        System.out.println("dfac = " + dfac.toScript());
323        rfac = new RecSolvablePolynomialRing<BigRational>(dfac, to, vars);
324        //rfac = (RecSolvablePolynomialRing<BigRational>) dfac.recursive(1);
325        System.out.println("rfac = " + rfac.toScript());
326
327        //kl = 3; ll = 2;
328        el = 2;
329
330        ar = rfac.random(kl, ll, el + 1, q);
331        br = rfac.random(kl, ll, el, q);
332        cr = rfac.random(kl, ll, el, q);
333
334        //ar = rfac.parse("a + b c^2 ");
335        //br = rfac.parse("( a^2 - 1/3  ) c - 1/4");
336        //cr = rfac.parse("(b - 1/2 a^2) c");
337
338        //cr = (RecSolvablePolynomial<BigRational>) fd.recursivePrimitivePart(cr).abs();
339        cr = (RecSolvablePolynomial<BigRational>) cr.monic();
340        if (cr.isZERO()) {
341            cr = rfac.getONE();
342        }
343
344        System.out.println("ar = " + ar);
345        System.out.println("br = " + br);
346        System.out.println("cr = " + cr);
347
348        ar = ar.multiply(cr);
349        br = br.multiply(cr);
350        System.out.println("ar = " + ar);
351        System.out.println("br = " + br);
352
353        dr = fd.leftRecursiveGcd(ar, br);
354        System.out.println("cr = " + cr);
355        System.out.println("dr = " + dr);
356
357        er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(dr, cr);
358        //System.out.println("er = " + er);
359        assertTrue("c | gcd(ac,bc): " + er, er.isZERO());
360
361        er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(ar, dr);
362        //System.out.println("er = " + er);
363        assertTrue("gcd(a,b) | a: " + er, er.isZERO());
364
365        er = (RecSolvablePolynomial<BigRational>) FDUtil.<BigRational> recursiveSparsePseudoRemainder(br, dr);
366        //System.out.println("er = " + er);
367        assertTrue("gcd(a,b) | b: " + er, er.isZERO());
368
369        // compare with field coefficients:
370        RecSolvablePolynomialRing<BigRational> rrfacTemp = rfac;
371        GenSolvablePolynomialRing<GenPolynomial<BigRational>> rrfac = rfac;
372
373        GenSolvablePolynomialRing<BigRational> rcfac = (GenSolvablePolynomialRing<BigRational>) rfac.coFac;
374        SolvableQuotientRing<BigRational> qfac = new SolvableQuotientRing<BigRational>(rcfac);
375        QuotSolvablePolynomialRing<BigRational> rqfac = new QuotSolvablePolynomialRing<BigRational>(qfac,
376                        rrfac);
377        List<GenSolvablePolynomial<GenPolynomial<BigRational>>> rl = rrfacTemp.coeffTable.relationList();
378        List<GenPolynomial<GenPolynomial<BigRational>>> rlc = PolynomialList
379                        .<GenPolynomial<BigRational>> castToList(rl);
380        rqfac.polCoeff.coeffTable.addRelations(rlc);
381        System.out.println("rrfac  = " + rrfac.toScript());
382        System.out.println("rcfac  = " + rcfac.toScript());
383        System.out.println("qfac   = " + qfac.toScript());
384        System.out.println("rqfac  = " + rqfac.toScript());
385
386        GenSolvablePolynomial<SolvableQuotient<BigRational>> ap, bp, cp, dp, gp, ep, apm, bpm, cpm, dpm, gpm;
387        ap = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, ar);
388        bp = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, br);
389        cp = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, cr);
390        dp = FDUtil.<BigRational> quotientFromIntegralCoefficients(rqfac, dr);
391        apm = ap.monic();
392        bpm = bp.monic();
393        cpm = cp.monic();
394        dpm = dp.monic();
395        System.out.println("ap  = " + ap);
396        System.out.println("apm = " + apm);
397        System.out.println("bp  = " + bp);
398        System.out.println("bpm = " + bpm);
399        System.out.println("cp  = " + cp);
400        System.out.println("cpm = " + cpm);
401        System.out.println("dp  = " + dp);
402        System.out.println("dpm = " + dpm);
403
404        GreatestCommonDivisorAbstract<SolvableQuotient<BigRational>> fdq = new GreatestCommonDivisorPrimitive<SolvableQuotient<BigRational>>(
405                        qfac);
406        gp = fdq.leftBaseGcd(ap, bp);
407        gpm = gp.monic();
408        System.out.println("gp  = " + gp);
409        System.out.println("gpm = " + gpm);
410
411        ep = FDUtil.<SolvableQuotient<BigRational>> leftBaseSparsePseudoRemainder(gp, dp);
412        //System.out.println("ep  = " + ep);
413        assertTrue("c | gcd(ac,bc): " + ep, ep.isZERO());
414
415        ep = FDUtil.<SolvableQuotient<BigRational>> leftBaseSparsePseudoRemainder(ap, gp);
416        //System.out.println("ep  = " + ep);
417        assertTrue("gcd(ac,bc)| ac): " + ep, ep.isZERO());
418
419        ep = FDUtil.<SolvableQuotient<BigRational>> leftBaseSparsePseudoRemainder(bp, gp);
420        //System.out.println("ep  = " + ep);
421        assertTrue("gcd(ac,bc)| bc): " + ep, ep.isZERO());
422    }
423
424
425    /**
426     * Test full gcd primitive.
427     */
428    public void testGCDPrimitive() {
429        String[] vars = new String[] { "a", "b", "c", "d" };
430        //String[] vars = new String[] { "a", "b" };
431        dfac = new GenSolvablePolynomialRing<BigRational>(new BigRational(1), to, vars);
432        RelationGenerator<BigRational> wl = new WeylRelationsIterated<BigRational>();
433        dfac.addRelations(wl);
434        //System.out.println("dfac = " + dfac.toScript());
435
436        //kl = 3; 
437        ll = 4;
438        el = 4;
439
440        //a = dfac.random(kl, ll, el, q);
441        //b = dfac.random(kl, ll, el, q);
442        //c = dfac.random(kl, ll, el, q);
443        //c = c.multiply(dfac.univariate(0));
444
445        a = dfac.parse("1/3 b^3 - 1/6 + d");
446        b = dfac.parse("( -1/2 ) b + 3 a^2 + d");
447        ////b = dfac.parse("( -1/2 ) b + 3 a^2 + c");
448        ////c = dfac.parse("(a - 5 b) + c + d");
449        ////ok: c = dfac.parse("(a - b) c");
450        ////c = dfac.parse("c (a - b)");
451        //c = dfac.parse("(a - b) + c + d ");
452        c = dfac.parse("(a - b) + c");
453        //c = dfac.parse("(a - b) + b^3");
454        //c = dfac.parse("(a - b) + d");
455
456        //a = dfac.parse("2 b^3 * d^2 + 2/3 a + 3/2");
457        //b = dfac.parse("2/3 d + 1/2 a^3 + 3/4");
458        //c = dfac.parse("c^2 * d - 1/2 a^3 * d + 5/4 d");
459
460        //c = (GenSolvablePolynomial<BigRational>) fd.primitivePart(c).abs();
461        c = c.monic();
462        if (c.isZERO()) {
463            c = dfac.getONE();
464        }
465        //System.out.println("a = " + a);
466        //System.out.println("b = " + b);
467        //System.out.println("c = " + c);
468
469        a = a.multiply(c);
470        b = b.multiply(c);
471        //System.out.println("a = " + a);
472        //System.out.println("b = " + b);
473        //System.out.println("c = " + c);
474
475        d = fd.leftGcd(a, b);
476        //System.out.println("c = " + c);
477        //System.out.println("d = " + d);
478
479        e = FDUtil.<BigRational> leftBaseSparsePseudoRemainder(d, c);
480        //System.out.println("e = " + e);
481        assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
482
483        e = FDUtil.<BigRational> leftBaseSparsePseudoRemainder(a, c);
484        //System.out.println("e = " + e);
485        assertTrue("c | ac " + e, e.isZERO());
486        e = FDUtil.<BigRational> leftBaseSparsePseudoRemainder(a, d);
487        //System.out.println("e = " + e);
488        assertTrue("gcd(a,b) | a " + e, e.isZERO());
489
490        e = FDUtil.<BigRational> leftBaseSparsePseudoRemainder(b, c);
491        //System.out.println("e = " + e);
492        assertTrue("c | bc " + e, e.isZERO());
493        e = FDUtil.<BigRational> leftBaseSparsePseudoRemainder(b, d);
494        //System.out.println("e = " + e);
495        assertTrue("gcd(a,b) | b " + e, e.isZERO());
496    }
497
498}