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 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
A. Ayad, “Complexity of solving parametric polynomial systems,” Zap. Nauchn. Sem. POMI, 387, 5–52 (2011).
A. L. Chistov, “Polynomial complexity algorithm for factoring polynomials and constructing components of a variety in subexponential time,” J. Sov. Math., 34, No. 4, 1838–1882 (1986).
A. L. Chistov, “An improvement of the complexity bound for solving systems of polynomial equations,” Zap. Nauchn. Sem. POMI, 390, 299–306 (2011).
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).
A. L. Chistov, “Computations with parameters: a theoretical background,” J. Math. Sci., 215, No. 6, 769–781 (2016).
A. L. Chistov, “Efficient absolute factorization of polynomials with parametric coefficients,” J. Math. Sci., 224, No. 2, 360–384 (2017).
A. L. Chistov, “Efficient algorithms for factorization of polynomials and their applications,” Doctor of Sciences Thesis, Leningrad (1987).
A. L. Chistov, H. Fournier, L. Gurvits, and P. Koiran, “Vandermonde matrices, NP-completeness, and transversal subspaces,” Found. Comput. Math., 3, No. 4, 421–427 (2003).
D. Lazard and F. Rouillier, “Solving parametric polynomial systems”, J. Symbolic Comput., 42, No. 6, 636–667 (2007).
D. Lazard, “Résolution des systémes d’équations algébriques,” Theoret. Comput. Sci., 15, 77–110 (1981).
D. Lazard, “Commutative algebra and computer algebra”, Lect. Notes Comput. Sci., 144, 40–48 (1983).
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 462, 2017, pp. 122–166.
Rights and permissions
About this article
Cite this article
Chistov, A.L. Systems with Parameters, or Efficiently Solving Systems of Polynomial Equations: 33 Years Later. I. J Math Sci 232, 177–203 (2018). https://doi.org/10.1007/s10958-018-3868-z
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10958-018-3868-z