Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 30 janvier 2018 à 14h00 en B107, Mohab Safey El Din nous parlera de : The quest of asymptotically fast algorithms for polynomial system solving over the reals

Résumé : Polynomial systems arise in many areas of engineering sciences and computer science. Most of the time, the end-user expects some information about the real solution set of the system under study. Algorithmic problems encompass which appear frequently is to decide the existence of real solutions, compute sample points in each connected component of the set under study, compute a description of this set on some affine space or answer connectivity queries. All these problems are NP-hard and, actually the best known complexities to solve them are exponential in the number of variables. Moreover, because of the non-linearity of the considered systems, reliable issues are important. In this talk, I will give an overview of computer algebra algorithms for solving these problems with a focus on those which conciliate practical efficiency with asymptotically optimal complexity.

Dernière modification : jeudi 18 janvier 2018 Valid HTML 4.01! Valid CSS! Contact : Cyril.Banderier at lipn.univ-paris13.fr