Logo de l'E.N.T. Alsace
Thèses électroniques Service Commun de la documentation
Logo de l'Université de Strasbourg
Thèses et Mémoire de l'Université de Strasbourg

Méthodes de dénombrement de points entiers de polyèdres et applications à l'optimisation de programmes

SEGHIR, Rachid (2006) Méthodes de dénombrement de points entiers de polyèdres et applications à l'optimisation de programmes. Thèses de doctorat, Université Louis Pasteur.

Plein texte disponible en tant que :

PDF - Un observateur de PDF est nécessaire, comme par exemple GSview, Xpdf or Adobe Acrobat Reader
1604 Kb

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 d'EPrint:Thèse de doctorat
Mots-clés libres:modèle polyédrique, nids de boucles, dénombrement de points entiers de Z-polytopes paramétrés, formules de Presburger, quasi-polynômes d’Ehrhart, optimisation de la mémoire
Sujets:UNERA Classification UNERA > ACT Domaine d'activité UNERA > ACT-10 Informatique
CL Classification > DDC Dewey Decimal Classification > 500 Sciences de la nature et mathématiques > 510 Mathématiques > 518 Analyse numérique > 518.1 Algorithmes
Classification Thèses Unistra > Sciences, technologies > Sciences de la nature et mathématiques > 510 Mathématiques > 518 Analyse numérique > 518.1 Algorithmes

UNERA Classification UNERA > DISC Discipline UNERA > DISC-19 Mathématiques et informatique
Code ID:1268
Déposé le :30 Mars 2007

Administrateurs de l'archive uniquement : éditer cet enregistrement