Expression et manipulation de la périodicité dans le modèle polyédrique,Applications à l'analyse et à l'optimisation de programmes
Langue Français
Ce document est protégé en vertu du Code de la Propriété Intellectuelle.
Auteur : Meister, Benoît
Date de soutenance : 01-01-2004
Directeur(s) de thèse : Clauss, Philippe
É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 : Mathématiques et Informatique
Classification : Informatique
Mots-clés libres : Polynôme d'Ehrhart , Modèle Polyédrique
Mots-clés :
- Compilation (informatique)
- Thèses et écrits académiques
- Programmation linéaire
- Thèses et écrits académiques
- Programmation en nombres entiers
- Thèses et écrits académiques
Résumé : Cette thèse est centrée sur les objets mathématiques formés de l'intersection entre un polyèdre rationnel dépendant de paramètres et un réseau régulier de points à coordonnées entières: les Z-polyèdres paramétriques.Ces objets sont utilisés en compilation où ils permettent de modéliser les nids de boucles for/do (on parle du "modèle polyédrique"), afin d'analyser leur comportement, et de les transformer pour les optimiser ou les paralléliser.Cette thèse contribue à l'amélioration de ce modèle en introduisant le concept de polyèdre périodique, qui traduit le caractère périodique des coordonnées de points entiers extrémaux du Z-polyèdre. Ce concept est d'abord utilisé pour définir le premier algorithme de calcul de la coque entière d'un Z-polyèdre paramétrique P, c'est à dire l'enveloppe convexe des points contenus dans P.Dans le même cadre, nous nous intéressons aux polynômes d'Ehrhart, qui donnent le nombre de points à coordonnées entières contenus dans P et qui possèdent un caractère périodique.Certaines observations fines sur le caractère périodique de la coque entière de P nous permettent d'étendre une conjecture prononcée par Ehrhart et qui donne des informations précises sur la périodicité des coefficients.Nous en dérivons une condition pour laquelle le polynôme d'Ehrhart d'un Z-polyèdre est non-périodique, et en déduisons deux méthodes d'approximation d'un polynôme d'Ehrhart par un polynôme non-périodique.Dans l'un des cas, nous donnons également un algorithme de calcul de ce polynôme dont la complexité est polynomiale en dimension fixée.D'autre part, l'ensemble des solutions faisables d'un problème de programmation linéaire paramétrique en nombre entiers est un Z-polyèdre S. La solution optimale est donnée par un un point extrémal de S, qui dépend périodiquement des paramètres.Notre approche est de considérer un problème général, englobant le problème du maximum lexicographique et la forme classique de la programmation linéaire en nombre entiers. Nous donnons un nouvel algorithme de calcul d'une solution optimale de ce problème.
Entrepôt d'origine : 
Identifiant : ecrin-ori-287493
Type de ressource : Thèse
