Finding at least one point in each connected component of a real algebraic set defined by a single equation.

*(English)*Zbl 1009.14010Let \(P\) be a \(n\)-variate polynomial with rational coefficients, defining an algebraic subset \(V\) of the real affine space \(\mathbb{R}^n\). The paper describes an implementable algorithm which decides whether \(V\) is empty. Otherwise the algorithm returns at least one (real algebraic) point of each connected component of \(V\). The authors claim that their algorithm has a low “practical complexity”. However they admit that their algorithm does not meet the best known theoretical complexity bounds, at least in worst case. Nevertheless, there is no doubt that, after a suitable rearrangement, their procedure may compete in efficiency with known theoretical algorithms. In case that \(P\) is squarefree and \(V\) is a real hypersurface with only finitely many singularities, their complexity claim seems convincing. In case of infinitely many singularities of \(V\), the authors use a deformation of the equation \(P\) and this may spoil considerably the “practical complexity” of their procedure.

The paper extends well known algorithmic critical point methods to the case \(V\) is not compact. In distinction to already existing, similar research in this field, the authors make no attempt to give definition of “practical complexity” in mathematical terms.

The paper extends well known algorithmic critical point methods to the case \(V\) is not compact. In distinction to already existing, similar research in this field, the authors make no attempt to give definition of “practical complexity” in mathematical terms.

Reviewer: Joos Heintz (Buenos Aires)

##### MSC:

14Q10 | Computational aspects of algebraic surfaces |

65H10 | Numerical computation of solutions to systems of equations |

14P05 | Real algebraic sets |

##### Keywords:

real hypersurface; Sard’s theorem; solving polynomial equation; Gröbner basis; rational univariate representation; complexity; algorithm
PDF
BibTeX
XML
Cite

\textit{F. Rouillier} et al., J. Complexity 16, No. 4, 716--750 (2000; Zbl 1009.14010)

Full Text:
DOI

##### References:

[1] | Alonso, M.E.; Becker, E.; Roy, M.-F.; Wormann, T., Zeroes, multiplicities and idempotents for zero dimensional systems, (), 6-16 |

[2] | Basu, S.; Pollack, R.; Roy, M.-F., A new algorithm to find a point in every cell defined by a family of polynomials, (), 341-349 · Zbl 0900.68278 |

[3] | Basu, S.; Pollack, R.; Roy, M.-F., On the combinatorial and algebraic complexity of quantifier elimination, J. assoc. comput. Mach., 43, 1002-1045, (1996) · Zbl 0885.68070 |

[4] | E. Becker, and, V. Powers, Deciding positivity of real polynomials, Contemp. Math, in press. · Zbl 1017.12002 |

[5] | Bochnak, J.; Coste, M.; Roy, M.-F., Real algebraic geometry, (1999), Springer-Verlag Berlin/New York · Zbl 0633.14016 |

[6] | Canny, J., Some algebraic and geometric computations in PSPACE, Proc. twentieth ACM symp. on theory of computing, (1988), p. 460-467 |

[7] | J. Canny, A toolkit for nonlinear algebra, in, Algorithmic Foundations of Robotics, Proceedings of the Workshop on the Algorithmic Foundations of Robotics, WAFR ’94, San Francisco, CA, February 17-19, 1994, (, Goldberg and Ken, et al., Eds.), A. K. Peters, Wellesley, MA. |

[8] | Collins, G.E., Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Lecture notes in computer science, 33, (1975), Springer-Verlag Berlin/New York, p. 515-532 |

[9] | P. Conti, and, C. Traverso, Algorithms for the real radical, unpublished manuscript. · Zbl 0755.13012 |

[10] | Cox, D.; Little, J.; O’Shea, D., Ideals, varieties, and algorithms, (1991), Springer-Verlag Berlin/New York |

[11] | J. C. Faugère, http://www-calfor.lip6.fr/jcf. |

[12] | J. C. Faugère, A new efficient algorithm for computing Gröbner bases, J. Pure Appl. Algebra, in press. |

[13] | Gianni, P., Properties of Gröbner basis under specializations, Lecture notes in computer science, 378, (1987), p. 293-297 |

[14] | Gonzalez-Vega, L.; Rouillier, F.; Roy, M.-F.; Trujillo, G., Symbolic recipes for real solutions, (), 121-167 · Zbl 0994.12003 |

[15] | Grigor’ev, D.; Vorobjov, N., Solving systems of polynomial inequalities in subexponential time, J. symbolic comput., 5, 37-64, (1988) · Zbl 0662.12001 |

[16] | Heintz, J.; Roy, M.-F.; Solernó, P., On the complexity of semi-algebraic sets, Proc. IFIP 89, San Francisco, (1989), North-Holland Amsterdam, p. 293-298 |

[17] | Heintz, J.; Roy, M.-F.; Solerno, P., On the theoretical and practical complexity of the existential theory of the reals, Comput. J., 36, 427-431, (1993) · Zbl 0780.68058 |

[18] | Z. Ligatsikas, R. Rioboo, and M. F. Roy, Generic computation of the real closure of an ordered field, in Proceedings of IMACS 93, Lille, May 1993, pp. 203-208. · Zbl 1037.68546 |

[19] | Mc Callum, S., An improved projection operator for cylindrical algebraic decomposition, (1984), University of Wisconsin-Madison |

[20] | Mumford, D., Algebraic geometry I, complex projective varieties, (1976), Springer-Verlag Berlin/Heidelberg/New York · Zbl 0356.14002 |

[21] | Renegar, J., On the computational complexity and geometry of the first order theory of the reals, J. symbolic comput., 13, 255-352, (1992) · Zbl 0798.68073 |

[22] | Rioboo, R., Quelques aspects du calcul exact avec LES nombres réels, (1992), University of Paris 6 |

[23] | R. Rioboo, Algebraic closure of an ordered field, implementation in axiom, in, Proc. of Issac’92, Berkeley, July 1992. · Zbl 0921.12003 |

[24] | Rouillier, F., Algorithmes efficaces pour l’étude des zéros réels des systèmes polynomiaux, (1996), University of Rennes I |

[25] | Rouillier, F., Solving zero-dimensional systems through the rational univariate representation, Aaecc j., 9, 433-461, (1999) · Zbl 0932.12008 |

[26] | Rouillier, F.; Roy, M.-F.; Safey El Din, M., Testing emptiness of real hypersurfaces, real algebraic sets and semi-algebraic sets, FRISCO rep. month., 23, (1998) |

[27] | F. Rouillier, and, P. Zimmermann, Uspensky’s algorithm: improvements and applications, in preparation, 1999. |

[28] | Roy, M.-F., Basic algorithms in real algebraic geometry: from Sturm theorem to the existential theory of reals, Lectures on real geometry in memoriam of mario raimondo, Expositions in mathematics, 23, (1996), de Gruyter Berlin/New York, p. 1-67 · Zbl 0894.14028 |

[29] | Seidenberg, A., A new decision method for elementary algebra, Ann. of math., 60, 365-374, (1954) · Zbl 0056.01804 |

[30] | Tarski, A., A decision method for elementary algebra and geometry, (1951), University of California Press Berkeley · Zbl 0044.25102 |

[31] | Walker, R.J., Algebraic curves, (1950), Princeton University Press Princeton · Zbl 0039.37701 |

[32] | Weispfenning, V., Solving parametric polynomial equations and inequalities by symbolic algorithms, Computer algebra in science and engineering, (1995), World Scientific Singapore, p. 163-179 |

[33] | Weispfenning, V., Quantifier elimination for real algebra—the quadratic case and beyond, J. aaecc, 8, 85-101, (1997) · Zbl 0867.03003 |

[34] | Weispfenning, V., A new approach to quantifier elimination for real algebra, Quantifier elimination and cylindrical algebraic decomposition, Texts and monographs in symbolic computation, (1998), Springer-Verlag Berlin/New York, p. 376-392 · Zbl 0900.03046 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.