1997-02-28Buch DOI: 10.18452/2547
Polar Varieties, Real Equation Solving and Data-Structures
 dc.contributor.author Bank, Bernd dc.contributor.author Giusti, Marc dc.contributor.author Heintz, Joos dc.contributor.author Mbakop, G. M. dc.date.accessioned 2017-06-15T17:30:47Z dc.date.available 2017-06-15T17:30:47Z dc.date.created 2005-10-26 dc.date.issued 1997-02-28 dc.identifier.issn 0863-0976 dc.identifier.uri http://edoc.hu-berlin.de/18452/3199 dc.description.abstract In this paper we apply for the first time a new method for multivariate equation solving which was developed in for complex root determination to the 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 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 polynomial in the length of the input (given in straight--line program representation) and an adequately defined geometric degree of the equation system. Replacing the notion of geometric degree of the given polynomial equation system by a suitably defined 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. eng dc.language.iso eng dc.publisher Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, Institut für Mathematik dc.rights.uri http://rightsstatements.org/vocab/InC/1.0/ dc.subject polar variety eng dc.subject Real polynomial equation solving eng dc.subject complexity eng dc.subject geometric degree eng dc.subject straight-line program eng dc.subject arithmetic network eng dc.subject.ddc 510 Mathematik dc.title Polar Varieties, Real Equation Solving and Data-Structures dc.type book dc.identifier.urn urn:nbn:de:kobv:11-10051256 dc.identifier.doi http://dx.doi.org/10.18452/2547 dc.subject.dnb 27 Mathematik local.edoc.pages 23 local.edoc.type-name Buch local.edoc.container-type series local.edoc.container-type-name Schriftenreihe local.edoc.container-year 1996 dc.title.subtitle The Hypersurface Case dc.identifier.zdb 2075199-0 bua.series.name Preprints aus dem Institut für Mathematik bua.series.issuenumber 1996,19