Geodesic
Systems with parameters, or efficiently solving systems of polynomial equations: 33 years later. I
Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial methods. Part XXVIII, Tome 462 (2017), pp. 122-166 
A. L. Chistov. Systems with parameters, or efficiently solving systems of polynomial equations: 33 years later. I. Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial methods. Part XXVIII, Tome 462 (2017), pp. 122-166. http://geodesic.mathdoc.fr/item/ZNSL_2017_462_a7/
@article{ZNSL_2017_462_a7,
     author = {A. L. Chistov},
     title = {Systems with parameters, or efficiently solving systems of polynomial equations: 33~years {later.~I}},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {122--166},
     year = {2017},
     volume = {462},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2017_462_a7/}
}
TY  - JOUR
AU  - A. L. Chistov
TI  - Systems with parameters, or efficiently solving systems of polynomial equations: 33 years later. I
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2017
SP  - 122
EP  - 166
VL  - 462
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2017_462_a7/
LA  - ru
ID  - ZNSL_2017_462_a7
ER  - 
%0 Journal Article
%A A. L. Chistov
%T Systems with parameters, or efficiently solving systems of polynomial equations: 33 years later. I
%J Zapiski Nauchnykh Seminarov POMI
%D 2017
%P 122-166
%V 462
%U http://geodesic.mathdoc.fr/item/ZNSL_2017_462_a7/
%G ru
%F ZNSL_2017_462_a7

Voir la notice du chapitre de livre provenant de la source Math-Net.Ru

Consider a system of polynomial equations with parametric coefficients over an arbitrary ground field. We show that the variety of parameters can be represented as a union of strata. For values of the parameters from each stratum, the solutions of the system are given by algebraic formulas depending only on this stratum. Each stratum is a quasiprojective algebraic variety with degree bounded from above by a subexponential function in the size of the input data. Also, the number of strata is subexponential in the size of the input data. Thus, here we avoid double exponential upper bounds on the degrees and solve a long-standing problem.

[1] A. Ayad, “Complexity of solving parametric polynomial systems”, Zap. Nauchn. Semin. POMI, 387, 2011, 5–52 | MR

[2] A. L. Chistov, “Algoritm polinomialnoi slozhnosti dlya razlozheniya mnogochlenov na neprivodimye mnozhiteli i nakhozhdenie komponent mnogoobraziya v subeksponentsialnoe vremya”, Zap. nauchn. semin. LOMI, 137, 1984, 124–188 | MR | Zbl

[3] A. L. Chistov, “An improvement of the complexity bound for solving systems of polynomial equations”, Zap. Nauchn. Semin. POMI, 390, 2011, 299–306 | MR

[4] A. L. Chistov, “Otsenka stepeni sistemy uravnenii, zadayuschei mnogoobrazie privodimykh mnogochlenov”, Algebra i analiz, 24:3 (2012), 199–222 ; “Исправление”, Алгебра и анализ, 25:2 (2013), 279 | MR | Zbl | MR

[5] A. L. Chistov, “Vychisleniya s parametrami: teoreticheskoe obosnovanie”, Zap. nauchn. semin. POMI, 436, 2015, 219–239 | MR

[6] A. L. Chistov, “Effektivnoe razlozhenie mnogochlenov s parametricheskimi koeffitsientami na absolyutno neprivodimye mnozhiteli”, Zap. nauchn. semin. POMI, 448, 2016, 286–325 | MR

[7] A. L. Chistov, Effektivnye algoritmy faktorizatsii mnogochlenov i ikh prilozheniya, Dissertatsiya na soiskanie uchenoi stepeni doktora fiziko-matematicheskikh nauk, Leningrad, 1987

[8] A. Chistov, H. Fournier, L. Gurvits, P. Koiran, “Vandermonde matrices, NP-completeness, and transversal subspaces”, Found. Comput. Math., 3:4 (2003), 421–427 | DOI | MR | Zbl

[9] D. Lazard, F. Rouillier, “Solving parametric polynomial systems”, J. Symbolic Comput., 42:6 (2007), 636–667 | DOI | MR | Zbl

[10] D. Lazard, “Résolution des systèmes d'équations algébriques”, Theoret. Comput. Sci., 15 (1981), 77–110 | DOI | MR | Zbl

[11] D. Lazard, “Commutative algebra and computer algebra”, Lect. Notes Comput. Sci., 144, 1983, 40–48 | DOI | MR