This paper is concerned with exact real solving of well-constrained, 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 algor
ithms and analyze their asymptotic bit complexity, obtaining a bound of $sOB(N^{14})$ for the purely projection-based method, and $sOB(N^{12})$ for two subresultant-based methods: this notation ignores polylogarithmic factors, where $N$ bounds the degree and the bitsize of the polynomials. The previous record bound was $sOB(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 two 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 $sOB(N^{12})$, whereas the previous bound was $sOB(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. Key words: real solving, polynomial systems, complexity, MAPLE software
In this paper we derive aggregate separation bounds, named after Davenport-Mahler-Mignotte (dmm), on the isolated roots of polynomial systems, specifically on the minimum distance between any two such roots. The bounds exploit the structure of the sy
stem and the height of the sparse (or toric) resultant by means of mixed volume, as well as recent advances on aggregate root bounds for univariate polynomials, and are applicable to arbitrary positive dimensional systems. We improve upon Cannys gap theorem cite{c-crmp-87} by a factor of $OO(d^{n-1})$, where $d$ bounds the degree of the polynomials, and $n$ is the number of variables. One application is to the bitsize of the eigenvalues and eigenvectors of an integer matrix, which also yields a new proof that the problem is polynomial. We also compare against recent lower bounds on the absolute value of the root coordinates by Brownawell and Yap cite{by-issac-2009}, obtained under the hypothesis there is a 0-dimensional projection. Our bounds are in general comparable, but exploit sparseness; they are also tighter when bounding the value of a positive polynomial over the simplex. For this problem, we also improve upon the bounds in cite{bsr-arxix-2009,jp-arxiv-2009}. Our analysis provides a precise asymptotic upper bound on the number of steps that subdivision-based algorithms perform in order to isolate all real roots of a polynomial system. This leads to the first complexity bound of Milnes algorithm cite{Miln92} in 2D.
