LIP6 CNRS Sorbonne Université Tremplin Carnot Interfaces
Direct Link LIP6 » News » PhD students

HASHEMI Amir

PhD graduated
Team : SPIRAL
Departure date : 09/01/2007
Supervision : Daniel LAZARD

Structure et complexité des bases de Gröbner

Dans cette thèse, nous introduisons la notion de position de Noether forte (PNF) pour un idéal homogène, qui est une définition simple et explicite du concept "coordonnées génériques" pour certains problèmes. Nous fournissons un algorithme qui décide en temps polynomial si un idéal homogène est en PNF ou non. Cette notion nous permet d'améliorer le meilleur algorithme connu pour calculer la régularité de Castelnuovo-Mumford d'un idéal. À chaque notion de régularité, nous associons une régularité stabilisée. Ceci nous permet de définir quatre régularités stabilisées, qui sont toutes égales à la régularité de Castelnuovo-Mumford. Nous améliorons les bornes de complexité des algorithmes concernant les idéaux polynomiaux qui sont polynomiales en d^n où d est le degré maximal des polynômes d'entrée et n le nombre des variables. Nous y remplaçons d^n par max{S, D^n}, où S est la taille de l'entrée pour la représentation dense des polynômes et D la moyenne arithmétique des degrés des polynômes d'entrée. Enfin, nous montrons que la base de Gröbner (pour tout ordre monomial) d'un idéal zéro--dimensionnel affine peut être calculée avec une complexité binaire qui est polynomiale en max{S, D^n}. Par conséquent, si tous les polynômes d'entrée ont le même degré, cette complexité est polynomiale en le maximum de la taille de l'entrée et de la taille de sortie pour presque toutes les entrées.
Defence : 06/20/2006 - 11h - Site Scott - salle C.044
Jury members :
FAUGERE Jean-Charles, CNRS, Université Paris 6, (Examinateur)
HEINTZ Joos, Universidad de Cantabria, (Rapporteur)
LAZARD Daniel, Université Paris 6, (Directeur)
MORA Theo, Università di Genova, (Rapporteur)
SORIA Michèle, Université Paris 6, (Examinatrice)

2005-2011 Publications

 Mentions légales
Site map |