Complexity of solving parametric polynomial systems |
| |
Authors: | A. Ayad |
| |
Affiliation: | 1.CEA LIST, Software Safety Laboratory,Gif-sur-Yvette,France;2.IRMAR, Université Rennes 1,Rennes,France |
| |
Abstract: | 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. Bibliography: 72 titles. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|