An algorithm for solving zero-dimensional parametric systems of polynomial homogeneous equations

Volume 5, Issue 6, pp 426--438 http://dx.doi.org/10.22436/jnsa.005.06.03

Download PDF

Download XML

• Export citations
  • CITATIONS & REFERENCES
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)
  • ARTICLE CITATION
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)
  • REFERENCES
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)

• 1712 Downloads
• 3023 Views

Authors

Ali Ayad - Équipe Algèbre et Combinatoire, EDST, Faculté des sciences--Section 1, Université libanaise, Hadath, Liban. Ali Fares - Équipe Algèbre et Combinatoire, EDST, Faculté des sciences--Section 1, Université libanaise, Hadath, Liban. Youssef Ayyad - Équipe Algèbre et Combinatoire, EDST, Faculté des sciences--Section 1, Université libanaise, Hadath, Liban.

Abstract

This paper presents a new algorithm for solving zero-dimensional parametric systems of polynomial homogeneous equations. This algorithm is based on the computation of what we call parametric U-resultants. The parameters space, i.e., the set of values of the parameters is decomposed into a finite number of constructible sets. The solutions of the input polynomial system are given uniformly in each constructible set by Polynomial Univariate Representations. The complexity of this algorithm is single exponential in the number n of the unknowns and the number r of the parameters.

Share and Cite

Keywords

• Symbolic computation
• complexity analysis
• theory of resultants
• algebraic polynomial systems
• parametric systems
• Rational Univariate Representation
• parametric Gaussian elimination.

MSC

•  11Y16
•  08A40
•  11R09
•  12D05
•  15A06

References

• [1] S. Basu, R. Pollack, M-F. Roy, Algorithms in real algebraic geometry, Springer, New York (2003)


• [2] B. Buchberger, G. E. Collins, R. Loos, R. Albrecht , Computer Algebra: Symbolic and Algebraic Computation, Wien, Springer (1983)


• [3] B. Buchberger , Gröbner Bases: An algorithmic method in polynomial ideal theory, , in Multidimensional System Theory (N.K.Bose et al.,Eds), Reidel, Dordrecht , (1985), 374-383.


• [4] 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.


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


• [6] D. Cox, J. Little, D. O'shea , Ideals, Varieties and Algorithms, Second Edition, Springer (1997)


• [7] A. Chistov, D. Grigoriev , Complexity of quantifier elimination in the theory of algebraically closed fields , LNCS, 176 (1984), 17-31.


• [8] A. Chistov, H. Fournier, L. Gurvits, P. Koiran, Vandermonde Matrices, NP-Completeness, and Transversal Subspaces, Foundations of Computational Mathematics, 3(4) (2003), 421-427.


• [9] X. Dahan, E. Schost, Sharp estimates for triangular sets , Proceedings ISSAC, (2004)


• [10] K. Gatermann, X. Bincan, Existence of 3 Positive Solutions of Systems from Chemistry, , (2003)


• [11] X-S. Gao, S-C. Chou , Solving parametric algebraic systems, ISSAC, California USA, (1992), 335-341.


• [12] M. Giusti, E. Schost , Solving some overdetermined polynomial systems, Proc. of the 1999 International Symposium on Symbolic and Algebraic Computation (Vancouver, BC), 1-8 (electronic), ACM, New York (1999)


• [13] M. Giusti, J. Heintz, K. Hagele, J. E. Morais, L. M. Pardo, J. l. Montana, Lower bounds for diophantine approximations , J. of Pure and Applied Algebra, 117, 118 (1997), 277-317.


• [14] M. Giusti, G. Lecerf, B. Salvy, A Gröbner free alternative for polynomial system solving , Journal of Complexity, 17 (1) (2001), 154-211.


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


• [16] M.-J. Gonzalez-Lopez, T. Recio, The ROMIN inverse geometric model and the dynamic evaluation method, In ''Computer Algebra in Industry, Problem Solving in Practice'', Edited by Arjeh M. Cohen, Wiley, (1991), 117- 141.


• [17] 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.


• [18] D. Grigoriev, Complexity of quantifier elimination in the theory of ordinary differential equations , Lecture Notes Computer Science, 378 (1989), 11-25.


• [19] 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.


• [20] D. Grigoriev, Constructing double-exponential number of vectors of multiplicities of solutions of polynomial systems , In Contemporary Math., AMS, 286 (2001), 115-120.


• [21] J. Heintz, Definability and fast quantifier elimination in algebraically closed fields , Theor. Comput. Sci. , 24 (3) (1983), 239-277.


• [22] J. Heintz, T. Krick, S. Puddu, J. Sabia, A. Waissbein , Deformation Techniques for efficient polynomial equation solving , Journal of Complexity, 16 (2000), 70-109.


• [23] D. Lazard , Algèbre linéaire sur \(k[X_1,...,X_n]\) et élimination, Bull. Soc. Math. France, 105 (1977), 165-190.


• [24] D. Lazard , Résolution des systèmes d'équations algébriques, Theo. Comput, Sci, 15 (1981), 77-110.


• [25] D. Lazard , On the specification for solvers of polynomial systems, 5th Asian Symposium on Computers Mathematics -ASCM 2001, Matsuyama, Japan. Lecture Notes Series in Computing, 9, World Scientific, (2001), 66-75.


• [26] D. Lazard, F. Rouillier , Solving parametric polynomial systems, Journal of Symbolic Computation, 42 (6) (2007), 636-667.


• [27] D. Lazard, Resolution of polynomial systems, Computers Mathematics, Proceedings of the Fourth Asian Symposium (ASCM 2000). Xiao-Shan Gao, Dongming Wang ed. World Scientific, (2000), 1-8.


• [28] G. Matera, J. M. T. Torres, The Space Complexity of Elimination Theory: Upper bounds, Foundations of Computational Mathematics, FOCM'97, Springer Verlag, (1997), 267-276.


• [29] E. W. Mayr, A. R. Meyer, The Complexity of the Word Problems for Commutative Semigroups and Polynomial Ideals , Advances in Mathematics, 46 (1982), 305-329.


• [30] A. Montes, A new algorithm for discussing Gröbner basis with parameters, J. of Symb. Comp., 33 (2002), 183-208.


• [31] G. Moroz, Complexity of the Resolution of Parametric Systems of Equations and Inequations, I, SSAC, Genova, Italy (2006)


• [32] T. Mora, Solving Polynomial Equation Systems I , The Kronecker-Duval Philosophy, Encyclopedia of Mathematics and its Applications 88 , Cambridge University Press (2003)


• [33] K. Rimey , A System of Polynomial Equations and a Solution by an Unusual Method , SIGSAM Bulletin, 18 (1) (1984), 30-32.


• [34] F. Rouillier, Solving zero-dimensional polynomial systems through the rational univariate representation, Appl. Alg. in Eng. Comm. Comput., 9 (5) (1999), 433-461.


• [35] E. Schost, Computing Parametric Geometric Resolutions, Applicable Algebra in Engineering, Communication and Computing, 13 (5) (2003), 349-393.


• [36] E. Schost, Sur la résolution des systèmes polynomiaux à paramètres, Thèse de doctorat, École polytechnique, dffecembre (2000)


• [37] E. Schost , Complexity results for triangular sets, Journal of Symbolic Computation , 36 (3-4) (2003), 555-594.


• [38] B. L. Van Der Waerden, Modern algebra, Vol 2, (1950)


• [39] D. Wang , Elimination Practice Software Tools and Applications, World Scientific Pub Co Inc, (2004)


• [40] V. Weispfenning, Comprehensive Gröbner bases, J. Symbolic Computation, 14 (1991), 1-29.


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