Complexity of solving parametric polynomial systems

A. Ayad

Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial methods. Part XIX, Tome 387 (2011), pp. 5-52

Résumé

We present three algorithms in this paper: the first algorithm solves zero-dimensional parametric homogeneous polynomial systems with single exponential time in the number $n$ of the unknowns, it decomposes the parameters space into a finite number of constructible sets and computes the finite number of solutions by parametric rational representations uniformly in each constructible set. The second algorithm factorizes absolutely multivariate parametric polynomials with single exponential time in $n$ and in the degree upper bound $d$ of the factorized polynomials. The third algorithm decomposes the algebraic varieties defined by parametric polynomial systems of positive dimension into absolutely irreducible components uniformly in the values of the parameters. The complexity bound of this algorithm is double-exponential in $n$. On the other hand, the complexity lower bound of the problem of resolution of parametric polynomial systems is double-exponential in $n$.

Bibliographie

[1] A. Ayad, “Complexity bound for the absolute factorization of parametric polynomials”, Teor. Slozhn. Vychisl. – 9, Zap. Nauchn. Semin. POMI, 316, 2004, 5–29 | MR | Zbl

[2] A. Ayad, Complexité de la résolution des systèmes algébriques paramétriques, PhD thesis, University of Rennes 1, France, October 2006 | Zbl

[3] S. Basu, R. Pollack, M.-F. Roy, Algorithms in real algebraic geometry, Springer, New York, 2003 | MR

[4] E. R. Berlekamp, “Factoring polynomials over finite fields”, Bell Systems Tech. J., 46 (1967), 1853–1859 | DOI | MR | Zbl

[5] E. R. Berlekamp, “Factoring polynomials over large finite fields”, Math. Comp., 24 (1970), 713–735 | DOI | MR

[6] B. Buchberger, “Gröbner Bases: An algorithmic method in polynomial ideal theory”, Multidimensional System Theory, eds. N. K. Bose et al., Reidel, Dordrecht, 1985, 374–383

[7] G. Chèze, G. Lecerf, Lifting and recombination techniques for absolute factorization, Manuscript, Universit de Versailles Saint-Quentin-en-Yvelines, 2005

[8] A. L. Chistov, “Algorithm of polynomial complexity for factoring polynomials and finding the components of varieties in subexponential time”, J. Sov. Math., 34:4 (1986), 1838–1882 | DOI | Zbl

[9] A. L. Chistov, D. Grigoriev, Subexponential-time solving systems of algebraic equations. I, Preprint E-9-83, LOMI, Leningrad, 1983; II, E-10-83

[10] A. Chistov, D. Grigoriev, “Complexity of quantifier elimination in the theory of algebraically closed fields”, LNCS, 176, 1984, 17–31 | MR | Zbl

[11] A. Chistov, D. Grigoriev, Polynomial-time factoring of the multivariable polynomials over a global field, Preprint E-5-82, LOMI, Leningrad, 1982 | Zbl

[12] A. Chistov, H. Fournier, L. Gurvits, P. Koiran, “Vandermonde Matrices, NP-Completeness, and Transversal Subspaces”, Found. Computat. Math., 3:4 (2003), 421–427 | DOI | MR | Zbl

[13] D. Cox, J. Little, D. O'shea, Ideals, Varieties, and Algorithms, Second Edition, Springer, 1997 | MR | Zbl

[14] D. Cox, J. Little, D. O'shea, Using Algebraic Geometry, Springer, 1998 | MR

[15] X. Dahan, E. Schost, “Sharp estimates for triangular sets”, Proceedings ISSAC, 2004, 103–110 | DOI | MR | Zbl

[16] A. Dickenstein, L. Z. Emiris, Solving Polynomial Equations, Foundations, Algorithms, and Applications, Springer, 2005 | MR | Zbl

[17] D. Eisenbud, Commutative Algebra with a View Toward Algebraic Geometry, Springer, New York, 1995 | MR | Zbl

[18] K. Gatermann, X. Bincan, Existence of 3 Positive Solutions of Systems from Chemistry, July, 2003

[19] S. Gao, “Factoring multivariate polynomials via partial differential equations”, Amer. Math. Soc., 72:242 (2003), 801–822 | MR | Zbl

[20] S. Gao, E. Kaltofen, J. May, Z. Yang, L. Zhi, “Approximate factorization of multivariate polynomials via differential equations”, ISSAC, Spain, 2004, 167–174 | DOI | MR | Zbl

[21] X.-S. Gao, S.-C. Chou, “Solving parametric algebraic systems”, ISSAC, California USA, 1992, 335–341 | Zbl

[22] M. Giusti, E. Schost, “Solving some overdetermined polynomial systems”, Proc. of the 1999 International Symposium on Symbolic and Algebraic Computation (Vancouver, BC), electronic, ACM, New York, 1999, 1–8 | DOI | MR

[23] M. Giusti, J. Heintz, K. Hagele, J. E. Morais, L. M. Pardo, J. L. Montana, “Lower bounds for diophantine approximations”, J. Pure Applied Algebra, 117–118 (1997), 277–317 | DOI | MR | Zbl

[24] M. Giusti, G. Lecerf, B. Salvy, “A Gröbner free alternative for polynomial system solving”, J. Complexity, 17:1 (2001), 154–211 | DOI | MR | Zbl

[25] M.-J. Gonzalez-Lopez, L. Gonzalez-Vega, C. Traverso, A. Zanoni, Parametric, Report Research, The FRISCO Consortium, 2000

[26] M. J. Gonzalez-Lopez, T. Recio, “The ROMIN inverse geometric model and the dynamic evaluation method”, Computer Algebra in Industry, Problem Solving in Practice, ed. Arjeh M. Cohen, Wiley, 1991, 117–141

[27] D. Grigoriev, “Factorization of polynomials over a finite field and the solution of systems of algebraic equations”, J. Sov. Math., 34:4 (1986), 1762–1803 | DOI

[28] D. Grigoriev, “Complexity of quantifier elimination in the theory of ordinary differential equations”, Lect. Notes Comp. Sci., 378, 1989, 11–25 | DOI | MR

[29] D. Grigoriev, N. Vorobjov, “Bounds on numbers of vectors of multiplicities for polynomials which are easy to compute”, Proc. ACM Intern. Conf. Symb and Algebraic Computations, Scotland, 2000, 137–145 | MR

[30] D. Grigoriev, “Constructing double-exponential number of vectors of multiplicities of solutions of polynomial systems”, Contemporary Math., 286, AMS, 2001, 115–120 | DOI | MR | Zbl

[31] J. Heintz, T. Krick, S. Puddu, J. Sabia, A. Waissbein, “Deformation Techniques for efficient polynomial equation solving”, J. Complexity, 16 (2000), 70–109 | DOI | MR | Zbl

[32] J. Heintz, “Definability and fast quantifier elimination in algebraically closed fields”, Theor. Comput. Sci., 24:3 (1983), 239–277 | DOI | MR | Zbl

[33] G. Jeronimo, J. Sabia, “Effective equidimensional decomposition of affine varieties”, J. Pure Appl. Algebra, 169:2–3 (2002), 229–248 | DOI | MR | Zbl

[34] E. Kaltofen, On the complexity of factoring polynomials with integer coefficients, PhD thesis, Rensselaer Polytechnic Instit., Troy, N.Y., December, 1982

[35] E. Kaltofen, “Factorization of polynomials”, Computer algebra, Springer, Vienna, 1983, 95–113 | DOI | MR

[36] E. Kaltofen, V. Shoup, “Subquadratic–time factoring of polynomials over finite fields”, Proc. 27th Annual ACM Symp. Theory Comput., ACM Press, New York, N.Y., 1995, 398–406 | Zbl

[37] E. Kaltofen, “Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization”, SIAM J. Comput., 14:2 (1985), 469–489 | DOI | MR | Zbl

[38] T. Krick, L. M. Pardo, “A computational method for diophantine approximation”, Algorithms Algebraic Geometry Applications, Santander, 1994, 193–253 | MR

[39] S. Lang, Algebra, Addison-Wesley, 1993 | MR | Zbl

[40] D. Lazard, “Algèbre linéaire sur $k[X_1,\dots,X_n]$ et élimination”, Bull. Soc. Math. France, 105 (1977), 165–190 | MR | Zbl

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

[42] D. Lazard, “On the specification for solvers of polynomial systems”, 5th Asian Symposium on Computers Mathematics, ASCM 2001 (Matsuyama, 2001), Japan Lect. Notes Series Computing, 9, World Scientific, 2001, 66–75 | MR | Zbl

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

[44] D. Lazard, “Resolution of polynomial systems”, Computers Mathematics, Proceedings of the Fourth Asian Symposium (ASCM 2000), eds. Xiao-Shan Gao, Dongming Wang, World Scientific, 2000, 1–8 | MR | Zbl

[45] D. Lazard, “Solving zero-dimensional algebraic systems”, J. Symb. Comput., 13 (1992), 117–131 | DOI | MR | Zbl

[46] G. Lecerf, “Computing an equidimensional decomposition of an algebraic variety by means of geometric resolutions”, Proceedings of International Symposium on Symbolic and Algebraic Computation Symbolic and Algebraic Computation, St. Andrews, Scotland, July 2000, 209–216 | MR

[47] G. Lecerf, “Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers”, J. Complexity, 19:4 (2003), 564–596 | DOI | MR | Zbl

[48] A. K. Lenstra, H. W. Lenstra (Jr.), L. Lovasz, “Factoring polynomials with rational coefficients”, Math. Ann., 261:4 (1982), 515–534 | DOI | MR | Zbl

[49] A. K. Lenstra, “Factoring multivariate polynomial over finite fields”, J. Comput. System Sci., 30:2 (1985), 235–248 | DOI | MR | Zbl

[50] A. K. Lenstra, “Factoring multivariate polynomials over algebraic number fields”, SIAM J. Comput., 16 (1987), 591–598 | DOI | MR | Zbl

[51] F. S. Macaulay, The Algebraic Theory of Modular Systems, Cambridge Tracts in Mathematics and Mathematical Physics, Cambridge University Press, 1916 | MR | Zbl

[52] A. Montes, “A new algorithm for discussing Gröbner basis with parameters”, J. Symb. Comp., 33 (2002), 183–208 | DOI | MR | Zbl

[53] T. Mora, Solving Polynomial Equation Systems, v. I, Encyclopedia of Mathematics and its Applications, 88, The Kronecker–Duval Philosophy, Cambridge University Press, 2003 | MR | Zbl

[54] G. Moroz, “Complexity of the Resolution of Parametric Systems of Equations and Inequations”, ISSAC, Genova, Italy, 2006

[55] D. Mumford, Algebraic Geometry, v. I, Complex Projective Varieties, Springer-Verlag, Berlin–Heidelberg–New York, 1995 | MR | Zbl

[56] H. Niederreiter, “Factorization of polynomials and some linear-algebra problems over finite fields”, Linear Algebra Applications, 192 (1993), 301–328 | DOI | MR | Zbl

[57] K. Rimey, “A system of polynomial equations and a solution by an unusual method”, SIGSAM Bulletin, 18:1 (1984), 30–32 | DOI | Zbl

[58] F. Rouillier, “Solving zero-dimensional polynomial systems through the rational univariate representation”, Appl. Alg. Eng. Comm. Comput., 9:5 (1999), 433–461 | DOI | MR | Zbl

[59] E. Schost, “Computing parametric geometric resolutions”, Appl. Alg. Eng. Commun. Comput., 13:5 (2003), 349–393 | DOI | MR | Zbl

[60] E. Schost, Sur la résolution des systèmes polynomiaux à paramètres, Thèse de doctorat, École polytechnique, décembre, 2000

[61] E. Schost, “Complexity results for triangular sets”, J. Symb. Comput., 36:3–4 (2003), 555–594 | DOI | MR | Zbl

[62] I. R. Shafarevich, Basic Algebraic Geometry, Springer, 1974 | MR | Zbl

[63] W. Y. Sit, “An algorithm for solving parametric linear systems”, J. Symb. Comput., 13 (1992), 353–394 | DOI | MR | Zbl

[64] W. Y. Sit, “A theory for parametric linear systems”, Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation, Bonn, West Germany, 1991, 112–121 | DOI | Zbl

[65] B. L. Van Der Waerden, Modern algebra, v. 2, 1950

[66] J. von zur Gathen, J. Gerhard, Modern Computer algebra, Cambridge University Press, 1999 | MR | Zbl

[67] J. von zur Gathen, E. Kaltofen, “Factorization of multivariate polynomials over finite fields”, Math. Comp., 45:171 (1985), 251–261 | DOI | MR | Zbl

[68] D. Wang, Elimination Practice, Software Tools and Applications, World Scientific Publ. Co Inc, 2004 | MR

[69] V. Weispfenning, “Comprehensive Gröbner bases”, J. Symb. Comput., 14 (1991), 1–29 | DOI | MR

[70] V. Weispfenning, Solving parametric polynomial equations and inequalities by symbolic algorithms, MIP–9504, Universitat Passau, Januar 1995; Proc. of the workshop “Computer Algebra in Science and Engineering” (Bielefed, August 1994), World Scientific, 1995, 163–179

[71] O. Zariski, P. Samuel, Commutative Algebra, v. 1, Springer-Verlag, 1958; v. 2, Springer-Verlag, 1976 | Zbl

[72] H. Zassenhaus, “On Hensel factorization”, J. Number Theory, 1 (1969), 291–311 | DOI | MR | Zbl