Polar varieties and computation of one point in each connected component of a smooth real algebraic set

ABSTRACT

Let f1, ldots, fs be polynomials in Q[X1, ..., Xn] that generate a radical ideal and let V be their complex zero-set. 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ⁿ. 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.

REFERENCES

• 1: M. E. Alonso , E. Becker , M.-F. Roy , T. Wörmann, Zeros, multiplicities, and idempotents for zero-dimensional systems, Algorithms in algebraic geometry and applications, Birkhauser Verlag, Basel, Switzerland, 1996
• 2: Philippe Aubry , Fabrice Rouillier , Mohab Safey El Din, Real solving for positive dimensional systems, Journal of Symbolic Computation, v.34 n.6, p.543-560, December 2002 [doi>10.1006/jsco.2002.0563]
• 3: B. Bank , M. Giusti , J. Heintz , G. M. Mbakop, Polar varieties, real equation solving, and data structures: the hypersurface case, Journal of Complexity, v.13 n.1, p.5-27, March 1997 [doi>10.1006/jcom.1997.0432]
• 4: B. Bank, M. Giusti, J. Heintz, and G.-M. Mbakop. Polar varieties and efficient real elimination. Mathematische Zeitschrift, 238(1):115--144, 2001.
• 5: B. Bank, M. Giusti, J. Heintz, and L.-M. Pardo. The light is polar. Unpublished manuscript, 2003.
• 6: Saugata Basu , Richard Pollack, Algorithms in semi-algebraic geometry, 1996
• 7: Saugata Basu , Richard Pollack , Marie-Françoise Roy, On the combinatorial and algebraic complexity of quantifier elimination, Journal of the ACM (JACM), v.43 n.6, p.1002-1045, Nov. 1996 [doi>10.1145/235809.235813]
• 8: S. Basu, R. Pollack, and M.-F. Roy. A new algorithm to find a point in every cell defined by a family of polynomials. In Quantifier elimination and cylindrical algebraic decomposition. Springer-Verlag, 1998.
• 9: M. Giusti, K. Hägele, J. Heintz, J.-E Morais, J.-L. Montaña, and L.-M. Pardo. Lower bounds for Diophantine approximation. In Proceedings of MEGA'96, number 117, 118 in Journal of Pure and Applied Algebra, pages 277--317, 1997.
• 10: M. Giusti, J. Heintz, J.-E. Morais, J. Morgenstern, and L.-M. Pardo. Straight-line programs in geometric elimination theory. Journal of Pure and Applied Algebra, 124:101--146, 1998.
• 11: Marc Giusti , Joos Heintz , Jose Enrique Morais , Luis M. Pardo, When Polynomial Equation Systems Can Be "Solved" Fast?, Proceedings of the 11th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.205-231, July 17-22, 1995
• 12: Marc Giusti , Grégoire Lecerf , Bruno Salvy, A Gröbner free alternative for polynomial system solving, Journal of Complexity, v.17 n.1, p.154-211, March 1, 2001 [doi>10.1006/jcom.2000.0571]
• 13: D. Yu. Grigor'ev , N. N. Vorobjov, Solving systems of polynomial inequalities in subexponential time, Journal of Symbolic Computation, v.5 n.1-2, p.37-64, February/April 1988 [doi>10.1016/S0747-7171(88)80005-1]
• 14: J. Heintz, M.-F. Roy, and P. Solernò. On the complexity of semi-algebraic sets. In Proceedings IFIP'89 San Francisco, North-Holland, 1989.
• 15: J. Heintz, M.-F. Roy, and P. Solernò. On the theoretical and practical complexity of the existential theory of the reals. The Computer Journal, 36(5):427--431, 1993.
• 16: Z. Jelonek. Testing sets for properness of polynomial mappings. Mathematische Annalen, 315(1):1--35, 1999.
• 17: G. Jeronimo, T. Krick, J. Sabia, and M. Sombra. The computational complexity of the Chow form. Technical report Institut de mathématiques de Jussieu, 2003.
• 18: G. Jeronimo, and J. Sabia. Effective equidimensional decomposition of affine varieties. Journal of Pure and Applied Algebra, 169(2-3):229--248, 2002.
• 19: Grégoire Lecerf, Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers, Journal of Complexity, v.19 n.4, p.564-596, August 2003 [doi>10.1016/S0885-064X(03)00031-1]
• 20: F. Rouillier. Solving zero-dimensional systems through the Rational Univariate Representation. AAECC Journal, 9(5):433--461, 1999.
• 21: F. Rouillier , M.-F. Roy , M. Safey El Din, Finding at least one point in each connected component of a real algebraic set defined by a single equation, Journal of Complexity, v.16 n.4, p.716-750, Dec. 1, 2000 [doi>10.1006/jcom.2000.0563]
• 22: M. Safey El Din. Résolution réelle des systèmes polynomiaux de dimension positive. PhD thesis, Université Paris 6, January 2001.
• 23: M. Safey El Din and É. Schost. Properness defects of projections and computation of one point in each connected component of a real algebraic set. Technical report, RR INRIA, 2002.
• 24: I. Shafarevich. Basic Algebraic Geometry 1. Springer Verlag, 1977.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.m MISCELLANEOUS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms

Keywords:
complexity, polynomial system solving, real solutions