On the complexity of real solving bivariate systems
Dimitrios I. Diochnos, Ioannis Z. Emiris, Elias Tsigaridas · 2007
We consider exact real solving of well-constrained, bivariate systems of relatively prime polynomials. The main problem is to compute all common real roots in isolating interval representation, and to determine their intersection multiplicities. We present three algorithms and analyze their asymptotic bit complexity, obtaining a bound of ÕB(N14) for the purely projection-based method, and ÕB(N12) for two subresultants-based methods: these ignore polylogarithmic factors, and N bounds the degree and the bitsize of the polynomials. The previous record bound was ÕB(N14).