You can manage bookmarks using lists, please log in to your user account for this.
Media type:
E-Book
Title:
Algorithms of intrinsic complexity for point searching in real singular hypersurfaces ; dedicated to Tomás Recio on the occasion of his 60th birthday
Description:
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 Fregular real solution (where the gradient of F does not vanish) and which has possibly other, Fsingular 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 ...