POLAR VARIETIES AND EFFICIENT REAL ELIMINATION

BERND BANK MARC GIUSTI JOOS HEINTZ GUY MERLIN MBAKOP

Abstract. Let S_{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 a representative point for each connected component of S_{0} . For this purpose we exhibit explicit polynomial equations that describe the generic polar varieties of S_{0}. 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, intrinsic geometric parameter, called the degree of the real interpretation of the given equation system f_{1}, …, f_{p}.