2003 · 131 citations · 17 references
Natural SciencesComputer ScienceMathematicsAlgebraAlgorithmsGeometryAlgebraic GeometryAlgebraic TopologyArithmetic GeometryComputational AlgebraComputational ComplexityAlgebraic Geometry ComputationAlgorithms For IdealsComplexityComputational Algebraic GeometryIdeal TheoryProjections
Let f1,..., fs be polynomials in Q[X1,..., Xn] that generate a radical ideal and let V be their complex zeroset. Suppose that V is smooth and equidimensional; then we show that computing suitable sections of the polar varieties associated to generic projections of V gives at least one point in each connected component of V ∩ R n. We deduce an algorithm that extends that of Bank, Giusti, Heintz and Mbakop to non-compact situations. Its arithmetic complexity is polynomial in the complexity of evaluation of the input system, an intrinsic algebraic quantity and a combinatorial quantity.
17
A Gröbner Free Alternative for Polynomial System Solving
M Giusti, Grégoire Lecerf, Bruno Salvy · Journal of Complexity · 2001 · 268 citations
Straight-line programs in geometric elimination theory
M Giusti, Joos Heintz, J. E. Morais et al. · Journal of Pure and Applied Algebra · 1998 · 171 citations