Efficient solution to systems of multivariate polynomials using expression trees

In recent years, several quite successful attempts have been made to solve systems of polynomial constraints, using geometric design tools, by making use of subdivision based solvers. This broad class of methods includes both binary domain subdivision as well as the projected polyhedron method of Sherbrooke and Patrikalakis [13]. One of the main difficulties in using subdivision solvers is their scalability. When the given constraint is represented as a tensor product of all its independent variables, it grows exponentially in size as a function of the number of variables. In this work, we show that for many applications, especially geometric, the exponential complexity of the constraints can be reduced to a polynomial one by representing the underlying problem structure in the form of expression trees that represent the constraints. We demonstrate the applicability and scalability of this representation and compare its performance to that of tensor product constraint representation, on several examples.