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.
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.
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 a_{n}x^{n} +...+ a_{i}x^{i} +...+ a_{1}x + a_{0} is obtained using the Lagrange-Zassenhaus bound 2 max_{i<n} (|a_{i}|/|a_{n}|)^{1/(n-i)}.
To generate random polynomials, we choose n+1 integer points from
[-2^{L}, +2^{L}]×[-2^{L}, +2^{L}]
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 - (123^{1/5}+321^{1/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 |
Descartes_{rndL} | 83 ms | 86 ms | 90 ms | 84 ms | 734 ms | 799 ms | 841 ms | 801 ms |
Descartes_{rndL}^{bias} | 40 ms | 44 ms | 47 ms | 41 ms | 351 ms | 379 ms | 428 ms | 356 ms |
Descartes_{rndG} | 41 ms | 45 ms | 49 ms | 42 ms | 353 ms | 384 ms | 423 ms | 362 ms |
Descartes_{integer} | 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.
The Mignotte polynomial q(x) = x^{20} - 2(10^{30}x - 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.
Descartes_{rndL} | 5920 ms |
---|---|
Descartes_{rndL}^{bias} | 2920 ms |
Descartes_{rndG} | 4970 ms |
Descartes_{integer} | 1280 ms |