Geodesic
Systems with parameters, or efficiently solving systems of polynomial equations 33 years later
Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial and algoritmic methods. Part XXX, Tome 481 (2019), pp. 146-177 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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 union of strata. For values of 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 the 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. This solves a long standing problem to avoid double exponential growth of coefficients for this problem. 
@article{ZNSL_2019_481_a10,
     author = {A. L. Chistov},
     title = {Systems with parameters, or efficiently solving systems of polynomial equations 33 years later},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {146--177},
     year = {2019},
     volume = {481},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2019_481_a10/}
}
TY  - JOUR
AU  - A. L. Chistov
TI  - Systems with parameters, or efficiently solving systems of polynomial equations 33 years later
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2019
SP  - 146
EP  - 177
VL  - 481
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2019_481_a10/
LA  - ru
ID  - ZNSL_2019_481_a10
ER  - 
%0 Journal Article
%A A. L. Chistov
%T Systems with parameters, or efficiently solving systems of polynomial equations 33 years later
%J Zapiski Nauchnykh Seminarov POMI
%D 2019
%P 146-177
%V 481
%U http://geodesic.mathdoc.fr/item/ZNSL_2019_481_a10/
%G ru
%F ZNSL_2019_481_a10
A. L. Chistov. Systems with parameters, or efficiently solving systems of polynomial equations 33 years later. Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial and algoritmic methods. Part XXX, Tome 481 (2019), pp. 146-177. http://geodesic.mathdoc.fr/item/ZNSL_2019_481_a10/

[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

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

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

[7] A. L. Chistov, Effektivnye algoritmy faktorizatsii mnogochlenov i ikh prilozheniya, Dissertatsiya na soiskanie uchënoi stepeni d.f.-m.n., Leningrad, 1987 | Zbl

[8] A. L. Chistov, “Sistemy s parametrami, ili effektivnoe reshenie sistem polinomialnykh uravnenii 33 goda spustya. I”, Zap. nauchn. semin. POMI, 462, 2017, 122–166

[9] A. L. Chistov, “Sistemy s parametrami, ili effektivnoe reshenie sistem polinomialnykh uravnenii 33 goda spustya. II”, Zap. nauchn. semin. POMI, 468, 2018, 138–176

[10] A. L. Chistov, “Algoritmy polinomialnoi slozhnosti dlya novoi modeli predstavleniya algebraicheskikh mnogoobrazii”, Zap. nauchn. semin. POMI, 378, 2010, 133–170

[11] 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

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

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

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