Application of Groebner Bases for Numerical Constraint Solving

Frederic Benhamou, Laurent Granvilliers

Date: July 19th (Friday)
Time: 11:00-11:30
Abstract
This work is an attempt to improve the computational behaviour of interval propagation methods by using techniques from computer algebra such as Groebner bases for solving polynomial constraints over the real numbers.

Interval propagation methods implement local consistency techniques and have to be combined together with enumeration techniques to compute approximations of the solutions satisfying the initial constraint set. Unfortunately the number of enumeration steps may be important due to unappropriate expressions of the initial problem. We show how Groebner bases computations, used as a preprocessing step, may generate better expressions of the initial problem which can be solved faster using interval propagation methods. Furthermore, we provide a general semantics for combining these different methods.

In the talk we present some small examples to illustrate the method and we give experimental results.

______________
__________________________________________

Previous page RISC SWP Linz Austria