Algorithms of Intrinsic Complexity for Point Searching in Compact Real Singular Hypersurfaces

Abstract

For a real square-free multivariate polynomial F, we treat the general problem of finding real solutions of the equation F=0, provided that the real solution set {F=0}ℝ is compact. We allow that the equation F=0 may have singular real solutions. We are going to decide whether this equation has a non-singular real solution and, if this is the case, we exhibit one for each generically smooth connected component of {F=0}ℝ. We design a family of elimination algorithms of intrinsic complexity which solves this problem. In the worst case, the complexity of our algorithms does not exceed the already known extrinsic complexity bound of (nd)O(n) for the elimination problem under consideration, where n is the number of indeterminates of F and d its (positive) degree. In the case that the real variety defined by F is smooth, there already exist algorithms of intrinsic complexity that solve our problem. However, these algorithms cannot be used in case when F=0 admits F-singular real solutions. An elimination algorithm of intrinsic complexity presupposes that the polynomial F is encoded by an essentially division-free arithmetic circuit of size L (i. e., F can be evaluated by means of L additions, subtractions and multiplications, using scalars from a previously fixed real ground field, say ℚ) and that there is given an invariant δ(F) which (roughly speaking) depends only on the geometry of the complex hypersurface defined by F. The complexity of the algorithm (measured in terms of the number of arithmetic operations in ℚ) is then linear in L and polynomial in n,d and δ(F). In order to find such a geometric invariant δ(F), we consider suitable incidence varieties which in fact are algebraic families of dual polar varieties of the complex hypersurface defined by F. The generic dual polar varieties of these incidence varieties are called bipolar varieties of the equation F=0. The maximal degree of these bipolar varieties then becomes the essential ingredient of our invariant δ(F).