On the complexity of solving a bivariate polynomial system

Abstract

We study the complexity of computing the real solutions of a bivariate polynomial system using the recently presented algorithm Bisolve [2]. Bisolve is an elimination method which, in a first step, projects the solutions of a system onto the x- and y-axes and, then, selects the actual solutions from the so induced candidate set. However, unlike similar algorithms, Bisolve requires no genericity assumption on the input, and there is no need for any kind of coordinate transformation. Furthermore, extensive benchmarks as presented in [2] confirm that the algorithm is highly practical, that is, a corresponding C++ implementation in Cgal outperforms state of the art approaches by a large factor. In this paper, we focus on the theoretical complexity of Bisolve. For two polynomials f,g ∈ Z[x,y] of total degree at most n with integer coefficients bounded by 2^τ, we show that Bisolve computes isolating boxes for all real solutions of the system f = g = 0 using O(n^8 + n^7τ) bit operations, thereby improving the previous record bound for the same task by several magnitudes.

Publication
In ISSAC