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?

  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ 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? $\endgroup$ – Faaf Apr 1 '16 at 23:33
  • $\begingroup$ 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. $\endgroup$ – 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.

  • 2
    $\begingroup$ 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. $\endgroup$ – Faaf Mar 17 '16 at 19:48
  • 1
    $\begingroup$ You can locate roots of one-dimensional polynomials with en.wikipedia.org/wiki/Sturm's_theorem $\endgroup$ – Per Alexandersson Mar 17 '16 at 21:20
  • $\begingroup$ @PerAlexandersson Yes, but I asked about two-dimensional polynomials... $\endgroup$ – Faaf Mar 17 '16 at 21:59

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.

  • $\begingroup$ 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. $\endgroup$ – Faaf Mar 23 '16 at 12:10
  • $\begingroup$ You just need an isolating interval for $x$, and from there you get an isolating interval for $y$. $\endgroup$ – Bruno Salvy Mar 24 '16 at 16:54
  • $\begingroup$ 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)$? $\endgroup$ – Faaf Mar 24 '16 at 20:25
  • $\begingroup$ You inject your interval into the other polynomial and evaluate using interval arithmetic. $\endgroup$ – Bruno Salvy Mar 30 '16 at 5:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.