D.8.8.11 rootIsolation

Usage:

rootIsolation(I, [start, eps]); I ideal, start box, eps number

Assume:

I is a zero-dimensional radical ideal

Return:

(L1, L2), where L1 contains boxes smaller than eps which may contain an element of V(I), i.e. a root and L2 contains boxes which contain exactly one element of V(I)

Purpose:

same as rootIsolationNoPreprocessing, but speeds up computation by preprocessing starting box

Theory:

As every root of I is a root of the polynomials I[i], we use Groebner elimination to find univariate polynomials for every variable which have these roots as well. Using that I is zero-dimensional these Groebner bases may be quickly computed using FGLM. Applying root isolation to these univariate polynomials then provides smaller starting boxes which speed up computations in the multivariate case.

Note:

This algorithm and some procedures used therein perform Groebner basis computations in basering. It is thus advised to define I w.r.t. a fast monomial ordering.
The algorithm performs checks on I to prevent errors. If I does not have the right number of generators, we first try to find a suitable Groebner basis. If this fails we apply the algorithm to the triangular decomposition of I.

LIB "rootisolation.lib";
ring R = 0,(x,y),dp;
ideal I = 2x2-xy+2y2-2,2x2-3xy+3y2-2;  // V(I) has four elements
interval i = bounds(-3/2,3/2);
box B = list(i, i);
list result = rootIsolation(I, B);
result;
==> [1]:
==>    empty list
==> [2]:
==>    [1]:
==>       [-1, -1] x [0, 0]
==>    [2]:
==>       [-1/2, -1/2] x [-1, -1]
==>    [3]:
==>       [1/2, 1/2] x [1, 1]
==>    [4]:
==>       [1, 1] x [0, 0]