Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.application;
006
007
008import java.util.ArrayList;
009import java.util.List;
010
011import edu.jas.arith.BigDecimal;
012import edu.jas.arith.BigRational;
013import edu.jas.kern.ComputerThreads;
014import edu.jas.poly.Complex;
015import edu.jas.poly.ComplexRing;
016import edu.jas.poly.GenPolynomial;
017import edu.jas.poly.GenPolynomialRing;
018import edu.jas.poly.PolyUtil;
019import edu.jas.poly.TermOrder;
020import edu.jas.structure.Power;
021import edu.jas.ufd.Squarefree;
022import edu.jas.ufd.SquarefreeFactory;
023
024import junit.framework.Test;
025import junit.framework.TestCase;
026import junit.framework.TestSuite;
027
028
029/**
030 * RootUtil tests with JUnit.
031 * @author Heinz Kredel
032 */
033
034public class ComplexRootTest extends TestCase {
035
036
037    /**
038     * main.
039     */
040    public static void main(String[] args) {
041
042        junit.textui.TestRunner.run(suite());
043        ComputerThreads.terminate();
044    }
045
046
047    /**
048     * Constructs a <CODE>ComplexRootTest</CODE> object.
049     * @param name String.
050     */
051    public ComplexRootTest(String name) {
052        super(name);
053    }
054
055
056    /**
057     */
058    public static Test suite() {
059        TestSuite suite = new TestSuite(ComplexRootTest.class);
060        return suite;
061    }
062
063
064    TermOrder to = new TermOrder(TermOrder.INVLEX);
065
066
067    GenPolynomialRing<BigRational> rfac;
068
069
070    GenPolynomialRing<Complex<BigRational>> dfac;
071
072
073    ComplexRing<BigRational> cfac;
074
075
076    BigRational eps;
077
078
079    Complex<BigRational> ceps;
080
081
082    BigDecimal deps;
083
084
085    GenPolynomial<Complex<BigRational>> a, b, c, d, e;
086
087
088    int rl = 1;
089
090
091    int kl = 3;
092
093
094    int ll = 3;
095
096
097    int el = 5;
098
099
100    float q = 0.7f;
101
102
103    @Override
104    protected void setUp() {
105        a = b = c = d = e = null;
106        cfac = new ComplexRing<BigRational>(new BigRational(1));
107        String[] vars = new String[] { "z" };
108        dfac = new GenPolynomialRing<Complex<BigRational>>(cfac, to, vars);
109        rfac = new GenPolynomialRing<BigRational>(new BigRational(1), to, vars);
110        eps = Power.positivePower(new BigRational(1L, 10L), BigDecimal.DEFAULT_PRECISION);
111        ceps = new Complex<BigRational>(cfac, eps);
112        deps = new BigDecimal(
113                        Power.positivePower(new BigRational(1L, 10L), BigDecimal.DEFAULT_PRECISION - 2));
114    }
115
116
117    @Override
118    protected void tearDown() {
119        a = b = c = d = e = null;
120        dfac = null;
121        cfac = null;
122        eps = null;
123    }
124
125
126    /**
127     * Test complex roots, imaginary.
128     */
129    public void testComplexRootsImag() {
130        //Complex<BigRational> I = cfac.getIMAG(); 
131        //a = dfac.parse("z^3 - i2"); 
132        //a = dfac.random(ll+1).monic();
133        //a = dfac.parse("z^7 - 2 z");
134        a = dfac.parse("z^6 - i3");
135        //System.out.println("a = " + a);
136
137        List<Complex<RealAlgebraicNumber<BigRational>>> roots;
138        roots = RootFactoryApp.<BigRational> complexAlgebraicNumbersComplex(a);
139        //System.out.println("a = " + a);
140        //System.out.println("roots = " + roots);
141        assertTrue("#roots == deg(a) ", roots.size() == a.degree(0));
142        for (Complex<RealAlgebraicNumber<BigRational>> root : roots) {
143            //System.out.println("root = " + root.getRe().decimalMagnitude() + " + " + root.getIm().decimalMagnitude() + " i");
144            assertTrue("f(r) == 0: " + root, RootFactoryApp.<BigRational> isRoot(a, root));
145        }
146    }
147
148
149    /*
150     * Test complex roots, random polynomial.
151     */
152    public void testComplexRootsRand() {
153        //Complex<BigRational> I = cfac.getIMAG(); 
154        a = dfac.random(2, ll, el, 0.37f).monic();
155        if (a.isZERO() || a.isONE()) {
156            a = dfac.parse("z^6 - i3");
157        }
158        //a = dfac.parse("z^3 - ( 1600/6123i-280/2041 )"); // fail, todo
159        //a = dfac.parse("z^3 - ( 1600/6123 )"); // fail, shows only one root
160        //a = dfac.parse("z^3 - ( 16/32i-280/2041 )"); // okay, 3 roots
161        Squarefree<Complex<BigRational>> sqf = SquarefreeFactory
162                        .<Complex<BigRational>> getImplementation(cfac);
163        a = sqf.squarefreePart(a);
164        //System.out.println("a = " + a);
165        List<Complex<RealAlgebraicNumber<BigRational>>> roots;
166        roots = RootFactoryApp.<BigRational> complexAlgebraicNumbersComplex(a);
167        //roots = RootFactoryApp.<BigRational> complexAlgebraicNumbersSquarefree(a);
168        //System.out.println("a = " + a);
169        //System.out.println("roots = " + roots);
170        assertTrue("#roots - deg(a): " + (roots.size() - a.degree(0)) + ", a = " + a,
171                        roots.size() == a.degree(0));
172        for (Complex<RealAlgebraicNumber<BigRational>> root : roots) {
173            //System.out.println("root = " + root.getRe().decimalMagnitude() + " + " + root.getIm().decimalMagnitude() + " i");
174            assertTrue("f(r) == 0: " + root, RootFactoryApp.<BigRational> isRoot(a, root));
175        }
176    }
177
178
179    /**
180     * Test polynomial with complex roots.
181     */
182    public void testPolynomialComplexRoots() {
183        a = dfac.parse("z^3 - 2");
184        //System.out.println("a = " + a);
185        List<Complex<RealAlgebraicNumber<BigRational>>> roots = RootFactoryApp
186                        .<BigRational> complexAlgebraicNumbersComplex(a);
187        //System.out.println("a = " + a);
188        //System.out.println("roots = " + roots);
189        assertTrue("#roots == deg(a) ", roots.size() == a.degree(0));
190        for (Complex<RealAlgebraicNumber<BigRational>> car : roots) {
191            //System.out.println("car = " + car);
192            RealAlgebraicRing<BigRational> rfac = car.getRe().ring;
193            rfac.setField(true); // ?? to check
194            assertTrue("isField(rfac) ", rfac.isField());
195            assertTrue("f(r) == 0: " + car, RootFactoryApp.<BigRational> isRoot(a, car));
196        }
197        Complex<RealAlgebraicNumber<BigRational>> root = roots.get(2); // 0,1,2)
198        //System.out.println("a = " + a);
199        //System.out.println("root = " + root.getRe().decimalMagnitude() + " + "
200        //                  + root.getIm().decimalMagnitude() + " i");
201        //System.out.println("root = " + root.getRe() + " + " + root.getIm() + " i");
202        //String vre = root.getRe().toString().replace("{", "").replace("}", "").trim();
203        //String vim = root.getIm().toString().replace("{", "").replace("}", "").trim();
204        //System.out.println("vre = " + vre);
205        //System.out.println("vim = " + vim);
206        //String IM = root.ring.getIMAG().toString().replace("{", "").replace("}", "").replace(" ", "").trim();
207        //System.out.println("IM  = " + IM);
208
209        GenPolynomialRing<Complex<RealAlgebraicNumber<BigRational>>> cring = new GenPolynomialRing<Complex<RealAlgebraicNumber<BigRational>>>(
210                        root.ring, to, new String[] { "t" });
211        //List<GenPolynomial<Complex<RealAlgebraicNumber<BigRational>>>> gens = cring.generators();
212        //System.out.println("gens  = " + gens);
213
214        GenPolynomial<Complex<RealAlgebraicNumber<BigRational>>> cpol;
215        //cpol = cring.random(1, 4, 4, q);
216
217        //cpol = cring.univariate(0,3L).subtract(cring.fromInteger(2L));
218        //cpol = cring.univariate(0,3L).subtract(gens.get(2));
219        //cpol = cring.univariate(0,5L).subtract(cring.univariate(0,2L).multiply(root));
220        //cpol = cring.univariate(0,4L).subtract(root);
221        //cpol = cring.univariate(0,4L).subtract(root.multiply(root));
222        //cpol = cring.univariate(0,3L).subtract(cring.univariate(0,1L).multiply(root).sum(root.multiply(root)));
223        cpol = cring.univariate(0, 2L).subtract(root.multiply(root)); // okay
224        //cpol = cring.univariate(0,3L).subtract(root.multiply(root)); // okay
225        //cpol = cring.univariate(0,3L).subtract(root.multiply(root).multiply(root)); // not much sense r^3 = 2
226        ///String vpol = vre + " + " + IM + " " + vim;
227        //String vpol = " 3 + " + IM + " * 3 ";
228        //String vpol = " 3i3 ";
229        //String vpol = IM + " " + vim;
230        //String vpol = " 2 ";// + vre; // + " " + IM;
231        //String vpol = vre; // + " " + IM;
232        //System.out.println("vpol = " + vpol);
233        //cpol = cring.univariate(0, 3L).subtract(cring.parse(vpol));
234        cpol = cpol.monic();
235        //System.out.println("cpol = " + cpol);
236        //long dd = cpol.degree(0);
237        Squarefree<Complex<RealAlgebraicNumber<BigRational>>> sen = SquarefreeFactory
238                        .<Complex<RealAlgebraicNumber<BigRational>>> getImplementation(root.ring);
239        cpol = sen.squarefreePart(cpol);
240        //if (cpol.degree(0) < dd) {
241        //System.out.println("cpol = " + cpol);
242        //}
243        //System.out.println("cpol = " + cpol);
244
245        // new version with recursion: with real factorization
246        long t1 = System.currentTimeMillis();
247        List<Complex<RealAlgebraicNumber<RealAlgebraicNumber<BigRational>>>> croots = RootFactoryApp
248                        .<RealAlgebraicNumber<BigRational>> complexAlgebraicNumbersComplex(cpol);
249        t1 = System.currentTimeMillis() - t1;
250        assertTrue("nonsense " + t1, t1 >= 0L);
251        //System.out.println("\na = " + a.toScript());
252        //System.out.println("root = " + root.getRe().decimalMagnitude() + " + "
253        //                             + root.getIm().decimalMagnitude() + " i");
254        //System.out.println("a = " + a);
255        //System.out.println("root = " + root.getRe().decimalMagnitude() + " + "
256        //                  + root.getIm().decimalMagnitude() + " i");
257        //System.out.println("root = " + root.getRe() + " + (" + root.getIm() + ") i");
258        //System.out.println("root.ring = " + root.ring);
259        //System.out.println("cpol      = " + cpol);
260        //System.out.println("cpol.ring = " + cpol.ring);
261        //System.out.println("croots = " + croots);
262        for (Complex<RealAlgebraicNumber<RealAlgebraicNumber<BigRational>>> croot : croots) {
263            //System.out.println("croot = " + croot);
264            //System.out.println("croot = " + croot.getRe() + " + ( " + croot.getIm() + ") i");
265            //System.out.println("croot.ring = " + croot.ring); //magnitude());
266            //System.out.println("croot = " + croot.getRe().decimalMagnitude() + " + "
267            //                              + croot.getIm().decimalMagnitude() + " i");
268            assertTrue("f(r) == 0: " + croot,
269                            RootFactoryApp.<RealAlgebraicNumber<BigRational>> isRoot(cpol, croot));
270        }
271        assertTrue("#croots == deg(cpol) " + croots.size() + " != " + cpol.degree(0),
272                        croots.size() == cpol.degree(0));
273
274
275        // existing version with winding number and recursion: but only one step
276        long t2 = System.currentTimeMillis();
277        List<edu.jas.root.ComplexAlgebraicNumber<RealAlgebraicNumber<BigRational>>> coroots = edu.jas.root.RootFactory
278                        .<RealAlgebraicNumber<BigRational>> complexAlgebraicNumbersComplex(cpol);
279        t2 = System.currentTimeMillis() - t2;
280        assertTrue("nonsense " + t2, t2 >= 0L);
281        //System.out.println("\ncpol = " + cpol);
282        //System.out.println("root = " + root.getRe() + " + (" + root.getIm() + ") i");
283        //System.out.println("root = " + root.getRe().decimalMagnitude() + " + "
284        //                             + root.getIm().decimalMagnitude() + " i");
285        for (edu.jas.root.ComplexAlgebraicNumber<RealAlgebraicNumber<BigRational>> cr2 : coroots) {
286            //System.out.println("r2.ring = " + cr2.ring); //magnitude());
287            assertTrue("f(r) == 0: " + cr2, edu.jas.root.RootFactory
288                            .<RealAlgebraicNumber<BigRational>> isRootComplex(cpol, cr2));
289        }
290
291        // decimal for comparison
292        long t3 = System.currentTimeMillis();
293        for (Complex<RealAlgebraicNumber<RealAlgebraicNumber<BigRational>>> croot : croots) {
294            String crs = croot.getRe().decimalMagnitude() + " + " + croot.getIm().decimalMagnitude() + " i";
295            //System.out.println("croot = " + crs);
296            assertFalse("crs not empty", crs.length() == 0); // java-5
297        }
298        t3 = System.currentTimeMillis() - t3;
299        assertTrue("nonsense " + t3, t3 >= 0L);
300        long t4 = System.currentTimeMillis();
301        for (edu.jas.root.ComplexAlgebraicNumber<RealAlgebraicNumber<BigRational>> cr2 : coroots) {
302            String crs = cr2.decimalMagnitude().toString();
303            //System.out.println("r2.dec  = " + crs);
304            assertFalse("crs not empty", crs.length() == 0); // java-5
305        }
306        t4 = System.currentTimeMillis() - t4;
307        assertTrue("nonsense " + t4, t4 >= 0L);
308        assertTrue("#coroots == deg(cpol) ", coroots.size() == cpol.degree(0));
309        //System.out.println("time, real ideal = " + t1 + "+" + t3 + ", complex winding = " + t2 + "+" + t4 + " milliseconds");
310    }
311
312
313    /**
314     * Test 0-dim ideal with complex roots.
315     */
316    public void testIdealComplexRoots() {
317        String[] vars = new String[] { "x", "z" };
318        rfac = new GenPolynomialRing<BigRational>(new BigRational(1), to, vars);
319        GenPolynomial<BigRational> ar, br;
320        ar = rfac.parse("z^3 - 2");
321        br = rfac.parse("x^2 - 3");
322        //System.out.println("ar = " + ar + ", deg(ar) = " + ar.degree(1));
323        //System.out.println("br = " + br + ", deg(br) = " + br.degree(0));
324        List<GenPolynomial<BigRational>> M;
325        M = new ArrayList<GenPolynomial<BigRational>>();
326        M.add(ar);
327        M.add(br);
328        //System.out.println("M = " + M);
329
330        Ideal<BigRational> I = new Ideal<BigRational>(rfac, M);
331        //System.out.println("I = " + I);
332
333        List<List<Complex<BigDecimal>>> roots = PolyUtilApp.<BigRational> complexRootTuples(I, eps);
334        //System.out.println("roots = " + roots);
335        assertEquals("#roots == deg(a)*deg(b) ", roots.size(), ar.degree(1) * br.degree(0));
336
337        a = PolyUtil.<BigRational> toComplex(dfac, ar);
338        b = PolyUtil.<BigRational> toComplex(dfac, br);
339        GenPolynomialRing<Complex<BigDecimal>> pfac;
340        pfac = new GenPolynomialRing<Complex<BigDecimal>>(new ComplexRing<BigDecimal>(new BigDecimal(1)),
341                        rfac);
342        GenPolynomial<Complex<BigDecimal>> ac, bc;
343        ac = PolyUtil.<BigRational> complexDecimalFromRational(pfac, a);
344        bc = PolyUtil.<BigRational> complexDecimalFromRational(pfac, b);
345        List<GenPolynomial<Complex<BigDecimal>>> Mc;
346        Mc = new ArrayList<GenPolynomial<Complex<BigDecimal>>>();
347        Mc.add(ac);
348        Mc.add(bc);
349        //System.out.println("Mc = " + Mc);
350        assertTrue("isComplexRoots: " + roots, PolyUtilApp.<BigRational> isComplexRoots(Mc, roots, deps));
351    }
352
353
354    /**
355     * Test 0-dim ideal with real roots.
356     */
357    public void testIdealRealRoots() {
358        String[] vars = new String[] { "x", "z" };
359        rfac = new GenPolynomialRing<BigRational>(new BigRational(1), to, vars);
360        GenPolynomial<BigRational> ar, br;
361        ar = rfac.parse("z^3 - 2");
362        br = rfac.parse("x^2 - 3");
363        //System.out.println("ar = " + ar + ", deg(ar) = " + ar.degree(1));
364        //System.out.println("br = " + br + ", deg(br) = " + br.degree(0));
365
366        List<GenPolynomial<BigRational>> M;
367        M = new ArrayList<GenPolynomial<BigRational>>();
368        M.add(ar);
369        M.add(br);
370        //System.out.println("M = " + M);
371
372        Ideal<BigRational> I = new Ideal<BigRational>(rfac, M);
373        //System.out.println("I = " + I);
374
375        List<List<BigDecimal>> roots = PolyUtilApp.<BigRational> realRootTuples(I, eps);
376        //System.out.println("roots = " + roots);
377        assertEquals("#roots == deg(a)*deg(b) ", roots.size(), 2);
378
379        GenPolynomialRing<BigDecimal> pfac;
380        pfac = new GenPolynomialRing<BigDecimal>(new BigDecimal(1), rfac);
381        List<GenPolynomial<BigDecimal>> Md;
382        Md = new ArrayList<GenPolynomial<BigDecimal>>();
383        Md.add(PolyUtil.<BigRational> decimalFromRational(pfac, ar));
384        Md.add(PolyUtil.<BigRational> decimalFromRational(pfac, br));
385        //System.out.println("Md = " + Md);
386        assertTrue("isRealRoots: " + roots, PolyUtilApp.<BigRational> isRealRoots(Md, roots, deps));
387    }
388
389}