Source code

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}