Polar varieties and efficient real elimination

By B. Bank, Marc Giusti, J. Heintz, G. M. Mbakop. 2000

98 citations recorded by the source corpus.

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

Subfields: Computational Mathematics, Computational Theory and Mathematics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/9fea394c981f4e24ec9388cfc37f19a5533ca7cf