×

zbMATH — the first resource for mathematics

Polynomial-time computation of the dimensions of components of algebraic varieties in zero-characteristic. (English) Zbl 0893.14020
An algorithm is described for the computation of the dimensions of all the irreducible components of an algebraic set over a zero characteristic ground field. The algebraic set is given as the zero set of a family of polynomials of degree \(< d\) in \(n\) variables and the working time of the algorithm is polynomial in the size of the input and \(d^n\). Techniques of real algebraic geometry are used in an essential way, hence the restriction to characteristic \(0\). In finite characteristic the best bound presently known is \(O(d^{n^2})\), and is also due to A. L. Chistov [see J. Sov. Math. 34, 1838-1882 (1986); translation from Zap. Nauchn. Semin. Leningrad. Otd. Mat. Inst. Steklova 137, 124-188 (1984; Zbl 0561.12010)].

MSC:
14P15 Real-analytic and semi-analytic sets
14Q15 Computational aspects of higher-dimensional varieties
68W30 Symbolic computation and algebraic computation
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bochnak, J.; Coste, M.; Roy, M.-F., Géométrie algébrique Réelle, (1987), Springer Berlin · Zbl 0633.14016
[2] Bourbaki, N.; Bourbaki, N.; Bourbaki, N., Algèbre commutative, Actualités sci. indust., no. 1290, Actualités sci. indust., no. 1293, Actualités sci. indust., no. 1308, (1965), 1314, Paris · Zbl 0141.03501
[3] Chistov, A.L., Polynomial-time computation of the dimension of algebraic varieties in zero-characteristic, J. symbol. comput., 22, 1, 1-25, (1996) · Zbl 0889.14027
[4] Chistov, A.L., Polynomial-time computation of the dimension of algebraic varieties in zero-characteristic, (), 23 · Zbl 0467.14003
[5] Chistov, A.L., Polynomial-time computation of the dimension of affine algebraic varieties in zero-characteristic, (), 24
[6] Chistov, A.L.; Chistov, A.L., Polynomial complexity algorithm for factoring polynomials and constructing components of a variety in subexponential time, (), J. sov. math., 34, 4, 124-188, (1986), English transl: · Zbl 0561.12010
[7] Chistov, A.L., Polynomial complexity of the Newton-Puiseux algorithm, (), 247-255 · Zbl 0636.65043
[8] [English transl, in: J. Sov. Math.]. · Zbl 0561.12010
[9] Giusti, M.; Heintz, J., La détermination des points isolés et de la dimension d’une variété algébrique peut se faire en temps polynomial, (1991), Ecole Polytechnique, France et Univesidad de Buenos Aires Argentina, preprint
[10] Giusti, M.; Heintz, J., La détermination des points isolés et de la dimension d’une variété algébrique peut se faire en temps polynomial, () · Zbl 0829.14029
[11] Hartshorne, R., Algebraic geometry, (1977), Springer New York · Zbl 0367.14001
[12] Lazard, D., Résolution des systèmes d’équations algébrique, Theoret. comput. sci., 15, 77-110, (1981) · Zbl 0459.68013
[13] Mumford, D., Algebraic geometry 1, () · Zbl 0114.13106
[14] Milnor, J., On Betti numbers of real varieties, (), 275-280, (2) · Zbl 0123.38302
[15] Renegar, J., A faster PSPACE algorithm for deciding the existential theory of reals, (), 291-295
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.