A Symbolic-Numerical Branch and Prune Algorithm for Solving Non-linear Polynomial Systems.pdfVIP

A Symbolic-Numerical Branch and Prune Algorithmfor Solving Non-linear Polynomial SystemsLaurent GranvilliersLIFO { Univ. Orleans { IIIA { Rue L. de VinciBP 6759 { 45067 ORLEANS Cedex 2 { FRANCELaurent.Granvilliers@lifo.univ-orleans.frAbstract: This paper discusses the processing of non-linear polynomial systems usinga branch and prune algorithm within the framework of constraint programming. Wepropose a formalism for a kind of branch and prune algorithm implementing symbolicand numerical methods to reduce the systems with respect to a relation de ned fromboth inclusion of variable domains and inclusion of sets of constraints. The secondpart of the paper presents an instantiation of this general scheme. The pruning step isimplemented as a cooperation of factorizations, substitutions and partial computationsof Grobner bases to simplify the systems, and interval Newton methods address thenumerical, approximate solving. The branching step creates a partition of domainsor generates disjunctive constraints from equations in factorized form. Experimentalresults from a prototype show that interval methods generally bene t from the symbolicprocessing of the initial constraints.Key Words: Branch and prune algorithm, non-linear constraint solving, cooperativeconstraint solvers, symbolic simpli cation, interval Newton methods, Grobner basis,polynomial system.1 IntroductionSimpli cation methods are foundations of computer algebra, used to normalizeformulae or to preprocess it before applying an appropriate resolution algorithm.Among others, Grobner bases computations [10] reduce sets of non-linear poly-nomials by deriving a particular basis of the ideal de ned by the initial poly-nomials, and cylindrical algebraic decomposition [11, 12] simpli es quanti edformulae over the reals.Interval analysis was introduced in the early sixties by Moore [32] to han-dle round-o errors of numerical computations using machine numbers, and toquantify precisely the accuracy of the results.