Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.ufd;
006
007
008import java.util.ArrayList;
009import java.util.List;
010import java.util.SortedMap;
011import java.util.TreeMap;
012
013import edu.jas.arith.BigRational;
014import edu.jas.poly.ExpVector;
015import edu.jas.poly.GenPolynomial;
016import edu.jas.poly.GenPolynomialRing;
017import edu.jas.poly.PolyUtil;
018import edu.jas.poly.TermOrder;
019
020import junit.framework.Test;
021import junit.framework.TestCase;
022import junit.framework.TestSuite;
023
024
025/**
026 * GCD partial fraction with rational coefficients algorithm tests with JUnit.
027 * @author Heinz Kredel
028 */
029
030public class GCDPartFracRatTest extends TestCase {
031
032
033    /**
034     * main.
035     */
036    public static void main(String[] args) {
037        junit.textui.TestRunner.run(suite());
038    }
039
040
041    /**
042     * Constructs a <CODE>GCDPartFracRatTest</CODE> object.
043     * @param name String.
044     */
045    public GCDPartFracRatTest(String name) {
046        super(name);
047    }
048
049
050    /**
051     */
052    public static Test suite() {
053        TestSuite suite = new TestSuite(GCDPartFracRatTest.class);
054        return suite;
055    }
056
057
058    GreatestCommonDivisorAbstract<BigRational> ufd;
059
060
061    TermOrder to = new TermOrder(TermOrder.INVLEX);
062
063
064    GenPolynomialRing<BigRational> dfac;
065
066
067    GenPolynomialRing<BigRational> cfac;
068
069
070    GenPolynomialRing<GenPolynomial<BigRational>> rfac;
071
072
073    BigRational mi;
074
075
076    BigRational ai, bi, ci, di, ei;
077
078
079    GenPolynomial<BigRational> a, b, c, d, e;
080
081
082    //GenPolynomial<GenPolynomial<BigRational>> ar, br, cr, dr, er;
083
084
085    int rl = 3;
086
087
088    int kl = 2;
089
090
091    int ll = 3;
092
093
094    int el = 3;
095
096
097    float q = 0.25f;
098
099
100    @Override
101    protected void setUp() {
102        a = b = c = d = e = null;
103        ai = bi = ci = di = ei = null;
104        //ar = br = cr = dr = er = null;
105        mi = new BigRational(1);
106        ufd = new GreatestCommonDivisorSubres<BigRational>();
107        String[] vars = ExpVector.STDVARS(rl);
108        String[] cvars = ExpVector.STDVARS(rl - 1);
109        String[] rvars = new String[] { vars[rl - 1] };
110        dfac = new GenPolynomialRing<BigRational>(mi, rl, to, vars);
111        cfac = new GenPolynomialRing<BigRational>(mi, rl - 1, to, cvars);
112        rfac = new GenPolynomialRing<GenPolynomial<BigRational>>(cfac, 1, to, rvars);
113        //System.out.println("mi = " + mi);
114    }
115
116
117    @Override
118    protected void tearDown() {
119        a = b = c = d = e = null;
120        ai = bi = ci = di = ei = null;
121        //ar = br = cr = dr = er = null;
122        mi = null;
123        ufd = null;
124        dfac = null;
125        cfac = null;
126        rfac = null;
127    }
128
129
130    /**
131     * Test base quotioent and remainder.
132     */
133    public void testBaseQR() {
134        dfac = new GenPolynomialRing<BigRational>(mi, 1, to);
135
136        for (int i = 0; i < 3; i++) {
137            a = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q);
138            c = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q);
139            //a = ufd.basePrimitivePart(a).abs();
140            //c = ufd.basePrimitivePart(c);
141            do {
142                ci = mi.random(kl * (i + 2));
143                ci = ci.sum(mi.getONE());
144            } while (ci.isZERO());
145
146            //System.out.println("a  = " + a);
147            //System.out.println("c  = " + c);
148            //System.out.println("ci = " + ci);
149
150            if (a.isZERO() || c.isZERO()) {
151                // skip for this turn
152                continue;
153            }
154            assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
155            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
156            //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
157
158            b = a.multiply(c);
159            //System.out.println("b  = " + b);
160            d = PolyUtil.<BigRational> baseSparsePseudoRemainder(b, c);
161            //System.out.println("d  = " + d);
162
163            assertTrue("rem(ac,c) == 0", d.isZERO());
164
165            b = a.multiply(ci);
166            //System.out.println("b  = " + b);
167            d = b.divide(ci);
168            //System.out.println("d  = " + d);
169
170            assertEquals("a == ac/c", a, d);
171
172            b = a.multiply(c);
173            //System.out.println("b  = " + b);
174            d = PolyUtil.<BigRational> basePseudoDivide(b, c);
175            //System.out.println("d  = " + d);
176
177            assertEquals("a == ac/c", a, d);
178
179            b = a.multiply(c).sum(dfac.getONE());
180            //System.out.println("b  = " + b);
181            //System.out.println("c  = " + c);
182            GenPolynomial<BigRational>[] qr = PolyUtil.<BigRational> basePseudoQuotientRemainder(b, c);
183            d = qr[0];
184            e = qr[1];
185            //System.out.println("d  = " + d);
186            //System.out.println("e  = " + e);
187
188            e = d.multiply(c).sum(e);
189            //System.out.println("e  = " + e);
190            assertEquals("b == b/c + b%c ", b, e);
191        }
192    }
193
194
195    /**
196     * Test base extended gcd.
197     */
198    public void testBaseExtGcd() {
199        dfac = new GenPolynomialRing<BigRational>(mi, 1, to);
200
201        for (int i = 0; i < 3; i++) {
202            a = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q);
203            b = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q);
204            c = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q);
205            //a = ufd.basePrimitivePart(a);
206            //b = ufd.basePrimitivePart(b);
207            //c = ufd.basePrimitivePart(c).abs();
208
209            //System.out.println("a  = " + a);
210            //System.out.println("b  = " + b);
211            //System.out.println("c  = " + c);
212
213            if (a.isZERO() || b.isZERO() || c.isZERO()) {
214                // skip for this turn
215                continue;
216            }
217            assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
218            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
219            //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
220
221            a = a.multiply(c);
222            b = b.multiply(c);
223
224            GenPolynomial<BigRational>[] egcd = ufd.baseExtendedGcd(a, b);
225            d = egcd[0];
226            e = PolyUtil.<BigRational> baseSparsePseudoRemainder(d, c);
227            //System.out.println("d  = " + d);
228            assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
229
230            e = egcd[1].multiply(a).sum(egcd[2].multiply(b));
231            assertEquals("gcd(a,b) = s a + t b ", d, e);
232
233            //System.out.println("a  = " + a);
234            //System.out.println("b  = " + b);
235            //System.out.println("d  = " + d);
236            GenPolynomial<BigRational>[] diop = ufd.baseGcdDiophant(a, b, d);
237            e = diop[0].multiply(a).sum(diop[1].multiply(b));
238            //System.out.println("e  = " + e);
239            assertEquals("d*gcd(a,b) = s a + t b ", d, e);
240        }
241    }
242
243
244    /**
245     * Test base partial fraction.
246     */
247    public void testBasePartFrac() {
248        dfac = new GenPolynomialRing<BigRational>(mi, 1, to);
249
250        for (int i = 0; i < 3; i++) {
251            a = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q);
252            b = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q);
253            c = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q);
254            //a = dfac.random(kl, ll + 2 * i, el + 2 * i, q);
255            //b = dfac.random(kl, ll + 2 * i, el + 2 * i, q);
256            //c = dfac.random(kl, ll + 2 * i, el + 2 * i, q);
257            //a = ufd.basePrimitivePart(a);
258            //b = ufd.basePrimitivePart(b);
259            //c = ufd.basePrimitivePart(c).abs();
260
261            if (b.isZERO() || c.isZERO()) {
262                // skip for this turn
263                continue;
264            }
265            if (b.isConstant() || c.isConstant()) {
266                // skip for this turn
267                continue;
268            }
269            //System.out.println("a  = " + a);
270            //System.out.println("b  = " + b);
271            //System.out.println("c  = " + c);
272
273            // a / (b*c) = a0 + ap/b + as/c
274            GenPolynomial<BigRational> gcd = ufd.baseGcd(b, c);
275            //System.out.println("gcd = " + gcd);
276            if (!gcd.isONE()) {
277                b = PolyUtil.<BigRational> basePseudoDivide(b, gcd);
278                c = PolyUtil.<BigRational> basePseudoDivide(c, gcd);
279            }
280            //System.out.println("b  = " + b);
281            //System.out.println("c  = " + c);
282
283            GenPolynomial<BigRational>[] pf = ufd.basePartialFraction(a, b, c);
284            //System.out.println("a0  = " + pf[0]);
285            //System.out.println("ap  = " + pf[1]);
286            //System.out.println("as  = " + pf[2]);
287
288            d = pf[0].multiply(b).multiply(c); // a0*b*c
289            //System.out.println("d  = " + d);
290
291            e = c.multiply(pf[1]).sum(b.multiply(pf[2])); // ap * b + as * c
292            //System.out.println("e  = " + e);
293
294            d = d.sum(e); // a0*b*c + ap * c + as * b
295            //System.out.println("d  = " + d);
296
297            assertEquals("a = a0*b*c + s * c + t * b ", a, d);
298
299            List<GenPolynomial<BigRational>> D = new ArrayList<GenPolynomial<BigRational>>(2);
300            D.add(b);
301            D.add(c);
302            //System.out.println("D  = " + D);
303            List<GenPolynomial<BigRational>> F = ufd.basePartialFraction(a, D);
304            //System.out.println("F  = " + F.size());
305
306            boolean t = ufd.isBasePartialFraction(a, D, F);
307            assertTrue("a/D = a0 + sum(fi/di)", t);
308        }
309    }
310
311
312    /**
313     * Test base partial fraction list.
314     */
315    public void testBasePartFracList() {
316        dfac = new GenPolynomialRing<BigRational>(mi, 1, to);
317
318        for (int i = 0; i < 3; i++) {
319            a = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q);
320            //System.out.println("a  = " + a);
321
322            List<GenPolynomial<BigRational>> D = new ArrayList<GenPolynomial<BigRational>>();
323            for (int j = 0; j < i * 3; j++) {
324                b = dfac.random(kl * (i + 1), ll + i, el + i, q);
325                if (b.isZERO() || b.isConstant()) {
326                    // skip for this turn
327                    continue;
328                }
329                D.add(b);
330            }
331            //System.out.println("D  = " + D);
332            D = ufd.coPrime(D);
333            //System.out.println("D  = " + D);
334
335            List<GenPolynomial<BigRational>> F = ufd.basePartialFraction(a, D);
336            //System.out.println("F  = " + F.size());
337
338            boolean t = ufd.isBasePartialFraction(a, D, F);
339            assertTrue("a = a0*b*c + s * c + t * b ", t);
340        }
341    }
342
343
344    /**
345     * Test base partial fraction exponent.
346     */
347    public void testBasePartFracExponent() {
348        dfac = new GenPolynomialRing<BigRational>(mi, 1, to);
349
350        for (int i = 0; i < 3; i++) {
351            a = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q);
352            //System.out.println("a  = " + a);
353
354            b = dfac.random(kl * (i + 1), ll + i, el + i, q);
355            if (b.isZERO() || b.isConstant()) {
356                // skip for this turn
357                continue;
358            }
359            //System.out.println("b  = " + b);
360
361            List<GenPolynomial<BigRational>> F = ufd.basePartialFraction(a, b, 3);
362            //System.out.println("F  = " + F);
363
364            boolean t = ufd.isBasePartialFraction(a, b, 3, F);
365            assertTrue("a/b^e = a0 + sum(ai/p^i) ", t);
366        }
367    }
368
369
370    /**
371     * Test base partial fraction list exponent (squarefree).
372     */
373    public void testBasePartFracListExponent() {
374        SquarefreeAbstract<BigRational> sqf = SquarefreeFactory.getImplementation(mi);
375
376        dfac = new GenPolynomialRing<BigRational>(mi, 1, to);
377
378        for (int i = 0; i < 3; i++) {
379            a = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q);
380            //System.out.println("a  = " + a);
381
382            List<GenPolynomial<BigRational>> D = new ArrayList<GenPolynomial<BigRational>>();
383            for (int j = 0; j < i * 3; j++) {
384                b = dfac.random(kl, ll + 1 + i, el + i, q);
385                if (b.isZERO() || b.isConstant()) {
386                    // skip for this turn
387                    continue;
388                }
389                D.add(b);
390            }
391            //System.out.println("D  = " + D);
392            D = ufd.coPrime(D);
393            //System.out.println("D  = " + D);
394
395            SortedMap<GenPolynomial<BigRational>, Long> Ds = new TreeMap<GenPolynomial<BigRational>, Long>();
396            long j = 1L;
397            for (GenPolynomial<BigRational> p : D) {
398                Ds.put(p, j);
399                j++;
400            }
401            //System.out.println("Ds = " + Ds);
402
403            List<List<GenPolynomial<BigRational>>> F = sqf.basePartialFraction(a, Ds);
404            //System.out.println("F  = " + F.size());
405
406            boolean t = sqf.isBasePartialFraction(a, Ds, F);
407            assertTrue("a/prod(b_i^i) = a0 + sum(aij/b_i^j) ", t);
408        }
409    }
410
411}