Solving Polynomial Systems Using a Branch and Prune Approach

Abstract

This paper presents {\tt Newton}, a branch and prune algorithm used to find all isolated solutions of a system of polynomial constraints. {\tt Newton} can be characterized as a global search method which uses intervals for numerical correctness and for pruning the search space early. The pruning in {\tt Newton} consists of enforcing at each node of the search tree a unique local consistency condition, called box-consistency, which approximates the notion of arc-consistency well known in artificial intelligence. Box-consistency is parametrized by an interval extension of the constraint and can be instantiated to produce the Hansen--Sengupta narrowing operator (used in interval methods) as well as new operators which are more effective when the computation is far from a solution. {\tt Newton} has been evaluated on a variety of benchmarks from kinematics, chemistry, combustion, economics, and mechanics. On these benchmarks, it outperforms the interval methods we are aware of and compares well with \textit{state-of-the-art} continuation methods. Limitations of {\tt Newton} (e.g., a sensitivity to the size of the initial intervals on some problems) are also discussed. Of particular interest is the mathematical and programming simplicity of the method.