Decoration
max planck institut
informatik
mpii logo Minerva of the Max Planck Society

Bit-Stream Descartes


Introduction

This page reports on some first experiments with the Bit-Stream Descartes Method for root isolation of square-free polynomials whose coefficients can be approximated to within an arbitrarily small but positive error bound. The key to get this done for all inputs is to avoid interval endpoints close to complex roots, and to represent the polynomial in the Bernstein basis in order to exploit its good numerical properties. For a description of the algorithm, see the following article.


Variants

We compare the following variants of the Descartes method.

The four variants have been implemented by the same team in a straightforward fashion without any advanced optimized techniques. Hence our experiments give a valid first impression of the relative performance of our new approach compared to exact arithmetic, but they are not the final word.


Experiments

We measured running times on an 1.2 GHz Pentium IIIM using LEDA-4.5 integer arithmetic, and averaged over 5 runs for each polynomial. The time for obtaining approximate power basis coefficients and converting to approximate Bernstein basis coefficients is included in the measurements. The initial interval enclosing all roots of anxn +...+ aixi +...+ a1x + a0 is obtained using the Lagrange-Zassenhaus bound 2 maxi<n (|ai|/|an|)1/(n-i).

Random Polynomials

To generate random polynomials, we choose n+1 integer points from [-2L, +2L]×[-2L, +2L] at random, interpolate a polynomial through them, and clear denominators. This results in random polynomials with integer coefficients and many real roots (see table below). On these instances, we compared our three new variants against the usual Bernstein Descartes method implemented in exact arithmetic. The table reports the average bitlength of the longest coefficient in power basis (usually the constant term).
To show that our method is largely unaffected by irrationality of coefficients, the last column reports on an L=50 instance generated by taking a polynomial interpolating through n random points (as above) and multiplying it with the irrational factor x - (1231/5+3211/7). This results in polynomials with coefficients that are algebraic of degree 35.

  n=30 n=60
L=10 L=30 L=50 ×(x-...) L=10 L=30 L=50 ×(x-...)
avg # real roots 28.6 27.8 28.4 27.2 54.2 58.8 58.0 57.6
avg max cof bits 1370 10642 19752 n/a 2710 37339 73456 n/a
DescartesrndL 83 ms 86 ms 90 ms 84 ms 734 ms 799 ms 841 ms 801 ms
DescartesrndLbias 40 ms 44 ms 47 ms 41 ms 351 ms 379 ms 428 ms 356 ms
DescartesrndG 41 ms 45 ms 49 ms   42 ms 353 ms 384 ms 423 ms  362 ms
Descartesinteger   41 ms  143 ms  266 ms n/a  403 ms 3328 ms 7996 ms n/a

These measurements indicate that our Bit-Stream Descartes Method succeeds in avoiding the extra cost incurred by exact computation with complicated coefficients (very long integers, algebraic numbers): The cost doesn't grow with coefficient complicatedness as long as degree and root separation, the problem's natural analytic/geometric complexity parameters, stay the same.

Special Polynomials

The Mignotte polynomial q(x) = x20 - 2(1030x - 1)2 has two very close roots. The recursion depth of the Descartes Method is large on this input, and our Bit-Stream variants require a high precision to separate the roots. Both for exact arithmetic and for the Bit-Stream variants, the bound on the coefficient bitlength is dominated by n log(1/sep(q)), hence there is not much to gain from approximate computation.

DescartesrndL 5920 ms
DescartesrndLbias 2920 ms
DescartesrndG 4970 ms
Descartesinteger  1280 ms