Tiled QR factorization algorithms

Abstract : This work revisits existing algorithms for the QR factorization of rectangular matrices composed of p x q tiles, where p is greater or equal than q. Within this framework, we study the critical paths and performance of algorithms such as Sameh-Kuck, Fibonacci, Greedy, and those found within PLASMA. Although neither Fibonacci nor Greedy is optimal, both are shown to be asymptotically optimal for all matrices of size p = q2 f(q), where f is any function such that limit of f is 0. This result applies to all matrices where p and q are proportional, p = lambda x q, with lambda greater than 1, thereby encompassing many important situations in practice (least squares). We provide an extensive set of experiments that show the superiority of the new algorithms for tall and skinny matrices.
Type de document :
Rapport
[Research Report] RR-7601, INRIA. 2011, pp.32
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00585721
Contributeur : Mathias Jacquelin <>
Soumis le : vendredi 22 avril 2011 - 15:21:29
Dernière modification le : samedi 21 avril 2018 - 01:27:35
Document(s) archivé(s) le : jeudi 30 mars 2017 - 09:45:11

Fichier

RR-7601.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00585721, version 3

Citation

Henricus Bouwmeester, Mathias Jacquelin, Julien Langou, Yves Robert. Tiled QR factorization algorithms. [Research Report] RR-7601, INRIA. 2011, pp.32. 〈inria-00585721v3〉

Partager

Métriques

Consultations de la notice

232

Téléchargements de fichiers

155