# 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?

• Googling "root isolation" and "polynomial systems" gives lots of references, like this one by Cheng et al., which also has a number of references. Other papers by Cheng seem to be on similar topics. – Igor Khavkine Mar 18 '16 at 1:47

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.

• Does this technique has a name so that I can read about it more somewhere? Has it something to do with Rational Univariate Representation by any chance? – Faaf Apr 1 '16 at 23:33
• I don't know, I've known about this since a long time, but I couldn't say where I heard about it or whether I (re)discovered it myself, I always thought it was pretty obvious. And yes, it seems at least related to Rational Univariate Representation in the sense that you would (or at least, could) obtain such a representation by applying the tricked I mentioned; I'm afraid I couldn't say more. – Gro-Tsen Apr 2 '16 at 13:59

The magic words are "Grobner basis" and "zero-dimensional ideal". See, for example, Balint Felszeghy's thesis.

• I read about Grobner basis but I don't think it is what I'm looking for: it replaces the system of polynomials with simpler polynomials which I can then solve and "back-substitute". But what I would like to have instead is to identify the regions without actually solving the polynomials. – Faaf Mar 17 '16 at 19:48
• You can locate roots of one-dimensional polynomials with en.wikipedia.org/wiki/Sturm's_theorem – Per Alexandersson Mar 17 '16 at 21:20
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$.
• Do you mean I should "compute" $x$, in order to get $y$, right? But I don't want find exact value of $x$, I'm only interested in the isolating regions. – Faaf Mar 23 '16 at 12:10
• You just need an isolating interval for $x$, and from there you get an isolating interval for $y$. – Bruno Salvy Mar 24 '16 at 16:54
• Could you please expand on it a bit? I have an isolating interval in $x$, ok. You mean I should just plug its endpoints into the other polynomial in $(x, y)$? – Faaf Mar 24 '16 at 20:25