D.8.8.10 rootIsolationNoPreprocessing

Usage:

rootIsolationNoPreprocessing(I, B, eps); I ideal, B list of boxes, 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:

Given input box(es) start we try to find all roots of I lying in start by computing boxes that contain exactly one root. If eps > 0 then boxes that become smaller than eps will be returned.

Theory:

We first check for every box if it contains no roots by interval arithmetic. If this is inconclusive we apply the Newton step which, as outlined in [2] and [3], converges to a root lying in the starting box. If the result of the Newton step is already contained in the interior of the starting box, it contains a unique root.

Note:

While rootIsolation does, rootIsolationNoPreprocessing does not check input ideal for necessary conditions.

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 = rootIsolationNoPreprocessing(I, list(B), 1/512);
size(result[1]);
==> 0
size(result[2]);
==> 4
result;
==> [1]:
==>    empty list
==> [2]:
==>    [1]:
==>       [-9/16, -15/32] x [-129/128, -127/128]
==>    [2]:
==>       [15/32, 33/64] x [31/32, 129/128]
==>    [3]:
==>       [63/64, 33/32] x [-1/256, 1/32]
==>    [4]:
==>       [-129/128, -63/64] x [-1/256, 1/32]