max planck institut
informatik

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.

• A. Eigenwillig, L. Kettner, W. Krandick, K. Mehlhorn, S. Schmitt and N. Wolpert:
  A Descartes Algorithm for Polynomials with Bit-Stream Coefficients.
  8th Internat. Workshop on Comp. Algebra in Sci. Computing (CASC 2005), Springer LNCS 3718, pp. 138-149.
  © Springer-Verlag, 2005. (Some of the authors have posted a pre-print version on their homepage.)

---

Variants

We compare the following variants of the Descartes method.

• Descartes_rndL:
  We apply the Bernstein Descartes method on polynomials with approximate coefficients at increasingly higher precision. The choice of bisection point is randomized in each interval (that is, locally).
• Descartes_rndL^bias:
  This is the same as Descartes_rndL, but here we bias the choice of bisection points to those with small denominators.
• Descartes_rndG:
  We apply the Bernstein Descartes method on polynomials with approximate coefficients at increasingly higher precision. All bisections happen at interval midpoints, but we shift the polynomial by a random offset before starting the recursive bisection (that is, we randomize globally).
• Descartes_integer:
  This is the usual deterministic Bernstein Descartes method implemented with exact integer arithmetic.

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 a_nxⁿ +...+ a_ixⁱ +...+ a₁x + a₀ is obtained using the Lagrange-Zassenhaus bound 2 max_i<n (|a_i|/|a_n|)^1/(n-i).

Random Polynomials

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
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) = x²⁰ - 2(10³⁰x - 1)² 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

• Bit-Stream Descartes:
• Introduction
• Variants
• Experiments