Nous étudions la mise en œuvre d'algorithmes parallèles sur des ordinateurs a mémoire distribuée. A travers plusieurs exemples issus de la programmation dynamique, de l'algèbre linéaire et du traitement d'images, nous exposons les problèmes lies a la programmation de ces machines: topologie d'interconnexion, stratégie d'allocation des données, équilibrage des calculs et minimisation du volume de communication inter-processeurs. Les exemples étudiés sont pour la plupart des algorithmes séquentiels couteux en temps de calcul et en place mémoire, et pour lesquels il est très intéressant d'avoir une parallélisation efficace. Nous avons choisi des problèmes dont l'implémentation sur des machines a mémoire distribuée n'est pas aisée, essentiellement a cause de la grande interdépendance entre les différentes taches composant les algorithmes

Différentes analyses de la méthode de Givens en parallèle sur une architecture à mémoire partagée sont examinées. Présentation de résultats de complexité et d'algorithmes asymptotiquement optimaux. Dans une deuxième partie, consacrée aux architectures à mémoire distribuée, les couts de communication sont pris en compte. Une analyse macroscopique montre l'influence de l'architecture sur la complexité des décompositions de Givens et de Householder s'exécutant sur différents réseaux de processeurs fonctionnant par échange de messages

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Dans cette thèse nous développons de nouveaux algorithmes de calcul numérique pour les matrices polynomiales. Nous abordons le problème du calcul de la structure propre (rang, espace nul, structures finie et infinie) d'une matrice polynomiale et nous appliquons les résultats obtenus au calcul de la factorisation J-spectrale des matrices polynomiales. Nous présentons également quelques applications de ces algorithmes en théorie de la commande. Tous les nouveaux algorithmes décrits ici sont basés sur le calcul d'espaces nuls constants de matrices bloc Toeplitz associées à la matrice polynomiale analysée. Pour calculer ces espaces nuls nous utilisons des méthodes standard de l'algèbre linéaire numérique comme la décomposition en valeurs singulières ou la factorisation QR. Nous étudions aussi l'application de méthodes rapides comme la méthode généralisée de Schur pour les matrices structurées. Nous analysons les algorithmes présentés au niveau complexité algorithmique et stabilité numérique, et effectuons des comparaisons avec d'autres algorithmes existants dans la littérature.

Les méthodes formelles ont atteint un degré de maturité conduisant à la conception de systèmes de preuves généralistes, permettant à la fois de vérifier la correction de systèmes logiciels complexes ou de formaliser des mathématiques avancées. Mais souvent, l'accent est mis davantage sur la facilité du raisonnement sur les programmes plutôt que sur leur exécution efficace. L'antagonisme entre ces deux aspects est particulièrement sensible pour les algorithmes de calcul formel, dont la correction repose habituellement sur des concepts mathématiques élaborés, mais dont l'efficacité pratique est une préoccupation importante. Cette thèse développe des approches à l'étude formelle et l'exécution efficace de programmes en théorie des types, et plus précisément dans l'assistant à la preuve \coq{}. Dans un premier temps, nous présentons un environnement d'exécution permettant de compiler en code natif de tels programmes tout en conservant la généralité et l'expressivité du formalisme. Puis, nous nous intéressons aux représentations de données et plus particulièrement au lien formellement vérifié et automatisé entre représentations adaptées aux preuves ou au calcul. Ensuite, nous mettons à profit ces techniques pour l'étude d'algorithmes en algèbre linéaire, comme le produit matriciel de Strassen, le procédé d'élimination de Gauss ou la mise en forme canonique de matrices, dont notamment la forme de Smith pour les matrices sur un anneau euclidien. Enfin, nous ouvrons le champ des applications à la formalisation et au calcul certifié des groupes d'homologie de complexes simpliciaux issus d'images numériques.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

Étant donnée une fonction lisse ˜ f définie sur un voisinage de la sphère euclidienne de dimension n dans la boule, peut-on l’étendre en une fonction définie sur la boule bordée par la sphère, de manière à ce que l’extension n’ait aucun point critique ? Cette thèse propose d’étudier cette question, en supposant que la restriction de ˜ f à la sphère, notée f, est Morse. Ce problème a été introduit pour la première fois par Blank et Laudenbach en1970, et a aussi été posé par Arnol’d en 1981. Nous donnons une condition nécessaire d’extension sans points critiques qui s’appuie sur le complexe de Morse de la fonction f, et de la répartition des points critiques de f en deux ensembles : ceux dont la dérivée normale est négative et ceux dont la dérivée normale est positive. Cette condition nécessaire permet alors de donner un cadre algébrique à ce problème venant de la topologie différentielle et s’appuie principalement sur lesgrandes théories de la deuxième moitié du XXème siècle, à savoir celle des cobordismes de Thom,Smale, Milnor etc. Elle permet notamment de donner des conditions nécessaires et suffisantesdans certains cas plus restrictifs, et donne lieu à une condition nécessaire plus faible qui présentel’intérêt d’être calculable.Le point de départ des résultats est celui de Barannikov, qui le premier a traduit le problèmed’extension de fonction avec des conditions de dérivées normales en un problème de chemin defonctions générique qui ne présente pas de singularité globale. / Given a smooth function ˜ f defined on a neighborhood of the euclidian sphere of dimension n in the ball, is it possible to extend it to a function defined on the ball which has no critical points ? This thesis studies this question, assuming the f, the restriction of ˜ f to the sphere, is Morse.This problem was first introduced by Blank and Laudenbach in 1970. We give a necessary condition of extension without critical points that is based on Morsehomology and the repartition of the critical set of f into two sets : the set of points whosenormal derivative to the sphere interior to the ball is negative and the set of points whosenormal derivative is positive. This necessary condition is of algebraic nature and uses great theories of the second half of the XXth century, namely cobordism theory of Thom, Smale,Milnor etc. It also leads to a sufficient condition in some interesting cases, and to a weaker necessary condition for a general function ˜ f which is easily computable.The point-of-view is the one of Barannikov, who was the first to tackle this problem bymeans of considerations about path of functions

Cette thèse présente une méthode de résolution parallèle de systèmes linéaires creux qui combine efficacement les techniques de résolutions directes et itératives en utilisant une approche de type complément de Schur. Nous construisons une décomposition de domaine. L'intérieur des sous-domaines est éliminé de manière directe pour se ramener à un problème sur l'interface. Ce problème est résolu grâce à une méthode itérative préconditionnée par une factorisation incomplète. Un réordonnancement de l'interface permet la construction d'un préconditionneur global du complément de Schur. Des algorithmes minimisant le pic mémoire de la construction du préconditionneur sont proposés. Nous exploitons un schéma d'équilibrage de charge utilisant une répartition de multiples sous-domaines sur les processeurs. Les méthodes sont implémentées dans le solveur HIPS et des résultats expérimentaux parallèles sont présentés sur de grands cas tests industriels.

L'objectif de cette thèse est d'examiner comment les technologies orientées-objet peuvent apporter aux applications scientifiques tout ce qu'elles ont apporté dans la programmation des machines séquentielles: une meilleure réutilisabilité et pérennité des codes, des démarches méthodologiques de conception et de réalisation claires... La contrainte du calcul scientifique parallèle de ne pas sacrifier les performances devant être respectée.<br /><br />Après une revue des moyens de programmation parallèle et des<br />concepts objets, la conception et la réalisation d'une bibliothèque parallèle d'algèbre linéaire orientée-objet sont présentées. Nous étudions deux moyens de programmation parallèle, le premier, C++//, est un LAO parallèle à objets actifs dérivé de C++, le second est l'utilisation de MPI au travers d'une surcouche objet minimale.<br />Ces deux approches objets posent des problèmes soit de performances soit de réutilisabilité séquentielle/parallèle qui sont présentés et résolus.<br /><br />Nous proposons notamment un mécanisme simple de partage en lecture pour les modèles à objets actifs, en montrant son utilité en terme de performances de nos applications. Suite à la seconde approche nous définissons les notions de formes de matrices et de matrices avec forme qui permettent d'atteindre nos objectifs de réutilisabilité séquentielle/parallèle.<br /><br />Au final, la conception et la réalisation permettent d'instancier, à partir du même code [séquentiel] d'algèbre linéaire, une version séquentielle et parallèle offrant des performances satisfaisantes.