Source code

001/*
002 * $Id: GCDSubresTest.java 5863 2018-07-20 11:13:34Z 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
014
015import edu.jas.arith.BigInteger;
016import edu.jas.arith.ModInteger;
017import edu.jas.poly.ExpVector;
018import edu.jas.poly.GenPolynomial;
019import edu.jas.poly.GenPolynomialRing;
020import edu.jas.poly.PolyUtil;
021import edu.jas.poly.TermOrder;
022
023
024/**
025 * GCD Subresultant PRS algorithm tests with JUnit.
026 * @author Heinz Kredel
027 */
028
029public class GCDSubresTest extends TestCase {
030
031
032    /**
033     * main.
034     */
035    public static void main(String[] args) {
036        junit.textui.TestRunner.run(suite());
037    }
038
039
040    /**
041     * Constructs a <CODE>GCDSubresTest</CODE> object.
042     * @param name String.
043     */
044    public GCDSubresTest(String name) {
045        super(name);
046    }
047
048
049    /**
050     */
051    public static Test suite() {
052        TestSuite suite = new TestSuite(GCDSubresTest.class);
053        return suite;
054    }
055
056
057    GreatestCommonDivisorAbstract<BigInteger> ufd;
058
059
060    TermOrder to = new TermOrder(TermOrder.INVLEX);
061
062
063    GenPolynomialRing<BigInteger> dfac;
064
065
066    GenPolynomialRing<BigInteger> cfac;
067
068
069    GenPolynomialRing<GenPolynomial<BigInteger>> rfac;
070
071
072    BigInteger ai;
073
074
075    BigInteger bi;
076
077
078    BigInteger ci;
079
080
081    BigInteger di;
082
083
084    BigInteger ei;
085
086
087    GenPolynomial<BigInteger> a;
088
089
090    GenPolynomial<BigInteger> b;
091
092
093    GenPolynomial<BigInteger> c;
094
095
096    GenPolynomial<BigInteger> d;
097
098
099    GenPolynomial<BigInteger> e;
100
101
102    GenPolynomial<GenPolynomial<BigInteger>> ar;
103
104
105    GenPolynomial<GenPolynomial<BigInteger>> br;
106
107
108    GenPolynomial<GenPolynomial<BigInteger>> cr;
109
110
111    GenPolynomial<GenPolynomial<BigInteger>> dr;
112
113
114    GenPolynomial<GenPolynomial<BigInteger>> er;
115
116
117    int rl = 5;
118
119
120    int kl = 4;
121
122
123    int ll = 5;
124
125
126    int el = 3;
127
128
129    float q = 0.3f;
130
131
132    @Override
133    protected void setUp() {
134        a = b = c = d = e = null;
135        ai = bi = ci = di = ei = null;
136        ar = br = cr = dr = er = null;
137        ufd = new GreatestCommonDivisorPrimitive<BigInteger>();
138        String[] vars = ExpVector.STDVARS(rl);
139        String[] cvars = ExpVector.STDVARS(rl - 1);
140        String[] rvars = new String[] { vars[rl - 1] };
141        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl, to, vars);
142        cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl - 1, to, cvars);
143        rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, to, rvars);
144    }
145
146
147    @Override
148    protected void tearDown() {
149        a = b = c = d = e = null;
150        ai = bi = ci = di = ei = null;
151        ar = br = cr = dr = er = null;
152        ufd = null;
153        dfac = null;
154        cfac = null;
155        rfac = null;
156    }
157
158
159    /**
160     * Test base gcd subresultant.
161     */
162    public void testBaseGcdSubres() {
163
164        ufd = new GreatestCommonDivisorSubres<BigInteger>();
165
166        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 1, to);
167
168        for (int i = 0; i < 1; i++) {
169            a = dfac.random(kl * (i + 2), ll + 2 * i, el + 2, q);
170            b = dfac.random(kl * (i + 2), ll + 2 * i, el + 2, q);
171            c = dfac.random(kl * (i + 2), ll + 2, el + 2, q);
172            c = c.multiply(dfac.univariate(0));
173            if (c.isZERO()) {
174                // skip for this turn
175                continue;
176            }
177            //a = ufd.basePrimitivePart(a);
178            //b = ufd.basePrimitivePart(b);
179            c = ufd.basePrimitivePart(c).abs();
180
181            //System.out.println("a  = " + a);
182            //System.out.println("b  = " + b);
183            //System.out.println("c  = " + c);
184
185            assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
186            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
187            //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
188
189            a = a.multiply(c);
190            b = b.multiply(c);
191
192            d = ufd.baseGcd(a, b);
193            e = PolyUtil.<BigInteger> basePseudoRemainder(d, c);
194            //System.out.println("d  = " + d);
195            //System.out.println("c  = " + c);
196            assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
197
198            e = PolyUtil.<BigInteger> basePseudoRemainder(a, d);
199            //System.out.println("e = " + e);
200            assertTrue("gcd(a,b) | a" + e, e.isZERO());
201
202            e = PolyUtil.<BigInteger> basePseudoRemainder(b, d);
203            //System.out.println("e = " + e);
204            assertTrue("gcd(a,b) | b" + e, e.isZERO());
205        }
206    }
207
208
209    /**
210     * Test recursive gcd subresultant.
211     */
212    public void testRecursiveGCDsubres() {
213
214        ufd = new GreatestCommonDivisorSubres<BigInteger>();
215
216        di = new BigInteger(1);
217        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2, to);
218        cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2 - 1, to);
219        rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, to);
220
221        for (int i = 0; i < 5; i++) {
222            ar = rfac.random(kl, ll, el + i, q);
223            br = rfac.random(kl, ll, el, q);
224            cr = rfac.random(kl, ll, el, q);
225            cr = ufd.recursivePrimitivePart(cr).abs();
226            //System.out.println("ar = " + ar);
227            //System.out.println("br = " + br);
228            //System.out.println("cr = " + cr);
229
230            if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
231                // skip for this turn
232                continue;
233            }
234            assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0);
235            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
236            //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
237
238            ar = ar.multiply(cr);
239            br = br.multiply(cr);
240            //System.out.println("ar = " + ar);
241            //System.out.println("br = " + br);
242            //System.out.println("cr = " + cr);
243
244            dr = ufd.recursiveUnivariateGcd(ar, br);
245            //System.out.println("dr = " + dr);
246
247            er = PolyUtil.<BigInteger> recursivePseudoRemainder(dr, cr);
248            //System.out.println("er = " + er);
249            assertTrue("c | gcd(ac,bc) " + er, er.isZERO());
250
251            er = PolyUtil.<BigInteger> recursivePseudoRemainder(ar, dr);
252            //System.out.println("er = " + er);
253            assertTrue("gcd(a,b) | a" + er, er.isZERO());
254
255            er = PolyUtil.<BigInteger> recursivePseudoRemainder(br, dr);
256            //System.out.println("er = " + er);
257            assertTrue("gcd(a,b) | b" + er, er.isZERO());
258        }
259    }
260
261
262    /**
263     * Test arbitrary recursive gcd subresultant.
264     */
265    public void testArbitraryRecursiveGCDsubres() {
266
267        ufd = new GreatestCommonDivisorSubres<BigInteger>();
268
269        di = new BigInteger(1);
270        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2, to);
271        cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2 - 1, to);
272        rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, to);
273
274        for (int i = 0; i < 5; i++) {
275            ar = rfac.random(kl, ll, el + i, q);
276            br = rfac.random(kl, ll, el, q);
277            cr = rfac.random(kl, ll, el, q);
278            cr = ufd.recursivePrimitivePart(cr).abs();
279            //System.out.println("ar = " + ar);
280            //System.out.println("br = " + br);
281            //System.out.println("cr = " + cr);
282
283            if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
284                // skip for this turn
285                continue;
286            }
287            assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0);
288            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
289            //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
290
291            ar = ar.multiply(cr);
292            br = br.multiply(cr);
293            //System.out.println("ar = " + ar);
294            //System.out.println("br = " + br);
295            //System.out.println("cr = " + cr);
296
297            dr = ufd.recursiveGcd(ar, br);
298            //System.out.println("dr = " + dr);
299
300            er = PolyUtil.<BigInteger> recursivePseudoRemainder(dr, cr);
301            //System.out.println("er = " + er);
302            assertTrue("c | gcd(ac,bc) " + er, er.isZERO());
303
304            er = PolyUtil.<BigInteger> recursivePseudoRemainder(ar, dr);
305            //System.out.println("er = " + er);
306            assertTrue("gcd(a,b) | a" + er, er.isZERO());
307
308            er = PolyUtil.<BigInteger> recursivePseudoRemainder(br, dr);
309            //System.out.println("er = " + er);
310            assertTrue("gcd(a,b) | b" + er, er.isZERO());
311        }
312    }
313
314
315    /**
316     * Test gcd subresultant.
317     */
318    public void testGCDsubres() {
319
320        //GreatestCommonDivisorAbstract<BigInteger> ufd_pp; 
321        //ufd_pp = ufd;
322
323        ufd = new GreatestCommonDivisorSubres<BigInteger>();
324
325        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 5, to);
326
327        for (int i = 0; i < 2; i++) {
328            a = dfac.random(kl, ll, el, q);
329            b = dfac.random(kl, ll, el, q);
330            c = dfac.random(kl, ll, el, q);
331            c = c.multiply(dfac.univariate(0));
332            c = ufd.primitivePart(c).abs();
333            //System.out.println("a = " + a);
334            //System.out.println("b = " + b);
335            //System.out.println("c = " + c);
336
337            if (a.isZERO() || b.isZERO() || c.isZERO()) {
338                // skip for this turn
339                continue;
340            }
341            assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
342            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
343            //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
344
345            a = a.multiply(c);
346            b = b.multiply(c);
347            //System.out.println("a = " + a);
348            //System.out.println("b = " + b);
349            //System.out.println("c = " + c);
350
351            d = ufd.gcd(a, b);
352            //System.out.println("c = " + c);
353            //System.out.println("d = " + d);
354
355            e = PolyUtil.<BigInteger> basePseudoRemainder(d, c);
356            //System.out.println("e = " + e);
357            assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
358
359            e = PolyUtil.<BigInteger> basePseudoRemainder(a, d);
360            //System.out.println("e = " + e);
361            assertTrue("gcd(a,b) | a " + e, e.isZERO());
362
363            e = PolyUtil.<BigInteger> basePseudoRemainder(b, d);
364            //System.out.println("e = " + e);
365            assertTrue("gcd(a,b) | b " + e, e.isZERO());
366        }
367    }
368
369
370    /**
371     * Test base subresultant.
372     */
373    public void testBaseSubresultant() {
374
375        GreatestCommonDivisorSubres<BigInteger> ufd = new GreatestCommonDivisorSubres<BigInteger>();
376
377        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 1, to);
378
379        for (int i = 0; i < 1; i++) {
380            a = dfac.random(kl * (i + 2), ll + 2 * i, el + 2, q);
381            b = dfac.random(kl * (i + 2), ll + 2 * i, el + 2, q);
382            c = dfac.random(kl, ll, 2, q);
383            //c = c.multiply( cfac.univariate(0) );
384            //c = dfac.getONE();
385            if (c.isZERO()) {
386                // skip for this turn
387                continue;
388            }
389            //System.out.println("a  = " + a);
390            //System.out.println("b  = " + b);
391            //System.out.println("c  = " + c);
392
393            assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
394            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
395            //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
396
397            a = a.multiply(c);
398            b = b.multiply(c);
399
400            d = ufd.baseResultant(a, b);
401            e = ufd.baseGcd(a, b);
402            //System.out.println("d  = " + d);
403            //System.out.println("c  = " + c);
404            //System.out.println("e  = " + e);
405            if (!e.isConstant()) {
406                assertTrue("res(a,b) == 0 " + d, d.isZERO());
407            } else {
408                assertTrue("res(a,b) != 0 " + d, !d.isZERO());
409            }
410        }
411    }
412
413
414    /**
415     * Test recursive subresultant.
416     */
417    public void testRecursiveSubresultant() {
418
419        GreatestCommonDivisorSubres<BigInteger> ufd = new GreatestCommonDivisorSubres<BigInteger>();
420
421        di = new BigInteger(1);
422        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2, to);
423        cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2 - 1, to);
424        rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, to);
425
426        for (int i = 0; i < 5; i++) {
427            ar = rfac.random(kl, ll, el + i, q);
428            br = rfac.random(kl, ll, el, q);
429            cr = rfac.random(kl, ll, 2, q);
430            //cr = rfac.getONE(); 
431            //cr = ufd.recursivePrimitivePart(cr).abs();
432            //cr = cr.multiply( rfac.univariate(0) );
433            //System.out.println("ar = " + ar);
434            //System.out.println("br = " + br);
435            //System.out.println("cr = " + cr);
436
437            if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
438                // skip for this turn
439                continue;
440            }
441            assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0);
442            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
443            //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
444
445            ar = ar.multiply(cr);
446            br = br.multiply(cr);
447            //System.out.println("ar = " + ar);
448            //System.out.println("br = " + br);
449
450            dr = ufd.recursiveUnivariateResultant(ar, br);
451            //System.out.println("cr = " + cr);
452            //System.out.println("dr = " + dr);
453            er = ufd.recursiveUnivariateGcd(ar, br);
454            //System.out.println("er = " + er);
455
456            if (er.isZERO()) { // cannot happen since a, b, c != 0
457                assertTrue("res(a,b) = 0 " + dr + " e = " + er, dr.isZERO());
458            }
459            if (er.isConstant() && er.leadingBaseCoefficient().isConstant()) {
460                assertTrue("res(a,b) != 0 " + dr + ", e = " + er + ", a = " + ar + ", b = " + br, !dr
461                        .isZERO());
462            } else {
463                assertTrue("res(a,b) = 0 or not const " + dr + ", e = " + er + ", a = " + ar + ", b = " + br,
464                        dr.isZERO() || !dr.isConstant() || !dr.leadingBaseCoefficient().isConstant());
465            }
466
467        }
468    }
469
470
471    /**
472     * Test subresultant.
473     */
474    public void testSubres() {
475
476        GreatestCommonDivisorSubres<BigInteger> ufd = new GreatestCommonDivisorSubres<BigInteger>();
477
478        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 3, to);
479
480        for (int i = 0; i < 2; i++) {
481            a = dfac.random(kl, ll, el, q);
482            b = dfac.random(kl, ll, el, q);
483            c = dfac.random(kl, ll, 2, q);
484            //c = dfac.getONE();
485            //c = c.multiply( dfac.univariate(0) );
486            //c = ufd.primitivePart(c).abs();
487            //System.out.println("a = " + a);
488            //System.out.println("b = " + b);
489            //System.out.println("c = " + c);
490
491            if (a.isZERO() || b.isZERO() || c.isZERO()) {
492                // skip for this turn
493                continue;
494            }
495            assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
496            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
497            //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
498
499            a = a.multiply(c);
500            b = b.multiply(c);
501            //System.out.println("a = " + a);
502            //System.out.println("b = " + b);
503
504            d = ufd.resultant(a, b);
505            e = ufd.gcd(a, b);
506            //System.out.println("c = " + c);
507            //System.out.println("d = " + d);
508            //System.out.println("e = " + e);
509
510            if (e.isZERO()) { // cannot happen since a, b, c != 0
511                assertTrue("res(a,b) = 0 " + d + " e = " + e, d.isZERO());
512            }
513            if (e.isConstant()) {
514                assertTrue("res(a,b) != 0 " + d + ", e = " + e + ", a = " + a + ", b = " + b, !d.isZERO());
515            } else {
516                assertTrue("res(a,b) = 0 or not const " + d + ", e = " + e + ", a = " + a + ", b = " + b, d
517                        .isZERO()
518                        || !d.isConstant());
519            }
520
521        }
522    }
523
524
525    /**
526     * Test and compare resultant.
527     */
528    public void testResultant() {
529
530        GreatestCommonDivisorAbstract<BigInteger> ufdm = new GreatestCommonDivisorModular<ModInteger>(true);
531        GreatestCommonDivisorSubres<BigInteger> ufds = new GreatestCommonDivisorSubres<BigInteger>();
532
533        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 3, to);
534
535        for (int i = 0; i < 1; i++) {
536            a = dfac.random(kl+(i+1), ll, el, q);
537            b = dfac.random(kl+(i+2), ll, el, q);
538            c = dfac.random(kl, ll, 2, q);
539            //c = dfac.getONE();
540            //c = c.multiply( dfac.univariate(0) );
541            //c = ufd.primitivePart(c).abs();
542            //System.out.println("a = " + a);
543            //System.out.println("b = " + b);
544 
545            if (a.isZERO() || b.isZERO() || c.isZERO()) {
546                // skip for this turn
547                continue;
548            }
549            if (c.isConstant()) {
550                c = dfac.univariate(0,1);
551            }
552            //System.out.println("c = " + c);
553            assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
554
555            d = ufdm.resultant(a, b);
556            //System.out.println("d = " + d);
557            e = ufds.resultant(a, b);
558            //System.out.println("e = " + e);
559            assertEquals("d == e: " + d.subtract(e), d.abs().signum(), e.abs().signum());
560            //assertEquals("d == e: " + d.subtract(e), d, e);
561
562            GenPolynomial<BigInteger> ac = a.multiply(c);
563            GenPolynomial<BigInteger> bc = b.multiply(c);
564            //System.out.println("ac = " + ac);
565            //System.out.println("bc = " + bc);
566
567            d = ufdm.resultant(ac, bc);
568            //System.out.println("d = " + d);
569            //assertTrue("d == 0: " + d, d.isZERO());
570
571            e = ufds.resultant(ac, bc);
572            //System.out.println("e = " + e);
573            //assertTrue("e == 0: " + e, e.isZERO());
574
575            assertEquals("d == e: " + d.subtract(e), d.abs().signum(), e.abs().signum());
576        }
577    }
578
579}