Project Description
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.
Keywords: QR factorization, critical path, greedy algorithms, tall and skinny.
The source code of the simulation framework is available as well as various matlab programs used in the proofs.
Documentation
Coming soon.Source Code
|
Download Matlab codes |
|
|
Download simulation codes |
Related Papers
|
Henricus Bouwmeester, Mathias Jacquelin, Julien Langou and Yves Robert.
Tiled QR factorization algorithms. Research report, RR INRIA 7601, LIP, ENS Lyon, 2011.
[Bibtex]
%% inria-00585721, version 2
%% http://hal.inria.fr/inria-00585721/en/
@techreport{BOUWMEESTER:2011:INRIA-00585721:2,
HAL_ID = {inria-00585721},
URL = {http://hal.inria.fr/inria-00585721/en/},
title = { {T}iled {QR} factorization algorithms},
author = {{B}ouwmeester, {H}enricus and {J}acquelin, {M}athias and {L}angou, {J}ulien and {R}obert, {Y}ves},
keywords = {{QR} factorization; critical path; greedy algorithms; tall matrix},
language = {{A}nglais},
affiliation = {{D}epartment of {M}athematical and {S}tatistical {S}ciences - {U}niversity of {C}olorado {D}enver - {GRAAL} - {INRIA} {R}h{\^o}ne-{A}lpes / {LIP} {L}aboratoire de l'{I}nformatique du {P}arall{\'e}lisme - {CNRS} : {UMR}5668 - {INRIA} - {\'E}cole {N}ormale {S}up{\'e}rieure de {L}yon - {U}niversit{\'e} {C}laude {B}ernard - {L}yon {I} - {L}aboratoire d'informatique du {P}arall{\'e}lisme - {L}aboratoire de l'{I}nformatique du {P}arall{\'e}lisme - {LIP} - {U}niversit{\'e} de {L}yon - {CNRS} : {UMR}5668 - {INRIA} - {\'E}cole {N}ormale {S}up{\'e}rieure de {L}yon - {U}niversit{\'e} {C}laude {B}ernard - {L}yon {I} },
type = {Research Report},
institution = {INRIA},
number = {{RR}-7601},
month = {04},
year = {2011},
URL = {http://hal.inria.fr/inria-00585721/PDF/RR-7601.pdf},
}
|