Asymptotic acceleration of solving multivariate polynomial systems of equations
Bernard Mourrain, Victor Ya. Pan · 1998
Award 668365) We propose new Las Vegas randomized algorithms for the solution of a multivariate generic or sparse polynomial system of equations. The algorithms use O ( ( +4 n)3 nD2 log b) arithmetic operations to approximate all real roots of the system as well as all roots lying in a fixed n-dimensional box or disc. Here D is an upper bound on the number of all the roots of the system, is the number of real roots or the roots lying in the box or disc, =2;b is the required upper bound on the output errors, and O (s) stands for O(s log c s), c being a constant independent of s. We also yield the bounds O (12 nD2) for the complexity of counting the numbers of all roots in a fixed box (disc) and all real roots and O (12 nD2 log b) for the complete solution of generic system. For a large class