Polar varieties, real equation solving, and data structures: the hypersurface case. (English) Zbl 0872.68066

Summary: We apply for the first time a new method for multivariate equation solving which was developed for complex root determination to the real case. Our main result concerns the problem of finding at least one representative point for each connected component of a real compact and smooth hypersurface. The basic algorithm yields a new method for symbolically solving zero-dimensional polynomial equation systems over the complex numbers. One feature of central importance of this algorithm is the use of a problem-adapted data type represented by the data structures arithmetic network and straight-line program (arithmetic circuit).
The algorithm finds the complex solutions of any affine zero-dimensional equation system in nonuniform sequential time that is polynomial in the length of the input (given in straight-line program representation) and an adequately defined geometric degree of the equation system. Replacing the notion of geometric degree of the given polynomial equation system by a suitably defined real (or complex) degree of certain polar varieties associated to the input equation of the real hypersurface under consideration, we are able to find for each connected component of the hypersurface a representative point (this point will be given in a suitable encoding). The input equation is supposed to be given by a straight-line program and the (sequential time) complexity of the algorithm is polynomial in the input length and the degree of the polar varieties mentioned above.


68Q25 Analysis of algorithms and problem complexity


Full Text: DOI arXiv


[2] Baur, W.; Strassen, V., The complexity of partial derivatives, Theoret. Comput. Sci., 22, 317-330 (1982) · Zbl 0498.68028
[3] Ben-Or, M.; Kozen, D.; Reif, J., The complexity of elementary algebra and geometry, J. Comput. System Sci., 32, 251-264 (1986) · Zbl 0634.03031
[4] Brodmann, M., Algebraische Geometrie (1989), Birkhäuser-Verlag: Birkhäuser-Verlag Basel/Boston/Berlin · Zbl 0688.14001
[5] Buchberger, B., Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems, Aequationes Math., 4, 371-383 (1970) · Zbl 0212.06401
[8] Caniglia, L.; Heintz, J., Some new effectivity bounds in computational geometry, Lecture Notes in Computer Science, 357, 131-152 (1989)
[10] Chistov, A. L.; Grigor’ev, D. J., Subexponential time solving systems of algebraic equations, LOMI Preprints, E-9-83, E-10-83 (1983)
[11] 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] Dickenstein, A.; Fitchas, N.; Giusti, M.; Sessa, C., The membership problem of unmixed ideals is solvable in single exponential time, Discrete Appl. Math., 33, 73-94 (1991) · Zbl 0747.13018
[15] Emiris, I. Z., On the Complexity of Sparse Elimination, Report, UCB/CSD-94/840 (1994)
[16] von zur Gathen, J.; Seroussi, G., Boolean circuits versus arithmetic circuits, Inform. and Comput., 91, 142-154 (1991) · Zbl 0718.11064
[21] Golubitsky, M.; Guillemin, V., Stable Mappings and Their Singularities (1986), Springer-Verlag: Springer-Verlag New York · Zbl 0294.58004
[22] Grigor’ev, D., Complexity of deciding Tarski Algebra, J. Symbolic Comput., 3, 65-108 (1987) · Zbl 0689.03021
[23] Grigor’, D.; Vorobjov, N., Solving systems of polynomial inequalities in subexponential time, J. Symbolic Comput., 5, 37-64 (1988) · Zbl 0662.12001
[24] Hermann, G., Die Frage der endlich vielen Schritte in der Theorie der Polynomideale, Math. Ann., 95, 736-788 (1926) · JFM 52.0127.01
[26] Heintz, J.; Roy, M.-F.; Solernó, P., Complexité du principe de Tarski-Seidenberg, C. R. Acad. Sci. Paris, Ser. I, 309, 825-830 (1989) · Zbl 0704.03013
[27] Heintz, J.; Roy, M.-F.; Solernó, P., Sur la complexité du principe de Tarski-Seidenberg, Bull. Soc. Math. France, 118, 101-126 (1990) · Zbl 0767.03017
[29] Heintz, J.; Wüthrich, R., An efficient quantifier elimination algorithm for algebraically closed fields of any characteristic, SIGSAM Bull., 9 (1975)
[31] Krick, T.; Pardo, L. M., Une approche informatique pour l’approximation diophantienne, C. R. Acad. Sci. Paris Sér. I, 318, 407-412 (1994) · Zbl 0814.14050
[32] Lang, S., Diophantine Geometry (1962), Interscience/Wiley: Interscience/Wiley New York/London · Zbl 0115.38701
[33] Lazard, D., Algèbre linéaire sur \(KX_1X_n]\) et élimination, Bull. Soc. Math. France, 105, 165-190 (1977) · Zbl 0447.13008
[34] Lazard, D., Résolution des systèmes d’équations algébriques, Theoret. Comput. Sci., 15, 77-110 (1981) · Zbl 0459.68013
[35] Lê, D. T.; Teissier, B., Variétés polaires locales et classes de Chern des variétés singuliéres, Ann. of Math., 114, 457-491 (1981) · Zbl 0488.32004
[36] Lenstra, A. K.; Lenstra, H. W.; Lovász, L., Factoring polynomials with rational coefficients, Math. Ann., 261, 534-543 (1982) · Zbl 0488.12001
[37] Milnor, M., On the Betti numbers of real algebraic varieties, Proc. Amer. Math. Soc., 15, 275-280 (1964) · Zbl 0123.38302
[41] Renegar, J., On the computational complexity and geometry of the first order theory of the reals, J. Symbolic Comput., 13, 255-352 (1992) · Zbl 0798.68073
[42] Roy, M.-F.; Szpirglas, A., Complexity of computation with real algebraic numbers, J. Symbolic Comput., 10, 39-51 (1990) · Zbl 0723.68054
[43] Seidenberg, A., Constructions in algebra, Trans. Amer. Math. Soc., 197, 273-313 (1974) · Zbl 0356.13007
[44] Shub, M.; Smale, S., Complexity of Bezout’s theorem. I. Geometric aspects, J. Amer. Math. Soc., 6, 459-501 (1993) · Zbl 0821.65035
[46] Shub, M.; Smale, S., Complexity of Bezout’s theorem. III. Condition number and packing, J. Complexity, 9, 4-14 (1993) · Zbl 0846.65018
[48] Shub, M.; Smale, M., Complexity of Bezout’s theorem. V. Polynomial time, Theoret. Comput. Sci., 133 (1994) · Zbl 0846.65022
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.