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.

2005-2011 Publications

• 2011
  • A. Hashemi, D. Lazard : “Sharper complexity bounds for zero-dimensional Göbner bases and polynomial system solving”, International Journal of Algebra and Computation, vol. 21 (5), pp. 703-713, (World Scientific Publishing) (2011)
• 2009
  • A. Hashemi : “Nullstellensätze for Zero–Dimensional Gröbner Bases”, Computational Complexity, vol. 18 (1), pp. 155-168, (Springer Verlag) (2009)
• 2007
  • A. Hashemi : “Efficient Algorithms for Computing Noether Normalization”, ASCM 2007: The 8^th ASian Symposium on Computer Mathematics, vol. 5081, Lecture Notes in Computer Science, Singapore, Singapore, pp. 97-107, (Springer) (2007)
  • G. Ars, A. Hashemi : “Efficient Computation of Syzygies by Faugere’s F5 algorithm”, MACIS 2007: Mathematical Aspects of Computer and Information Sciences, Paris, France (2007)
  • A. Hashemi : “Polynomial-Time Algorithm for Hilbert Series of Borel Type Ideals”, SNC'07: Symbolic-Numeric Computation'07, London, Ontario, Canada, pp. 97-102, (ACM) (2007)
  • A. Hashemi : “Polynomial Complexity for Hilbert Series of Borel Type Ideals”, Albanian Journal of Mathematics, vol. 1 (3), pp. 145-155, (University of Vlora) (2007)
• 2006
  • A. Hashemi : “Structure et complexité des bases de Gröbner”, thesis, phd defence 06/20/2006, supervision Lazard, Daniel (2006)
  • A. Hashemi : “Strong Noether Position”, International Congress of Mathematical Software, Castro Urdiales, Spain (2006)
  • A. Hashemi : “Position de Noether Forte et Régularités Stabilisées”, 21 pages (2006)
• 2005
  • A. Hashemi, D. Lazard : “Almost polynomial Complexity for Zero-dimensional Grbner Bases”, ASCM 2005 - 7^th Asian Symposium on Computer Mathematics, Seoul, Korea, Republic of, pp. 16-21 (2005)