Méthodes de dénombrement de points entiers de polyèdres et applications à l'optimisation de programmes
Langue Français
Accéder à la thèseDroits d'accès : non autorisé

Ce document est protégé en vertu du Code de la Propriété Intellectuelle.

 
Auteur : Seghir, Rachid
Date de soutenance : 07-12-2006

Directeur(s) de thèse : Mongenet, Catherine - Loechner, Vincent

Établissement de soutenance : Université Louis Pasteur (Strasbourg)
École doctorale : École doctorale Mathématiques, sciences de l'information et de l'ingénieur (Strasbourg ; 1997-....)
 
Discipline : Informatique
Classification : Mathématiques

Mots-clés libres : Ehrhart, Polynômes d'
Mots-clés :
  • Ehrhart, Polynômes d' - Thèses et écrits académiques
  • Optimisation mathématique - Thèses et écrits académiques
Résumé : Le modèle polyédrique est un formalisme utilisé en optimisation automatique de programmes. Il permet notamment de représenter les itérations et les références à des tableaux, dans des nids de boucles affines, par des points à coordonnées entières de polyèdres bornés, ou Z-polytopes (paramétrés). Dans cette thèse, trois nouveaux algorithmes de dénombrement ont été développés : des points entiers dans un Z-polytope paramétré, dans une union non disjointe de Z-polytopes paramétrés et dans leurs images par des fonctions affines. Le résultat de ces dénombrements est donné par un ou plusieurs polynômes multivariable à coefficients périodiques. Ces polynômes, connus sous le nom de quasi-polynômes d'Ehrhart, sont définis sur des sous-ensembles de valeurs des paramètres, dits domaines de validité. De nombreuses méthodes d'analyse et d'optimisation de nids de boucles affines font appel à ces algorithmes. Nous les avons en particulier appliqués à la linéarisation de tableaux, dont l'objectif est la compression mémoire et l'amélioration de la localité spatiale. Outre l'optimisation de programmes, les algorithmes proposés ont des applications dans bien d'autres domaines, tels que les mathématiques et l'économie.
 
Type de contenu : Text
 
Entrepôt d'origine : Ressource locale
Identifiant : ecrin-ori-292745
Type de ressource : Thèse