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: (Also see my very similar reply to the very similar question Certification of roots.)
Your intuition is correct: it does not suffice to be able to exclude non-solutions unless you know a priori that the system is in sufficiently generic position: all solutions have to be finite (no solutions at infinity), simple (in particular, the algebraic curves defined by the input polynomials may not intersect tangentially), and the solutions must be inside your search domain. If you only isolate real roots of the resultants, but your system has complex roots, you somehow have to know when to stop with your exclusion tests.
The reason is that the typical exclusion tests rely on simply evaluating the bivariate polynomials in interval arithmetic on subsequently refined isolating intervals of the resultants' roots. However, you will obviously never be able to exclude a solution, so you need some means to stop refinement and declare a certified solution. Short of worst-case separation bounds for the roots of bivariate systems, this means having a proper inclusion predicate.
This is non-trivial, and the key point of research on the Cylindrical Algebraic Decomposition (CAD) method. For the current state-of-the-art algorithm in that sector as well as references, have a look at On the complexity of computing with planar algebraic curves (disclaimer: I'm one of the authors).
