×

Complexity of solving parametric polynomial systems. (English) Zbl 1334.12013

J. Math. Sci., New York 179, No. 6, 635-661 (2011) and Zap. Nauchn. Semin. POMI 381, 5-52 (2011).
Summary: In this paper, we present three algorithms: the first one solves zero-dimensional parametric homogeneous polynomial systems within single exponential time in the number \(n\) of unknowns; it decomposes the parameter 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 factirizes absolutely multivariate parametic polynomials within single exponential time in \(n\) and in the upper bound d on the degree of the factorized polynomials. The third algorithm decomposes algebraic varieties defined by parametric polynomial systems of positive dimension into absolutely irreducible components uniformly in the values of the parameters. The complexity bound for this algorithm is double exponential in \(n\). On the other hand, the lower bound on the complexity of the problem of resolution of parametric polynomial systems is double exponential in \(n\).

MSC:

12Y05 Computational aspects of field theory and polynomials (MSC2010)
68W30 Symbolic computation and algebraic computation
13P15 Solving polynomial systems; resultants
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] A. Ayad, ”Complexity bound for the absolute factorization of parametric polynomials,” Zap. Nauchn. Semin, POMI, 316, 5–29 (2004). · Zbl 1077.65046
[2] A. Ayad. ”Complexité de la résolution des systèmes algébriques paramétriques,” PhD thesis, University of Rennes 1 (2006).
[3] S. Basu, R. Pollack, and M.-F. Roy, Algorithms in Real Algebraic Geometry, Springer, New York (2003). · Zbl 1031.14028
[4] E. R. Berlckamp, ”Factoring polynomials over finite fields,” Bell Systems Tech. J., 46, 1853–1859 (1967).
[5] E. R. Berlekamp, ”Factoring polynomials over large finite fields,” Math. Comp., 24, 713–735 (1970). · Zbl 0247.12014
[6] B. Buchberger, ”Gröbner bases: An algorithmic method in polynomial ideal theory,” in: N. K. Bose et al. (eds), Multidimensional System Theory, Reidel, Dordrecht (1985), pp. 374–383. · Zbl 0587.13009
[7] G. Chèze and G, Lecerf, ”Lifting and recombination techniques for absolute factorization.” Manuscript, Université de Versailles Saint-Quentin-en-Yvelines (2005). · Zbl 1130.12007
[8] A. L. Chistov, ”Algorithm of polynomial complexity for factoring polynomials and finding the components of varieties in subexponential time,” J. Sov. Math., 34, No. 4, 1838–1882 (1986). · Zbl 0596.12022
[9] A. L. Chistov and D. Grigoriev, ”Subexponential-time solving systems of algebraic equations. I, II,” LOMI Preprint, E-9-83, E-10-83, Leningrad (1983).
[10] A. Chistov and D. Grigoriev, ”Complexity of quantifier elimination in the theory of algebraically closed fields,” Lect. Notes Comput. Sci., 176, 17–31 (1984).
[11] A. Chistov and D. Grigoriev, ”Polynomial-time factoring of the multivariable polynomials over a global field,” Preprint LOMI, E-5-82, Leningrad (1982). · Zbl 0509.68029
[12] 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). · Zbl 1050.15001
[13] D. Cox, J. Little, and D. O’Shea, Ideals, Varieties, and Algorithms, 2nd edition, Springer-Verlag, New York (1997).
[14] D. Cox, J. Little, and D. O’Shea, Using Algebraic Geometry, Springer-Verlag, New York (1998).
[15] X. Dahan and E. Schost, ”Sharp estimates for triangular sets,” in: Proceedings of ISSAC 2004, ACM, New York (2004), pp. 108–110. · Zbl 1134.13308
[16] A. Dickenstein and L. Z. Emiris (eds.), Solving Polynomial Equations. Foundations, Algorithms, and Applications, Springer-Verlag, New York (2005). · Zbl 1061.12001
[17] D. Eisenbud, Commutative Algebra with a View Toward Algebraic Geometry, Springer, New York (1995). · Zbl 0819.13001
[18] K. Gatermann and X. Bincan, ”Existence of 3 positive solutions of systems from chemistry.” Preprint (2003).
[19] S. Gao, ”Factoring multivariate polynomials via partial differential equations,” Math. Comp., 72, No. 242, 801–822 (2003). · Zbl 1052.12006
[20] S. Gao, E. Kaltofen, J. May, Z. Yang, and L. Zhi, ”Approximate factorization of multivariate polynomials via differential equations,” in: Proceedings of ISSAC 2004, ACM, New York (2004), pp. 167–74. · Zbl 1134.65346
[21] X.-S. Gao and S.-C. Chou, ”Solving parametric algebraic systems,” in: Proceedings of ISSAC 1992, ACM, New York (1992), pp. 335–341. · Zbl 0925.13014
[22] M. Giusti and E. Schost, ”Solving some overdetermined polynomial systems,” in: Proceedings of ISSAG 1999, ACM, New York (1999), pp. 1–8.
[23] M. Giusti, J. Heintz, K. Hagele, J. E. Morais, L. M. Pardo, and J. l. Montana, ”Lower bounds for diophantine approximations,” J. Pure Appl. Algebra, 117, 118, 277–317 (1997). · Zbl 0871.68101
[24] M. Giusti, G. Lecerf, and B. Salvy, ”A Gröbner free alternative for polynomial system solving,” J. Complexity, 17, No. 1, 154–211 (2001). · Zbl 1003.12005
[25] M.-J. Gonzalez-Lopez, L. Gonzalez-Vega, C. Traverso, and A. Zanoni, ”Parametric,” Report Research, The FRISCO Consortium (2000). · Zbl 1169.68662
[26] M.-J. Gonzalez-Lopez and T. Recio, ”The ROMIN inverse geometric model and the dynamic evaluation method,” in: A. M. Cohen (ed.), Computer Algebra in Industry. Problem Solving in Practice, Wiley, New York (1991), pp. 117–141.
[27] D. Grigoriev, ”Factorization of polynomials over a finite field and the solution of systems of algebraic equations,” J. Sov. Math., 34, No. 4, 1762–1803 (1986). · Zbl 0596.12023
[28] D. Grigoriev, ”Complexity of quantifier elimination in the theory of ordinary differential equations,” Lect. Notes Comput. Sci., 378, 11–25 (1989). · Zbl 1209.68679
[29] D. Grigoriev and N. Vorobjov, ”Bounds on numbers of vectors of multiplicities for polynomials which are easy to compute,” in: Proceedings of the 2000 International Symposium on Symbolic and Algebraic Computations (St.Andrews), ACM, New York (2000), pp. 137–145. · Zbl 1326.68354
[30] D. Grigoriev, ”Constructing double-exponential number of vectors of multiplicities of solutions of polynomial systems,” Contemp. Math., 286, 115–120 (2001). · Zbl 1050.68048
[31] J. Heintz, T. Krick, S. Puddu, J. Sabia, and A. Waissbein, ”Deformation techniques for efficient polynomial equation solving,” J. Complexity, 16, 70–109 (2000). · Zbl 1041.65044
[32] J. Heintz, ”Definability and fast quantifier elimination in algebraically closed fields,” Theoret. Comput. Sci., 24, No. 3, 239–277 (1983). · Zbl 0546.03017
[33] G. Jeronimo and J. Sabia, ”Effective equidimensional decomposition of affine varieties,” J. Pure Appl. Algebra, 169, Nos. 2–3, 229–248 (2002). · Zbl 1055.14061
[34] E. Kaltofen, ”On the complexity of factoring polynomials with integer coefficients,” PhD thesis, Rensselaer Polytechnic Institute, Troy, New York (1982). · Zbl 0519.68059
[35] E. Kaltofen, ”Factorization of polynomials,” in: Computer Algebra, Springer, Vienna (1983), pp. 95–113.
[36] E. Kaltofen and V. Shoup, ”Subquadratic-time factoring of polynomials over finite fields,” in: Proceedings of the 27th Annual ACM Symposium on the Theory of Computing, ACM Press, New York (1995), pp. 398–406. · Zbl 0921.11068
[37] E. Kaltofen, ”Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization,” SIAM J. Comput., 14, No. 2, 469–489 (1985). · Zbl 0605.12001
[38] T. Krick and L. M. Pardo, ”A computational method for diophantine approximation,” in: Algorithms in Algebraic Geometry and Applications, Birkhäuser, Basel (1994), pp. 193–253. · Zbl 0878.11043
[39] S. Lang, Algebra, Addison-Wesley, Reading (1993).
[40] D. Lazard, ”Algebre linéaire sur k[X 1. , . . . , X n ] et élimination,” Bull. Soc. Math. France, 105, 165–190 (1977). · Zbl 0447.13008
[41] D. Lazard, ”Résolution des systèmes d’équations algébriques,” Theoret. Comput. Sci., 15, 77–110 (1981). · Zbl 0459.68013
[42] D. Lazard, ”On the specification for solvers of polynomial systems,” in: Computer Mathematics (Matsuyama, 2001), Lect. Notes Ser. Comput., 9, World Scientific, River Edge (2001), pp. 66–75. · Zbl 1009.65028
[43] D. Lazard and F. Rouillier, ”Solving parametric polynomial systems,” J. Symbolic Comput., 42, No. 6, 636–667 (2007). · Zbl 1156.14044
[44] D. Lazard, ”Resolution of polynomial systems,” in: Computer Mathematics (Chiang Mai, 2000), Lect. Notes Ser. Comput., 8, World Scientific, River Edge (2000), pp. 1–8. · Zbl 0981.65062
[45] D. Lazard, ”Solving zero-dimensional algebraic systems,” J. Symbolic Comput., 13, 117–131 (1992). · Zbl 0753.13012
[46] G. Lecerf, ”Computing an equidimensional decomposition of an algebraic variety by means of geometric resolutions,” in: Proceedings of the 2000 International Symposium on Symbolic and Algebraic Computation (St.Andrews), ACM, New York (2000), pp. 209–216. · Zbl 1326.68360
[47] G. Lecerf, ”Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers,” J. Complexity. 19, No. 4, 564–596 (2003). · Zbl 1230.68222
[48] A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovasz. ”Factoring polynomials with rational coefficients,” Math. Ann., 261, No. 4, 515–534 (1982). · Zbl 0488.12001
[49] A. K. Lenstra, ”Factoring multivariate polynomials over finite fields,” J. Comput. System Sci., 30. No. 2, 235–248 (1985). · Zbl 0577.12013
[50] A. K. Lenstra, ”Factoring multivariate polynomials over algebraic number fields,” SIAM J. Comput., 16, 591–598 (1987). · Zbl 0636.12005
[51] F. S. Macaulay, The Algebraic Theory of Modular Systems, Cambridge Univ. Press, Cambridge (1916). · JFM 46.0167.01
[52] A. Montes, ”A new algorithm for discussing Gröhner basis with pararneters,” J. Symbolic Comput., 33, 183–208 (2002). · Zbl 1068.13016
[53] T. Mora, Solving Polynomial Equation Systems. I. The Kroneelcer-Duval Philosophy, Cambridge Univ. Press, Cambridge (2003). · Zbl 1059.12001
[54] G. Moroz, ”Complexity of the resolution of parametric systems of equations and inequations,” in: ISSAC 2006 (Genova), ACM, New York (2006), pp. 246–253. · Zbl 1356.14050
[55] D. Mumford, Algebraic Geometry. I. Complex Projective Varieties, Springer-Verlag, Berlin (1995). · Zbl 0821.14001
[56] H. Niederreiter, ”Factorization of polynomials and sonic linear-algebra problems over finite fields,” Linear Algebra Appl., 192, 301–328 (1993). · Zbl 0845.11042
[57] K. Rimey, ”A system of polynomial equations and a solution by an unusual method,” SIGSAM Bulletin, 18, No. 1, 30–32 (1984). · Zbl 0579.76002
[58] F. Rouillier, ”Solving zero-dimensional polynomial systems through the rational univariate representation,” Appl. Algebra Engrg. Comm. Comput., 9, No. 5, 433–461 (1999). · Zbl 0932.12008
[59] E. Schost, ”Cornputing parametric geometric resolutions,” Appl. Algebra Engrg. Comm. Comput. 13, No. 5, 349–393 (2003). · Zbl 1058.68123
[60] E. Schost. ”Sur la résolution des systèmes polynomiaux à paramètres,” Thesè de doctorat, École Polytechnique (2000).
[61] E. Schost, ”Complexity results for triangular sets,” J. Symbolic Comput., 36, No. 3–4, 555–594 (2003). · Zbl 1074.68082
[62] I. R. Shafarevich, Basic Algebraic Geometry, Springer-Verlag, New York-Heidelberg (1974). · Zbl 0284.14001
[63] W. Y. Sit, ”An algorithm for solving parametric linear systems,” J. Symbolic Comput., 13, 353–394 (1992). · Zbl 0752.34010
[64] W. Y. Sit, ”A theory for parametric linear systems,” in: Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation (Bonn), ACM, New York (1991), pp. 112–121. · Zbl 0923.65016
[65] B. L. van der Waerden, Modern Algebra, Vol. 2 (1950). · Zbl 0037.01903
[66] J. von zur Gathen and J. Gerhard, Modern Computer Algebra, Cambridge Univ. Press, Cambridge (1999).
[67] J. von zur Gathen and E. Kaltofen, ”Factorization of multivariate polynomials over Finite fields,” Math. Comp., 45, No. 171, 251–261 (1985). · Zbl 0596.12017
[68] D. Wang, Elimination Practice. Software Tools and Applications, World Scientific (2004). · Zbl 1099.13047
[69] V. Weispfenning, ”Comprehensive Gröbner bases,” J. Symbolic Comput., 14, 1–29 (1991). · Zbl 0784.13013
[70] V. Weispfenning, ”Solving parametric polynomial equations and inequalities by symbolic algorithms,” in: Proceedings of the Workshop an Computer Algebra in Science and Engineering (Bielefeld 1994), World Scientific (1995), pp. 163–179.
[71] O. Zariski and P. Samuel, Commutative Algebra, Vol. 1, Springer-Verlag (1958); Vol. 2, Springer-Verlag (1976). · Zbl 0081.26501
[72] H. Zassenhaus, ”On Hensel factorization,” J. Number Theory, 1, 291–311 (1969). · Zbl 0188.33703
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.