Polar Varieties, Real Equation Solving and Data-Structures: The hypersurface case
| dc.creator | Bank, B. | |
| dc.creator | Giusti, M. | |
| dc.creator | Heintz, J. | |
| dc.creator | Mbakop, G. M. | |
| dc.date | 1996-09-06 | |
| dc.date.accessioned | 2026-07-07T09:06:57Z | |
| dc.date.available | 2026-07-07T09:06:57Z | |
| dc.description | In this paper we apply for the first time a new method for multivariate equation solving which was developed in \cite{gh1}, \cite{gh2}, \cite{gh3} for complex root determination to the {\em real} case. Our main result concerns the problem of finding at least one representative point for each connected component of a real compact and smooth hypersurface. The basic algorithm of \cite{gh1}, \cite{gh2}, \cite{gh3} yields a new method for symbolically solving zero-dimensional polynomial equation systems over the complex numbers. One feature of central importance of this algorithm is the use of a problem--adapted data type represented by the data structures arithmetic network and straight-line program (arithmetic circuit). The algorithm finds the complex solutions of any affine zero-dimensional equation system in non-uniform sequential time that is {\em polynomial} in the length of the input (given in straight--line program representation) and an adequately defined {\em geometric degree of the equation system}. Replacing the notion of geometric degree of the given polynomial equation system by a suitably defined {\em real (or complex) degree} of certain polar varieties associated to the input equation of the real hypersurface under consideration, we are able to find for each connected component of the hypersurface a representative point (this point will be given in a suitable encoding). The input equation is supposed to be given by a straight-line program and the (sequential time) complexity of the algorithm is polynomial in the input length and the degree of the polar varieties mentioned above. | |
| dc.description | Latex | |
| dc.identifier | https://arxiv.org/abs/alg-geom/9609004 | |
| dc.identifier | http://arxiv.org/abs/alg-geom/9609004 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/150201 | |
| dc.subject | Algebraic Geometry | |
| dc.title | Polar Varieties, Real Equation Solving and Data-Structures: The hypersurface case | |
| dc.type | text |