## Polar varieties and efficient real elimination.(English)Zbl 1073.14554

Summary: Let $$S_0$$ be a smooth and compact real variety given by a reduced regular sequence of polynomials $$f_1, \dots, 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,\dots, f_p$$ and in a suitably introduced, intrinsic geometric parameter, called the degree of the real interpretation of the given equation system $$f_1,\dots,f_p$$.

### MSC:

 14P05 Real algebraic sets 14Q99 Computational aspects in algebraic geometry 68W30 Symbolic computation and algebraic computation
Full Text: