Geodesic
Efficient absolute factorization of polynomials with parametric coefficients
Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial methods. Part XXVII, Tome 448 (2016), pp. 286-325
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

Consider a polynomial with parametric coefficients. We show that the variety of parameters can be represented as a union of strata. For values of the parameters from each stratum, the decomposition of this polynomial into absolutely irreducible factors is given by algebraic formulas depending only on the stratum. Each stratum is a quasiprojective algebraic variety. This variety and the corresponding output are given by polynomials of degrees at most $D$ with $D=d'd^{O(1)}$ where $d',d$ are bounds on the degrees of the input polynomials. The number of strata is polynomial in the size of the input data. This solves a long-standing problem of avoiding a double exponential growth of the degrees of coefficients for this problem. 
@article{ZNSL_2016_448_a19,
     author = {A. L. Chistov},
     title = {Efficient absolute factorization of polynomials with parametric coefficients},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {286--325},
     year = {2016},
     volume = {448},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2016_448_a19/}
}
TY  - JOUR
AU  - A. L. Chistov
TI  - Efficient absolute factorization of polynomials with parametric coefficients
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2016
SP  - 286
EP  - 325
VL  - 448
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2016_448_a19/
LA  - ru
ID  - ZNSL_2016_448_a19
ER  - 
%0 Journal Article
%A A. L. Chistov
%T Efficient absolute factorization of polynomials with parametric coefficients
%J Zapiski Nauchnykh Seminarov POMI
%D 2016
%P 286-325
%V 448
%U http://geodesic.mathdoc.fr/item/ZNSL_2016_448_a19/
%G ru
%F ZNSL_2016_448_a19
A. L. Chistov. Efficient absolute factorization of polynomials with parametric coefficients. Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial methods. Part XXVII, Tome 448 (2016), pp. 286-325. http://geodesic.mathdoc.fr/item/ZNSL_2016_448_a19/

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

[2] A. L. Chistov, “Otsenka stepeni sistemy uravnenii, zadayuschei mnogoobrazie privodimykh mnogochlenov”, Algebra i analiz, 24:3 (2012), 199–222 ; “Исправление к статье А. Л. Чистова “Оценка степени системы уравнений, задающей многообразие приводимых многочленов” (“Алгебра и анализ”, т. 24 (2012), No 3, с. 199–222)”, Алгебра и анализ, 25:2 (2013), 279 | MR | Zbl | MR

[3] G. E. Collins, “Subresultants and reduced polynomial remainder sequences”, J. ACM, 14:1 (1967), 128–142 | DOI | MR | Zbl

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