Real algebraic numbers and polynomial systems of small degree

摘要

Based on precomputed Sturm-Habicht sequences, discriminants and invariants, we classify, isolate with rational points, and compare the real roots of polynomials of degree up to 4. In particular, we express all isolating points as rational functions of the input polynomial coefficients. Although the roots are algebraic numbers and can be expressed by radicals, such representation involves some roots of complex numbers. This is inefficient, and hard to handle in applications in geometric computing and quantifier elimination. We also define rational isolating points between the roots of the quintic. We combine these results with a simple version of Rational Univariate Representation to isolate all common real roots of a bivariate system of rational polynomials of total degree ≤2 and to compute the multiplicity of these roots. We present our software within library SYNAPS and perform experiments and comparisons with several public-domain implementations. Our package is 2-10 times faster than numerical methods and exact subdivision-based methods, including software with intrinsic filtering.