Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces--Revised version of preprint 10--11

Bernd Bank , Marc Giust , Joos Heintz , Lutz Lehmann , Luis Miguel Pardo

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

MSC 2000

68W30 Symbolic computation and algebraic computation

14P05 Real algebraic sets

14B05 Singularities

Abstract
For a real squarefree 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}R is compact. We admit 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 exibit one for each generically smooth connected component of {F = 0}R . We design a family of elimination algorithms of intrinsic complexity which solves this problem. 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 the real variety defined by is smooth, there exist already 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 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 δ(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 δ(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 becomes then the essential ingredient of our invariant δ(F ) .