Details:
Title  On the asymptotic and practical complexity of solving bivariate systems over the reals  Author(s)  Dimitrios I. Diochnos, Ioannis Z. Emiris, Elias P. Tsigaridas  Type  Article in Journal  Abstract  This paper is concerned with exact real solving of wellconstrained, bivariate polynomial systems. The main problem is to isolate all common real roots in rational rectangles, and to determine their intersection multiplicities. We present three algorithms and analyze their asymptotic bit complexity, obtaining a bound of O_B ( N^14 ) for the purely projectionbased method, and O_B ( N^12 ) for two subresultantbased methods: this notation ignores polylogarithmic factors, where N bounds the degree, and the bitsize of the polynomials. The previous record bound was O_B ( N^14 ) . Our main tool is signed subresultant sequences. We exploit recent advances on the complexity of univariate root isolation, and extend them to sign evaluation of bivariate polynomials over algebraic numbers, and real root counting for polynomials over an extension field. Our algorithms apply to the problem of simultaneous inequalities; they also compute the topology of real plane algebraic curves in O_B ( N^12 ) , whereas the previous bound was O_B ( N^14 ) . All algorithms have been implemented in maple, in conjunction with numeric filtering. We compare them against fgb/rs, system solvers from synaps, and maple libraries insulate and top , which compute curve topology. Our software is among the most robust, and its runtimes are comparable, or within a small constant factor, with respect to the C/C++ libraries.  Keywords  Real solving, Polynomial system, Complexity, maple software  ISSN  07477171 
URL 
http://www.sciencedirect.com/science/article/pii/S0747717108001235 
Language  English  Journal  Journal of Symbolic Computation  Volume  44  Number  7  Pages  818  835  Year  2009  Note  International Symposium on Symbolic and Algebraic Computation  Edition  0  Translation 
No  Refereed 
No 
