001/*
002 * $Id: RealRootTest.java 5688 2017-01-03 08:45:09Z kredel $
003 */
004
005package edu.jas.root;
006
007
008import java.util.ArrayList;
009import java.util.Collections;
010import java.util.List;
011
012import junit.framework.Test;
013import junit.framework.TestCase;
014import junit.framework.TestSuite;
015
016import edu.jas.arith.BigDecimal;
017import edu.jas.arith.BigRational;
018import edu.jas.poly.GenPolynomial;
019import edu.jas.poly.GenPolynomialRing;
020import edu.jas.poly.TermOrder;
021import edu.jas.structure.Power;
022
023
024/**
025 * RealRoot tests with JUnit.
026 * @author Heinz Kredel
027 */
028
029public class RealRootTest 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>RealRootTest</CODE> object.
042     * @param name String.
043     */
044    public RealRootTest(String name) {
045        super(name);
046    }
047
048
049    /**
050     */
051    public static Test suite() {
052        TestSuite suite = new TestSuite(RealRootTest.class);
053        return suite;
054    }
055
056
057    TermOrder to = new TermOrder(TermOrder.INVLEX);
058
059
060    GenPolynomialRing<BigRational> dfac;
061
062
063    BigRational ai;
064
065
066    BigRational bi;
067
068
069    BigRational ci;
070
071
072    BigRational di;
073
074
075    BigRational ei;
076
077
078    BigRational eps;
079
080
081    GenPolynomial<BigRational> a;
082
083
084    GenPolynomial<BigRational> b;
085
086
087    GenPolynomial<BigRational> c;
088
089
090    GenPolynomial<BigRational> d;
091
092
093    GenPolynomial<BigRational> e;
094
095
096    int rl = 1;
097
098
099    int kl = 5;
100
101
102    int ll = 7;
103
104
105    int el = 7;
106
107
108    float q = 0.7f;
109
110
111    @Override
112    protected void setUp() {
113        a = b = c = d = e = null;
114        ai = bi = ci = di = ei = null;
115        String[] vars = new String[] { "x" };
116        dfac = new GenPolynomialRing<BigRational>(new BigRational(1), rl, to, vars);
117        // eps = new BigRational(1L,1000000L*1000000L*1000000L);
118        eps = Power.positivePower(new BigRational(1L, 10L), BigDecimal.DEFAULT_PRECISION);
119    }
120
121
122    @Override
123    protected void tearDown() {
124        a = b = c = d = e = null;
125        ai = bi = ci = di = ei = null;
126        dfac = null;
127        eps = null;
128    }
129
130
131    /**
132     * Test Sturm sequence.
133     * 
134     */
135    public void testSturmSequence() {
136        a = dfac.random(kl, ll, el, q);
137        //System.out.println("a = " + a);
138
139        RealRootsSturm<BigRational> rrs = new RealRootsSturm<BigRational>();
140
141        List<GenPolynomial<BigRational>> S = rrs.sturmSequence(a);
142        //System.out.println("S = " + S);
143
144        try {
145            b = a.remainder(S.get(0));
146        } catch (Exception e) {
147            fail("not S(0)|f " + e);
148        }
149        assertTrue("a mod S(0) == 0 ", b.isZERO());
150
151        assertTrue("S(-1) == 1 ", S.get(S.size() - 1).isConstant());
152    }
153
154
155    /**
156     * Test root bound.
157     * 
158     */
159    public void testRootBound() {
160        a = dfac.random(kl, ll, el, q);
161        //System.out.println("a = " + a);
162
163        RealRoots<BigRational> rr = new RealRootsSturm<BigRational>();
164
165        BigRational M = rr.realRootBound(a);
166
167        //System.out.println("M = " + M);
168        assertTrue("M >= 1 ", M.compareTo(BigRational.ONE) >= 0);
169
170        a = a.monic();
171        //System.out.println("a = " + a);
172        M = rr.realRootBound(a);
173
174        //System.out.println("M = " + M);
175        assertTrue("M >= 1 ", M.compareTo(BigRational.ONE) >= 0);
176    }
177
178
179    /**
180     * Test real root isolation.
181     * 
182     */
183    public void testRealRootIsolation() {
184        a = dfac.random(kl, ll * 2, el * 2, q);
185        //a = a.multiply( dfac.univariate(0) );
186        //System.out.println("a = " + a);
187
188        RealRoots<BigRational> rr = new RealRootsSturm<BigRational>();
189
190        List<Interval<BigRational>> R = rr.realRoots(a);
191        //System.out.println("R = " + R);
192        //assertTrue("#roots >= 0 ", R.size() >= 0);
193        assertTrue("#roots >= 0 ", R != null);
194    }
195
196
197    /**
198     * Test real root isolation Wilkinson polynomials.
199     * p = (x-0)*(x-1)*(x-2)*(x-3)*...*(x-n)
200     */
201    public void testRealRootIsolationWilkinson() {
202        final int N = 10;
203        d = dfac.getONE();
204        e = dfac.univariate(0);
205
206        List<Interval<BigRational>> Rn = new ArrayList<Interval<BigRational>>(N);
207        a = d;
208        for (int i = 0; i < N; i++) {
209            c = dfac.fromInteger(i);
210            Rn.add(new Interval<BigRational>(c.leadingBaseCoefficient()));
211            b = e.subtract(c);
212            a = a.multiply(b);
213        }
214        //System.out.println("a = " + a);
215
216        RealRoots<BigRational> rr = new RealRootsSturm<BigRational>();
217
218        List<Interval<BigRational>> R = rr.realRoots(a);
219        //System.out.println("R = " + R);
220
221        assertTrue("#roots = " + N + " ", R.size() == N);
222
223        //System.out.println("eps = " + eps);
224        //BigDecimal eps1 = new BigDecimal(eps);
225        //System.out.println("eps1 = " + eps1);
226
227        R = rr.refineIntervals(R, a, eps);
228        //System.out.println("R = " + R);
229        int i = 0;
230        for (Interval<BigRational> v : R) {
231            BigDecimal dd = v.toDecimal(); //.sum(eps1);
232            BigDecimal di = Rn.get(i++).toDecimal();
233            //System.out.println("v  = " + dd);
234            //System.out.println("vi = " + di);
235            assertTrue("|dd - di| < eps ", dd.compareTo(di) == 0);
236        }
237    }
238
239
240    /**
241     * Test real root isolation Wilkinson polynomials inverse.
242     * p = (x-1)*(x-1/2)*(x-1/3)*...*(x-1/n)
243     */
244    public void testRealRootIsolationWilkinsonInverse() {
245        final int N = 9;
246        d = dfac.getONE();
247        e = dfac.univariate(0);
248
249        List<Interval<BigRational>> Rn = new ArrayList<Interval<BigRational>>(N);
250        a = d;
251        for (int i = 1; i < N; i++) { // use only for i > 0, since reverse
252            c = dfac.fromInteger(i);
253            if (i != 0) {
254                c = d.divide(c);
255            }
256            Rn.add(new Interval<BigRational>(c.leadingBaseCoefficient()));
257            b = e.subtract(c);
258            a = a.multiply(b);
259        }
260        //System.out.println("a = " + a);
261        //System.out.println("Rn = " + Rn);
262        Collections.reverse(Rn);
263        //System.out.println("Rn = " + Rn);
264
265        RealRoots<BigRational> rr = new RealRootsSturm<BigRational>();
266
267        List<Interval<BigRational>> R = rr.realRoots(a);
268        //System.out.println("R = " + R);
269
270        assertTrue("#roots = " + (N - 1) + " ", R.size() == (N - 1));
271
272        //System.out.println("eps = " + eps);
273        //BigDecimal eps1 = new BigDecimal(eps);
274        //System.out.println("eps1 = " + eps1);
275
276        R = rr.refineIntervals(R, a, eps);
277        //System.out.println("R = " + R);
278        int i = 0;
279        for (Interval<BigRational> v : R) {
280            BigDecimal dd = v.toDecimal(); //.sum(eps1);
281            BigDecimal di = Rn.get(i++).toDecimal();
282            //System.out.println("v  = " + dd);
283            //System.out.println("vi = " + di);
284            assertTrue("|dd - di| < eps ", dd.compareTo(di) == 0);
285        }
286    }
287
288
289    /**
290     * Test real algebraic number sign.
291     * 
292     */
293    public void testRealAlgebraicNumberSign() {
294        d = dfac.fromInteger(2);
295        e = dfac.univariate(0);
296
297        a = e.multiply(e);
298        // a = a.multiply(e).multiply(e).multiply(e);
299        a = a.subtract(d); // x^2 -2
300        //System.out.println("a = " + a);
301
302        RealRoots<BigRational> rr = new RealRootsSturm<BigRational>();
303
304        ai = new BigRational(1);
305        bi = new BigRational(2);
306        Interval<BigRational> iv = new Interval<BigRational>(ai, bi);
307        //System.out.println("iv = " + iv);
308        assertTrue("sign change", rr.signChange(iv, a));
309
310        b = dfac.random(kl, (int) a.degree() + 1, (int) a.degree(), 1.0f);
311        //b = dfac.getZERO();
312        //b = dfac.random(kl,ll,el,q);
313        //b = b.multiply(b);
314        //b = b.abs().negate();
315        //System.out.println("b = " + b);
316        if (b.isZERO()) {
317            int s = rr.realSign(iv, a, b);
318            assertTrue("algebraic sign", s == 0);
319            return;
320        }
321
322        int as = rr.realSign(iv, a, b);
323        //System.out.println("as = " + as);
324        // how to test?
325        int asn = rr.realSign(iv, a, b.negate());
326        //System.out.println("asn = " + asn);
327        assertTrue("algebraic sign", as != asn);
328
329        iv = new Interval<BigRational>(bi.negate(), ai.negate());
330        //System.out.println("iv = " + iv);
331        assertTrue("sign change", rr.signChange(iv, a));
332
333        int as1 = rr.realSign(iv, a, b);
334        //System.out.println("as1 = " + as1);
335        // how to test?
336        int asn1 = rr.realSign(iv, a, b.negate());
337        //System.out.println("asn1 = " + asn1);
338        assertTrue("algebraic sign", as1 != asn1);
339
340        assertTrue("algebraic sign", as * as1 == asn * asn1);
341    }
342
343
344    /**
345     * Test real root isolation and decimal refinement of Wilkinson polynomials.
346     * p = (x-0)*(x-1)*(x-2)*(x-3)*...*(x-n)
347     */
348    public void testRealRootIsolationDecimalWilkinson() {
349        final int N = 10;
350        d = dfac.getONE();
351        e = dfac.univariate(0);
352
353        List<Interval<BigRational>> Rn = new ArrayList<Interval<BigRational>>(N);
354        a = d;
355        for (int i = 0; i < N; i++) {
356            c = dfac.fromInteger(i);
357            Rn.add(new Interval<BigRational>(c.leadingBaseCoefficient()));
358            b = e.subtract(c);
359            a = a.multiply(b);
360        }
361        //System.out.println("a = " + a);
362
363        RealRootsAbstract<BigRational> rr = new RealRootsSturm<BigRational>();
364
365        List<Interval<BigRational>> R = rr.realRoots(a);
366        //System.out.println("R = " + R);
367
368        assertTrue("#roots = " + N + " ", R.size() == N);
369
370        eps = eps.multiply(new BigRational(100000));
371        //System.out.println("eps = " + eps);
372        BigDecimal eps1 = new BigDecimal(eps);
373        BigDecimal eps2 = eps1.multiply(new BigDecimal("100"));
374        //System.out.println("eps1 = " + eps1);
375        //System.out.println("eps2 = " + eps2);
376
377        try {
378            int i = 0;
379            for (Interval<BigRational> v : R) {
380                //System.out.println("v = " + v);
381                BigDecimal dd = rr.approximateRoot(v,a,eps);
382                BigDecimal di = Rn.get(i++).toDecimal();
383                //System.out.println("di = " + di);
384                //System.out.println("dd = " + dd);
385                assertTrue("|dd - di| < eps ", dd.subtract(di).abs().compareTo(eps2) <= 0);
386            }
387        } catch (NoConvergenceException e) {
388            fail(e.toString());
389        }
390    }
391
392
393    /**
394     * Test real root isolation and decimal refinement of Wilkinson polynomials, inverse roots.
395     * p = (x-1)*(x-1/2)*(x-1/3)*...*(x-1/n)
396     */
397    public void testRealRootIsolationDecimalWilkinsonInverse() {
398        final int N = 10;
399        d = dfac.getONE();
400        e = dfac.univariate(0);
401
402        List<Interval<BigRational>> Rn = new ArrayList<Interval<BigRational>>(N);
403        a = d;
404        for (int i = 1; i < N; i++) { // use only for i > 0, since reverse
405            c = dfac.fromInteger(i);
406            if (i != 0) {
407                c = d.divide(c);
408            }
409            Rn.add(new Interval<BigRational>(c.leadingBaseCoefficient()));
410            b = e.subtract(c);
411            a = a.multiply(b);
412        }
413        //System.out.println("a = " + a);
414        //System.out.println("Rn = " + Rn);
415        Collections.reverse(Rn);
416        //System.out.println("Rn = " + Rn);
417
418        RealRootsAbstract<BigRational> rr = new RealRootsSturm<BigRational>();
419
420        List<Interval<BigRational>> R = rr.realRoots(a);
421        //System.out.println("R = " + R);
422
423        assertTrue("#roots = " + (N - 1) + " ", R.size() == (N - 1));
424
425        eps = eps.multiply(new BigRational(1000000));
426        //System.out.println("eps = " + eps);
427        BigDecimal eps1 = new BigDecimal(eps);
428        BigDecimal eps2 = eps1.multiply(new BigDecimal("10"));
429        //System.out.println("eps1 = " + eps1);
430        //System.out.println("eps2 = " + eps2);
431
432        try {
433            int i = 0;
434            for (Interval<BigRational> v : R) {
435                //System.out.println("v = " + v);
436                BigDecimal dd = rr.approximateRoot(v,a,eps);
437                BigDecimal di = Rn.get(i++).toDecimal();
438                //System.out.println("di = " + di);
439                //System.out.println("dd = " + dd);
440                assertTrue("|dd - di| < eps ", dd.subtract(di).abs().compareTo(eps2) <= 0);
441            }
442        } catch (NoConvergenceException e) {
443            fail(e.toString());
444        }
445    }
446
447
448    /**
449     * Test real root isolation and decimal refinement of Wilkinson polynomials, all roots.
450     * p = (x-0)*(x-1)*(x-2)*(x-3)*...*(x-n)
451     */
452    public void testRealRootIsolationDecimalWilkinsonAll() {
453        final int N = 10; 
454        d = dfac.getONE();
455        e = dfac.univariate(0);
456
457        List<Interval<BigRational>> Rn = new ArrayList<Interval<BigRational>>(N);
458        a = d;
459        for (int i = 0; i < N; i++) {
460            c = dfac.fromInteger(i);
461            Rn.add(new Interval<BigRational>(c.leadingBaseCoefficient()));
462            b = e.subtract(c);
463            a = a.multiply(b);
464        }
465        //System.out.println("a = " + a);
466
467        RealRootsAbstract<BigRational> rr = new RealRootsSturm<BigRational>();
468
469        eps = eps.multiply(new BigRational(10000));
470        //System.out.println("eps = " + eps);
471        BigDecimal eps1 = new BigDecimal(eps);
472        BigDecimal eps2 = eps1.multiply(new BigDecimal("100"));
473        //System.out.println("eps1 = " + eps1);
474        //System.out.println("eps2 = " + eps2);
475
476        List<BigDecimal> R = null;
477        R = rr.approximateRoots(a,eps);
478        //System.out.println("R = " + R);
479        assertTrue("#roots = " + N + " ", R.size() == N);
480
481        int i = 0;
482        for (BigDecimal dd : R) {
483            //System.out.println("dd = " + dd);
484            BigDecimal di = Rn.get(i++).toDecimal();
485            //System.out.println("di = " + di);
486            assertTrue("|dd - di| < eps ", dd.subtract(di).abs().compareTo(eps2) <= 0);
487        }
488        boolean t = rr.isApproximateRoot(R,a,eps);
489        assertTrue("some |a(dd)| < eps ", t);
490    }
491
492
493    /**
494     * Test real root isolation and decimal refinement of Wilkinson polynomials, inverse roots, all roots.
495     * p = (x-1)*(x-1/2)*(x-1/3)*...*(x-1/n)
496     */
497    public void testRealRootIsolationDecimalWilkinsonInverseAll() {
498        final int N = 10;
499        d = dfac.getONE();
500        e = dfac.univariate(0);
501
502        List<Interval<BigRational>> Rn = new ArrayList<Interval<BigRational>>(N);
503        a = d;
504        for (int i = 1; i < N; i++) { // use only for i > 0, since reverse
505            c = dfac.fromInteger(i);
506            if (i != 0) {
507                c = d.divide(c);
508            }
509            Rn.add(new Interval<BigRational>(c.leadingBaseCoefficient()));
510            b = e.subtract(c);
511            a = a.multiply(b);
512        }
513        //System.out.println("a = " + a);
514        //System.out.println("Rn = " + Rn);
515        Collections.reverse(Rn);
516        //System.out.println("Rn = " + Rn);
517
518        RealRootsAbstract<BigRational> rr = new RealRootsSturm<BigRational>();
519
520        eps = eps.multiply(new BigRational(1000000));
521        //System.out.println("eps = " + eps);
522        BigDecimal eps1 = new BigDecimal(eps);
523        BigDecimal eps2 = eps1.multiply(new BigDecimal("10"));
524        //System.out.println("eps1 = " + eps1);
525        //System.out.println("eps2 = " + eps2);
526
527        List<BigDecimal> R = null;
528        R = rr.approximateRoots(a,eps);
529        //System.out.println("R = " + R);
530        assertTrue("#roots = " + (N - 1) + " ", R.size() == (N - 1));
531
532        int i = 0;
533        for (BigDecimal dd : R) {
534            //System.out.println("dd = " + dd);
535            BigDecimal di = Rn.get(i++).toDecimal();
536            //System.out.println("di = " + di);
537            assertTrue("|dd - di| < eps ", dd.subtract(di).abs().compareTo(eps2) <= 0);
538        }
539        boolean t = rr.isApproximateRoot(R,a,eps);
540        assertTrue("some |a(dd)| < eps ", t);
541    }
542
543}