Beyond Worst-Case Analysis for Root Isolation Algorithms

Alperen Ali Ergür, Josué Tonelli-Cueto, Elias P. Tsigaridas

Abstract: The Descartes solver is a cornerstone of symbolic computation, favored for its simplicity and practical efficiency in isolating real roots of univariate polynomials. However, a significant gap has persisted between its observed performance and its theoretical worst-case complexity, which is often outperformed by more complex algorithms like Pan’s. This paper resolves this paradox by moving beyond worst-case analysis. By employing smoothed analysis on polynomials with integer coefficients, the authors demonstrate that the algorithm’s expected complexity is quasi-linear, providing a rigorous theoretical foundation for its real-world success.

Introduction: The Complexity Paradox

In the field of computer algebra, isolating the real roots of a univariate polynomial—finding disjoint intervals that each contain exactly one root—is a fundamental operation. For decades, researchers have faced a contradiction: while Pan’s algorithm holds the record for the best worst-case complexity, it is rarely implemented due to its extreme complexity. Conversely, the Descartes solver is the industry "workhorse," praised for its speed and simplicity, despite having theoretical worst-case bounds that are significantly worse.

The authors argue that worst-case analysis is an insufficient lens for this problem because it focuses on "pathological" inputs that are rarely encountered. They propose a more realistic "average-case" or "smoothed" analysis, specifically tailored to polynomials with integer coefficients of a given bit-size.

Methodology: A Probabilistic Framework

To bridge the theory-practice gap, the authors developed a probabilistic framework for random bit polynomials—polynomials where coefficients are independent discrete random variables (integers).

A key part of their analysis involves bounding the depth of the algorithm's subdivision tree. The Descartes solver works by recursively subdividing an initial interval. The complexity of this process is tied to the "separation bound"—the minimum distance between any two roots.

The sequence of disks $D_n$ illustrating the subdivision process in the Descartes solver.

To handle the discrete nature of integer coefficients, the authors adapted sophisticated anti-concentration tools from random matrix theory. These tools help prove that "bad" polynomials with extremely close roots are statistically rare. Furthermore, they utilized complex analytic techniques involving Obreshkoff areas. These lens-shaped regions in the complex plane help bound the number of complex roots near the real axis, which in turn controls the "width" of the subdivision tree.

Obreshkoff areas used to bound complex roots near the real axis during subdivision.

Mathematical Data Models

The study analyzes several mathematical models to represent realistic data:

  • Uniform Random Bit Polynomials: Coefficients are chosen uniformly from an integer range $[-2^\tau, 2^\tau]$.
  • Structured Perturbations: A deterministic polynomial is "jittered" by a random one, the standard setup for smoothed analysis.
  • Specific Support Models: Scenarios where only a subset of coefficients are random or signs are fixed.

Key Insights and Results

The primary "aha moment" of this research is the realization that the scenarios that typically break the Descartes solver—roots being infinitesimally close—almost never occur in random or slightly noisy integer-coefficient settings.

The paper provides several landmark results:

  1. Quasi-Linear Complexity: For a uniform random bit polynomial of degree $d$ and bitsize $\tau$, the Descartes solver isolates real roots in expected time $\widetilde{\mathcal{O}}_B(d^2 + d\tau)$. This is a factor of $d$ better than previous worst-case bounds.
  2. Improved Subdivision Bounds: The expected number of subdivision steps is shown to be $\mathcal{O}(d \log d)$, a major improvement over the worst-case $\mathcal{O}(d \tau)$.
  3. Discrete Smoothed Analysis: While most smoothed analysis focuses on continuous Gaussian distributions, this work successfully tackles the discrete case (integers), which is far more relevant to symbolic computation.

Conclusion and Future Directions

This work provides the first rigorous theoretical justification for the Descartes solver's practical efficiency. However, some limitations remain. The current model assumes independent coefficients, whereas real-world problems (like those involving resultants) often feature correlated coefficients. Additionally, the analysis focuses on square-free polynomials.

Future work may extend this "beyond worst-case" approach to multivariate polynomial systems, which are significantly more complex to analyze but vital for fields like robotics and modern engineering.

Summary updated

Abstract

Isolating the real roots of univariate polynomials is a fundamental problem in symbolic computation and it is arguably one of the most important problems in computational mathematics. The problem has a long history decorated with numerous ingenious algorithms and furnishes an active area of research. However, the worst-case analysis of root-finding algorithms does not correlate with their practical performance. We develop a smoothed analysis framework for polynomials with integer coefficients to bridge the gap between the complexity estimates and the practical performance. In this setting, we derive that the expected bit complexity of DESCARTES solver to isolate the real roots of a polynomial, with coefficients uniformly distributed, is $\widetilde{\mathcal{O}}_B(d^2 + d τ)$, where $d$ is the degree of the polynomial and $τ$ the bitsize of the coefficients.
BibTeX
@inproceedings{ergur2022beyond,
  author = {Alperen Ali Ergür and Josué Tonelli-Cueto and Elias P. Tsigaridas},
  title = {{Beyond Worst-Case Analysis for Root Isolation Algorithms}},
  booktitle = {ISSAC},
  year = {2022},
  doi = {10.1145/3476446.3535475},
}
Figure