Abstract | ||
---|---|---|
This work revisits existing algorithms for the QR factorization of rectangular matrices composed of p × q tiles, where p ≥ 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 = q2f(q), where f is any function such that lim+∞ f = 0. This novel and important complexity result applies to all matrices where p and q are proportional, p = λq, with λ ≥ 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 matrices. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1145/2063384.2063393 | Clinical Orthopaedics and Related Research |
Keywords | DocType | Volume |
rectangular matrix,extensive set,size p,qr factorization,important complexity result,asymptotically optimal,critical path,important situation,new algorithm,tiled qr factorization algorithm,q tile,kernel,parallel processing,parallel,plasmas,algorithm design and analysis,greedy algorithms,matrix decomposition | Conference | abs/1104.4475 |
Citations | PageRank | References |
14 | 0.76 | 14 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Henricus Bouwmeester | 1 | 32 | 3.02 |
Mathias Jacquelin | 2 | 62 | 8.96 |
Julien Langou | 3 | 1028 | 71.98 |
Yves Robert | 4 | 842 | 70.03 |