2008/06/12 by James Demmel, Laura Grigori, Demmel, James +5
Computer Science · Engineering · #FOS: Mathematics #Interconnection Networks and Systems #Numerical Analysis (math.NA) #Wireless Communication Networks Research #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.0806.2159
openalex publication_date 2008/06/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present parallel and sequential dense QR factorization algorithms that are both optimal (up to polylogarithmic factors) in the amount of communication they perform, and just as stable as Householder QR. Our first algorithm, Tall Skinny QR (TSQR), factors m-by-n matrices in a one-dimensional (1-D) block cyclic row layout, and is optimized for m >> n. Our second algorithm, CAQR (Communication-Avoiding QR), factors general rectangular matrices distributed in a two-dimensional block cyclic layout. It invokes TSQR for each block column factorization.