COMPUTATION OF THE SOLUTIONS OF NONLINEAR POLYNOMIAL SYSTEMS

A fundamental problem in computer aided design is the efficient computation of all roots of a system of nonlinear polynomial equations in n variables which lie within an n-dimensional box. We present two techniques designed to solve such problems, which rely on representation of polynomials in the multivariate Bernstein basis and subdivision. In order to isolate all of the roots within the given domain, each method uses a different scheme for constructing a series of bounding boxes; the first method projects control polyhedra onto a set of coordinate planes, and the second employs linear optimization. We also examine in detail the local convergence properties of the two methods, proving that the former is quadratically convergent for n = 1 and linearly convergent for n > 1, while the latter is quadratically convergent for all n. Worst-case complexity analysis, as well as analysis of actual running times are performed.