The Taub Faculty of Computer Science Events and Talks

Solving polynomial systems of equations is an important problem in many fields such as computer-aided design, manufacturing and robotics. In recent years, subdivision-based solvers, which typically make use of the properties of the Bezier/B-spline representation, have proven very successful in solving such systems of polynomial constraints.

A major drawback in using subdivision solvers is their lack of scalability. When the given constraint is represented as a tensor product of its variables, it grows exponentially in size as a function of the number of variables. This is especially problematic in many engineering problems that are characterized by (or can be transformed to) systems of high-dimension (i.e., a large number of variables) and relatively low polynomial degree. A well-known example is computing the kinematics of a parallel mechanism such as the Stewart-Gouge platform, where each joint adds constraints of relatively low degree. As parallel mechanisms are becoming more complex, the number of such constraints (and thus the number of variables in the system) grows, and solving their kinematics becomes a greater challenge. This leads to the conclusion that there is a need for devising methods specialized for high-dimensional, low-degree systems. In this talk I will describe ongoing research on such specialized subdivision methods, which are based on sparse representations of the polynomials, but still benefit from the features of the Bezier form. In particular I will describe a new method based on the concept of "bounding hyperplane arithmetic", which can be viewed as a generalization of interval arithmetic. We construct bounding hyperplanes, which are then passed to a linear programming (LP) solver in order to efficiently reduce the root domain. The new method has been implemented and I will present experimental results that show it compares favorably to previous methods. I will also discuss further possible approaches and future directions of research for this problem.