Abstract FR:

Nous nous interessons a la factorisation qr de grandes matrices creuses carrees et sur-determinees dans un environnement mimd a memoire partagee. Nous supposons que le rang des vecteurs colonnes de ces matrices est maximal. Notre demarche est basee sur la methode multifrontale (duff et reid (1983)) et utilise les transformations de householder. Nous donnons une description detaillee de l'approche multifrontale pour la factorisation qr et de son implementation dans un environnement multiprocesseur. Nous montrons qu'en choisissant de facon adequate la strategie de factorisation de nuds, des gains considerables peuvent etre obtenus, aussi bien du point de vue de la memoire que du parallelisme et du temps de calcul. Un niveau de parallelisme supplementaire est utilise pour equilibrer le manque de parallelisme pres de la racine de l'arbre d'elimination. Par ailleurs, nous decrivons aussi comment modifier l'arbre d'elimination pour ameliorer les performances du code. Nous examinons ensuite les problemes de stabilite et de precision numerique de la factorisation qr en tant que methode de resolution des systemes lineaires et des problemes de moindres carres. Nous etudions l'influence du raffinement iteratif et du pivotage des lignes et montrons qu'il existe des matrices pour lesquelles une solution precise ne peut etre obtenue que si la factorisation qr est effectuee avec un pivotage par lignes et suivie de quelques etapes de raffinement iteratif. Finalement, nous etudions la factorisation qr en tant que methode de resolution des problemes de moindres carres et nous la comparons a trois autres approches classiques: la methode des equations normales, la methode des equations semi-normales, et l'approche par systeme augmente. La methode qr s'avere etre particulierement appropriee pour les problemes tres mal conditionnes. En outre, notre code parallele optimise est efficace sur toutes les classes de problemes que nous avons testees