Normal view MARC view ISBD view

Stating and manipulating periodicity in the polytope model [Texte imprimé] : Applications to program analysis and optimization / Benoît Meister ; [sous la direction de ]Philippe Clauss

Auteur principal : Meister, Benoît, 1977-...., AuteurAuteur secondaire : : Clauss, Philippe, Directeur de thèseAuteur secondaire collectivité : Université Louis Pasteur, Strasbourg, Organisme de soutenanceLangue :de résumé, Français ; de résumé, Anglais.Publication : [S.l.] : [s.n.], 2004Description : 1 vol. (136 p.) : ill. ; 30 cmRé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.; 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..Bibliographie: Bibliogr. p.125-133.Thèse : .Sujet - Nom d'actualité : Programmation en nombres entiers -- Thèses et écrits académiques ;Compilation (informatique) -- Thèses et écrits académiques ;Programmation linéaire -- Thèses et écrits académiques Sujet : POLYEDRE
Current location Call number Status Date due Barcode
Centre de recherche en informatique
2004 MEI Sur demande CRI05693D

Publication autorisée par le jury

Bibliogr. p.125-133

Thèse doctorat Sciences de l'Informatique de l'Image et de la Télédétection Strasbourg 1 2004

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.

Powered by Koha