Tiled QR factorization algorithms - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2011

Tiled QR factorization algorithms

Résumé

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.
Fichier principal
Vignette du fichier
RR-7601.pdf (609.07 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00585721 , version 1 (13-04-2011)
inria-00585721 , version 2 (15-04-2011)
inria-00585721 , version 3 (22-04-2011)

Identifiants

  • HAL Id : inria-00585721 , version 3

Citer

Henricus Bouwmeester, Mathias Jacquelin, Julien Langou, Yves Robert. Tiled QR factorization algorithms. [Research Report] RR-7601, INRIA. 2011, pp.32. ⟨inria-00585721v3⟩
142 Consultations
418 Téléchargements

Partager

Gmail Facebook X LinkedIn More