Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleBounds on Numbers of Vectors of Multiplicities for Polynomials which are Easy to Compute
Author(s) Dima Grigoriev, Nicolai Vorobjov
TypeArticle in Conference Proceedings
AbstractLet F be an algebraically closed field of zero characteristic, a polynomial varphi in F[X1, ... ,Xn] have a multiplicative complexity r and f1, ... ,fk in F[X1, ... ,Xn] be some polynomials of degrees not exceeding d, such that varphi = f1 = ... = fk = 0 has a finite number of roots. We show that the number of possible distinct vectors of multiplicities of these roots is small when r, d and k are small. As technical tools we design algorithms which produce Groebner bases and vectors of multiplicities of the roots for a parametric zerodimensional system. The complexities of these algorithms are singly exponential. We also describe an algorithm for parametric absolute factorization of multivariate polynomials. This algorithm has subexponential complexity in the case of a small (relative to the number of variables) degree of the polynomials.
Translation No
Refereed No