A Descartes Algorithms for Polynomials with Bit-Stream Coefficients

Kurt Mehlhorn, Arno Eigenwillig, Lutz Kettner, Werner Krandick, Susanne Schmitt, Nicola Wolpert

TL;DR

This paper presents a novel variant of the Descartes method that can isolate the real roots of polynomials whose coefficients are not known exactly but can be approximated to arbitrary precision (bit-streams). The authors achieve this by adapting the algorithm to handle these approximate coefficients, leading to an expected bit complexity of $O(n^4 (\log(1/\rho) + \tau)^2)$ for isolating roots of a polynomial of degree $n$ with root separation $\rho$ and coefficient precision $\tau$.

What Problem Does This Paper Address?

Finding the real roots of polynomials is a fundamental problem in computer algebra. The Descartes method is a well-established algorithm for this task, typically performing well for polynomials with exact coefficients. However, in many practical scenarios, coefficients are not known exactly but are rather approximations obtained from measurements or previous computations. These are often represented as "bit-streams," meaning they can be approximated to any desired accuracy. Existing Descartes method implementations struggle with these inexact coefficients, as small errors can propagate and lead to incorrect root isolation. This paper bridges this gap by developing a version of the Descartes method that robustly handles bit-stream coefficients, ensuring correct root isolation even with approximations.

Methods

The core of the paper is an adaptation of the Descartes method to work with approximate coefficients. The standard Descartes method relies on the Descartes Rule of Signs, which counts sign variations in the coefficients of a polynomial. When coefficients are approximate, the sign variations become uncertain, leading to indeterminate cases. The authors address this by:

  • Sharper Analysis of the Rule of Signs: They introduce new lemmas (Lemmas 5 and 6) that provide tighter bounds on sign variations when dealing with approximate coefficients.
  • Interval Arithmetic: Coefficients are treated as intervals, and the algorithm operates on these intervals. The concept of "indeterminate" intervals (those containing zero) is crucial.
  • Randomization: To handle the uncertainty introduced by approximate coefficients and to ensure that the first and last coefficients of the polynomial remain "large" (and thus determinate), the authors employ randomization. Two main strategies are proposed:
  • DescartesrndL: Randomly choosing the split point within an interval.
  • DescartesrndG: Randomly translating the polynomial before applying a deterministic split point strategy.
  • Error Bounds and Complexity Analysis: The paper provides detailed analysis of the bit complexity, showing how the required precision of coefficient approximations and the overall computational cost depend on the degree of the polynomial, the root separation, and the coefficient precision.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithm development and analysis, not on empirical evaluation with specific datasets.

Key Insights and Ideas

  • Robustness with Approximations: The most significant insight is that the Descartes method, with careful adaptation and the use of randomization, can be made robust to inexact coefficients. This opens up the possibility of using this powerful root isolation technique in more practical, real-world scenarios where exact coefficients are rare.
  • The Power of Randomization: Randomization is not just a theoretical tool but a practical necessity to overcome the inherent uncertainties of bit-stream coefficients. It helps in ensuring that the algorithm makes progress and avoids getting stuck in indeterminate states.
  • Trade-offs in Complexity: The paper clearly demonstrates the trade-offs involved. While the bit complexity is polynomial in the degree ($n^4$), it is linear in the precision of the coefficients and logarithmic in the root separation, which is a significant improvement over some other methods.
  • Bernstein Basis Advantage: The use of the Bernstein basis is highlighted as being particularly amenable to interval arithmetic and error propagation analysis, making it a suitable choice for this problem.

Key Results

  • Algorithm for Bit-Stream Coefficients: The paper presents a variant of the Descartes algorithm that can isolate real roots of square-free polynomials with bit-stream coefficients.
  • Required Coefficient Precision: To isolate roots with separation $\rho$ for a polynomial of degree $n$ and coefficient precision $\tau$, the algorithm requires coefficient approximations to $O(n(\log(1/\rho) + \tau))$ bits after the binary point.
  • Expected Bit Complexity: The expected bit cost for root isolation is $O(n^4 (\log(1/\rho) + \tau)^2)$.
  • Randomization Strategies: Two effective randomization strategies (DescartesrndL and DescartesrndG) are introduced to ensure algorithm termination and correctness.

Limitations and Future Work

  • Square-Free Polynomials: The current algorithm is restricted to square-free polynomials (polynomials with no multiple roots). Detecting multiple roots is inherently difficult with approximate coefficients, and this remains a limitation.
  • Cost of Approximation: The analysis of the bit complexity does not include the cost of computing the initial approximations of the coefficients to the required quality. This is a separate, potentially significant, computational step.
  • Experimental Validation: While the paper outlines experimental plans, the presented work is primarily theoretical. Further experimental validation would be valuable to confirm the practical performance of the algorithms.
  • General Polynomials: Extending the method to handle polynomials with multiple roots would be a natural and important next step.
  • Comparison with Other Methods: The paper briefly compares its approach to Pan's algorithm, noting that Pan's is asymptotically faster but more complex. Further comparative studies, especially on practical instances, would be beneficial.

Summary updated

Abstract

The Descartes method is an algorithm for isolating the real roots of square-free polynomials with real coefficients. We assume that coefficients are given as (potentially infinite) bit-streams. In other words, coefficients can be approximated to any desired accuracy, but are not known exactly. We show that a variant of the Descartes algorithm can cope with bit-stream coefficients. To isolate the real roots of a square-free real polynomial $q(x) = q_nx^n+ldots+q_0$ with root separation $ ho$, coefficients $abs{q_n}ge1$ and $abs{q_i} le 2^ au$, it needs coefficient approximations to $O(n(log(1/ ho) + au))$ bits after the binary point and has an expected cost of $O(n^4 (log(1/ ho) + au)^2)$ bit operations.
BibTeX
@inproceedings{mehlhorn2006descartes,
  author = {Kurt Mehlhorn and Arno Eigenwillig and Lutz Kettner and Werner Krandick and Susanne Schmitt and Nicola Wolpert},
  title = {{A Descartes Algorithms for Polynomials with Bit-Stream Coefficients}},
  booktitle = {Reliable Implementation of Real Number Algorithms},
  year = {2006},
  url = {https://openreview.net/forum?id=I22MkWfDOTI},
}
Figure