Algorithms of intrinsic complexity for point searching in real singular hypersurfaces

Bernd Bank , Marc Giusti , Joos Heintz , Lutz Lehmann , Luis-Miguel Pardo

Preprint series: Institut für Mathematik, Humboldt-Universität zu Berlin (ISSN 0863-0976), 2010-11, 65

MSC 2000

68W30 Symbolic computation and algebraic computation

14P05 Real algebraic sets

14B05 Singularities

Abstract
We treat the general problem of finding real solutions of multivariate polynomial equation systems in the case of a single equation F = 0 which is supposed to admit at least one F–regular real solution (where the gradient of F does not vanish) and which has possibly other, F–singular real solutions. We present two families of elimination algorithms of intrinsic complexity which solve this problem, one in the case that the real hypersurface defined by F is compact and another without this assumption. In 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 F is squarefree and the real variety defined by F is smooth, there exist already algorithms of intrinsic complexity that solve our problem. However these algorithms cannot be used in case that F = 0 admits F-singular real solutions. An elimination algorithm of intrinsic complexity supposes 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 Q) and that there is given an invariant $\delta(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 Q) is then linear in L and polynomial in n, d and $\delta(F)$. In order to find such a geometric invariant $\delta(F)$ we consider certain deformations of the gradient of F restricted to the complex hypersurface defined by F. These deformations give rise to certain complex varieties which we call the bipolar varieties of the equation F = 0. The maximal degree of these bipolar varieties becomes then the essential ingredient of our invariant $\delta(F)$. By the way, our algorithms find F-regular algebraic sample points for all connected components of the real hypersurface defined by F that are generically smooth (i.e., that contain F-regular points).