Polar Varieties and Efficient Real Equation Solving

Abstract

The objective of this paper is to show how the recently proposed method by Giusti, Heintz, Morais, Morgenstern, Pardo can be applied to a case of real polynomial equation solving. Our main result concerns the problem of finding one representative point for each connected component of a real bounded smooth hypersurface. The algorithm in yields a method for symbolically solving a zero-dimensional polynomial equation system in the affine (and toric) case. Its main feature is the use of adapted data structure: Arithmetical networks and straight-line programs. The algorithm solves any affine zero-dimensional equation system in non-uniform sequential time that is polynomial in the length of the input description and an adequately defined affine degree of the equation system. Replacing the affine degree of the equation system by a suitably defined real degree of certain polar varieties associated to the input equation, which describes the hypersurface under consideration, and using straight-line program codification of the input and intermediate results, we obtain a method for the problem introduced above that is polynomial in the input length and the real degree.