Generalized polar varieties and an efficient real elimination

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

Kybernetika (2004)

  • Volume: 40, Issue: 5, page [519]-550
  • ISSN: 0023-5954

Abstract

top
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 ℚ -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.

How to cite

top

Bank, Bernd, et al. "Generalized polar varieties and an efficient real elimination." Kybernetika 40.5 (2004): [519]-550. <http://eudml.org/doc/33718>.

@article{Bank2004,
abstract = {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.},
author = {Bank, Bernd, Giusti, Marc, Heintz, Joos, Pardo, Luis M.},
journal = {Kybernetika},
keywords = {Geometry of polar varieties and its generalizations; geometric degree; real polynomial equation solving; elimination procedure; arithmetic circuit; arithmetic network; complexity; polar variety; geometric degree; elimination procedure; arithmetic circuit; arithmetic network; complexity},
language = {eng},
number = {5},
pages = {[519]-550},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Generalized polar varieties and an efficient real elimination},
url = {http://eudml.org/doc/33718},
volume = {40},
year = {2004},
}

TY - JOUR
AU - Bank, Bernd
AU - Giusti, Marc
AU - Heintz, Joos
AU - Pardo, Luis M.
TI - Generalized polar varieties and an efficient real elimination
JO - Kybernetika
PY - 2004
PB - Institute of Information Theory and Automation AS CR
VL - 40
IS - 5
SP - [519]
EP - 550
AB - 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.
LA - eng
KW - Geometry of polar varieties and its generalizations; geometric degree; real polynomial equation solving; elimination procedure; arithmetic circuit; arithmetic network; complexity; polar variety; geometric degree; elimination procedure; arithmetic circuit; arithmetic network; complexity
UR - http://eudml.org/doc/33718
ER -

References

top
  1. Aubry P., Rouillier, F., Din M. Safey El, 10.1006/jsco.2002.0563, J. Symb. Computation 34 (2002), 6, 543–560 MR1943042DOI10.1006/jsco.2002.0563
  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 Zbl1085.14047MR2152713
  3. Bank B., Giusti M., Heintz, J., Mbakop G. M., 10.1007/PL00004896, Math.Z. 238 (2001), 115–144. Digital Object Identifier (DOI) 10.1007/s002090100248 Zbl1073.14554MR1860738DOI10.1007/PL00004896
  4. Bank B., Giusti M., Heintz, J., Mbakop G. M., 10.1006/jcom.1997.0432, J. Complexity 13 (1997), 1, 5–27. Best Paper Award J. Complexity 1997 (1997) Zbl0872.68066MR1449757DOI10.1006/jcom.1997.0432
  5. Basu S., Pollack, R., Roy M.-F., 10.1145/235809.235813, J.ACM 43 (1996), 6, 1002–1045 (1996) Zbl0885.68070MR1434910DOI10.1145/235809.235813
  6. 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 (1998) Zbl0960.14033MR1805168
  7. 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 Zbl0633.14016MR0949442
  8. Bruns W., Vetter U., Determinantal Rings, (Lecture Notes in Mathematics 1327), Springer, Berlin 1988 Zbl1079.14533MR0953963
  9. 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 Zbl1087.68568MR1440179
  10. Canny J. F., Some algebraic and geometric computations in PSPACE, In: Proc. 20th ACM Symp. on Theory of Computing 1988, pp. 460–467 (1988) 
  11. Canny J. F., Emiris I. Z., 10.1006/jsco.1995.1041, J. Symb. Comput. 20 (1995), 2, 117–149 (1995) Zbl0843.68036MR1374227DOI10.1006/jsco.1995.1041
  12. Castro D., Giusti M., Heintz J., Matera, G., Pardo L. M., 10.1007/s10208-002-0065-7, Found. Comput. Math. 3, (2003), 4, 347–420 MR2009683DOI10.1007/s10208-002-0065-7
  13. Castro D., Hägele K., Morais J. E., Pardo L. M., 10.1006/jcom.2000.0572, J. Complexity 17 (2001), 1, 212–303 MR1817613DOI10.1006/jcom.2000.0572
  14. Coste M., Roy M.-F., 10.1016/S0747-7171(88)80008-7, J. Symbolic Comput. 5 (1988), 121–130 (1988) MR0949115DOI10.1016/S0747-7171(88)80008-7
  15. Cucker F., Smale S., 10.1145/300515.300519, J. ACM 46 (1999), 1, 113–184 (1999) MR1692497DOI10.1145/300515.300519
  16. Demazure M., Catastrophes et bifurcations, Ellipses, Paris 1989 Zbl0907.58002
  17. Eagon J. A., Northcott D. G., 10.1098/rspa.1962.0170, Proc. R. Soc. Lond., Ser. A 269 (1962), 188–204 (1962) Zbl0106.25603MR0142592DOI10.1098/rspa.1962.0170
  18. Eagon J. A., Hochster M., R–sequences and indeterminates, O.J. Math., Oxf. II. Ser. 25 (1974), 61–71 (1974) Zbl0278.13008MR0337934
  19. Eisenbud D., Commutative Algebra with a View Toward Algebraic Geometry, Springer, New York 1995 Zbl0819.13001MR1322960
  20. Fulton W., Intersection Theory, (Ergebnisse der Mathematik und ihrer Grenzgebiete 3), Springer, Berlin 1984 Zbl0935.00036MR0732620
  21. Gathen J. von zur, Parallel linear algebra, In: Synthesis of Parallel Algorithmns (J. Reif, ed.), Morgan Kaufmann 1993 
  22. Giusti M., Heintz J., 10.1017/CBO9781107360198.005, Foundations of Computational Mathematics (R. A. DeVore, A. Iserles, and E. Süli, eds.), Cambridge Univ. Press 284 (2001), 69–104 Zbl0978.65043MR1836615DOI10.1017/CBO9781107360198.005
  23. Giusti M., Heintz J., Morais J. E., Morgenstern, J., Pardo L. M., 10.1016/S0022-4049(96)00099-0, J. Pure Appl. Algebra 124 (1998), 1 – 3, 101–146 (1998) Zbl0944.12004MR1600277DOI10.1016/S0022-4049(96)00099-0
  24. Giusti M., Heintz J., Hägele K., Morais J. E., Montaña J. L., Pardo L. M., 10.1016/S0022-4049(97)00015-7, J. Pure and Applied Alg. 117, 118 (1997), 277–317 (1997) Zbl0871.68101MR1457843DOI10.1016/S0022-4049(97)00015-7
  25. Giusti M., Lecerf, G., Salvy B., 10.1006/jcom.2000.0571, J. Complexity 17 (2001), 1, 154–211 Zbl1003.12005MR1817612DOI10.1006/jcom.2000.0571
  26. Grigor’ev D., Vorobjov N., 10.1016/S0747-7171(88)80005-1, J. Symb. Comput. 5 (1998), 1/2, 37–64 (1998) MR0949112DOI10.1016/S0747-7171(88)80005-1
  27. Heintz J., 10.1016/0304-3975(83)90002-6, Theoret. Comp. Sci. 24 (1983), 239–277 (1983) MR0716823DOI10.1016/0304-3975(83)90002-6
  28. Heintz J., Matera, G., Waissbein A., 10.1007/s002000000046, Appl. Algebra Engrg. Comm. Comput. 11 (2001), 4, 239–296 Zbl0977.68101MR1818975DOI10.1007/s002000000046
  29. Heintz J., Roy, M.–F., Solernó P., Complexité du principe de Tarski–Seidenberg, CRAS, t. 309, Série I, Paris 1989, pp. 825–830 (1989) Zbl0704.03013MR1055203
  30. Heintz J., Roy,, M–F., Solernó P., Sur la complexité du principe de Tarski–Seidenberg, Bull. Soc. Math. France 18 (1990), 101–126 (1990) Zbl0767.03017MR1077090
  31. 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 (1980) MR0648305
  32. 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 (1996) Zbl0878.11043MR1414452
  33. Kunz E., Kähler Differentials, Advanced Lectures in Mathematics. Vieweg, Braunschweig – Wiesbaden 1986 Zbl0587.13014MR0864975
  34. Lê D. T., Teissier B., 10.2307/1971299, Annals of Mathematics 114 (1981), 457–491 (1981) Zbl0488.32004MR0634426DOI10.2307/1971299
  35. Lecerf G., 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., 10.1007/s102080010026, Found. Comput. Math. 2 (2002), 3, 247–293 MR1907381DOI10.1007/s102080010026
  37. Lehmann L., Waissbein A., Wavelets and semi–algebraic sets, In: WAIT 2001, (M. Frias and J. Heintz eds.), Anales JAIIO 30 (2001), 139–155 
  38. Matera G., 10.1007/s002000050115, Appl. Algebra Engrg. Commun. Comput. 9 (1999), 6, 463–520 (1999) Zbl0934.68122MR1706433DOI10.1007/s002000050115
  39. Matsumura H., Commutative Ring Theory, (Cambridge Studies in Adv. Math. 8), Cambridge Univ. Press, Cambridge 1986 Zbl0666.13002MR0879273
  40. Piene R., Polar classes of singular varieties, Ann. Scient. Éc. Norm. Sup. 4. Série, t. 11 (1978), 247–276 (1978) Zbl0401.14007MR0510551
  41. 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 (1988) 
  42. Renegar J., On the computational complexity and geometry of the first order theory of the reals, J. Symbolic Comput. 13 (1992), 3, 255–352 (1992) Zbl0798.68073MR1156882
  43. Din M. Safey El, Résolution réelle des systèmes polynomiaux en dimension positive, Thèse. Université Paris VI 2001 
  44. 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 MR2035216
  45. Spivak M., Calculus on Manifolds, A Modern Approach to Classical Theorems of Calculus. W. A. Benjamin, Inc., New York – Amsterdam 1965 Zbl0381.58003MR0209411
  46. 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 (1981) Zbl0572.14002MR0708342
  47. Vogel W., Lectures on Results on Bézout’s Theorem, Springer, Berlin 1984 Zbl0553.14022MR0743265

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.