A generic position based method for real root isolation of zero-dimensional polynomial systems

摘要

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 (O) over tilde (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. (C) 2014 Elsevier Ltd. All rights reserved.