×

Generalized polar varieties: geometry and algorithms. (English) Zbl 1085.14047

Summary: Let \(V\) be a closed algebraic subvariety of the \(n\)-dimensional projective space over the complex or real numbers and suppose that \(V\) is non-empty and equidimensional. The classic notion of a polar variety of \(V\) associated with a given linear subvariety of the ambient space of \(V\) was generalized and motivated by the authors in [Generalized polar varieties and an efficient real elimination procedure, Kybernetika, 40 (5), 519–550 (2004)]. As particular instances of this notion of a generalized polar variety one reobtains the classic one and an alternative type of a polar variety, called dual. As main result of the present paper we show that for a generic choice of their parameters the generalized polar varieties of \(V\) are empty or equidimensional and smooth in any regular point of \(V\). In the case that the variety \(V\) 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 \(V\) by explicit equations. Finally, we indicate how this description may be used in order to design in the context of algorithmic elimination theory a highly efficient, probabilistic elimination procedure for the following task: In case, that the variety \(V\) is \(\mathbb Q\)-definable and affine, having a complete intersection ideal of definition, and that the real trace of \(V\) is non-empty and smooth, find for each connected component of the real trace of \(V\) an algebraic sample point.

MSC:

14P05 Real algebraic sets
14B05 Singularities in algebraic geometry
14Q99 Computational aspects in algebraic geometry
68Q25 Analysis of algorithms and problem complexity
68W30 Symbolic computation and algebraic computation

Software:

Kronecker
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aubry, P.; Rouillier, F.; Safey El Din, M., Real solving for positive dimensional systems, J. Symbolic Comput., 34, 6, 543-560 (2002) · Zbl 1046.14031
[2] Bank, B.; Giusti, M.; Heintz, J.; Mbakop, G. M., Polar varieties, real equation solving and data structuresthe hypersurface case, J. Complexity, 13, 1, 5-27 (1997), (Best Paper Award) · Zbl 0872.68066
[3] Bank, B.; Giusti, M.; Heintz, J.; Mbakop, G. M., Polar varieties and efficient real elimination, Math. Z., 238, 115-144 (2001) · Zbl 1073.14554
[4] B. Bank, M. Giusti, J. Heintz, L.M. Pardo, Generalized polar varieties and an efficient real elimination procedure, Kybernetika, 40 (5) (2004) 519-550.; B. Bank, M. Giusti, J. Heintz, L.M. Pardo, Generalized polar varieties and an efficient real elimination procedure, Kybernetika, 40 (5) (2004) 519-550. · Zbl 1249.14019
[5] Basu, S.; Pollack, R.; Roy, M.-F., On the combinatorial and algebraic complexity of quantifier elimination, J. ACM, 43, 6, 1002-1045 (1996) · Zbl 0885.68070
[6] Basu, S.; Pollack, R.; Roy, M.-F., Complexity of computing semi-algebraic descriptions of the connected components of a semialgebraic set, (Gloor, O., Proceedings, ISSAC ’98. Proceedings, ISSAC ’98, Rostock, Germany, August 13-15, 1998 (1998), ACM Press: ACM Press New York, NY), 25-29 · Zbl 0960.14033
[7] Bochnak, J.; Coste, M.; Roy, M.-F., Géométrie algébrique réelle, Ergebnisse der Mathematik und ihrer Grenzgebiete (1987), Springer: Springer Berlin, Heidelberg, New York · Zbl 0633.14016
[8] P. Bürgisser, M. Clausen, M.A. Shokrollahi, Algebraic complexity theory. With the collaboration of Thomas Lickteig. Grundlehren der Mathematischen Wissenschaften, vol. 315, Berlin, Springer, 1997.; P. Bürgisser, M. Clausen, M.A. Shokrollahi, Algebraic complexity theory. With the collaboration of Thomas Lickteig. Grundlehren der Mathematischen Wissenschaften, vol. 315, Berlin, Springer, 1997. · Zbl 1087.68568
[9] Canny, J. F., Some algebraic and geometric computations in PSPACE, (Proceedings of the 20th ACM Symposium on Theory of Computing (1998)), 460-467
[10] Canny, J. F.; Emiris, I. Z., Efficient incremental algorithms for the sparse resultant and the mixed volume, J. Symbolic Comput., 20, 2, 117-149 (1995) · Zbl 0843.68036
[11] Castro, D.; Giusti, M.; Heintz, J.; Matera, G.; Pardo, L. M., The hardness of polynomial solving, Found. Comput. Math., 3, 4, 347-420 (2003) · Zbl 1049.68070
[12] Castro, D.; Hägele, K.; Morais, J. E.; Pardo, L. M., Kronecker’s and Newton’s approaches to solvinga first comparison, J. Complexity, 17, 1, 212-303 (2001) · Zbl 1013.68296
[13] 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, 121-130 (1988) · Zbl 0689.14006
[14] Cucker, F.; Smale, S., Complexity estimates depending on condition and round-of error, J. ACM, 46, 1, 113-184 (1999) · Zbl 1065.68533
[15] Demazure, M., Catastrophes et bifurcations (1989), Ellipses: Ellipses Paris · Zbl 0907.58002
[16] Eagon, J. A.; Hochster, M., R-sequences and indeterminates, Osaka J. Math., Oxford II., 25, 61-71 (1974) · Zbl 0278.13008
[17] Eagon, J. A.; Northcott, D. G., Ideals defined by matrices and a certain complex associated with them, Proc. Roy. Soc. Lond. Ser. A, 269, 188-204 (1962) · Zbl 0106.25603
[18] Fulton, W., Intersection Theory. Ergebnisse der Mathematik und ihrer Grenzgebiete (3) (1984), Springer: Springer Berlin · Zbl 0541.14005
[19] von zur Gathen, J., Parallel linear algebra, (Reif, J., Synthesis of Parallel Algorithms (1993), Morgan Kaufmann: Morgan Kaufmann Los Altos, CA) · Zbl 0636.68034
[20] M. Giusti, J. Heintz, Kronecker’s smart, little black boxes, in: R.A. DeVore, A. Iserles, E.Süli (Eds.), Foundations of Computational Mathematics, Cambridge University Press, Cambridge, vol. 284, 2001, pp. 69-104.; M. Giusti, J. Heintz, Kronecker’s smart, little black boxes, in: R.A. DeVore, A. Iserles, E.Süli (Eds.), Foundations of Computational Mathematics, Cambridge University Press, Cambridge, vol. 284, 2001, pp. 69-104. · Zbl 0978.65043
[21] Giusti, M.; Heintz, J.; Hägele, K.; Morais, J. E.; Montaña, J. L.; Pardo, L. M., Lower bounds for diophantine approximations, J. Pure Appl. Algebra, 117-118, 277-317 (1997) · Zbl 0871.68101
[22] Giusti, M.; Heintz, J.; Morais, J. E.; Morgenstern, J.; Pardo, L. M., Straight-line programs in geometric elimination theory, J. Pure Appl. Algebra, 124, 1-3, 101-146 (1998) · Zbl 0944.12004
[23] Giusti, M.; Lecerf, G.; Salvy, B., A Gröbner free alternative for polynomial system solving, J. Complexity, 17, 1, 154-211 (2001) · Zbl 1003.12005
[24] Grigor’ev, D.; Vorobjov, N., Solving systems of polynomial inequalities in subexponential time, J. Symb. Comput., 5, 1/2, 37-64 (1988) · Zbl 0662.12001
[25] Heintz, J., Fast quantifier elimination over algebraically closed fields, Theoret. Comp. Sci., 24, 239-277 (1983) · Zbl 0546.03017
[26] Heintz, J.; Matera, G.; Waissbein, A., On the time-space complexity of geometric elimination procedures, Appl. Algebra Eng. Commun. Comput., 11, 4, 239-296 (2001) · Zbl 0977.68101
[27] Heintz, J.; Roy, M.-F.; Solernó, P., On the complexity of semialgebraic sets, (Ritter, G., Proceedings of Information Processing ’89. Proceedings of Information Processing ’89, (IFIP ’89), San Francisco, 1989 (1989), North-Holland: North-Holland Amsterdam), 293-298
[28] Heintz, J.; Roy, M.-F.; Solernó, P., Complexité du principe de Tarski-Seidenberg, Paris C. R. Acad. Sci. Sér. I, 309, 825-830 (1989) · Zbl 0704.03013
[29] Heintz, J.; Roy, M.-F.; Solernó, P., Sur la complexité du principe de Tarski-Seidenberg, Bull. Soc. Math. France, 18, 101-126 (1990) · Zbl 0767.03017
[30] J. Heintz, C.P. Schnorr, Testing polynomials which are easy to compute, Proceedings of the 12th Annual ACM Symposium on Computing, 1980, pp. 262-268, also in: Logic and Algorithmic: An International Symposium held in Honour of Ernst Specker, Monographie No.30 de l’Enseignement de Mathématiques, Genève, 1982, pp. 237-254.; J. Heintz, C.P. Schnorr, Testing polynomials which are easy to compute, Proceedings of the 12th Annual ACM Symposium on Computing, 1980, pp. 262-268, also in: Logic and Algorithmic: An International Symposium held in Honour of Ernst Specker, Monographie No.30 de l’Enseignement de Mathématiques, Genève, 1982, pp. 237-254. · Zbl 0483.68043
[31] Kleiman, S. L., Transversality of the general translate, Compos. Math., 28, 287-297 (1973) · Zbl 0288.14014
[32] T. Krick, L.M. Pardo, A computational method for diophantine approximation, in: L. Gonzales-Vega, T. Recio (Eds.), Proceedings of MEGA ’94, Algorithms in Algebraic Geometry and Applications, Progress in Mathematics, vol. 143, Birkhäuser, Basel, 1996, pp. 193-254.; T. Krick, L.M. Pardo, A computational method for diophantine approximation, in: L. Gonzales-Vega, T. Recio (Eds.), Proceedings of MEGA ’94, Algorithms in Algebraic Geometry and Applications, Progress in Mathematics, vol. 143, Birkhäuser, Basel, 1996, pp. 193-254. · Zbl 0878.11043
[33] Kunz, E., Kähler differentials, Advanced Lectures in Mathematics (1986), Wiesbaden Vieweg: Wiesbaden Vieweg Braunschweig · Zbl 0587.13014
[34] Lê, D. T.; Teissier, B., Variétés polaires locales et classes de Chern des variétés singulières, Ann. Math., 114, 457-491 (1981) · Zbl 0488.32004
[35] G. Lecerf, Une alternative aux méthodes de réÉcriture pour la résolution des systèmes algébriques, Thèse, École Polytechnique, 2001.; G. Lecerf, Une alternative aux méthodes de réÉcriture pour la résolution des systèmes algébriques, Thèse, École Polytechnique, 2001.
[36] Lecerf, G., Quadratic Newton iterations for systems with multiplicity, Found. Comput. Math., 2, 3, 247-293 (2002) · Zbl 1030.65050
[37] Matera, G., Probabilistic algorithms for geometric elimination, Appl. Algebra Eng. Commun. Comput., 9, 6, 463-520 (1999) · Zbl 0934.68122
[38] H. Matsumura, Commutative Ring Theory, Cambridge Studies in Advanced Mathematics, vol. 8, Cambridge University Press, Cambridge, UK, 1986.; H. Matsumura, Commutative Ring Theory, Cambridge Studies in Advanced Mathematics, vol. 8, Cambridge University Press, Cambridge, UK, 1986. · Zbl 0603.13001
[39] M. Merle, Variétés polaires, stratifications de Whitney et classes de Chern des espaces analytiques complexes, d’ après Lê-Teissier 35, Exposés du Séminaire Bourbaki, no. 600, 1982/83.; M. Merle, Variétés polaires, stratifications de Whitney et classes de Chern des espaces analytiques complexes, d’ après Lê-Teissier 35, Exposés du Séminaire Bourbaki, no. 600, 1982/83.
[40] Piene, R., Polar classes of singular varieties, Ann. Scient. Éc. Norm. Sup. 4. t., 11, 247-276 (1978) · Zbl 0401.14007
[41] Renegar, J., A faster PSPACE algorithm for the existential theory of the reals, (Proceedings of the 29th Annual IEEE Symposium on the Foundation of Computer Science (1988)), 291-295
[42] Renegar, J., On the computational complexity and geometry of the first order theory of the reals, J. Symbolic Comput., 13, 3, 255-352 (1992) · Zbl 0798.68073
[43] M. Safey El Din, Résolution réelle des systèmes polynomiaux en dimension positive, Thèse, Université Paris VI, 2001.; M. Safey El Din, Résolution réelle des systèmes polynomiaux en dimension positive, Thèse, Université Paris VI, 2001.
[44] M. Safey El Din, E. Schost, Polar varieties and computation of one point in each connected component of a smooth real algebraic set, ISSAC ’03, August 3-6 2003, Philadelphia, Pennsylvania, USA, 2003.; M. Safey El Din, E. Schost, Polar varieties and computation of one point in each connected component of a smooth real algebraic set, ISSAC ’03, August 3-6 2003, Philadelphia, Pennsylvania, USA, 2003. · Zbl 1072.68693
[45] Schoenhage, A.; Grotefeld, A.; Vetter, E., Fast Algorithms (1994), Bibl. Inst.: Bibl. Inst. Mannheim · Zbl 0853.68108
[46] Spivak, M., Calculus on manifolds. A Modern Approach to Classical Theorems of Calculus (1965), W. A. Benjamin, Inc.: W. A. Benjamin, Inc. New York, Amsterdam · Zbl 0141.05403
[47] B. Teissier, Variétés Polaires. II. Multiplicités polaires, sections planes et conditions de Whitney, in: J.M. Aroca, R. Buchweitz, M. Giusti, M. Merle (Eds.), Algebraic Geometry (La Rábida, 1981), Lecture Notes in Mathematics, vol. 961, Springer, Berlin, 1982, pp. 314-491.; B. Teissier, Variétés Polaires. II. Multiplicités polaires, sections planes et conditions de Whitney, in: J.M. Aroca, R. Buchweitz, M. Giusti, M. Merle (Eds.), Algebraic Geometry (La Rábida, 1981), Lecture Notes in Mathematics, vol. 961, Springer, Berlin, 1982, pp. 314-491. · Zbl 0585.14008
[48] Vogel, W., Lectures on Results on Bézout’s Theorem (1984), Springer: Springer Berlin · Zbl 0553.14022
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.