Polar Varieties and Efficient Real Equation Solving: The Hypersurface Case

MaRDI QIDQ4229165zbMATH OpenFDO

Authors Marc Giusti, Joos Heintz, Reinhard Mandel, Guy Merlin Mbakop, Bernd Bank

Publication date 9 March 1999

Full work available at URL https://arxiv.org/abs/alg-geom/9609003, http://www.emis.de/proceedings/3ICAOC/

zbMATH Keywords

algorithmarithmetical networkspolar varietiesreal polynomial equation solvingstraight-line programs

Mathematics Subject Classification ID

Computational aspects of higher-dimensional varieties (14Q15) Numerical computation of solutions to systems of equations (65H10) Symbolic computation and algebraic computation (68W30)

Abstract: The objective of this paper is to show how the recently proposed method by Giusti, Heintz, Morais, Morgenstern, Pardo cite{gihemorpar} can be applied to a case of real polynomial equation solving. Our main result concerns the problem of finding one representative point for each connected component of a real bounded smooth hypersurface. The algorithm in cite{gihemorpar} yields a method for symbolically solving a zero-dimensional polynomial equation system in the affine (and toric) case. Its main feature is the use of adapted data structure: Arithmetical networks and straight-line programs. The algorithm solves any affine zero-dimensional equation system in non-uniform sequential time that is polynomial in the length of the input description and an adequately defined {em affine degree} of the equation system. Replacing the affine degree of the equation system by a suitably defined {em real degree} of certain polar varieties associated to the input equation, which describes the hypersurface under consideration, and using straight-line program codification of the input and intermediate results, we obtain a method for the problem introduced above that is polynomial in the input length and the real degree.

Recommendations

• scientific article; zbMATH DE number 1552220
• Polar varieties, real equation solving, and data structures: the hypersurface case
• Polar varieties and efficient real elimination

Cited in

(11)

• Polar varieties, real equation solving, and data structures: the hypersurface case
• Penalty function based critical point approach to compute real witness solution points of polynomial systems
• Real solving for positive dimensional systems.
• Nonstandard decision methods for the solvability of real polynomial equations
• Smooth points on semi-algebraic sets
• Bipolar varieties and real solving of a singular polynomial equation
• scientific article; zbMATH DE number 1552220 (Why is no real title available?)
• scientific article; zbMATH DE number 2151204 (Why is no real title available?)
• Polars of real singular curves
• Polar varieties and efficient real elimination
• Sampling smooth points on real algebraic sets using perturbations

This page was built for publication: Polar Varieties and Efficient Real Equation Solving: The Hypersurface Case

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4229165)