Equations for Polar Varieties and Efficient Real Elimination

Abstract

Let $V_0$ be a smooth and compact real variety given by a reduced regular sequence of polynomials $f_1,..., f_p$. This paper is devoted to the algorithmic problem of finding efficiently for each connected component of $V_0$ a representative point. For this purpose we exhibit explicit polynomial equations which describe for generic variables the polar varieties of $V_0$ 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_1,...,f_p$ and in a suitably introduced geometric (extrinsic) parameter, called the degree of the real interpretation of the given equation system $f_1,...,f_p$.