A Generic Position Based Method for Real Root Isolation of Zero-Dimensional Polynomial Systems

Abstract

We improve the local generic position method for isolating the real roots of a zero-dimensional bivariate polynomial system with two polynomials and extend the method to general zero-dimensional polynomial systems. The method mainly involves resultant computation and real root isolation of univariate polynomial equations. The roots of the system have a linear univariate representation. The complexity of the method is ${\tilde{O}}_B(N^{10})$ for the bivariate case, where $N=\max (d,\tau )$, $d$ resp., $\tau$ is an upper bound on the degree, resp., the maximal coefficient bitsize of the input polynomials. The algorithm is certified with probability 1 in the multivariate case. The implementation shows that the method is efficient, especially for bivariate polynomial systems.

24 pages, 5 figures

References in corpus (1)

• On the asymptotic and practical complexity of solving bivariate systems over the reals

Cited by in corpus (1)

• On the Complexity of Computing the Topology of Real Algebraic Space Curves