Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1006/jcom.1997.0432 | J. Complexity |
Keywords | DocType | Volume |
hypersurface case,data structure,real equation,polar variety | Journal | 13 |
Issue | ISSN | Citations |
1 | Journal of Complexity | 21 |
PageRank | References | Authors |
1.24 | 19 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| B. Bank | 1 | 21 | 1.24 |
| M. Giusti | 2 | 54 | 2.46 |
| J. Heintz | 3 | 162 | 19.20 |
| G. M. Mbakop | 4 | 21 | 1.58 |