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