Experimental evaluation and cross-benchmarking of univariate real solvers

Michael Hemmer, Elias P. Tsigaridas, Zafeirakis Zafeirakopoulos, Ioannis Z. Emiris, Menelaos I. Karavelas, Bernard Mourrain

Introduction

Finding the real roots of a univariate polynomial—solving equations of the form $f(x) = 0$—is a cornerstone of computational mathematics. This task is essential in diverse fields such as robotics, computer-aided design (CAD), computer vision, and algebraic geometry. While the theoretical foundations for root isolation have existed for centuries, the practical implementation of solvers that are simultaneously efficient and exact (guaranteed to find all roots without numerical error) remains a significant challenge.

This study presents a comprehensive "battle royale" of state-of-the-art univariate real root solvers. By benchmarking nine different implementations across a massive dataset of 5,000 diverse polynomials, the authors provide the first large-scale standardized comparison of these algorithms on identical hardware.

Algorithmic Families

The solvers evaluated in this study fall into four primary algorithmic categories, each with distinct strengths and weaknesses:

  1. Sturm Sequences (ST): A classical baseline method. While mathematically robust and reliable, it is generally the slowest due to the high computational cost of sequence construction.
  2. Symbolic-Numeric Methods (Sleeve/Symbnum): These solvers utilize interval arithmetic and numerical approximations. They are exceptionally fast for "easy" polynomials but often fail to isolate roots that are clustered extremely close together.
  3. Continued Fractions (CF, NCF, NCF2): These methods isolate roots by expanding them into continued fractions. The NCF2 variant incorporates square-free factorization to handle multiple roots more efficiently, making this family a strong contender for general-purpose use.
  4. Descartes' Rule of Signs (Descartes, Bitstream Descartes, RS): These solvers employ a subdivision strategy. Bitstream Descartes (BD) is a sophisticated variant that only examines as much precision in the coefficients as necessary to make a branching decision, significantly reducing the overhead for polynomials with large coefficients. RS is a highly optimized interval-based implementation of the Descartes method.

Experimental Methodology

To ensure a rigorous evaluation, the authors utilized 150 datasets comprising 5,000 polynomials with degrees up to 184 and coefficients up to 8,000 bits. The test suite was designed to stress-test various aspects of solver performance:

  • Random Polynomials ([rnd]): Varied degrees and bitsizes to assess average-case performance.
  • Big Bitsize ([bts]): Polynomials with coefficients up to 8,000 bits to test handling of massive integers.
  • Mignotte Polynomials ([mgn]): Specifically constructed cases where roots are extremely close, designed to challenge the precision of numerical solvers.
  • Integer/Rational Roots ([int]/[rat]): Testing performance on polynomials with specific root types.
  • Geometric Benchmarks ([3darr], [vorell]): Real-world problems derived from 3D arrangement calculations and Voronoi diagrams.

Analysis of Performance

The benchmarking results revealed several critical insights into the state of modern root-solving technology:

The Maturity of Exact Computation

A significant finding was that all theoretically exact methods (CF, Descartes, Sturm) achieved 100% accuracy throughout 50 hours of intensive testing. This demonstrates that exact algebraic computation has transitioned from a theoretical pursuit to a reliable, production-ready tool.

The "Mignotte" Wall and Robustness

Approximation-based methods, such as Sleeve, consistently failed on Mignotte polynomials. The root separation in these cases exceeded standard machine precision, causing numerical failures. In contrast, Continued Fraction-based methods proved to be the most resilient, successfully handling these difficult cases where others faltered.

Efficiency through Bitstream Evaluation

For polynomials characterized by massive coefficients but moderate degrees, Bitstream Descartes and RS emerged as the clear winners. Their "lazy evaluation" strategy—processing only the necessary bits of a coefficient—allowed them to significantly outperform methods that process full-precision integers. The study identified a "break-even" point around 2,000 bits, beyond which bitstream methods become markedly superior.

Experimental Results

The evaluation showed that there is no single "best" solver for every scenario, but clear patterns emerged:

  • Consistency: The Continued Fraction (CF) family, particularly NCF2, proved to be the most consistent "all-rounder," performing well across the widest variety of datasets.
  • Speed: For random polynomials of degree 100, NCF2 demonstrated significant speedups over standard Descartes or Sturm implementations.
  • Resource Constraints: While the RS solver was often the fastest, it exhibited high memory consumption in certain high-degree cases, occasionally exceeding the 256MB limit of the test hardware (a Pentium III).

Conclusion and Future Directions

The study concludes that while Continued Fraction methods are currently the most robust general-purpose solvers, the optimal choice depends heavily on the specific characteristics of the polynomial (degree vs. bitsize).

Future research directions suggested by the authors include:

  • Hybridization: Combining the lazy evaluation of Bitstream methods with the robustness of Continued Fraction solvers.
  • Filtering: Implementing fast, inexact numerical methods as a preliminary filter to quickly handle easy cases before falling back to exact methods for difficult root clusters.
  • Parallelization: Leveraging multi-core architectures to accelerate subdivision-based algorithms.

This benchmark serves as a vital reference for developers and researchers, providing a clear map of the performance landscape for univariate real root solving.

Summary updated

Abstract

Real solving of univariate polynomials is a fundamental problem with several important applications. This paper is focused on the comparison of black-box implementations of state-of-the-art algorithms for isolating real roots of univariate polynomials over the integers. We have tested 9 different implementations based on symbolic-numeric methods, Sturm sequences, Continued Fractions and Descartes' rule of sign. The methods under consideration were developed at the GALAAD group at INRIA,the VEGAS group at LORIA and the MPI Saarbrücken. We compared their sensitivity with respect to various aspects such as degree, bitsize or root separation of the input polynomials. Our datasets consist of 5,000 polynomials from many different settings, which have maximum coefficient bitsize up to bits 8,000, and the total running time of the experiments was about 50 hours. Thereby, all implementations of the theoretically exact methods always provided correct results throughout this extensive study. For each scenario we identify the currently most adequate method, and we point to weaknesses in each approach, which should lead to further improvements. Our results indicate that there is no "best method" overall, but one can say that for most instances the solvers based on Continued Fractions are among the best methods. To the best of our knowledge, this is the largest number of tests for univariate real solving up to date.
BibTeX
@inproceedings{hemmer2009experimental,
  author = {Michael Hemmer and Elias P. Tsigaridas and Zafeirakis Zafeirakopoulos and Ioannis Z. Emiris and Menelaos I. Karavelas and Bernard Mourrain},
  title = {{Experimental evaluation and cross-benchmarking of univariate real solvers}},
  booktitle = {SNC},
  year = {2009},
  doi = {10.1145/1577190.1577202},
}
Figure