Implementation of QR factorization of tall and very skinny matrices on current GPUs

Jonas Thies, Melven Röhrig-Zöllner · 2026

Read Implementation of QR factorization of tall and very skinny matrices on current GPUs by Jonas Thies, Melven Röhrig-Zöllner (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-20889.txt.

Introduction

Thies and Röhrig-Zöllner compare GPU methods for QR factorization of tall, very skinny matrices. Such matrices have far more rows than columns, so most work is bound by memory speed. They study Gram matrix methods, such as Cholesky-QR2 and SVQB, against a Householder tree method called TSQR. Two tricks help: skip writing back the Q factor, and use fast local memory. They find TSQR matches the best time to solution, but needs much more low level tuning work.

Catalog record

CREATORJonas Thies, Melven Röhrig-Zöllner
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE28966
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.20889

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Implementation of QR factorization of tall and very skinny matrices on current GPUs Jonas Thies, Melven Röhrig-Zöllner Abstract We consider the problem of computing a QR (or QZ) decomposition of a real, dense, tall and very skinny matrix. That is, the number of columns is tiny compared to the number of rows, rendering most computations completely or partially memory-bandwidth limited. The paper focuses on recent NVIDIA GPGPUs still supporting 64-bit floating-point arithmetic, but the findings carry over to AMD GPUs as well. We discuss two basic algorithms: Methods based on the normal equations (Gram matrix), in particular Cholesky-QR2 and SVQB, and the "tall-skinny QR" (TSQR), based on Householder transformations in a tree-reduction scheme. We propose two primary optimization techniques: Avoiding the write-back of the Q factor (“Q-less QR”), and exploiting fast local memory (shared memory on GPUs). We compare a straight-forward implementation of Gramian-based methods, and a more sophisticated TSQR implementation, in terms of performance achieved, time-to-solution, and implementation complexity. By performance modelling and numerical experiments with our own code and a vendor-optimized library routine, we demonstrate the crucial need for specialized methods and implementations in this memory-bound to transitional (memory/compute-bound) regime, and that TSQR is competitive in terms of time-to-solution, but at the cost of an investment in low-level code optimization. 1 Introduction We consider the problem of computing a QR-decomposition of a real, dense matrix X\in\mathbb{R}^{m\times n} , where m\gg n . Such a matrix is often referred to as “tall and skinny”. There are many use cases for tall-and-skinny QR, e.g., computing an orthogonal basis of a subspace in iterative linear or eigenvalue solvers, as a building block for tensor factorization, for data fitting or compression. Formally, we want to compute Q\in\mathbb{R}^{m\times n} and R\in\mathbb{R}^{n\times n} such that X=QR , Q^{T}Q=I , and R is upper triangular. If X is rank-deficient ( r=\mathrm{rank}(X)<n ), R will have some zero diagonal entries. Specialized algorithms for the tall and skinny case include methods based on the normal equations (Gram matrix): Variants of SVQB [ 30 ] and Cholesky-QR [ 15 ] , and the “tall-and-skinny QR” (TSQR [ 7 ] ), which is based on Householder transformations. SVQB produces the decomposition XB=Q,Q^{T}Q=I , which can be transformed into the QZ-factorization: X=QZ,Z=\Sigma U . Here \Sigma,Q , and U are the singular values and right (left) singular vectors of X , respectively. The entire class of algorithms is referred to as “communication-avoiding” methods as they aim to reduce the data traffic between memory and computing units, and among the nodes of a cluster. For matrices with relatively few columns, this reduces the time-to-solution because the required floating point calculations do not amortize data movement. In this paper, we focus specifically on the case of tall and very skinny matrices, where the number of columns is so small that the memory traffic dominates the computing time. We focus on algorithmic variants for the ‘Q-less QR’, that is, they do not return Q or its generating coefficients at all. If X is sufficiently well-conditioned, Q can be re-constructed at a later stage if needed. The term was introduced by Fan et al. [ 12 ] and is useful, e.g., for large tensor decomposition algorithms such as TT-SVD [ 27 ] . It can also be used to solve least squares problems \min_{x}\|Ax-b\|_{2} with a single pass over the data by calculating the Q-less QR decomposition of the extended matrix \begin{pmatrix}A&b\end{pmatrix} . Our implementations focus on achieving high performance on current NVIDIA GPUs, with the primary optimization technique being manual caching in shared memory. The results should carry over to other types of GPUs (e.g., AMD) that support double precision arithmetic and provide fast local memory per multiprocessor. 2 Related work Numerical results on accuracy and stability of various methods can be found in classical textbooks [ 17 , 19 ] . The operations of standard Householder QR can be combined into level-3 BLAS operations, resulting in the fast LAPACK routine dgeqrf . But unconditional backward stability is only achieved with suitable pivoting [ 6 ] . Unfortunately, pivoting reduces the performance significantly as it usually requires bandwidth-limited level-2 BLAS operations (LAPACK routine dgeqp3 ). This performance penalty increases for newer CPU generations and GPUs due to the widening gap between memory bandwidth and floating-point performance (the von Neumann bottleneck). Therefore, researchers try to overcome the costs of pivoting, e.g., by solving multiple shifted linear systems by unpivoted QR [ 4 ] , or by skipping small columns in the QR calculation [ 29 ] . These approaches seem promising for specific classes of well-behaved problems, but might not be stable in general. In particular, even with pivoting, the maximal error for “truncating” small diagonal entries in the triangular factor of the QR decomposition grows with O(2^{r}) for rank r , see [ 18 , 20 ] . For computing the SVD, one typically employs a preceding unpivoted Householder-QR orthogonalization step for rectangular and tall-skinny matrices, see [ 32 ] . The important case of tall and skinny matrices, where data transfers determine runtime more than anything else, motivated the development of so-called communication-avoiding algorithms. TSQR (tall-skinny QR) and CAQR (communication-avoiding QR, which uses TSQR as a panel factorization for not-so-skinny to square matrices) [ 7 ] allow much faster implementations: TSQR requires logarithmically less data to be transferred and “messages” (number of data transfers) compared to Householder QR. This provides the basis for high-performant QR implementations for today’s cache-based multicore CPUs, highly parallel GPUs [ 1 ] and clusters of those [ 22 , 5 ] . More recent work on implementing CAQR for square matrices on GPUs is presented in [ 23 , 28 ] . Other work related to TSQR includes a variant with approximate Householder reflectors [ 31 ] , a parallel pivoting strategy [ 8 ] , and combining TSQR with an outer block modified Gram-Schmidt iteration, which is unconditionally backward stable [ 2 ] . A communication-avoiding alternative to TSQR are methods based on the Gram matrix, C=X^{T}X . Such approaches have the inherent disadvantage that the condition number of the input matrix X is squared before computing the final factorization. On the other hand, the core computation is a tall-and-skinny GEMM, which is a well-optimized kernel on GPUs [ 11 ] . SVQB [ 30 ] , in fact a tall-and-skinny SVD, was the first publication in the context of avoiding communication, although the underlying principles were known for decades. Recently, Cholesky-QR has received more attention than SVQB, probably because for larger n , the Cholesky factorization is cheaper. For better robustness, the method is applied twice using re-orthogonalization [ 3 ] , a method that we refer to as CholQR2 [ 34 ] . The authors of [ 30 ] also consider re-orthogonalization in the context of the “two-phase problem” ( QR=(I-YY^{T})X ) for orthogonalizing X with respect to some already orthogonal matrix Y . Even if CholQR2 theoretically has twice the cost of TSQR, its implementations can be more efficient, as illustrated in [ 15 ] for a multicore CPU. In [ 35 ] , the Gramian is accumulated in higher precision to alleviate the restriction on the condition number, with similar performance as

Read the complete text