B. Bank, M. Giusti, J. Heintz, G.M. Mbakop
Equations for Polar Varieties and Efficient Real Elimination
Preprint series: Institut für Mathematik, Humboldt-Universität zu Berlin (ISSN 0863-0976)

MSC:

14E15 Global theory of singularities, resolution, See Also {14B05, 32S20, 32S45}

14P99 None of the above but in this section

Abstract: Let V₀ be a smooth and compact real variety given by a reduced regular sequence of polynomials f₁,..., f_p. This paper is devoted to the algorithmic problem of finding efficiently for each connected component of V₀ a representative point. For this purpose we exhibit explicit polynomial equations which describe for generic variables the polar varieties of V₀ of all dimensions. This leads to a procedure which solves our algorithmic problem in time that is polynomial in the (extrinsic) description length of the input equations f₁,...,f_p and in a suitably introduced geometric (extrinsic) parameter, called the degree of the real interpretation of the given equation system f₁,...,f_p.
Keywords: Real polynomial equatin solving, polar variety, geometric degree, arithmetic circuit, arithmetic network, complexity