×

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.

MSC:

68Q25 Analysis of algorithms and problem complexity

Software:

TERA
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] S. Basu, R. Pollack, M.-F. Roy, On the combinatorial and algebraic complexity of quantifier elimination, Proc. 35th IEEE Symposium on Foundations of Computer Science; S. Basu, R. Pollack, M.-F. Roy, On the combinatorial and algebraic complexity of quantifier elimination, Proc. 35th IEEE Symposium on Foundations of Computer Science · Zbl 0885.68070
[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
[6] J. F. Canny, 1988, Some algebraic and geometric computations in PSPACE, Proc. 20th ACM Symposium on Theory of Computing, 460, 467, Assoc. Computing Machinery; J. F. Canny, 1988, Some algebraic and geometric computations in PSPACE, Proc. 20th ACM Symposium on Theory of Computing, 460, 467, Assoc. Computing Machinery
[7] J. F. Canny, I. Z. Emiris, 1995, Efficient incremental algorithms for the sparse resultant and the mixed volume; J. F. Canny, I. Z. Emiris, 1995, Efficient incremental algorithms for the sparse resultant and the mixed volume · Zbl 0843.68036
[8] Caniglia, L.; Heintz, J., Some new effectivity bounds in computational geometry, Lecture Notes in Computer Science, 357, 131-152 (1989) · Zbl 0685.68044
[9] A. L. Chistov, 1995, Polynomial-time computation of the dimension of components of algebraic varieties in zero-characteristic, Universtité Paris XII; A. L. Chistov, 1995, Polynomial-time computation of the dimension of components of algebraic varieties in zero-characteristic, Universtité Paris XII
[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
[12] J.-P. Dedieu, 1995, Estimations for the separation number of a polynomial system, Univ. Paul Sabatier, Toulouse; J.-P. Dedieu, 1995, Estimations for the separation number of a polynomial system, Univ. Paul Sabatier, Toulouse
[13] J.-P. Dedieu, 1995, Approximate solutions of numerical problems, condition number analysis and condition number theorems, Univ. Paul Sabatier, Toulouse; J.-P. Dedieu, 1995, Approximate solutions of numerical problems, condition number analysis and condition number theorems, Univ. Paul Sabatier, Toulouse
[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
[17] M. Giusti, J. Heintz, 1993, La détermination des points isolés et de la dimension d’une variété algébrique peut se faire en temps polynomial, Computational Algebraic Geometry and Commutative Algebra, Proceedings of the Cortona Conference on Computational Algebraic Geometry and Commutative Algebra, Istituto Nazionale di Alta Matematica, D. EisenbudL. Robbiano, Symposia Matematica, 34, Cambridge Univ. Press, Cambridge; M. Giusti, J. Heintz, 1993, La détermination des points isolés et de la dimension d’une variété algébrique peut se faire en temps polynomial, Computational Algebraic Geometry and Commutative Algebra, Proceedings of the Cortona Conference on Computational Algebraic Geometry and Commutative Algebra, Istituto Nazionale di Alta Matematica, D. EisenbudL. Robbiano, Symposia Matematica, 34, Cambridge Univ. Press, Cambridge
[18] M. Giusti, J. Heintz, J. E. Morais, L. M. Pardo, 1995, When polynomial equation systems can be “solved” fast?, Proc. 11th International Symposium Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-11, Paris, 1995, G. CohenM. GiustiT. Mora, Lecture Notes in Computer Science, 948, 205, 231, Springer-Verlag, New York/Berlin; M. Giusti, J. Heintz, J. E. Morais, L. M. Pardo, 1995, When polynomial equation systems can be “solved” fast?, Proc. 11th International Symposium Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-11, Paris, 1995, G. CohenM. GiustiT. Mora, Lecture Notes in Computer Science, 948, 205, 231, Springer-Verlag, New York/Berlin · Zbl 0902.12005
[19] M. Giusti, J. Heintz, J. E. Morais, J. Morgenstern, L. M. Pardo, Straight-line programs in geometric elimination theory, Pure Appl. Algebra; M. Giusti, J. Heintz, J. E. Morais, J. Morgenstern, L. M. Pardo, Straight-line programs in geometric elimination theory, Pure Appl. Algebra · Zbl 0944.12004
[20] M. Giusti, J. Heintz, K. Hägele, J. E. Morais, J. L. Montaña, L. M. Pardo, 1996, Lower bounds for diophantine Approximations, Departamento de Matemáticas, Estadistica y Computación, Universidad de Cabtabria, Spain;; M. Giusti, J. Heintz, K. Hägele, J. E. Morais, J. L. Montaña, L. M. Pardo, 1996, Lower bounds for diophantine Approximations, Departamento de Matemáticas, Estadistica y Computación, Universidad de Cabtabria, Spain;
[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)
[25] J. Heintz, M.-F. Roy, P. Solernó, 1989, On the complexity of semialgebraic sets, Proc. Information Processing’89 (IFIP 89), San Francisco, CA, 1989, G. X. Ritter, 293, 298, North-Holland, Amsterdam; J. Heintz, M.-F. Roy, P. Solernó, 1989, On the complexity of semialgebraic sets, Proc. Information Processing’89 (IFIP 89), San Francisco, CA, 1989, G. X. Ritter, 293, 298, North-Holland, Amsterdam
[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
[28] J. Heintz, C. P. Schnorr, 1980, Testing polynomials which are easy to compute, Proc. 12th Annual ACM Symposium on Computing, 1980, 262, 268; J. Heintz, C. P. Schnorr, 1980, Testing polynomials which are easy to compute, Proc. 12th Annual ACM Symposium on Computing, 1980, 262, 268 · Zbl 0483.68043
[29] Heintz, J.; Wüthrich, R., An efficient quantifier elimination algorithm for algebraically closed fields of any characteristic, SIGSAM Bull., 9 (1975)
[30] T. Krick, L. M. Pardo, 1996, A computational method for Diophantine approximation, Algorithms in Algebraic Geometry and Applications, MEGA ’94, L. Gonzales-VegaT. Recio, Progress in Mathematics, 143, 193, 254, Birkhäuser, Basel; T. Krick, L. M. Pardo, 1996, A computational method for Diophantine approximation, Algorithms in Algebraic Geometry and Applications, MEGA ’94, L. Gonzales-VegaT. Recio, Progress in Mathematics, 143, 193, 254, Birkhäuser, Basel · Zbl 0841.00016
[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
[38] J. Morgenstern, 1984, How to compute fast a function and all its derivatives, Université de Nice; J. Morgenstern, 1984, How to compute fast a function and all its derivatives, Université de Nice · Zbl 0558.68033
[39] L. M. Pardo, 1995, How lower and upper complexity bounds meet in elimination theory, Proc. 11th International Symposium Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-11, Paris, 1995, G. CohenM. GiustiT. Mora, Lecture Notes in Computer Science, 948, 33, 69, Springer-Verlag, New York/Berlin; L. M. Pardo, 1995, How lower and upper complexity bounds meet in elimination theory, Proc. 11th International Symposium Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-11, Paris, 1995, G. CohenM. GiustiT. Mora, Lecture Notes in Computer Science, 948, 33, 69, Springer-Verlag, New York/Berlin · Zbl 0899.68054
[40] J. Renegar, 1988, A faster PSPACE algorithm for the existential theory of the reals, Proc. 29th Annual IEEE Symposium on the Foundation of Computer Science (FOCS), 291, 295; J. Renegar, 1988, A faster PSPACE algorithm for the existential theory of the reals, Proc. 29th Annual IEEE Symposium on the Foundation of Computer Science (FOCS), 291, 295
[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
[45] M. Shub, S. Smale, 1993, Complexity of Bezout’s theorem II: Volumes and probabilities, Proceedings, Effective Methods in Algebraic Geometry, MEGA’92, Nice, 1992, F. EyssetteA. Galligo, Progress in Mathematics, 109, 267, 285, Birkhäuser, Basel; M. Shub, S. Smale, 1993, Complexity of Bezout’s theorem II: Volumes and probabilities, Proceedings, Effective Methods in Algebraic Geometry, MEGA’92, Nice, 1992, F. EyssetteA. Galligo, Progress in Mathematics, 109, 267, 285, Birkhäuser, Basel · Zbl 0851.65031
[46] Shub, M.; Smale, S., Complexity of Bezout’s theorem. III. Condition number and packing, J. Complexity, 9, 4-14 (1993) · Zbl 0846.65018
[47] M. Shub, S. Smale, Complexity of Bezout’s theorem. IV. Probability of success, extensions, SIAM J. Numer. Anal.; M. Shub, S. Smale, Complexity of Bezout’s theorem. IV. Probability of success, extensions, SIAM J. Numer. Anal. · Zbl 0843.65035
[48] Shub, M.; Smale, M., Complexity of Bezout’s theorem. V. Polynomial time, Theoret. Comput. Sci., 133 (1994) · Zbl 0846.65022
[49] P. Solernó, 1989, Complejidad de conjuntos semialgebraicos, Univ. de Buenos Aires; P. Solernó, 1989, Complejidad de conjuntos semialgebraicos, Univ. de Buenos Aires
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.