Previous |  Up |  Next


Title: Generalized polar varieties and an efficient real elimination (English)
Author: Bank, Bernd
Author: Giusti, Marc
Author: Heintz, Joos
Author: Pardo, Luis M.
Language: English
Journal: Kybernetika
ISSN: 0023-5954
Volume: 40
Issue: 5
Year: 2004
Pages: [519]-550
Summary lang: English
Category: math
Summary: 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. (English)
Keyword: Geometry of polar varieties and its generalizations
Keyword: geometric degree
Keyword: real polynomial equation solving
Keyword: elimination procedure
Keyword: arithmetic circuit
Keyword: arithmetic network
Keyword: complexity
MSC: 14B05
MSC: 14N05
MSC: 14P05
MSC: 68Q25
MSC: 68W30
idZBL: Zbl 1249.14019
idMR: MR2120995
Date available: 2009-09-24T20:03:37Z
Last updated: 2015-03-23
Stable URL:
Reference: [1] Aubry P., Rouillier, F., Din M. Safey El: Real solving for positive dimensional systems.J. Symb. Computation 34 (2002), 6, 543–560 MR 1943042, 10.1006/jsco.2002.0563
Reference: [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 Zbl 1085.14047, MR 2152713
Reference: [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 Zbl 1073.14554, MR 1860738, 10.1007/PL00004896
Reference: [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 Zbl 0872.68066, MR 1449757, 10.1006/jcom.1997.0432
Reference: [6] Basu S., Pollack, R., Roy M.-F.: On the combinatorial and algebraic complexity of quantifier elimination.J.ACM 43 (1996), 6, 1002–1045 Zbl 0885.68070, MR 1434910, 10.1145/235809.235813
Reference: [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 Zbl 0960.14033, MR 1805168
Reference: [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 Zbl 0633.14016, MR 0949442
Reference: [9] Bruns W., Vetter U.: Determinantal Rings.(Lecture Notes in Mathematics 1327), Springer, Berlin 1988 Zbl 1079.14533, MR 0953963
Reference: [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 Zbl 1087.68568, MR 1440179
Reference: [11] Canny J. F.: Some algebraic and geometric computations in PSPACE.In: Proc. 20th ACM Symp. on Theory of Computing 1988, pp. 460–467
Reference: [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 Zbl 0843.68036, MR 1374227, 10.1006/jsco.1995.1041
Reference: [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 MR 2009683, 10.1007/s10208-002-0065-7
Reference: [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 MR 1817613, 10.1006/jcom.2000.0572
Reference: [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 MR 0949115, 10.1016/S0747-7171(88)80008-7
Reference: [16] Cucker F., Smale S.: Complexity estimates depending on condition and round-of error.J. ACM 46 (1999), 1, 113–184 MR 1692497, 10.1145/300515.300519
Reference: [17] Demazure M.: Catastrophes et bifurcations.Ellipses, Paris 1989 Zbl 0907.58002
Reference: [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 Zbl 0106.25603, MR 0142592, 10.1098/rspa.1962.0170
Reference: [19] Eagon J. A., Hochster M.: R–sequences and indeterminates.O.J. Math., Oxf. II. Ser. 25 (1974), 61–71 Zbl 0278.13008, MR 0337934
Reference: [20] Eisenbud D.: Commutative Algebra with a View Toward Algebraic Geometry.Springer, New York 1995 Zbl 0819.13001, MR 1322960
Reference: [21] Fulton W.: Intersection Theory.(Ergebnisse der Mathematik und ihrer Grenzgebiete 3), Springer, Berlin 1984 Zbl 0935.00036, MR 0732620
Reference: [22] Gathen J. von zur: Parallel linear algebra.In: Synthesis of Parallel Algorithmns (J. Reif, ed.), Morgan Kaufmann 1993
Reference: [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 Zbl 0978.65043, MR 1836615, 10.1017/CBO9781107360198.005
Reference: [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 Zbl 0944.12004, MR 1600277, 10.1016/S0022-4049(96)00099-0
Reference: [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 Zbl 0871.68101, MR 1457843, 10.1016/S0022-4049(97)00015-7
Reference: [26] Giusti M., Lecerf, G., Salvy B.: A Gröbner free alternative for polynomial system solving.J. Complexity 17 (2001), 1, 154–211 Zbl 1003.12005, MR 1817612, 10.1006/jcom.2000.0571
Reference: [27] Grigor’ev D., Vorobjov N.: Solving systems of polynomial inequalities in subexponential time.J. Symb. Comput. 5 (1998), 1/2, 37–64 MR 0949112, 10.1016/S0747-7171(88)80005-1
Reference: [28] Heintz J.: Fast quantifier elimination over algebraically closed fields.Theoret. Comp. Sci. 24 (1983), 239–277 MR 0716823, 10.1016/0304-3975(83)90002-6
Reference: [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 Zbl 0977.68101, MR 1818975, 10.1007/s002000000046
Reference: [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 Zbl 0704.03013, MR 1055203
Reference: [32] Heintz J., Roy,, M–F., Solernó P.: Sur la complexité du principe de Tarski–Seidenberg.Bull. Soc. Math. France 18 (1990), 101–126 Zbl 0767.03017, MR 1077090
Reference: [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 0648305
Reference: [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 Zbl 0878.11043, MR 1414452
Reference: [35] Kunz E.: Kähler Differentials.Advanced Lectures in Mathematics. Vieweg, Braunschweig – Wiesbaden 1986 Zbl 0587.13014, MR 0864975
Reference: [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 Zbl 0488.32004, MR 0634426, 10.2307/1971299
Reference: [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
Reference: [38] Lecerf G.: Quadratic Newton iterations for systems with multiplicity.Found. Comput. Math. 2 (2002), 3, 247–293 MR 1907381, 10.1007/s102080010026
Reference: [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
Reference: [40] Matera G.: Probabilistic algorithms for geometric elimination.Appl. Algebra Engrg. Commun. Comput. 9 (1999), 6, 463–520 Zbl 0934.68122, MR 1706433, 10.1007/s002000050115
Reference: [41] Matsumura H.: Commutative Ring Theory.(Cambridge Studies in Adv. Math. 8), Cambridge Univ. Press, Cambridge 1986 Zbl 0666.13002, MR 0879273
Reference: [42] Piene R.: Polar classes of singular varieties.Ann. Scient. Éc. Norm. Sup. 4. Série, t. 11 (1978), 247–276 Zbl 0401.14007, MR 0510551
Reference: [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
Reference: [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 Zbl 0798.68073, MR 1156882
Reference: [45] Din M. Safey El: Résolution réelle des systèmes polynomiaux en dimension positive.Thèse. Université Paris VI 2001
Reference: [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 2035216
Reference: [47] Spivak M.: Calculus on Manifolds.A Modern Approach to Classical Theorems of Calculus. W. A. Benjamin, Inc., New York – Amsterdam 1965 Zbl 0381.58003, MR 0209411
Reference: [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 Zbl 0572.14002, MR 0708342
Reference: [49] Vogel W.: Lectures on Results on Bézout’s Theorem.Springer, Berlin 1984 Zbl 0553.14022, MR 0743265


Files Size Format View
Kybernetika_40-2004-5_2.pdf 4.754Mb application/pdf View/Open
Back to standard record
Partner of
EuDML logo