Tiled QR factorization algorithms

2011/04/22 by Henricus Bouwmeester, Mathias Jacquelin, Bouwmeester, Henricus +5 · 2 citations
Computer Science · Engineering · #Cellular Automata and Applications #Distributed #FOS: Computer and information sciences #Interconnection Networks and Systems #Parallel #and Cluster Computing (cs.DC) #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1104.4475

openalex publication_date 2011/04/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This work revisits existing algorithms for the QR factorization of rectangular matrices composed of p-by-q tiles, where p >= q. Within this framework, we study the critical paths and performance of algorithms such as Sameh and Kuck, Modi and Clarke, Greedy, and those found within PLASMA. Although neither Modi and Clarke nor Greedy is optimal, both are shown to be asymptotically optimal for all matrices of size p = q² f(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.

Cited by

• Bidiagonalization with Parallel Tiled Algorithms
• Tiled Algorithms for Matrix Computations on Multicore Architectures

Related

• Implementing Communication-Optimal Parallel and Sequential QR Factorizations
• Communication-optimal parallel and sequential QR and LU factorizations: theory and practice
• A block Cholesky-LU-based QR factorization for rectangular matrices
• Blocked rank-revealing QR factorizations: How randomized sampling can be used to avoid single-vector pivoting
• QR factorization of ill-conditioned tall-and-skinny matrices on distributed-memory systems