Isolating roots of polynomial system I would like to isolate the regions which contain the roots of a system of two bivariate cubic polynomials.
I thought I would project the solutions onto $x$ and $y$ axis by means of resultant computations. Then I would isolate the roots of two 9th degree univariate polynomials which would give me at most 9 $\times$ 9 candidate regions.
But then I got stuck: how do I know for sure which regions do contain the roots, and which do not? Is it sufficient (i.e. is there such a test) to exclude all the regions which do not contain any roots or do I also need some kind of "inclusion predicate" to be really sure I found the right regions?
To put it differently: how do I "match" the isolating intervals of one univariate polynomial ($x$) with the intervals of the other univariate polynomial ($y$) so that the pair demarcates a region having a solution of the original system?
 A: Find some slope $c$ so that the projections $x+cy$ of the 9×9 candidate regions are pairwise disjoint (if they are sufficiently narrow, this $c$ exists, and they can be made sufficiently narrow by repeatedly applying Sturm's theorem).  Then compute the projection $x+cy$ of your zero set (by performing a linear change of variables and yet another resultant computation) and isolate that.  This should tell you which of the 9×9 projections, hence of the 9×9 regions, actually contain a zero.
A: The magic words are "Grobner basis" and "zero-dimensional ideal". See, for example, Balint Felszeghy's thesis.
A: When you compute a Gröbner basis using a lexicographic order with $y>>x$, you will get one polynomial in $x$ only and a polynomial of degree 1 (usually) in $y$ with coefficients depending on $x$. So for each root of the univariate polynomial in $x$, you know exactly what is the corresponding value of $y$.
If you don't like Gröbner bases, the same computation can be achieved by subresultants.
A reference for these questions (and much more) is the book by Basu, Pollack, and Roy, Algorithms in real algebraic geometry.
