Geodesic
An algorithm for solving zero-dimensional parametric systems of polynomial homogeneous equations
Ayad, Ali1 ; Fares, Ali1 ; Ayyad, Youssef1
1 Équipe Algèbre et Combinatoire, EDST, Faculté des sciences--Section 1, Université libanaise, Hadath, Liban
Journal of nonlinear sciences and its applications, Tome 5 (2012) no. 6, p. 426-438.

Voir la notice de l'article provenant de la source International Scientific Research Publications

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.
DOI : 10.22436/jnsa.005.06.03
Classification : 11Y16, 08A40, 11R09, 12D05, 15A06
Keywords: Symbolic computation, complexity analysis, theory of resultants, algebraic polynomial systems, parametric systems, Rational Univariate Representation, parametric Gaussian elimination.

Ayad, Ali 1 ; Fares, Ali 1 ; Ayyad, Youssef 1

1 Équipe Algèbre et Combinatoire, EDST, Faculté des sciences--Section 1, Université libanaise, Hadath, Liban 
@article{JNSA_2012_5_6_a2,
     author = {Ayad, Ali and Fares, Ali and Ayyad, Youssef},
     title = {An algorithm for solving zero-dimensional parametric systems of polynomial homogeneous equations},
     journal = {Journal of nonlinear sciences and its applications},
     pages = {426-438},
     publisher = {mathdoc},
     volume = {5},
     number = {6},
     year = {2012},
     doi = {10.22436/jnsa.005.06.03},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.22436/jnsa.005.06.03/}
}
TY  - JOUR
AU  - Ayad, Ali
AU  - Fares, Ali
AU  - Ayyad, Youssef
TI  - An algorithm for solving zero-dimensional parametric systems of polynomial homogeneous equations
JO  - Journal of nonlinear sciences and its applications
PY  - 2012
SP  - 426
EP  - 438
VL  - 5
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.22436/jnsa.005.06.03/
DO  - 10.22436/jnsa.005.06.03
LA  - en
ID  - JNSA_2012_5_6_a2
ER  - 
%0 Journal Article
%A Ayad, Ali
%A Fares, Ali
%A Ayyad, Youssef
%T An algorithm for solving zero-dimensional parametric systems of polynomial homogeneous equations
%J Journal of nonlinear sciences and its applications
%D 2012
%P 426-438
%V 5
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.22436/jnsa.005.06.03/
%R 10.22436/jnsa.005.06.03
%G en
%F JNSA_2012_5_6_a2
Ayad, Ali; Fares, Ali; Ayyad, Youssef. An algorithm for solving zero-dimensional parametric systems of polynomial homogeneous equations. Journal of nonlinear sciences and its applications, Tome 5 (2012) no. 6, p. 426-438. doi : 10.22436/jnsa.005.06.03. http://geodesic.mathdoc.fr/articles/10.22436/jnsa.005.06.03/

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

[2] Buchberger, B.; Collins, G. E.; Loos, R.; 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), pp. 374-383

[4] Chistov, A. L. Algorithm of polynomial complexity for factoring polynomials and finding the components of varieties in subexponential time, J. Sov. Math., Volume 34(4) (1986), pp. 1838-1882

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

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

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

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

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

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

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

[12] Giusti, M.; 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] Giusti, M.; Heintz, J.; Hagele, K.; Morais, J. E.; Pardo, L. M.; Montana, J. l. Lower bounds for diophantine approximations , J. of Pure and Applied Algebra, Volume 117, 118 (1997), pp. 277-317

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

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

[16] Gonzalez-Lopez, M.-J.; Recio, T. 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), pp. 117-141

[17] Grigoriev, D. Factorization of polynomials over a finite field and the solution of systems of algebraic equations, J. Sov. Math. , Volume 34 (4) (1986), pp. 1762-1803

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

[19] Grigoriev, D.; 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), pp. 137-145

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

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

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

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

[24] D. Lazard Résolution des systèmes d'équations algébriques, Theo. Comput, Sci, Volume 15 (1981), pp. 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), pp. 66-75

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

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

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

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

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

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

[32] Mora, T. 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, Volume 18 (1) (1984), pp. 30-32

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

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

[36] Schost, E. 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 , Volume 36 (3-4) (2003), pp. 555-594

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

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

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

[41] Weispfenning, V. 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), pp. 163-179

Cité par Sources :