Etude de la complexité de la décomposition orthogonale d'une matrice sur plusieurs modèles d'architectures parallèles

Abstract

Nous étudions de la décomposition orthogonale d’une matrice sur plusieurs modèles d’architecture multiprocesseurs. Dans la première partie, différentes analyses de la méthode de Givens en parallèle sur une architecture à mémoire partagée sont examinées. Nous présentons des résultats de complexité et nous construirons des algorithmes asymptotiquement optimaux. L’approche que nous adoptons dans la deuxième partie, consacrée aux architectures à mémoire distribuée, prend en compte les coûts de communication. Nous commençons par une analyse macroscopique pour montrer 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 des messages. Ensuite nous analysons et comparons plusieurs implémentations parallèles et présentons des résultats expérimentaux sur une machine hypercube, T20 de FPS.