Generalized polar varieties and an efficient real elimination

Bank, Bernd   ; Giusti, Marc   ; Heintz, Joos   ; Pardo, Luis M.

Kybernetika, Tome 40 (2004) no. 5, pp. 519-550

Abstract (VO)

Let $W$ be a closed algebraic subvariety of the $n$-dimensional projective space over the complex or real numbers and suppose that $W$ is non-empty and equidimensional. In this paper we generalize the classic notion of polar variety of $W$ associated with a given linear subvariety of the ambient space of $W$. As particular instances of this new notion of generalized polar variety we reobtain the classic ones and two new types of polar varieties, called dual and (in case that $W$ is affine) conic. We show that for a generic choice of their parameters the generalized polar varieties of $W$ are empty or equidimensional and, if $W$ is smooth, that their ideals of definition are Cohen-Macaulay. In the case that the variety $W$ is affine and smooth and has a complete intersection ideal of definition, we are able, for a generic parameter choice, to describe locally the generalized polar varieties of $W$ by explicit equations. Finally, we use this description in order to design a new, highly efficient elimination procedure for the following algorithmic task: In case, that the variety $W$ is $\mathbb{Q}$-definable and affine, having a complete intersection ideal of definition, and that the real trace of $W$ is non-empty and smooth, find for each connected component of the real trace of $W$ a representative point.

Détail

Classification : 14B05, 14N05, 14P05, 68Q25, 68W30
Keywords: Geometry of polar varieties and its generalizations; geometric degree; real polynomial equation solving; elimination procedure; arithmetic circuit; arithmetic network; complexity

Bibliographie

[1] Aubry P., Rouillier, F., Din M. Safey El: Real solving for positive dimensional systems. J. Symb. Computation 34 (2002), 6, 543–560 | DOI | MR

[2] Bank B., Giusti M., Heintz, J., Pardo L. M.: Generalized polar varieties: Geometry and algorithms. Manuscript. Humboldt Universität zu Berlin, Institut für Mathematik 2003. Submitted to J. Complexity | MR | Zbl

[4] Bank B., Giusti M., Heintz, J., Mbakop G. M.: Polar varieties and efficient real elimination. Math.Z. 238 (2001), 115–144. Digital Object Identifier (DOI) 10.1007/s002090100248 | DOI | MR | Zbl

[5] Bank B., Giusti M., Heintz, J., Mbakop G. M.: Polar varieties, real equation solving and data structures: The hypersurface case. J. Complexity 13 (1997), 1, 5–27. Best Paper Award J. Complexity 1997 | DOI | MR | Zbl

[6] Basu S., Pollack, R., Roy M.-F.: On the combinatorial and algebraic complexity of quantifier elimination. J.ACM 43 (1996), 6, 1002–1045 | DOI | MR | Zbl

[7] Basu S., Pollack, R., Roy M.-F.: Complexity of computing semi-algebraic descriptions of the connected components of a semialgebraic set. In: Proc. ISSAC’98, (XXX. Gloor and XXX. Oliver, eds.), Rostock 1998, pp. 13–15. ACM Press. (1998), 25–29 | MR | Zbl

[8] Bochnak J., Coste, M., Roy M.–F.: Géométrie algébrique réelle. Ergebnisse der Mathematik und ihrer Grenzgebiete. Springer, Berlin – Heidelberg – New York 1987 | MR | Zbl

[9] Bruns W., Vetter U.: Determinantal Rings. (Lecture Notes in Mathematics 1327), Springer, Berlin 1988 | MR | Zbl

[10] Bürgisser P., Clausen, M., Shokrollahi M. A.: Algebraic complexity theory. With the collaboration of Thomas Lickteig. (Grundlehren der Mathematischen Wissenschaften 315), Springer, Berlin 1997 | MR | Zbl

[11] Canny J. F.: Some algebraic and geometric computations in PSPACE. In: Proc. 20th ACM Symp. on Theory of Computing 1988, pp. 460–467

[12] Canny J. F., Emiris I. Z.: Efficient incremental algorithms for the sparse resultant and the mixed volume. J. Symb. Comput. 20 (1995), 2, 117–149 | DOI | MR | Zbl

[13] Castro D., Giusti M., Heintz J., Matera, G., Pardo L. M.: The hardness of polynomial solving. Found. Comput. Math. 3, (2003), 4, 347–420 | DOI | MR

[14] Castro D., Hägele K., Morais J. E., Pardo L. M.: Kronecker’s and Newton’s approaches to solving: A first comparision. J. Complexity 17 (2001), 1, 212–303 | DOI | MR

[15] Coste M., Roy M.-F.: Thom’s Lemma, the coding of real algebraic numbers and the computation of the topology of semialgebraic sets. J. Symbolic Comput. 5 (1988), 121–130 | DOI | MR

[16] Cucker F., Smale S.: Complexity estimates depending on condition and round-of error. J. ACM 46 (1999), 1, 113–184 | DOI | MR

[17] Demazure M.: Catastrophes et bifurcations. Ellipses, Paris 1989 | Zbl

[18] Eagon J. A., Northcott D. G.: Ideals defined by matrices and a certain complex associated with them. Proc. R. Soc. Lond., Ser. A 269 (1962), 188–204 | DOI | MR | Zbl

[19] Eagon J. A., Hochster M.: R–sequences and indeterminates. O.J. Math., Oxf. II. Ser. 25 (1974), 61–71 | MR | Zbl

[20] Eisenbud D.: Commutative Algebra with a View Toward Algebraic Geometry. Springer, New York 1995 | MR | Zbl

[21] Fulton W.: Intersection Theory. (Ergebnisse der Mathematik und ihrer Grenzgebiete 3), Springer, Berlin 1984 | MR | Zbl

[22] Gathen J. von zur: Parallel linear algebra. In: Synthesis of Parallel Algorithmns (J. Reif, ed.), Morgan Kaufmann 1993

[23] Giusti M., Heintz J.: Kronecker’s smart, little black boxes. Foundations of Computational Mathematics (R. A. DeVore, A. Iserles, and E. Süli, eds.), Cambridge Univ. Press 284 (2001), 69–104 | DOI | MR | Zbl

[24] Giusti M., Heintz J., Morais J. E., Morgenstern, J., Pardo L. M.: Straight–line programs in geometric elimination theory. J. Pure Appl. Algebra 124 (1998), 1 – 3, 101–146 | DOI | MR | Zbl

[25] Giusti M., Heintz J., Hägele K., Morais J. E., Montaña J. L., Pardo L. M.: Lower bounds for diophantine approximations. J. Pure and Applied Alg. 117, 118 (1997), 277–317 | DOI | MR | Zbl

[26] Giusti M., Lecerf, G., Salvy B.: A Gröbner free alternative for polynomial system solving. J. Complexity 17 (2001), 1, 154–211 | DOI | MR | Zbl

[27] Grigor’ev D., Vorobjov N.: Solving systems of polynomial inequalities in subexponential time. J. Symb. Comput. 5 (1998), 1/2, 37–64 | DOI | MR

[28] Heintz J.: Fast quantifier elimination over algebraically closed fields. Theoret. Comp. Sci. 24 (1983), 239–277 | DOI | MR

[29] Heintz J., Matera, G., Waissbein A.: On the time–space complexity of geometric elimination procedures. Appl. Algebra Engrg. Comm. Comput. 11 (2001), 4, 239–296 | DOI | MR | Zbl

[31] Heintz J., Roy, M.–F., Solernó P.: Complexité du principe de Tarski–Seidenberg. CRAS, t. 309, Série I, Paris 1989, pp. 825–830 | MR | Zbl

[32] Heintz J., Roy,, M–F., Solernó P.: Sur la complexité du principe de Tarski–Seidenberg. Bull. Soc. Math. France 18 (1990), 101–126 | MR | Zbl

[33] Heintz J., Schnorr C. P.: Testing polynomials which are easy to compute. In: Proc. 12th Ann. ACM Symp. on Computing, 1980, pp. 262–268, also in: Logic and Algorithmic: An Int. Symposium held in Honour of Ernst Specker, Monographie No.30 de l’Enseignement de Mathématiques, Genève 1982, pp. 237–254 | MR

[34] Krick T., Pardo L. M.: A computational method for diophantine approximation. In: Proc. MEGA’94, Algorithms in Algebraic Geometry and Applications, (L. Gonzales-Vega and T. Recio, eds.), (Progress in Mathematics 143), Birkhäuser, Basel 1996, pp. 193-254 | MR | Zbl

[35] Kunz E.: Kähler Differentials. Advanced Lectures in Mathematics. Vieweg, Braunschweig – Wiesbaden 1986 | MR | Zbl

[36] Lê D. T., Teissier B.: Variétés polaires locales et classes de Chern des variétés singulières. Annals of Mathematics 114 (1981), 457–491 | DOI | MR | Zbl

[37] Lecerf G.: Une alternative aux méthodes de réécriture pour la résolution des systèmes algébriques. Thèse. École Polytechnique 2001

[38] Lecerf G.: Quadratic Newton iterations for systems with multiplicity. Found. Comput. Math. 2 (2002), 3, 247–293 | DOI | MR

[39] Lehmann L., Waissbein A.: Wavelets and semi–algebraic sets. In: WAIT 2001, (M. Frias and J. Heintz eds.), Anales JAIIO 30 (2001), 139–155

[40] Matera G.: Probabilistic algorithms for geometric elimination. Appl. Algebra Engrg. Commun. Comput. 9 (1999), 6, 463–520 | DOI | MR | Zbl

[41] Matsumura H.: Commutative Ring Theory. (Cambridge Studies in Adv. Math. 8), Cambridge Univ. Press, Cambridge 1986 | MR | Zbl

[42] Piene R.: Polar classes of singular varieties. Ann. Scient. Éc. Norm. Sup. 4. Série, t. 11 (1978), 247–276 | MR | Zbl

[43] Renegar J.: A faster PSPACE algorithm for the existential theory of the reals. In: Proc. 29th Annual IEEE Symposium on the Foundation of Computer Science 1988, pp. 291–295

[44] Renegar J.: On the computational complexity and geometry of the first order theory of the reals. J. Symbolic Comput. 13 (1992), 3, 255–352 | MR | Zbl

[45] Din M. Safey El: Résolution réelle des systèmes polynomiaux en dimension positive. Thèse. Université Paris VI 2001

[46] Din M. Safey El, Schost E.: Polar varieties and computation of one point in each connected component of a smooth real algebraic set. In: Proc. 2003 International Symposium on Symbolic and Algebraic Computation (ISSAC 2003), ACM Press 2003, pp. 224–231 | MR

[47] Spivak M.: Calculus on Manifolds. A Modern Approach to Classical Theorems of Calculus. W. A. Benjamin, Inc., New York – Amsterdam 1965 | MR | Zbl

[48] Teissier B.: Variétés Polaires. II. Multiplicités polaires, sections planes et conditions de Whitney. Algebraic geometry (La Rábida, 1981), (J. M. Aroca, R. Buchweitz, M. Giusti and M. Merle eds.), pp. 314–491, (Lecture Notes in Math. 961) Springer, Berlin 1982, pp. 314–491 | MR | Zbl

[49] Vogel W.: Lectures on Results on Bézout’s Theorem. Springer, Berlin 1984 | MR | Zbl