Details:
Title  A SymbolicNumerical Branch and Prune Algorithm for Solving Nonlinear Polynomial Systems  Author(s)  Laurent Granvilliers  Type  Article in Journal  Abstract  This paper discusses the processing of nonlinear polynomial systems using a branch and prune algorithm within the framework of constraint programming. We propose a formalism for a kind of branch and prune algorithm implementing symbolic and numerical methods to reduce the systems with respect to a relation defined from both inclusion of variable domains and inclusion of sets of constraints. The second part of the paper presents an instantiation of this general scheme. The pruning step is implemented as a cooperation of factorizations, substitutions and partial computations of Grobner bases to simplify the systems, and interval Newton methods address the numerical, approximate solving. The branching step creates a
partition of domains or generates disjunctive constraints from equations in factorized form. Experimental results from a prototype show that interval methods generally benefit from the symbolic
processing of the initial constraints.  Keywords  Branch and prune algorithm, nonlinear constraint solving, cooperative constraint solvers, symbolic simplification, interval Newton methods, Gröbner basis polynomial system  Length  23 
File 
 Language  English  Journal  Journal of Universal Computer Science (J. UCS)  Volume  4  Number  2  Pages  125146  Year  1998  Translation 
No  Refereed 
No 
