Effective equidimensional decomposition of affine varieties

AbstractIn this paper we present a probabilistic algorithm which computes, from a finite set of polynomials defining an algebraic variety V, the decomposition of V into equidimensional components. If V is defined by s polynomials in n variables of degrees bounded by an integer d⩾n and V=⋃ℓ=0rVℓ is the equidimensional decomposition of V, the algorithm obtains in sequential time bounded by sO(1)dO(n), for each 0⩽ℓ⩽r, a set of n+1 polynomials of degrees bounded by deg(Vℓ) which define Vℓ