|
D.8.8.11 rootIsolation
Procedure from library rootisolation.lib (see rootisolation_lib).
- 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 .
Example:
| 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]
|
|