Ce mémoire étudie trois types de problèmes à cheval entre algorithmes discrets, optimisation combinatoire et méthodes numériques. Les trois types de problèmes sont ceux du partitionnement, du couplage et de l'ordonnancement.
Des problèmes de partitionnement se posent lors de la décomposition de tâches pour le calcul parallèle. Nous discutons de la partition acyclique des graphes acycliques dirigés et des hypergraphes. Alors que nos contributions au premier problème concernent des outils combinatoires, ceux pour le second problème concernent l’utilisation d’outils pour une décomposition efficace de tenseurs dans les systèmes à mémoire distribuée.
Des problèmes du couplage surviennent dans les cas où les agents se font concurrence pour un accès exclusif aux ressources. Nous présentons des algorithmes d’approximation pour les couplage dans les graphes, et des heuristiques efficaces pour en trouver dans des hypergraphes. Nous étudions également le problème de la décomposition de Birkhoff - von Neumann avec un petit nombre de matrices de permutation, et nous donnons des résultats de complexité sur ce problème.
Des problèmes d'ordonnancement surviennent quand on veut permuter matrices et tenseurs creux dans des formes souhaitables. Nous proposons des heuristiques pour permuter des matrices creuses dans une forme spéciale dans le but de réduire la hauteur de l’arbre d’élimination résultant. Nous proposons également des heuristiques pour permuter des éléments non nuls d'un tenseur creux autour de sa diagonale afin d’améliorer les performances de certaines opérations de tenseurs.
Gratuit
Disciplines