Abstract:
Subdivision and subdivision/iterative hybrid methods for solving a system of polynomial equations require the ability to compute the bounding set of a polynomial function for a given domain. There are different methods to compute the bounding sets and each method produces different bounding sets. Since the sizes of these bounding sets directly affect the running time of subdivision and hybrid methods, selecting the appropriate method for computing bounding sets is important. This article investigates three methods for computing bounding sets and compares them experimentally to see which one produces the smallest sets. The results show that reparametrization followed by constructing convex hulls of the control points of the resulting polynomials in Bernstein basis almost always produces smaller bounding sets than the other two methods. Therefore, using this method to compute bounding sets would result in more efficient subdivision or hybrid methods for solving polynomial systems.
Key Words: Bounding sets; Subdivision; Polynomial equations; Intersection problems.
2000 Mathematics Subject Classification: Primary: 68U07;
Secondary: 65D17.
Download the paper in pdf format here.
