Search

Cette thèse est consacrée a l'étude de la forme normale d'Hermite et a la conception d'algorithmes parallèles pour son calcul. Nous avons examine deux cas particuliers: le cas entier et le cas polynomial. Ce problème présente de manière intrinsèque une caractéristique du calcul formel: le grossissement des coefficients intermédiaires. Cette particularité en fait un exemple test pour évaluer la parallélisation en calcul formel. La forme normale d'Hermite pour des matrices a coefficients dans un anneau euclidien est présentée. Les concepts et propriétés sur lesquels sont bases les algorithmes sont décrits. Nous introduisons la théorie sur les réseaux et les problèmes qui lui sont attaches, la forme normale d'Hermite étant une forme canonique du réseau engendre par les colonnes de la matrice initiale. Les différents algorithmes séquentiels sont présentes. Nous étudions et comparons leurs complexités. Puis, une approche parallèle est considérée. Après la présentation des résultats théoriques de nc-réductibilité du problème, nous abordons l'étude de la parallélisation sur modèles expérimentaux. Nous définissons différents algorithmes pour les modèles a mémoire partagée et distribuée. Une implantation a été réalisée sur un hypercube fps t40 (32 processeurs). Le calcul de la forme normale d'Hermite d'une matrice 160160 à coefficients entiers a pu etre effectue en 3 heures. Ce travail s'inscrit dans le cadre du projet massivement Parallele Pac (parallel algebraic computing).

Universités : Université scientifique et médicale de Grenoble et Institut National Polytechnique

Université : Université scientifique et médicale de Grenoble

Pac est un système de calcul formel dédié a une machine Mind massivement parallèle. Dans une première partie, l'architecture du système est décrite. Elle est illustrée par une modélisation théorique et pratique de la parallélisation du produit de deux polynômes. Le système Pac est implante sur la machine t40 de Fps (32 processeurs). Dans une deuxième partie, l'arithmétique nodale en précision infinie sur les rationnels est étudiée. Différents algorithmes sont dégagés, notamment pour la multiplication, la division et le pgcd d'entiers de taille quelconque. Une vectorisation de l'arithmétique de base est discutée et expérimentée

Université : Université scientifique et médicale de Grenoble; Elements de théorie de l'approximation polynomiale par morceaux. Approximation d'une intégrale simple avec poids par une combinaison linéaire de valeurs de la fonction. Approximation d'une intégrale simple avec poids par une combinaison linéaire de valeurs de la fonction et de sa dérivée. Application à l'interpolation affine par morceaux. Approximation d'une intégrale double avec poids

Université : Université scientifique et médicale de Grenoble

Université : Faculté des sciences de l'Université de Grenoble