Stating and manipulating periodicity in the polytope model (Applications to program analysis and optimization)

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.This thesis focuses on mathematical objects that are the intersection between a rational parametric polyhedron and a lattice of integer points: Z-polyhedra.These objects are used in compilers, where they model nested for/do loops (this model is known as the "polyhedron model"), in order to analyze their behaviour and to transform them in an optimal or parallel loop nest.The main contribution of this thesis is an enhancement of this model, by integrating the periodic character of extremal integer points of the Z-polyhedron, using "periodic polyhedra".This concept is first used to devise the first algorithm for computing the integer hull of a parametric Z-polyhedron P, i.e., the convex hull of the integer points that belong to P.In the same frame, we study Ehrhart polynomials, which give the number of points with integer coordinates that belong to P.Ehrhart polynomials depend periodically on the parameters of P.Starting from observations about the periodicity of the integer hull of P, we extend a conjecture stated by Ehrhart which gives accurate information on the periodicity of the polynomial's coefficients.Using this, we derive a new condition for which the Ehrhart polynomial of a Z-polyhedron is non-periodic. This allows to give two methods for approximating an Ehrhart polynomial by a non-periodic polynomial.In one of the two cases, we also give a new method for computing this polynomial, whose complexity is polynomial for a fixed dimension.Besides, the set of feasible solutions of a parametric linear integer programming problem is a Z-polyhedron S. The optimal solution is given by an extremal integer point of S, which depends periodically on S's parameters.Our approach considers a problem that encompasses the integer lexicographic maximum problem and the classical integer linear programming problem.We devise a new algorithm for computing the optimal solution of such a problem.STRASBOURG-Sc. et Techniques (674822102) / SudocFONTAINEBLEAU-MINES ParisTech (771862302) / SudocSudocFranceF