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. Thus, here we avoid double exponential upper bounds for the degrees and solve a long-standing problem.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
A. L. Chistov, “Computations with parameters: a theoretical background,” J. Math. Sci., 215, No. 6, 769–781 (2016).
A. L. Chistov, “A bound for the degree of a system of equations determining the variety of reducible polynomials,” St.Petersburg Math. J., 24, No. 3, 513–528 (2013).
G. E. Collins, “Subresultants and reduced polynomial remainder sequences,” J. ACM, 14, No. 1, 128–142 (1967).
A. Chistov, H. Fournier, L. Gurvits, and P. Koiran, “Vandermonde matrices, NP-completeness, and transversal subspaces,” Found. Comput. Math., 3, No. 4, 421–427 (2003).
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 448, 2016, pp. 286–325.
Rights and permissions
About this article
Cite this article
Chistov, A.L. Efficient Absolute Factorization of Polynomials with Parametric Coefficients. J Math Sci 224, 360–384 (2017). https://doi.org/10.1007/s10958-017-3422-4
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10958-017-3422-4