Polynomial System Solving over the Reals: Algorithms, Complexity, Implementations and Applications

English

Séminaire Modèles et Algorithmes Déterministes: CASYS

9/12/2011 - 09:45 Mr Mohab Safey El Din (Universite Pierre et Marie Curie (Paris 6)) Salle 1 - Tour IRMA

Solving non-linear algebraic problems is one of the major challenges in scientific computing. In several areas of engineering sciences, algebraic problems encode geometric conditions on variables
taking their values over the reals. Thus, most of the time, one aims to obtain some information on the real solution set of polynomial systems. The resolution of these problems often has a  complexity which is exponential in the number of variables. Moreover, the non-linear nature of the considered algebraic problems and the necessity to
ensure the numerical quality of the output led us to choosing to use Computer Algebra techniques to handle these problems. In this context, the issues are to develop exact algorithms, to control their complexity suitably, to implement efficient software and to identify useful specifications for the end-users. These works rely on recent geometric ideas that lead to practically efficient algorithms with a good control of the complexity.