2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ This is an important idea. In one-dimension the continuity of polynomials makes it straightforward to isolate roots in intervals where there is a change of sign. In higher dimensions there is no simple analogy for functions that are simply continuous, but the derivatives of polynomials are easily bounded, giving us additional information to work with. $\endgroup$ – hardmath Apr 1 '16 at 23:41
  • $\begingroup$ Could you provide a simple example of polynomials you are working on ? $\endgroup$ – Jean Marie Apr 2 '16 at 0:02
  • 1
    $\begingroup$ Your use of resultants and emphasis on bivariate systems of modest degree suggests you will find the paper Nonlinear Polynomial Systems: Multiple Roots and their Multiplicities by Ko, Sakkalis, and Patrikalakis (and its references) interesting. A later version of this paper appeared as "Resolution of multiple roots of nonlinear polynomial systems" in Int. J. of Shape Modeling, Nov. 2011. $\endgroup$ – hardmath Apr 2 '16 at 9:37
1
$\begingroup$

(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).

$\endgroup$
  • $\begingroup$ If I made the 9 $\times$ 9 candidate regions really, really tiny, would it suffice to use only the interval arithmetic exclusion predicate? In other words, if there was a separation bound for the roots and I made the regions even smaller, wouldn't that be enough to certify the solutions? I don't know if there is such a bound for bivariate systems but for univariate polynomial there is one... And regarding the "sufficiently generic position", I'm not really familiar with the term: in general I don't know anything about the roots (e.g. whether there are only simple roots). $\endgroup$ – Faaf Dec 28 '16 at 18:33
  • $\begingroup$ Yes, if you refine that much, it'll be enough. And there are bounds for multivariate systems, assuming that your input is in $\mathbb{Z}[x_1, \dots, x_n]$ or can be scaled to have integer coefficients. In fact, they arise from univariate separation bounds on the elimination polynomials (resultants). You might want to look in Emiris', Mourrain' and Tsigaridas' article "Separation bounds for polynomial systems". $\endgroup$ – akobel Dec 28 '16 at 22:43
  • $\begingroup$ Thank you! Just curious: if I had used very tight separation bound and only the exclusion test, would the regions be similar in size to the ones obtained by proper exclusion and inclusion predicates? My thinking is that using the proper predicates should (?) result in well separated regions, too... $\endgroup$ – Faaf Dec 29 '16 at 15:41
  • $\begingroup$ In general, you have to refine the regions until they are way smaller. To give you an idea: For a system of two bivariate polynomials of total degree $d$ and coefficients of bitsize $\tau$, the worst-case separation bound is - up to current knowledge - something like $2^{-\Theta(d^4 + d^3\tau)}$, with small constants hidden. That is, you'll need some $d^4 + d^3\tau$ bits of precision, for up to $d^2$ regions. That's feasible for toy instances, but not a lot more. E.g., if your input is floating point, rescaling to integers can easily produce a $\tau$ in the order of 2000. $\endgroup$ – akobel Dec 29 '16 at 16:38
  • $\begingroup$ OTOH, the necessary precision for "proper" predicates will mostly depend on the geometry of the solutions; that is, it will adapt to the actual distances. Imagine a very easy system, say, $f(x,y):=(x-1)x(x+1)=g(x,y):=(y-1)y(y+1)=0$ with only simple solutions at $\{-1,0,1\}\times\{-1,0,1\}$. Perturbing all input coefficients by marginally small values (say, due to rounding) does not change the intrinsic complexity of the problem at all; however, the worst-case bounds do not reflect this. The worst-case bound can be arbitrarily bad - imagine $2^\tau f-1=2^\tau g+1=0$ with almost identical roots. $\endgroup$ – akobel Dec 29 '16 at 16:44

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.