real polynomial equation solving
intrinsic complexity
singularities
polar and bipolar varieties
degree of varieties
Algorithms of intrinsic complexity for point searching in real singular hypersurfaces
Bernd Bank
Bank
Bernd
Marc Giusti
Giusti
Marc
Joos Heintz
Heintz
Joos
Lutz Lehmann
Lehmann
Lutz
LuisMiguel Pardo
Pardo
LuisMiguel
Institut für Mathematik, HumboldtUniversität zu Berlin (ISSN 08630976), 201011, 65
Algorithms of intrinsic complexity for point searching in real singular hypersurfaces
Bernd Bank
,
Marc Giusti
,
Joos Heintz
,
Lutz Lehmann
,
LuisMiguel Pardo
Preprint series:
Institut für Mathematik, HumboldtUniversität zu Berlin (ISSN 08630976), 201011, 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 Fsingular real solutions.
An elimination algorithm of intrinsic complexity supposes that the polynomial F is encoded by an essentially divisionfree 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 Fregular algebraic sample points for all connected components of the real hypersurface defined by F that are generically smooth (i.e., that contain
Fregular points).
This document is wellformed XML.