Parallélisation de quelques algorithmes d'algèbre linéaire à l'aide du formalisme du graphe des taches

L'objet de cette thèse est l'étude de la parallélisation d'algorithmes du calcul scientifique et<br />leur implémentation sur des ordinateurs parallèles à mémoire partagée et sur des réseaux systoliques.<br /> Un accent particulier est mis sur l'obtention de résultats de complexité. La thèse est organisée autour<br /> d'articles et textes de conférences qui sont analysés et discutés dans une première partie de façon à <br />permettre de replacer les problèmes traités dans leur contexte.<br />Dans le premier chapitre, nous présentons les principaux résultats théoriques concernant <br />l'étude de complexité des algorithmes parallèles, ainsi qu'une description critique de l'architecture <br />de référence, qui est une machine de type MIMD à mémoire partagée. Le chapitre suivant est dédie" à <br />l'ensemble des résultats de complexité concernant les algorithmes de diagonalisation et <br />l'élimination de Gauss, il a pour but d'illustrer la méthodologie. Il existe en tout dix écritures possibles de la méthode de Gauss, qui conduisent principalement à deux grandes classes de graphes de précédente, conceptuellement différents : les graphes de type "glouton" et ceux du type "2 pas".<br />Ces types de graphes se rencontrent d'une manière plus générale dans d'autres problèmes <br />d'algèbre linéaire et même dans certaines méthodes non numériques de la théorie des graphes. <br />Nous développons les résultats de complexité concernant ces deux types de graphes sur les exemples<br /> les plus courant (versions kji et kij de Gauss en parallèle), puis nous montrons comment adapter<br /> l'étude en prenant en compte t'es temps de communication entre tes processeurs, ce qui rend le modèle<br /> théorique plus réaliste.<br />Le chapitre 6 est consacré aux architectures systoliques. Le problème du chemin algébrique permet <br />d'unifier plusieurs problèmes informatiques. Nous présentons un réseau résolvant ce problème en Sn-2 <br />pas sur un réseau de taille n(n+l ). De plus, quelques modifications permettent de calculer des projections<br /> en filtrage adaptatif en vu d'obtenir une solution en temps réel pour le traitement numérique des signaux.<br />Avant de conclure, nous présentons des résultats complémentaires de parallélisation effective sur d'autres<br /> types d'architectures : l'étude de l'algorithme du gradient conjugué sur des super calculateurs <br />(CRAY-XMP et IBM 3090-VF).

Présentation de différentes méthodes de calcul du nombre de racines des polynômes dans le disque-unité, utilisant les transformations de Schur, de Sturn et de Schelin. Mise en évidence du rôle des polynômes à facteurs autoréciproques. Etude de la complexité des algorithmes et développement d'une méthode générale dépendant d'un paramètre. Applications à la commande automatique et à la biochimie

On approfondit la notion de bases discrètes présentée dans un rapport précédent, en montrant en particulier son extension possible à d'autres bases de numérotation que la base 2. On élabore des algorithmes de calcul des fonctions mathématiques usuelles dans n'importe quelle base de numérotation. On établit un résultat de complexité

Les algorithmes de résolution polynomiale sont impliqués dans des outils sophistiqués de calcul en géométrie algébrique aussi bien quen ingénierie. Les plus populaires dentre eux reposent sur des bases de Gröbner, des matrices de Macaulay ou des décompositions triangulaires. Dans tous ces algorithmes, les polynômes sont développés dans une base des monômes et les calculs utilisent essentiellement des routines dalgèbre linéaire. L'inconvénient majeur de ces méthodes est lexplosion exponentielle du nombre de monômes apparaissant dans des polynômes éliminants. De manière alternative, lalgorithme Kronecker manie des polynômes codés comme la fonction qui calcule ses valeurs en tout point.<br />Dans cette thèse, nous donnons une présentation concise de ce dernier algorithme, ainsi qu'une preuve autonome de son bon fonctionnement. Toutes nos démonstrations sont intimement liées aux algorithmes, et ont pour conséquence des résultats classiques en géométrie algébrique, comme un théorème de Bézout. Au delà de leur intérêt pédagogique, ces preuves permettent de lever certaines hypothèses de régularité, et donc d'étendre l'algorithme au calcul des multiplicités sans coût supplémentaire.<br />Ensuite, nous présentons un algorithme de décomposition primaire pour les idéaux de polynômes de dimension nulle. Nous en donnerons également une étude de complexité précise, complexité qui est polynomiale en le nombre de variables, en le coût dévaluation du système, et en un nombre de Bézout.

.

Valiant définit des analogues algébriques des classes P et NP. Nous caractérisons les classes VP et VQP, d'où une preuve simplifiée de VNP = VNPe et de la VQP-complétude du déterminant, et la preuve d'une conjecture de Bürgisser. Les classes VPo et VNPo, définies sans constantes arbitraires, donnent facilement un lien entre la complexité d'un polynôme et celle de sa fonction coefficient: VNPo est stable par passage à la fonction coefficient et réciproquement; supposer ce résultat pour VPo est équivalent à VPo = VNPo. Pour traiter le cas du degré non borné, il faut un calcul rapide des coefficients binomiaux, faisable en caractéristique positive et peu probable en caractéristique 0. Nous étudions enfin un problème lié: l'effet de la dérivation sur la complexité. Nous retrouvons le résultat de Kaltofen (le nombre de variables fait exploser la taille plus que l'ordre de dérivation) et donnons un calcul simultané des dérivées partielles.

Après un état de l'art sur l'ordonnancement en général et l'ordonnancement temps réel en particulier permetttant de préciser les notions utilisées par la suite et après avoir motivé l'intérêt d'une nouvelle contrainte temps réel de latence, nous proposons un modèle qui formalise les systèmes temps réel avec contraintes de précédences, de périodicités et de latences. Dans ce modèle, les précédences sont définies par un graphe orienté acyclique infiniment répété. Pour le cas monoprocesseur, on étudie trois problèmes d'ordonnancement : celui des systèmes avec contraintes de précédences et de périodicités, celui des systèmes avec contraintes de précédences et de latences et enfin celui des systèmes avec contraintes de précédences, de périodicités et de latences. Pour chaque problème on étudie la cohérence entre les différentes contraintes, on donne des conditions d'ordonnançabilité et on propose un algorithme prouvé optimal dans le sens où s'il y a un ordonnancement, l'algorithme le trouvera. On passe ensuite au cas multiprocesseur où l'architecture est définie par un graphe non-orienté. On étudie trois problèmes d'implantation (distribution et ordonnancement) dans les mêmes cas qu'en monoprocesseur en tenant compte des temps de communications. On prouve que ces trois problèmes sont NP-difficiles et on propose, donc, des heuristiques. Les performances de chaque heuristique sont comparées à celles d'algorithme exacte de type "branch and bound", en utilisant des simulations numériques.

Nous étudions les structures logiques finies ou infinies à travers les énoncés de profondeur de quantification donnée qui sont vrais dans ces structures. <br /><br />Cette étude porte principalement sur un nouvel outil logique appelé $k$-destinées de Nézondet. Une $k$-destinée d'une structure consiste en une présentation arborescente des types de $k$-isomorphisme de Fraïssé de la structure. Nous analysons ce nouvel outil, en particulier nous montrons que les destinées s'intègrent parfaitement au contexte des $k$-isomorphismes de Fraïssé et des jeux d'Ehrenfeucht. <br /><br />Nous détaillons un algorithme de décision utilisant les destinées. Nous comparons en détail les structures dont on peut construire récursivement les destinées et les structures $H$-bornées. Enfin, nous donnons quelques résultats intermédiaires du problème NE ?= CoNE et de sa version logique, la conjecture du Spectre.

Dans une première partie, nous étudions les bibliothèques académiques dont les principes fondateurs sont aujourd'hui interrogés par la société de l'information. Le gestionnaire d'une bibliothèque recherche la voie d'avancement la meilleure possible pour l'unité qu'il conduit. Les outils d'évaluation et de management utilisés en bibliothèque suscitente des insatisfactions car ils sont parfois inaptes à rendre compte de la nécessité d'une vision holistique de la bibliothèque. L'appproche constructiviste du management semble alors une alternative plausible pour aider les gestionnaires de biblithèques académiques à construire une vision stratégique de ces organisations. Nous bâtissons alors, dans une deuxième partie, un projet de modélisation basé sur la modélisation des systèmes complexes préconisée par Jean-Louis Le Moigne et sur la méthodologie des systèmes souples de Peter Checkland. Notre terrain de recherche est constitué de bibliothèques académiques françaises dans lesquelles nous effectuons interviews et observations participantes. Nous construisons un diagnostic en trois phases. La première phase permt au gestionnaire de visualiser l'offre de service dont nous montrons qu'elle est en évolution selon les trois axes des technologies, des moyens et des savoir-faire mise en oeuvre. La deuxième phase interroge le système informationnel de la bibliothèque, par une étude des environnements dans lequel l'organisation évolue et des flux qui la traversent. La troisième phase étudie le système décisionnel, s'intéressant à son organisation, à la circulation de l'information interne et aux processus de décision mis en oeuvre. Ce diagnostic en construction permanente est entendu dans la continuité du management de la bibliothèque et non comme une première étape d'une stratégie. Il est mis en oeuvre dans cinq bibliothèques. Les résultats montrent la richesse de l'apport de la modélisation, qui permet de proposer des modèles évolutifs, transposables et permettant l'apprentissage.