betaFeedback

WorksMathematics

Reduced and Mixed-Precision Block Householder QR Factorization

Abstract

Recent advances in hardware architecture have highlighted the importance of reduced-precision arithmetic for improving performance and reducing energy consumption in large-scale scientific applications. However, uniformly low-precision methods can suffer from numerical instability, especially in fundamental linear algebra routines. Mixed-precision strategies therefore play an important role in balancing efficiency, stability, and accuracy. In this paper, we focus on the block Householder QR decomposition using the WY representation and study its behavior in reduced- and mixed-precision settings. Starting from a uniform half-precision variant, we show that performing norm computations with fp32 accumulation is necessary to avoid overflow and underflow on large matrices. Based on this observation, we introduce mpWYQR, a mixed-precision algorithm that increases the precision of only selected computations and avoids most of the precision conversions required by the existing mixed-precision blocked QR algorithm (mpBQR3) introduced in [L. M. Yang, A. Fox, and G. Sanders, SIAM J. Sci. Comp., 43.3 (2021), pp. A1723–A1753]. Our analysis shows that mpWYQR accuracy is governed by low-precision unit roundoff, and that its error bound exceeds that of mpBQR3 by only a constant factor, with identical heuristic bounds. In experiments across a range of matrix sizes and condition numbers, we show that mpWYQR retains mpBQR3 accuracy while running up to 18×18\times faster and using less memory. We also discuss the performance cost of computing inner products in higher precision, and the library support needed for an efficient GPU implementation.

Novelty statement: A mixed-precision Householder QR algorithm based on the WY representation, mpWYQR, is introduced, in which the precision of only selected computations is raised, and fewer precision conversions are required than in existing mixed-precision blocked QR algorithms. Its error bound differs from that of mpBQR3 only by a constant factor, and it achieves comparable accuracy experimentally with speedups of up to 18×. These results are important for using low-precision hardware in QR-based solvers in high-performance computing.

Introduction

The QR decomposition is a fundamental and versatile tool in numerical linear algebra, with various applications including least-squares problems, eigenvalue computations, and low-rank matrix approximations [11]. It is a key computational step in many scientific and engineering applications, where both accuracy and performance are critical. Among the various algorithms for computing the QR factorization, Householder QR [16] is widely used owing to its normwise backward stability, a desirable property in the presence of rounding errors. However, classical Householder QR can suffer from communication and synchronization bottlenecks on modern parallel architectures: the repeated global synchronizations entailed in the sequential construction of Householder reflectors limit its scalability, and the computational cost is cubic in the matrix dimension. As problem sizes continue to grow in modern scientific applications, performing QR factorization entirely in high precision becomes computationally expensive, motivating more efficient alternatives.

To address these limitations, several improvements have been proposed over the years. Bischof and Van Loan introduced the WY representation of Householder transformations, enabling the use of BLAS3-level operations and improving data locality [2]. Rotella and Zambettakis extended this idea through block Householder transformations, enabling more efficient parallel QR factorization [24]. Demmel et al. further developed communication-avoiding, parallel, and stable QR algorithms based on Householder reflections, reducing the communication overhead while preserving numerical stability [7]. More recently, Haidar et al. demonstrated the effectiveness of batched and GPU-resident Householder QR factorization, enabling high-performance computing on modern architectures [12].

With the emergence of low-precision arithmetic, particularly half-precision (binary16, referred to as fp16)[17], on modern hardware, both computational time and memory bandwidth requirements can be significantly reduced. Using low precision uniformly throughout the QR factorization nevertheless introduces significant numerical challenges. In particular, computing Householder reflectors in fp16 is prone to overflow and underflow when evaluating the 2-norm of a vector, due to the limited dynamic range of fp16. Even when the range issue is avoided, the loss of orthogonality (LOO) in the computed Q-factor is in general bounded by the unit roundoff of fp16, which is about 4.8×10−44.8 \times10^{-4}, and achieving even this level of orthogonality reliably requires the use of higher precision in critical parts of the factorization. While this accuracy is insufficient for many numerical linear algebra applications, some application settings may accept a Q-factor with fp16-level LOO. For instance, in certain machine learning applications such as Gaussian process training, half-precision iterative solvers that maintain orthogonality only at the level of the working precision have been shown to perform well in practice [22]. Similarly, in randomized numerical linear algebra, where QR is applied to sketched matrices or used within randomized range-finding algorithms [13], the inherent randomness already introduces errors of a comparable or larger magnitude, making fp16 arithmetic a reasonable choice. Furthermore, in signal processing applications such as adaptive beamforming [23] and wireless multiple-input multiple-output precoding [5], where the required application-level accuracy may tolerate reduced-precision arithmetic, a lower-precision QR factorization may be sufficient in practice.

Higham provided a rigorous rounding-error analysis of Householder QR in uniform precision, showing that, for A∈Rm×nA \in\mathbb{R}^{m \times n}, the worst-case backward error is of order mnmn times the working-precision unit roundoff [14]. Building on these analyses, recent advances have improved mixed-precision variants of Householder QR. Yang et al. proposed a mixed-precision block Householder QR algorithm (mpBQR3), which achieves improved performance by performing selected operations in lower precision while attaining an LOO bound of order 2ul+nuh2u_l + nu_h, where ulu_l and uhu_h denote the lower- and higher-precision unit roundoffs, respectively [27]. More recently, Leng et al. developed a high-performance Householder QR factorization for NVIDIA GPUs that exploits Tensor Cores and reduced-precision arithmetic [20]. Connolly and Higham developed a probabilistic rounding-error analysis for Householder QR that yields a probabilistic bound proportional to mnu\sqrt{mn}u with high probability under the assumptions that rounding errors are mean-independent of and mean zero [6]. A comprehensive survey of mixed-precision methods in numerical linear algebra, including orthogonalization and QR factorization, can be found in [15].

Beyond these direct use cases, low-precision QR factorization can also be desirable when a correction step can recover lost accuracy. For example, in iterative refinement methods, a low-precision QR factorization can be used to construct a preconditioner, with the accuracy subsequently improved through refinement iterations [4]. Similarly, in mixed-precision Jacobi SVD algorithms, a low-precision QR factorization serves as a preprocessing step, followed by reorthogonalization using working-precision QR factorization and one-sided Jacobi sweeps [10]. Furthermore, in the solution of Sylvester matrix equations [8] and the computation of the matrix square root [9], Schur-based initial approximations obtained from the low-precision QR-related kernels can be refined to working-precision accuracy. Finally, the QR-based CP-ALS algorithm may benefit from a stable QR factorization in half precision, given the satisfactory performance observed when switching the QR computation from double to single precision [28 Fig. 5].

In this work, we propose a new mixed-precision variant of block Householder QR factorization, mpWYQR, to maximize low-precision computation without compromising overall factorization quality. Identifying the components of the algorithm most critical to accuracy, we examine which parts of the classical block approach can be computed at lower precision—such as inner products—and use higher precision to preserve numerical stability.

The rest of the paper is organized as follows. We first provide background on floating-point arithmetic, rounding error analysis, and the block Householder QR decomposition with the WY representation. In § 3, we introduce our reduced- and mixed-precision block Householder QR variants, and in § 4, we present their error analysis. We then present the numerical experiments in § 5 and conclude the paper in § 6.

Preliminaries

This section introduces the concepts and methods necessary for the analysis and algorithms presented in the rest of the paper. We first review the basic concepts of floating-point arithmetic and finite-precision error analysis, which are then generalized to facilitate our mixed-precision analysis. Next, we describe the Householder QR factorization and discuss how blocking and the WY representation have been employed to improve its performance in scientific computing. Finally, we review the mixed-precision block Householder QR algorithm mpBQR3 proposed in [27] and discuss the limitations that motivate the present work.

Floating-point arithmetic and error analysis

Floating-point operations satisfy the standard model [14 sect. 2.2]

fl⁡(a∘b)=(a∘b)(1+δ),∣δ∣≤u,\operatorname{fl}(a \mathbin{\circ} b) = (a \mathbin{\circ} b)(1+\delta), \qquad|\delta| \le u,

with uu denoting the working precision of the operation; in this paper u=uhu = u_h or uℓu_\ell and fl⁡h\operatorname{fl}_h or fl⁡ℓ\operatorname{fl}_\ell, depending on the precision used, and we particularly focus on the precision combination (uh,uℓ)=(fp32,fp16)(u_h,u_\ell) = (\mathrm{fp32},\mathrm{fp16}).

The standard product lemma [14 Lem. 3.1] expresses the accumulation of rounding errors in uniform precision as

∏i=1k(1+δi)ρi=1+θk,∣θk∣≤γk≔ku1−ku,\prod_{i=1}^{k}(1+\delta_i)^{\rho_i} = 1+\theta_k, \qquad|\theta_k| \le\gamma_k \coloneqq\frac{ku}{1-ku},

where ∣δi∣≤u|\delta_i| \le u, ρi∈{−1,1}\rho_i \in\{-1,1\}, and ku<1ku < 1; see also [26 Chap. 1]. To distinguish the contributions of the two precisions and analyze rounding errors in mixed precision for mpWYQR later in § 4, we extend this notation by defining, for nonnegative integers p,qp,q,

1+θp,q≔∏i=1p(1+δih)ρi∏j=1q(1+δjℓ)τj,∣δih∣≤uh,∣δjℓ∣≤uℓ,ρi,τj∈{−1,1}.1+\theta_{p,q} \coloneqq\prod_{i=1}^{p}(1+\delta_i^h)^{\rho_i}\prod_{j=1}^{q}(1+\delta_j^\ell)^{\tau_j}, \qquad|\delta_i^h| \le u_h,\quad|\delta_j^\ell| \le u_\ell,\quad\rho_i,\tau_j \in\{-1,1\}.

The notation satisfies

(1+θp,q)(1+θr,s)=1+θp+r,q+s,(1+θp,q)−1=1−θp,q1+θp,q=1+θp,q′,(1+\theta_{p,q})(1+\theta_{r,s}) = 1+\theta_{p+r,q+s}, \qquad(1+\theta_{p,q})^{-1} = 1-\frac{\theta_{p,q}}{1+\theta_{p,q}} = 1+\theta'_{p,q},

where θp,q′\theta'_{p,q} denotes a possibly different quantity of the same form as θp,q\theta_{p,q}. We omit the prime in subsequent calculations, in accordance with the convention that each occurrence may have a different value. With a=(1−uh)p(1−uℓ)q∈(0,1]a = (1-u_h)^p(1-u_\ell)^q \in(0,1], it follows that a≤1+θp,q≤a−1a \le1+\theta_{p,q} \le a^{-1}. Since 1−a≤a−1−11-a \le a^{-1}-1, we obtain

ηp,q:=(1−uh)−p(1−uℓ)−q−1,∣θp,q∣≤ηp,q,(1)\eta_{p,q}:=(1-u_h)^{-p}(1-u_\ell)^{-q}-1,\qquad|\theta_{p,q}| \le\eta_{p,q}, \tag*{(1)}

Thus ηp,q\eta_{p,q} plays the same role for θp,q\theta_{p,q} as γk\gamma_k does for θk\theta_k. The bound (2.1) retains all orders of unit roundoff and holds under the assumption uh,uℓ<1u_h,u_\ell<1.

Define

μp,q:=puh+quℓ.\mu_{p,q}:=pu_h+qu_\ell.

If μp,q<1\mu_{p,q}<1, Bernoulli’s inequality gives (1−uh)p(1−uℓ)q≥1−μp,q>0(1-u_h)^p(1-u_\ell)^q \ge1-\mu_{p,q}>0. Taking reciprocals therefore yields

∣θp,q∣≤ηp,q≤μp,q1−μp,q,μp,q<1,|\theta_{p,q}| \le\eta_{p,q} \le\frac{\mu_{p,q}}{1-\mu_{p,q}},\qquad\mu_{p,q}<1,

where rightmost upper bound reduces to γp+q\gamma_{p+q} when uh=uℓ=uu_h=u_\ell=u. Furthermore, (1−u)−1≥1+u(1-u)^{-1}\ge1+u implies ηp,q≥μp,q\eta_{p,q}\ge\mu_{p,q}, so the preceding bound gives

0≤ηp,q−μp,q≤μp,q21−μp,q,μp,q<1.0\le\eta_{p,q}-\mu_{p,q}\le\frac{\mu_{p,q}^{2}}{1-\mu_{p,q}},\qquad\mu_{p,q}<1.

Consequently,

ηp,q=μp,q+O(μp,q2)asμp,q→0.\eta_{p,q}=\mu_{p,q}+O(\mu_{p,q}^{2})\quad\text{as}\quad\mu_{p,q}\to0.

The first-order estimate is useful only when μp,q≪1\mu_{p,q}\ll1, just as the first-order approximation γk≈ku\gamma_k\approx ku requires ku≪1ku\ll1 in uniform precision. We will also use

γ~k(s):=ckus1−ckus,s∈{h,ℓ},\widetilde{\gamma}_k^{(s)}:=\frac{cku_s}{1-cku_s},\qquad s\in\{h,\ell\},

where cc is the modest positive constant and ckus<1cku_s<1.

Block Householder QR with WY representation

The classical Householder QR algorithm factorizes an m×nm\times n matrix AA into an orthogonal matrix QQ and an upper triangular matrix RR by successively applying Householder reflections. At each step kk, a Householder reflector Hk=I−τkvkvkTH_k=I-\tau_kv_kv_k^T zeros out the subdiagonal entries of the kk-th column of AA, where vkv_k is the Householder vector and τk\tau_k is the corresponding scalar. The reflector is then applied to the remaining columns of the matrix. After nn steps, the product Q=H1H2⋯HnQ=H_1H_2\cdots H_n yields the orthogonal factor. While this approach is unconditionally backward stable, it relies heavily on BLAS2-level operations, which limits performance on modern architectures because of the large number of synchronizations and the inability to exploit cache efficiently.

The WY representation, introduced in [2], reformulates the product of kk Householder reflectors as I+WYTI+WY^T, where WW and YY are m×km\times k matrices. This representation allows the accumulated reflectors to be applied to a matrix block via (triangular) matrix-matrix products, namely TRMM and GEMM, rather than a sequence of BLAS2 operations. Since it involves more BLAS3 operations than the classical Householder QR approach, the WY representation is more advantageous for HPC applications.

To further improve performance, the algorithm is organized into blocks of size bb. At a given block step, the next bb columns form a panel. The panel factorization constructs the corresponding bb Householder reflectors and accumulates them into a WY representation. These accumulated reflectors are then applied simultaneously to the remaining columns, called the trailing matrix. Compared with applying a single reflector at a time, the block formulation improves cache utilization by leveraging GEMM operations, providing better performance on large-scale problems. Algorithm 2.1 presents the pseudocode for the block Householder QR approach with a WY representation. For more detailed algorithm, see [11, Sec. 5.

Algorithm 2.1: Block Householder QR with WY representation

Input: A∈Rm×nA \in\mathbb{R}^{m \times n}, m≥nm \ge n, and block size bb.

Output: R∈Rn×nR \in\mathbb{R}^{n \times n} and panel WY factors {(Wj,Yj)}j=1s\{(W_j,Y_j)\}_{j=1}^{s}, where s=⌈n/b⌉s = \lceil n/b \rceil.

  1. j←0j \gets0

  2. for k=1:b:nk = 1 : b : n do

    1. j←j+1j \gets j + 1

    2. r←min⁡(b,n−k+1)r \gets\min(b,n-k+1)

    3. ℓ←k+r−1\ell\gets k+r-1

    4. Factor the panel A[k:m,k:ℓ]A[k:m,k:\ell] by Householder QR, storing the Householder vectors in VV and the corresponding scalars in τ\tau

    5. Form the WY factors WjW_j and YjY_j from (V,τ)(V,\tau) so that the product of the panel reflectors is I+WjYjTI + W_jY_j^{T}

    6. if ℓ<n\ell< n then

      1. C←A[k:m,ℓ+1:n]C \gets A[k:m,\ell+1:n]

      2. A[k:m,ℓ+1:n]←C+Yj(WjTC)A[k:m,\ell+1:n] \gets C + Y_j(W_j^{T}C)

    7. R←triu⁡(A[1:n,1:n])R \gets\operatorname{triu}(A[1:n,1:n])

mpBQR3

The mixed-precision blocked QR algorithm mpBQR3 introduced in [27 Alg. 7] is based on a blocked WY approach in which each panel is first cast into uhu_h and then factorized by Householder QR to build the WY representation in precision uhu_h. The resulting panel matrices, including the Householder basis and the WY factor, are subsequently cast back to uℓu_\ell so that the trailing matrix update can be performed by low-precision matrix–matrix operations with uhu_h accumulation, as in Tensor Core-type block fused multiply–add operations [3]. This design exploits the high throughput of low-precision BLAS3 kernels while retaining uhu_h for the lower-order operations inside the panel factorization. However, repeated cast-up and cast-down operations introduce additional expensive conversion overhead and low-precision perturbations, which cause the attainable accuracy to remain governed by uℓu_\ell, despite extensive use of uhu_h inside each panel.

New Reduced/Mixed Precision Variants

Revising the strategy above, we first investigate whether Householder QR can run uniformly in uℓu_\ell without overflow or underflow while improving performance. We then introduce a mixed precision approach, mpWYQR, achieving O(uℓ)O(u_\ell) accuracy in terms of residual and LOO, with substantially fewer uhu_h inner products and less precision-conversion overhead.

Algorithm 2.1 is presented using the general WY representation introduced by Bischof and Van Loan [2]. In practice, a more storage-efficient compact WY representation is commonly used [25]; with the sign convention adopted in our implementation, Y=VY = V and W=YTW = YT, so that only VV and the small triangular factor TT need to be stored. We retain the more general W,YW,Y notation in Algorithm 2.1 to keep the presentation independent of this particular implementation.

Reduced precision variant (rWYQR)

A natural starting point for a low-precision block Householder QR algorithm is to adapt the existing LAPACK [1] QR routines, geqr2, geqrf, and geqrt(2,3), to operate in uℓu_\ell. However, a difficulty arises in the norm computation required for Householder reflector construction in line 6 of Algorithm 2.1. LAPACK evaluates the Euclidean norm using a carefully scaled nrm2 implementation to reduce the risk of intermediate overflow and underflow. Nevertheless, when the entire computation is carried out in a low precision such as fp16, the limited dynamic range still poses a numerical bottleneck for the norm evaluation. This motivates a more careful treatment of norm computation in the uℓu_\ell setting.

To compute ∥x∥2\lVert x\rVert_2, we first evaluate the squared norm of the tail, s=x2:nTx2:n=∥x2:n∥22s = x_{2:n}^{T}x_{2:n} = \lVert x_{2:n}\rVert_2^2, and then form ∥x∥2=x12+s\lVert x\rVert_2 = \sqrt{x_1^2+s} [11]. Thus, we avoid unnecessarily computing the intermediate quantity ∥x2:n∥2=s\lVert x_{2:n}\rVert_2 = \sqrt{s}, saving one square-root operation and reducing the overflow and underflow risk. After implementing the revised approach, we first use uℓu_\ell throughout Algorithm 2.1, call it the rWYQR approach, and compare it with the geqrf routine in uℓu_\ell for fp16. Table 3.1 shows the effects of norm scaling on time, LOO, and residuals. The test matrices A∈Rm×nA \in\mathbb{R}^{m \times n} are generated with uniformly randomly distributed elements from the range [−1,1][-1,1]. All matrices are scaled from the right by the largest absolute value of each column to prevent overflow and/or underflow. We use a fixed block size of nb=64n_b = 64 throughout all experiments. We compare the reduced-precision variant with the proposed modification on norm computation, rWYQR, against the LAPACK routine for block Householder QR factorization analogous to mpBQR3, geqrf, in terms of LOO, ∥QTQ−I∥F\lVert Q^TQ-I\rVert_F, residual, ∥A−QR∥F\lVert A-QR\rVert_F, and runtime.

(m,n)(m,n)Method∥A−QR∥F\lVert A-QR\rVert_F∥QTQ−I∥F\lVert Q^TQ-I\rVert_FTime (s)
(30000,128)(30000,128)geqrf6.48926E−016.48926\mathrm{E}{-01}2.60498E−012.60498\mathrm{E}{-01}0.788860.78886
rWYQR6.48438E−016.48438\mathrm{E}{-01}2.60498E−012.60498\mathrm{E}{-01}0.058320.05832
(40000,100)(40000,100)geqrf2.54883E+002.54883\mathrm{E}{+00}2.75781E+002.75781\mathrm{E}{+00}0.686150.68615
rWYQR2.80078E+002.80078\mathrm{E}{+00}3.39062E+003.39062\mathrm{E}{+00}0.056540.05654

Table 3.1. Performance and accuracy results for A∈R(m,n)A \in\mathbb{R}^{(m,n)} for various (m,n)(m,n) settings.

We observe that the residual and LOO are still very large, indicating that uniform fp16 arithmetic is insufficient for reliable factorization at these dimensions. However, norm scaling still yields more than a ×13\times13 speedup for a 30000×12830000 \times128 matrix. When we increase the large dimension to 40000×10040000 \times100, we still observe order 10010^0 error even with norm scaling, while still achieving more than ×12\times12 speedup. This result shows that with the introduced modification, reduced precision accelerates the computation of the Householder reflectors. However, while norm scaling is sufficient to prevent overflow, it is not sufficient to maintain full numerical accuracy to order uℓu_\ell.

Motivated by the numerical experiments, we introduce a mixed-precision variant of the Householder construction given in Algorithm 3.1. Since the two norm evaluations are the critical operations in uℓu_\ell, we perform both in uhu_h and use uℓu_\ell for the remaining operations. We choose the sign of the leading entry of the transformed vector according to the standard convention [14 eq. (19.1)]. To show how the precision used for norm evaluations affects the accuracy of the algorithm, we run numerical experiments in two configurations. The first configuration is rWYQR, as explained above, where uℓ=uhu_\ell= u_h. In the second configuration, denoted mpWYQR, we implement Algorithm 3.1 with uh<uℓu_h < u_\ell, corresponding to the mixed-precision implementation presented in § 3.2.

Algorithm 3.1: Mixed-precision Householder reflector construction

Input: x∈Rmx \in\mathbb{R}^m

Output: v∈Rmv \in\mathbb{R}^m, β∈R\beta\in\mathbb{R}

  1. α=−sign⁡(x1)⋅∥x∥2\alpha= -\operatorname{sign}(x_1)\cdot\lVert x\rVert_2 \hfill norm in uhu_h, result converted to uℓu_\ell

  2. v=(x−αe1)/∥x−αe1∥2v = (x-\alpha e_1)/\lVert x-\alpha e_1\rVert_2 \hfill norm in uhu_h, subtraction and division in uℓu_\ell

  3. β=2/(vTv)\beta= 2/(v^Tv) \hfill uℓu_\ell

To investigate how the accuracy of the Householder reflector construction affects the overall QR factorization, we run experiments on square, dense random matrices of various sizes. Table 3.2 shows relative errors in vv and β\beta, computed using fp16 for the low-precision operations, against vfp32v_{fp32} and βfp32\beta_{fp32} computed in fp32. Although mpBQR3 gives more accurate vv and β\beta in most cases, the overall factorization errors remain similar. For instance, while the reported relative errors in vv for mpBQR3 and mpWYQR differ by 0.1135 for (m,n)=(4000,4000)(m,n)=(4000,4000), their LOO and QR errors differ by at most 2×10−42\times10^{-4}, which is smaller than one fp16 unit roundoff, 4.88×10−44.88\times10^{-4}. We anticipate that the reason for this behavior is that, during the calculation of β\beta in line 3 of Algorithm 3.1, the inaccuracy from the computation of vkv_k from the previous step can be subject to cancellation due to the inner product computation vkTvkv_k^Tv_k. This shows that using high precision for every inner product, as in mpBQR3, is unnecessary; instead, one can use uhu_h to compute the norm, which can significantly improve performance. The importance of using uhu_h for norm computation is also evident in the difference between the results of rWYQR and mpWYQR. We see that rWYQR cannot recover inaccuracies in computing vv and β\beta, leading to highly inaccurate QR factors. The dashed entries in rWYQR show that the norm evaluations in uℓu_\ell can easily overflow for large problems.

(m,n)(m,n)Method∥A−QR∥F\lVert A-QR\rVert_F∥QTQ−I∥F\lVert Q^TQ-I\rVert_F∥vfp32−v∥∥vfp32∥\frac{\lVert v_{fp32}-v\rVert}{\lVert v_{fp32}\rVert}∥βfp32−β∥∥βfp32∥\frac{\lVert\beta_{fp32}-\beta\rVert}{\lVert\beta_{fp32}\rVert}Time (s)
(4000, 4000)rWYQR8.55713E-029.95483E-020.672570.035900.33285
(4000, 4000)mpWYQR5.99670E-037.92694E-030.633470.032170.31996
(4000, 4000)mpBQR35.90515E-037.70950E-030.519970.028320.56634
(12000, 12000)rWYQR5.42969E-016.17676E-010.813450.020971.60879
(12000, 12000)mpWYQR5.65338E-037.54547E-030.671930.018511.50179
(12000, 12000)mpBQR35.54276E-037.40814E-030.688530.019685.09183
(36000, 36000)rWYQR–––––
(36000, 36000)mpWYQR3.51143E-035.52368E-030.729250.0133230.14354
(36000, 36000)mpBQR33.34358E-035.51224E-030.744340.0130158.15787
(42000, 42000)rWYQR–––––
(42000, 42000)mpWYQR3.00980E-035.22614E-030.738350.0116257.78656
(42000, 42000)mpBQR33.15475E-035.15747E-030.745340.0125279.60925

Table 3.2. Performance and accuracy results for A∈Rm×nA \in\mathbb{R}^{m \times n}, where m=nm=n.

The numerical experiments show that the uniform uℓu_\ell implementation achieves lower accuracy than O(ufp16)\mathcal{O}(u_{fp16}), indicating that norm evaluations in uℓu_\ell introduce rounding errors that degrade the quality of the Householder reflectors.

Error analysis in § 4 shows that computing the norm in uhu_h rather than uℓu_\ell only decreases the constant in the error bound, while the structure of the heuristic error bound remains the same. This suggests the importance of using uhu_h in the norm computation, especially in practice, as it stabilizes the computation without affecting the asymptotic accuracy of the algorithm.

Mixed Precision variant (mpWYQR)

Building on the reduced-precision algorithm introduced in the previous subsection, we now present the mixed-precision variant, which addresses the numerical instabilities observed when uniform low precision is used throughout the algorithm.

As discussed above, the two 2-norm evaluations in the Householder reflector construction are particularly sensitive in low precision. We therefore use uhu_h for both norm evaluations. The remaining parts of the algorithm are carried out in uℓu_\ell, and the resulting LOO remains of order O(uℓ)\mathcal{O}(u_\ell).

Numerical experiments show that the Householder reflector I−βvvTI-\beta vv^T determines accuracy. In particular, if any precision upu_p is used to compute the Householder reflector, the accuracy of the resulting mixed-precision Householder QR with WY representation will be limited by the order O(up)\mathcal{O}(u_p). This motivates a careful precision assignment: the norm computation in the reflector construction uses a upu_p accumulator, the resulting scalar is converted to uℓu_\ell, and the remaining reflector quantities are formed and stored in uℓu_\ell. The more computationally intensive operations, such as the matrix–matrix multiplications in the WY representation update, are then carried out in uℓu_\ell.

The overhead of mpWYQR over a uniform low-precision WY Householder QR is limited to the two norm evaluations used to form each Householder reflector. For the jjth reflector, with active vector length ℓj=m−j+1\ell_j=m-j+1, each ℓ2\ell_2-norm requires 2ℓj−12\ell_j-1 high-precision additions and multiplications and one square root, followed by one scalar conversion to uℓu_\ell. Since the conversions occur in registers, they introduce no additional memory traffic or memory. Summed over all nn reflectors, the high-precision work is 2∑j=1n(2ℓj−1)=4mn−2n22\sum_{j=1}^{n}(2\ell_j-1)=4mn-2n^2 flops plus 2n2n square roots and 2n2n scalar conversions. This is lower order than the leading factorization cost F(m,n)=2mn2−23n3F(m,n)=2mn^2-\frac{2}{3}n^3. In the tall-skinny regime (m≫nm\gg n), the relative high-precision work remains O(1/n)\mathcal{O}(1/n).

We now compare the computational and communication costs of mpBQR3 and mpWYQR. Let b=nbb = n_b be the block size, assume for simplicity that n=Nbn = Nb, and let mk=m−(k−1)bm_k = m - (k-1)b be the active panel height at block step kk. A key structural difference is that mpWYQR uses a geqrt-type blocked panel kernel in uℓu_\ell, whereas mpBQR3 uses a geqrf/HQR-type panel factorization and forms the WY representation in uhu_h before casting it to uℓu_\ell. Both algorithms apply the block reflectors through WY updates; the main cost difference is therefore the precision used to generate the reflectors and WY factors.

In terms of computational cost, the panel QR and WY construction in mpBQR3 require O(mkb2)O(m_kb^2) high-precision flops at step kk, for a total of O(b2∑k=1Nmk)=O(mnb)O\left(b^2\sum_{k=1}^{N}m_k\right)=O(mnb) high-precision flops overall. Its trailing updates contain F(m,n)+O(mnb)F(m,n)+O(mnb) low-input block-FMA (bFMA) flops, whose accumulation is performed in uhu_h. In contrast, mpWYQR restricts uhu_h to norm computations, while the remaining, more computationally dominant operations are carried out in uℓu_\ell. Furthermore, the block structure of mpWYQR enables greater parallelization via batch computation. As a result, both algorithms have the same leading total flop count, but mpWYQR reduces the high-precision work from O(mnb)O(mnb) to O(mn)O(mn).

mpWYQR also improves precision-conversion communication. Here we count only data movement caused by changing precision, since the ordinary blocked-QR traffic is common to both algorithms. In mpBQR3, casting each active panel up and the panel and WY factors back down requires a constant number of passes over mkbm_kb entries. Since b∑k=1Nmk=mn−12n(n−b)b\sum_{k=1}^{N}m_k = mn-\frac{1}{2}n(n-b), the additional conversion traffic is O(mn)O(mn) array entries; the constant depends on storage reuse. In mpWYQR, the high-precision norm accumulators and the two converted scalars per reflector remain in registers, so no high-precision panel is materialized and the additional cost is only O(n)O(n) scalar register conversions, with no additional memory traffic. Overall, mpWYQR is cheaper in both computational and communication costs than mpBQR3; see Table 3.3.

Algorithmuhu_h costuℓu_\ell/bFMA costConversion traffic
mpBQR3O(mnb)O(mnb)F(m,n)+O(mnb)F(m,n)+O(mnb) bFMAO(mn)O(mn) array entries
mpWYQR4mn−2n24mn-2n^2F(m,n)+O(mnb)F(m,n)+O(mnb)0 array; O(n)O(n) register

Table 3. Cost comparison of mpBQR3 and mpWYQR, where F(m,n)=2mn2−23n3F(m,n)=2mn^2-\frac{2}{3}n^3.

Error Analysis

Let A∈Rm×nA\in\mathbb{R}^{m\times n} with m≥nm\ge n. The Householder QR factorization triangularizes AA by applying a sequence of Householder matrices. Given a nonzero vector v∈Rmv\in\mathbb{R}^{m}, the Householder matrix (or Householder reflector) is of the form

H=I−βvvT,β=2/vTv,(2)H=I-\beta vv^{T},\qquad\beta=2/v^{T}v, \tag*{(2)}

which zeros out the elements of AA by columns. The Householder matrices are never formed explicitly in practice, because storage and computations are feasible by solely using the Householder vector vv.

The following lemma bounds the forward errors in the Householder vector and scaling factor computed by Algorithm 3.1. Here and henceforth, computed quantities are denoted with a hat notation.

Lemma 4.1. Let x∈Rmx\in\mathbb{R}^{m} be nonzero, with sign⁡(0)=1\operatorname{sign}(0)=1, and define

α=−sign⁡(x1)∥x∥2,z=x−αe1,v=z∥z∥2,β=2vTv=2.\alpha=-\operatorname{sign}(x_1)\lVert x\rVert_2,\qquad z=x-\alpha e_1,\qquad v=\frac{z}{\lVert z\rVert_2},\qquad\beta=\frac{2}{v^{T}v}=2.

In floating-point arithmetic with uhu_h and uℓu_\ell, the computed Householder vector v^\hat{v} and scaling factor β^\hat{\beta} produced by Algorithm 3.1 satisfy

∣v^−v∣≤η2m+2,4∣v∣,∣β^−β∣≤η2m+2,m+5∣β∣.(3)\lvert\hat{v}-v\rvert\le\eta_{2m+2,4}\lvert v\rvert,\qquad\lvert\hat{\beta}-\beta\rvert\le\eta_{2m+2,m+5}\lvert\beta\rvert. \tag*{(3)}

In particular,

∥v^−v∥2≤η2m+2,4∥v∥2.\lVert\widehat{v}-v\rVert_2 \le\eta_{2m+2,4}\lVert v\rVert_2.

Consequently, when the corresponding μp,q\mu_{p,q} are small, the first-order estimates are

∥v^−v∥2≤((2m+2)uh+4uℓ+O(μ2m+2,42))∥v∥2,\lVert\widehat{v}-v\rVert_2 \le\left((2m+2)u_h+4u_\ell+O\left(\mu_{2m+2,4}^2\right)\right)\lVert v\rVert_2,
∣β^−β∣≤((2m+2)uh+(m+5)uℓ+O(μ2m+2,m+52))∣β∣.|\widehat{\beta}-\beta| \le\left((2m+2)u_h+(m+5)u_\ell+O\left(\mu_{2m+2,m+5}^2\right)\right)|\beta|.

Proof. For the input vector xx, the standard inner-product error expansion [14 sect. 3.1, eq. (3.2)] and the nonnegativity of the summands give

fl⁡h(xTx)=ξh∥x∥22,(1−uh)m≤ξh≤(1+uh)m≤(1−uh)−m.(4)\operatorname{fl}_h(x^T x)=\xi_h\lVert x\rVert_2^2,\qquad(1-u_h)^m\le\xi_h\le(1+u_h)^m\le(1-u_h)^{-m}. \tag*{(4)}

Let r^(x)\widehat{r}(x) denote the norm of xx evaluated by a high-precision dot product and square root, followed by conversion to low precision. Taking the square root in (4) and including its rounding and the conversion error gives

a∥x∥2≤r^(x)≤a−1∥x∥2,a:=(1−uh)m+1(1−uℓ).(5)a\lVert x\rVert_2\le\widehat{r}(x)\le a^{-1}\lVert x\rVert_2,\qquad a:=(1-u_h)^{m+1}(1-u_\ell). \tag*{(5)}

Thus α^=−sign⁡(x1)r^(x)\widehat{\alpha}=-\operatorname{sign}(x_1)\widehat{r}(x) satisfies a≤α^/α≤a−1a\le\widehat{\alpha}/\alpha\le a^{-1}. Since the sign choice gives ∣z1∣=∣x1∣+∣α∣>0|z_1|=|x_1|+|\alpha|>0 and prevents cancellation, we also have a≤(x1−α^)/z1≤a−1a\le(x_1-\widehat{\alpha})/z_1\le a^{-1}. For the subsequent subtraction, we have

z^1=(x1−α^)(1+δzℓ),∣δzℓ∣≤uℓ.\widehat{z}_1=(x_1-\widehat{\alpha})(1+\delta^{\ell}_z),\qquad|\delta^{\ell}_z|\le u_\ell.

It follows that

z^1=gz1,z^i=zi (i>1),g=(1+δzℓ)x1−α^z1.(6)\widehat{z}_1=gz_1,\qquad\widehat{z}_i=z_i\ (i>1),\qquad g=(1+\delta^{\ell}_z)\frac{x_1-\widehat{\alpha}}{z_1}. \tag*{(6)}

Combining the preceding bounds yields

b:=a(1−uℓ)≤g≤a−1(1−uℓ)−1=b−1,b∈(0,1].(7)b:=a(1-u_\ell)\le g\le a^{-1}(1-u_\ell)^{-1}=b^{-1},\qquad b\in(0,1]. \tag*{(7)}

In particular, z^≠0\widehat{z}\ne0.

To analyze the normalization step, define q=z^/∥z^∥2q=\widehat{z}/\lVert\widehat{z}\rVert_2, the exact normalization of the computed vector, and t=∥z^∥2/∥z∥2t=\lVert\widehat{z}\rVert_2/\lVert z\rVert_2. By (6), we have t2=1+(g2−1)v12t^2=1+(g^2-1)v_1^2. Since ∥v∥2=1\lVert v\rVert_2=1, we have 0≤v12≤10\le v_1^2\le1, and hence

min⁡{1,g2}≤t2≤max⁡{1,g2}.\min\{1,g^2\}\le t^2\le\max\{1,g^2\}.

Taking positive square roots shows that tt lies between gg and 11. Hence g/tg/t lies between gg and 11, while 1/t1/t lies between g−1g^{-1} and 11. For vi≠0v_i\ne0, combining this with (7) gives

b≤qivi=z^i/∥z^∥2zi/∥z∥2={g/t,i=1,1/t,i>1≤b−1.(8)b\le\frac{q_i}{v_i}=\frac{\widehat{z}_i/\lVert\widehat{z}\rVert_2}{z_i/\lVert z\rVert_2}= \begin{cases} g/t, & i=1,\\ 1/t, & i>1 \end{cases} \le b^{-1}. \tag*{(8)}

Zero components of vv remain zero in qq. Repeating the norm analysis in (5) for z^≠0\widehat{z}\ne0 gives

c:=r^(z^)∥z^∥2,a≤c≤a−1.(9)c:=\frac{\widehat{r}(\widehat{z})}{\lVert\widehat{z}\rVert_2},\qquad a\le c\le a^{-1}. \tag*{(9)}

Then the low-precision divisions satisfy

v^i=z^ir^(z^)(1+δiℓ)=c−1qi(1+δiℓ),∣δiℓ∣≤uℓ.(10)\widehat{v}_i=\frac{\widehat{z}_i}{\widehat{r}(\widehat{z})}(1+\delta^\ell_i)=c^{-1}q_i(1+\delta^\ell_i),\qquad|\delta^\ell_i|\le u_\ell. \tag*{(10)}

Collecting these errors in D=diag⁡(1+δ1ℓ,…,1+δmℓ)D=\operatorname{diag}(1+\delta^\ell_1,\ldots,1+\delta^\ell_m) yields

v^=c−1Dq,∣D−I∣≤uℓI.\widehat{v}=c^{-1}Dq,\qquad|D-I|\le u_\ell I.

For vi≠0v_i\ne0, combining (8)–(10) and then using (7) gives

b2=ab(1−uℓ)≤v^ivi=1+δiℓcqivi≤[ab(1−uℓ)]−1=b−2.b^2=ab(1-u_\ell)\le\frac{\widehat{v}_i}{v_i}=\frac{1+\delta^\ell_i}{c}\frac{q_i}{v_i}\le\left[ab(1-u_\ell)\right]^{-1}=b^{-2}.

Since 1−b2≤b−2−11-b^2 \le b^{-2}-1 and zero components are preserved,

∣v^−v∣≤(b−2−1)∣v∣=η2m+2,4∣v∣,|\widehat{v}-v| \le(b^{-2}-1)|v| = \eta_{2m+2,4}|v|,

where b2=(1−uh)2m+2(1−uℓ)4b^2=(1-u_h)^{2m+2}(1-u_\ell)^4.

For the final dot product, the low-precision analogue of (4) gives

fl⁡ℓ(v^Tv^)=ξℓ∥v^∥22,(1−uℓ)m≤ξℓ≤(1+uℓ)m≤(1−uℓ)−m.(11)\operatorname{fl}_{\ell}(\widehat{v}^{T}\widehat{v})=\xi_{\ell}\|\widehat{v}\|_2^2,\qquad(1-u_\ell)^m\le\xi_\ell\le(1+u_\ell)^m\le(1-u_\ell)^{-m}. \tag*{(11)}

Set s=∥Dq∥2s=\|Dq\|_2. Since DD is diagonal, ∣D−I∣≤uℓI|D-I|\le u_\ell I implies ∥D−I∥2≤uℓ\|D-I\|_2\le u_\ell. Together with ∥q∥2=1\|q\|_2=1, the reverse triangle inequality therefore gives

∣s−1∣≤∥(D−I)q∥2≤uℓ.|s-1|\le\|(D-I)q\|_2\le u_\ell.

Thus, using v^=c−1Dq\widehat{v}=c^{-1}Dq, we have

1−uℓ≤s≤1+uℓ≤(1−uℓ)−1,∥v^∥22=c−2s2.(12)1-u_\ell\le s\le1+u_\ell\le(1-u_\ell)^{-1},\qquad\|\widehat{v}\|_2^2=c^{-2}s^2. \tag*{(12)}

The final low-precision division and β=2\beta=2 then give

β^=2(1+δβℓ)fl⁡ℓ(v^Tv^)=β(1+δβℓ)c2ξℓs2,∣δβℓ∣≤uℓ.(13)\widehat{\beta}=\frac{2(1+\delta_\beta^\ell)}{\operatorname{fl}_{\ell}(\widehat{v}^{T}\widehat{v})}=\beta\frac{(1+\delta_\beta^\ell)c^2}{\xi_\ell s^2},\qquad|\delta_\beta^\ell|\le u_\ell. \tag*{(13)}

Combining (9) and (11)–(13) gives

Lβ≤β^β≤Lβ−1,Lβ:=a2(1−uℓ)m+3=(1−uh)2m+2(1−uℓ)m+5.L_\beta\le\frac{\widehat{\beta}}{\beta}\le L_\beta^{-1},\qquad L_\beta:=a^2(1-u_\ell)^{m+3}=(1-u_h)^{2m+2}(1-u_\ell)^{m+5}.

Since 0<Lβ≤10<L_\beta\le1 and 1−Lβ≤Lβ−1−11-L_\beta\le L_\beta^{-1}-1, it follows that

∣β^−β∣≤(Lβ−1−1)∣β∣=η2m+2,m+5∣β∣.|\widehat{\beta}-\beta|\le(L_\beta^{-1}-1)|\beta|=\eta_{2m+2,m+5}|\beta|.

Finally, taking Euclidean norms in the componentwise bound for v^\widehat{v} and expanding ηp,q\eta_{p,q} as in § 2.1 gives the remaining statements. □

Lemma 4.1 moves the dimension-dependent errors in the two norm evaluations to uhu_h, while the low-precision term proportional to muℓmu_\ell remains in the bound for β^\widehat{\beta}, since the inner product v^Tv^\widehat{v}^{T}\widehat{v} is still evaluated in uℓu_\ell. Next, we provide rounding error bounds for the application of a Householder matrix to a vector.

Lemma 4.2. Let v,βv,\beta define the exact Householder matrix P=I−βvvT∈Rm×mP=I-\beta vv^T\in\mathbb{R}^{m\times m} associated with a nonzero xx as in Lemma 4.1, and let v^,β^\widehat{v},\widehat{\beta} be the computed quantities produced by Algorithm 3.1. Let b∈Rmb\in\mathbb{R}^m, and consider the computed application

y^=fl⁡ℓ(b−β^v^(v^Tb)),\widehat{y}=\operatorname{fl}_{\ell}(b-\widehat{\beta}\widehat{v}(\widehat{v}^{T}b)),

where all arithmetic in the application is performed in uℓu_\ell. Then

y^=(P+ΔP)b,∥ΔP∥F≤εm,(14)\widehat{y}=(P+\Delta P)b,\qquad\|\Delta P\|_F\le\varepsilon_m, \tag*{(14)}

where the all-orders bound is

εm:=2η0,m+1+4ηm+1,4+η0,1+2(1+η0,m+1)η0,m+3.(15)\varepsilon_m:=2\eta_{0,m+1}+4\eta_{m+1,4}+\eta_{0,1}+2(1+\eta_{0,m+1})\eta_{0,m+3}. \tag*{(15)}

When μ4m+4,4m+25\mu_{4m+4,4m+25} is small, this gives the first-order estimate

εm=(4m+4)uh+(4m+25)uℓ+O(μ4m+4,4m+252).(16)\varepsilon_m=(4m+4)u_h+(4m+25)u_\ell+O(\mu_{4m+4,4m+25}^2). \tag*{(16)}

Proof. Set P~=I−β^v^v^T\widetilde{P}=I-\widehat{\beta}\widehat{v}\widehat{v}^{T} and separate the error in the stored reflector from the rounding error in its application as

y^−Pb=(P~−P)b+(y^−P~b).(17)\widehat{y}-Pb=(\widetilde{P}-P)b+(\widehat{y}-\widetilde{P}b). \tag*{(17)}

We first bound P~−P\widetilde{P}-P using the quantities q,c,D,sq,c,D,s from the proof of Lemma 4.1. Define

p=Dqs,λ=1+δβℓξℓ.p=\frac{Dq}{s},\qquad\lambda=\frac{1+\delta_{\beta}^{\ell}}{\xi_{\ell}}.

Since s=∥Dq∥2>0s=\lVert Dq\rVert_{2}>0, we have ∥p∥2=1\lVert p\rVert_{2}=1. By (11) and (13),

(1−uℓ)m+1≤λ≤(1−uℓ)−m−1,∣λ−1∣≤η0,m+1.(1-u_{\ell})^{m+1}\leq\lambda\leq(1-u_{\ell})^{-m-1},\qquad\lvert\lambda-1\rvert\leq\eta_{0,m+1}.

Moreover, v^=(s/c)p\widehat{v}=(s/c)p and β^=2λc2/s2\widehat{\beta}=2\lambda c^{2}/s^{2}, so

β^v^v^T=2λppT,∣β^∣∥v^∥22=2∣λ∣.(18)\widehat{\beta}\widehat{v}\widehat{v}^{T}=2\lambda pp^{T},\qquad\lvert\widehat{\beta}\rvert\lVert\widehat{v}\rVert_{2}^{2}=2\lvert\lambda\rvert. \tag*{(18)}

To compare pp with vv, first note the division-error bounds in (10) and the bounds on ss in (12) give

(1−uℓ)2≤diis≤(1−uℓ)−2,(1-u_{\ell})^{2}\leq\frac{d_{ii}}{s}\leq(1-u_{\ell})^{-2},

where diid_{ii} denote the diagonal entries of DD. For vi≠0v_i\ne0, we have pi/vi=(dii/s)(qi/vi)p_i/v_i=(d_{ii}/s)(q_i/v_i). Combining this with (7) and (8) yields

(1−uh)m+1(1−uℓ)4≤pivi≤(1−uh)−m−1(1−uℓ)−4.(1-u_h)^{m+1}(1-u_{\ell})^{4}\leq\frac{p_i}{v_i}\leq(1-u_h)^{-m-1}(1-u_{\ell})^{-4}.

Zero components of vv remain zero in pp, and hence

∣p−v∣≤ηm+1,4∣v∣,∥p−v∥2≤ηm+1,4.\lvert p-v\rvert\leq\eta_{m+1,4}\lvert v\rvert,\qquad\lVert p-v\rVert_{2}\leq\eta_{m+1,4}.

Using ∥p∥2=∥v∥2=1\lVert p\rVert_{2}=\lVert v\rVert_{2}=1 and ppT−vvT=p(p−v)T+(p−v)vTpp^{T}-vv^{T}=p(p-v)^{T}+(p-v)v^{T}, we obtain from (18)

∥P~−P∥F=2∥λppT−vvT∥F≤2∣λ−1∣+4∥p−v∥2≤2η0,m+1+4ηm+1,4.(19)\begin{aligned} \lVert\widetilde{P}-P\rVert_{F} &=2\lVert\lambda pp^{T}-vv^{T}\rVert_{F}\leq2\lvert\lambda-1\rvert+4\lVert p-v\rVert_{2}\\ &\leq2\eta_{0,m+1}+4\eta_{m+1,4}. \tag*{(19)} \end{aligned}

We now hold v^\widehat{v} and β^\widehat{\beta} fixed and analyze their low-precision application to bb. For the dot product, we have

d=v^Tb,d^=fl⁡ℓ(v^Tb),∣d^−d∣≤η0,m∣v^T∣∣b∣.(20)d=\widehat{v}^{T}b,\qquad\widehat{d}=\operatorname{fl}_{\ell}(\widehat{v}^{T}b),\qquad\lvert\widehat{d}-d\rvert\leq\eta_{0,m}\lvert\widehat{v}^{T}\rvert\lvert b\rvert. \tag*{(20)}

In particular, ∣d^∣≤(1+η0,m)∣v^T∣∣b∣\lvert\widehat{d}\rvert\leq(1+\eta_{0,m})\lvert\widehat{v}^{T}\rvert\lvert b\rvert. The standard componentwise error bounds for the two multiplications and the final subtraction [14 sect. 2.2] give

∣y^−(b−β^v^d^)∣≤uℓ∣b∣+∣β^∣η0,3∣v^∣∣d^∣.(21)\lvert\widehat{y}-(b-\widehat{\beta}\widehat{v}\widehat{d})\rvert\leq u_{\ell}\lvert b\rvert+\lvert\widehat{\beta}\rvert\eta_{0,3}\lvert\widehat{v}\rvert\lvert\widehat{d}\rvert. \tag*{(21)}

Combining (20) and (21), and using

η0,m+(1+η0,m)η0,3=η0,m+3,uℓ≤η0,1,\eta_{0,m}+(1+\eta_{0,m})\eta_{0,3}=\eta_{0,m+3},\qquad u_{\ell}\leq\eta_{0,1},

yields

∣y^−P~b∣≤η0,1∣b∣+∣β^∣η0,m+3∣v^∣(∣v^T∣∣b∣).\lvert\widehat{y}-\widetilde{P}b\rvert\leq\eta_{0,1}\lvert b\rvert+\lvert\widehat{\beta}\rvert\eta_{0,m+3}\lvert\widehat{v}\rvert\bigl(\lvert\widehat{v}^{T}\rvert\lvert b\rvert\bigr).

Taking Euclidean norms and applying the Cauchy–Schwarz inequality gives

∥y^−P~b∥2≤(η0,1+∣β^∣∥v^∥22η0,m+3)∥b∥2.\lVert\widehat{y}-\widetilde{P}b\rVert_{2}\leq\bigl(\eta_{0,1}+\lvert\widehat{\beta}\rvert\lVert\widehat{v}\rVert_{2}^{2}\eta_{0,m+3}\bigr)\lVert b\rVert_{2}.

By (18), ∣β^∣∥v^∥22=2∣λ∣≤2(1+η0,m+1)\lvert\widehat{\beta}\rvert\lVert\widehat{v}\rVert_{2}^{2}=2\lvert\lambda\rvert\leq2(1+\eta_{0,m+1}), and therefore

∥y^−P~b∥2≤(η0,1+2(1+η0,m+1)η0,m+3)∥b∥2.(22)\lVert\widehat{y}-\widetilde{P}b\rVert_{2}\leq\bigl(\eta_{0,1}+2(1+\eta_{0,m+1})\eta_{0,m+3}\bigr)\lVert b\rVert_{2}. \tag*{(22)}

Combining (17), (19), and (22) gives ∥y^−Pb∥2≤εm∥b∥2\lVert\widehat{y}-P b\rVert_2 \le\varepsilon_m\lVert b\rVert_2, with εm\varepsilon_m defined in (15). For b≠0b \ne0, set

ΔP=(y^−Pb)bT∥b∥22.\Delta P = \frac{(\widehat{y}-P b)b^T}{\lVert b\rVert_2^2}.

Then ΔPb=y^−Pb\Delta P b=\widehat{y}-P b. The identity ∥uvT∥F=∥u∥2∥v∥2\lVert uv^T\rVert_F=\lVert u\rVert_2\lVert v\rVert_2, together with the preceding estimate, gives the required Frobenius-norm bound and proves (14). For b=0b=0, the computed result is zero and we take ΔP=0\Delta P=0. Finally, when μ4m+4,4m+25≪1\mu_{4m+4,4m+25}\ll1, expanding the ηp,q\eta_{p,q} terms in (15), as in Section 2.1, gives (16).

Next we derive columnwise error bounds for applying a sequence of Householder transformations to a matrix. These bounds describe the reflector-level sequential application; we discuss additional errors from forming and applying a WY representation below.

Lemma 4.3. Let A∈Rm×nA\in\mathbb{R}^{m\times n} and consider rr Householder transformations

Pk=I−βkvkvkT,k=1,…,r,P_k=I-\beta_kv_kv_k^T,\qquad k=1,\ldots,r,

whose computed reflector quantities are produced by Algorithm 3.1. Let QT=PrPr−1⋯P1Q^T=P_rP_{r-1}\cdots P_1. Then the computed result satisfies

A^r+1=QT(A+ΔA),\widehat{A}_{r+1}=Q^T(A+\Delta A),

with the all-orders columnwise and normwise bounds

∥Δaj∥2≤((1+εm)r−1)∥aj∥2,∥ΔA∥F≤((1+εm)r−1)∥A∥F.(23)\lVert\Delta a_j\rVert_2\le\bigl((1+\varepsilon_m)^r-1\bigr)\lVert a_j\rVert_2,\qquad \lVert\Delta A\rVert_F\le\bigl((1+\varepsilon_m)^r-1\bigr)\lVert A\rVert_F. \tag*{(23)}

If rμ4m+4,4m+25r\mu_{4m+4,4m+25} is small, the corresponding first-order estimate is

∥Δaj∥2≤(r((4m+4)uh+(4m+25)uℓ)+O(r2μ4m+4,4m+252))∥aj∥2,\lVert\Delta a_j\rVert_2\le\left(r\bigl((4m+4)u_h+(4m+25)u_\ell\bigr)+O\bigl(r^2\mu_{4m+4,4m+25}^2\bigr)\right)\lVert a_j\rVert_2,

and the same factor bounds ∥ΔA∥F/∥A∥F\lVert\Delta A\rVert_F/\lVert A\rVert_F.

Proof. For each column aja_j, Lemma 4.2 gives

a^j(r+1)=(Pr+ΔPr,j)⋯(P1+ΔP1,j)aj,∥ΔPk,j∥2≤∥ΔPk,j∥F≤εm.\widehat{a}_j^{(r+1)}=(P_r+\Delta P_{r,j})\cdots(P_1+\Delta P_{1,j})a_j,\qquad \lVert\Delta P_{k,j}\rVert_2\le\lVert\Delta P_{k,j}\rVert_F\le\varepsilon_m.

Since every PkP_k is orthogonal,

∥(Pr+ΔPr,j)⋯(P1+ΔP1,j)−Pr⋯P1∥2≤(1+εm)r−1.\left\lVert(P_r+\Delta P_{r,j})\cdots(P_1+\Delta P_{1,j})-P_r\cdots P_1\right\rVert_2\le(1+\varepsilon_m)^r-1.

Setting Δaj=Qa^j(r+1)−aj\Delta a_j=Q\widehat{a}_j^{(r+1)}-a_j proves the columnwise bound. Summing the squared columnwise bounds gives the Frobenius-norm bound. The first-order estimate follows from (16) and the expansion of (1+εm)r(1+\varepsilon_m)^r.

For the active column xx used to construct a reflector, we have Px=αe1Px=\alpha e_1, and the stored diagonal entry α^\widehat{\alpha} satisfies ∣α^−α∣≤ηm+1,1∥x∥2≤εm∥x∥2|\widehat{\alpha}-\alpha|\le\eta_{m+1,1}\lVert x\rVert_2\le\varepsilon_m\lVert x\rVert_2. Thus Lemma 4.3 yields the following QR backward-error result by the standard argument [14 Thm. 19.4].

Theorem 4.4. Let R^∈Rm×n\widehat{R}\in\mathbb{R}^{m\times n} be the computed upper trapezoidal QRQR factor of A∈Rm×nA\in\mathbb{R}^{m\times n} obtained from the Householder reflector constructions and sequential applications analyzed above. Then there exists an orthogonal Q∈Rm×mQ\in\mathbb{R}^{m\times m} such that

A+ΔA=QR^,A+\Delta A=Q\widehat{R},

where

∥Δaj∥2≤((1+εm)n−1)∥aj∥2,j=1,…,n.(24)\lVert\Delta a_j\rVert_2\le\bigl((1+\varepsilon_m)^n-1\bigr)\lVert a_j\rVert_2,\qquad j=1,\ldots,n. \tag*{(24)}

If nμ4m+4,4m+25n\mu_{4m+4,4m+25} is small, the first-order estimate is

∥Δaj∥2≤(n((4m+4)uh+(4m+25)uℓ)+O(n2μ4m+4,4m+252))∥aj∥2.\lVert\Delta a_j\rVert_2\le\left(n\bigl((4m+4)u_h+(4m+25)u_\ell\bigr)+O\bigl(n^2\mu_{4m+4,4m+25}^2\bigr)\right)\lVert a_j\rVert_2.

The matrix QQ is given explicitly by Q=(PnPn−1⋯P1)TQ=(P_nP_{n-1}\cdots P_1)^T, where PkP_k is the exact Householder matrix associated with the kkth active column.

Finally, we present results concerning the error in the computed QQ, the factorization residual, and the loss of orthogonality.

Theorem 4.5. Under the assumptions of Theorem 4.4, let Q^T\widehat{Q}^{T} be the result of applying the same computed reflector quantities to ImI_m in the order used to form QTQ^{T}, and set Q^=(Q^T)T\widehat{Q}=(\widehat{Q}^{T})^{T}. Then

∥Q^−Q∥F≤m((1+ϵm)n−1).(25)\left\|\widehat{Q}-Q\right\|_{F}\leq\sqrt{m}\left((1+\epsilon_m)^n-1\right). \tag*{(25)}

Moreover,

∥A−Q^R^∥F≤((1+ϵm)n−1)(1+m(1+ϵm)n)∥A∥F,(26)\left\|A-\widehat{Q}\widehat{R}\right\|_{F}\leq\left((1+\epsilon_m)^n-1\right)\left(1+\sqrt{m}(1+\epsilon_m)^n\right)\|A\|_{F}, \tag*{(26)}

and

∥Q^TQ^−I∥F≤2m((1+ϵm)n−1)+m((1+ϵm)n−1)2.(27)\left\|\widehat{Q}^{T}\widehat{Q}-I\right\|_{F}\leq2\sqrt{m}\left((1+\epsilon_m)^n-1\right)+m\left((1+\epsilon_m)^n-1\right)^2. \tag*{(27)}

If nμ4m+4,4m+25n\mu_{4m+4,4m+25} is small, the respective first-order estimates are

∥Q^−Q∥F≤nm((4m+4)uh+(4m+25)uℓ)+O(n2mμ4m+4,4m+252),\left\|\widehat{Q}-Q\right\|_{F}\leq n\sqrt{m}\left((4m+4)u_h+(4m+25)u_\ell\right)+O\left(n^2\sqrt{m}\mu_{4m+4,4m+25}^2\right),
∥A−Q^R^∥F≤n(1+m)((4m+4)uh+(4m+25)uℓ)∥A∥F+O(n2(1+m)μ4m+4,4m+252)∥A∥F,\left\|A-\widehat{Q}\widehat{R}\right\|_{F}\leq n(1+\sqrt{m})\left((4m+4)u_h+(4m+25)u_\ell\right)\|A\|_{F}+O\left(n^2(1+\sqrt{m})\mu_{4m+4,4m+25}^2\right)\|A\|_{F},

and

∥Q^TQ^−I∥F≤2nm((4m+4)uh+(4m+25)uℓ)+O(mn2μ4m+4,4m+252).\left\|\widehat{Q}^{T}\widehat{Q}-I\right\|_{F}\leq2n\sqrt{m}\left((4m+4)u_h+(4m+25)u_\ell\right)+O\left(mn^2\mu_{4m+4,4m+25}^2\right).

The orthogonal matrix QQ is the one in Theorem 4.4.

Proof. Applying Lemma 4.3 to ImI_m and transposing the result gives (25). Let

ΔA=Q^R^−A,E=Q^−Q.\Delta A=\widehat{Q}\widehat{R}-A,\qquad E=\widehat{Q}-Q.

By Theorem 4.4 and (4.24),

∥ΔA∥F≤((1+ϵm)n−1)∥A∥F,\|\Delta A\|_{F}\leq\left((1+\epsilon_m)^n-1\right)\|A\|_{F},
∥E∥F≤m((1+ϵm)n−1),∥R^∥F≤(1+ϵm)n∥A∥F.\|E\|_{F}\leq\sqrt{m}\left((1+\epsilon_m)^n-1\right),\qquad\|\widehat{R}\|_{F}\leq(1+\epsilon_m)^n\|A\|_{F}.

Therefore,

∥A−Q^R^∥F≤∥ΔA∥F+∥E∥F∥R^∥F,\left\|A-\widehat{Q}\widehat{R}\right\|_{F}\leq\|\Delta A\|_{F}+\|E\|_{F}\|\widehat{R}\|_{F},

which gives (26). Finally,

Q^TQ^−I=QTE+ETQ+ETE,\widehat{Q}^{T}\widehat{Q}-I=Q^{T}E+E^{T}Q+E^{T}E,

so

∥Q^TQ^−I∥F≤2∥E∥F+∥E∥F2,\left\|\widehat{Q}^{T}\widehat{Q}-I\right\|_{F}\leq2\|E\|_{F}+\|E\|_{F}^{2},

which proves (27). Expanding the all-orders bounds gives the stated first-order estimates.

Note that the mixed-precision bounds in Theorems 4.4 and 4.5 have the same qualitative form as the standard uniform-precision error bounds [14 sect. 19.3]. Our results essentially reduce these bounds by a constant factor via performing the norm evaluation in the Householder matrix construction at uhu_h. Since our approach differs from the standard construction of the Householder vector and scaling factor only in the norm evaluation, the above conclusion also applies when the WY representation [2], or its more storage-efficient compact WY representation [25], is used in the assembly and application of the Householder matrices [14 sect. 19.5]. Additional rounding errors incurred in forming and applying the WY representation must be accounted for by the corresponding matrix–matrix error analysis.

Connolly and Higham Connolly and Higham [6, Thm. 4.4 and eq. (4.20)] show that the dimension dependence in the standard deterministic Householder QR bounds can be substantially reduced under a probabilistic model in which rounding errors are mean independent and have mean zero, together with suitable probabilistic bounds for applying a sequence of Householder matrices to a vector. In uniform precision, the worst-case mnumnu dependence is replaced by mnu\sqrt{mnu}, up to constants and powers of the probability parameter λ\lambda [6 eq. (4.17)]. An analogous probabilistic loss-of-orthogonality result also holds [6 Thm. 4.5]. Applying the same reasoning to the present mixed-precision analysis suggests that the deterministic first-order term

n((4m+4)uh+(4m+25)uℓ)n\bigl((4m+4)u_h+(4m+25)u_\ell\bigr)

may be replaced, schematically, by terms of order mn(uh+uℓ)\sqrt{mn}(u_h+u_\ell). A rigorous probabilistic result for the present precision assignment would require a separate analysis, but this viewpoint helps explain why the deterministic bounds can be much more pessimistic than the observed residuals and loss of orthogonality.

In comparison, the mixed-precision analysis of Yang, Fox, and Sanders [27 Alg. 7 and eqs. (4.26)–(4.27)] studies a different precision assignment. In mpBQR3, each panel is cast to uhu_h, the panel QR factorization and WY representation are formed in uhu_h, and the WY factors are cast back to uℓu_\ell so that the trailing updates can use low-precision matrix products with higher-precision accumulation. If rr is the block size and N=n/rN=n/r is the number of column blocks, their error bound for the computed thin orthogonal factor has the leading form

∥Q^mpBQR3−Q∥F≲n(γ~N(ℓ)+nγ~m(h)).\left\lVert\widehat{Q}_{\mathrm{mpBQR3}}-Q\right\rVert_F \lesssim\sqrt{n}\left(\widetilde{\gamma}^{(\ell)}_N+n\widetilde{\gamma}^{(h)}_m\right).

Since γ~N(ℓ)≈CNuℓ\widetilde{\gamma}^{(\ell)}_N\approx CNu_\ell and γ~m(h)≈Cmuh\widetilde{\gamma}^{(h)}_m\approx Cmu_h, the low-precision contribution comes mainly from block-level cast-down errors, while the panel factorization contributes through the high-precision term.

Our mpWYQR variant uses uℓu_\ell more aggressively: only the two norm evaluations in the reflector construction are carried out in uhu_h, while the remaining reflector construction, reflector application, and WY-style updates are governed by uℓu_\ell. Consequently, the deterministic bounds in Theorems 4.4 and 4.5 do not predict high-precision accuracy; they predict uℓu_\ell-level accuracy with the norm computations protected from overflow, underflow, and large accumulation errors that can occur in a fully low-precision reflector construction. The comparison therefore highlights a trade-off. mpBQR3 obtains a sharper high-precision panel term by doing substantially more panel work and conversion in uhu_h, whereas mpWYQR keeps the high-precision work to the lower-order norm evaluations and aims for a cheaper factorization whose attainable accuracy is still expected to be of order uℓu_\ell.

Numerical Experiments

The primary goals of our implementation are to leverage existing LAPACK and BLAS routines, minimize hardware-specific dependencies to enable a native CPU implementation, and achieve performance improvements in large-scale experiments. However, several challenges arise in practice. Standard LAPACK and BLAS libraries do not provide routines for lower-precision arithmetic; mixed-precision routines are largely limited to GPU libraries, and memory bandwidth can become a performance bottleneck.

To overcome these challenges, we build on the work of Köhler and Benner [18], which provides implementations of fp16 BLAS3 operations as well as mixed-precision LAPACK routines supporting fp16-fp32 precision combination. These routines form the foundation for the mpWYQR implementation.

The implementation is carried out using Intel Math Kernel Library (MKL), which provides native support for fp16 GEMM operations, and is executed on an Intel Xeon Platinum Emerald Rapids Series CPU, which natively supports fp16 arithmetic. This setup lets us evaluate the proposed algorithm on a standard CPU architecture without relying on GPU-specific libraries, making the implementation more broadly accessible. The code for generating the results in this section is available at [19].

Random well-scaled matrices

We first test mpWYQR on well-scaled random matrices of various sizes to examine accuracy and performance behavior. We generate the test matrices A∈Rm×nA\in\mathbb{R}^{m\times n} with uniformly random elements in [−1,1][-1, 1]. All matrices are scaled from the right to prevent overflow and/or underflow. A fixed block size of nb=64n_b = 64 is used throughout all experiments, and the precision pair (uℓ,uh)=(fp16,fp32)(u_\ell, u_h) = (\mathrm{fp16}, \mathrm{fp32}) is used. We ran each experiment 5 times and report the average results throughout this section.

We compare the proposed algorithm against sgeqrt, which is the standard block Householder QR factorization in fp32, rWYQR, and mpBQR3 in terms of LOO, ∥QTQ−I∥F\lVert Q^{T}Q-I\rVert_F, residual, ∥A−QR∥F\lVert A-QR\rVert_F, and runtime.

Table 5.1 shows experiments on square random matrices with sizes ranging from m=n=1000m=n=1000 to 45000. For small matrices (m=n≤2000m=n\leq2000), we observe that sgeqrt or mpBQR3 can outperform mpWYQR with higher accuracy. However, as the size increases, mpWYQR starts to outperform the other variants, achieving more than 2.4×2.4\times speedup over sgeqrt and more than 3×3\times speedup over mpBQR3. As a trade-off, mpWYQR provides less accurate results than sgeqrt, as expected. This error difference follows from the error analysis as well: mpWYQR guarantees an error up to O(uℓ)O(u_\ell), whereas sgeqrt error is bounded by O(uh)=O(ufp32)≈10−7O(u_h)=O(u_{\mathrm{fp32}})\approx10^{-7}. Compared with mpBQR2, mpWYQR yields slightly less accurate results, again as expected. However this difference is between 3.36×10−43.36\times10^{-4} and 2.29×10−52.29\times10^{-5}, which can be neglected considering that both algorithms are using fp16 as the working precision and unit roundoff of fp16 is 4.88×10−44.88\times10^{-4}. Comparing rWYQR with mpWYQR shows the importance of using a high-precision accumulator when computing the norm. Both errors are higher in rWYQR than in mpWYQR. Another important issue is the performance of rWYQR. Although rWYQR uses uniform fp16 and mpWYQR uses fp32 elements, mpWYQR still slightly outperforms rWYQR. This behavior is related to the compiler and hardware properties. Even though rWYQR uses fp16 BLAS routines, the compiler is still underdeveloped for native fp16 operations. The hardware (CPU in this case) supports only basic operations (++, −-, ×\times, \\backslash), and, unfortunately, performs advanced operations in fp32. These limitations show the importance of mixed precision and can also motivate hardware and compiler development for lower precisions. We expect performance to improve for rWYQR when GPUs with Tensor Cores are used. However, one should note that the error is still expected to be worse than mpWYQR. The dashed lines in rWYQR show algorithm failure due to fp16 overflow.

Method(1000, 1000)(2000, 2000)(4000, 4000)(10000, 10000)(26000, 26000)(45000, 45000)
sgeqrt ∥A−QR∥F\lVert A-QR\rVert_F7.92003E-079.82351E-071.27310E-061.86841E-063.42155E-065.54632E-06
sgeqrt ∥QTQ−I∥F\lVert Q^TQ-I\rVert_F1.02469E-061.25968E-061.59754E-062.32236E-064.17879E-066.72147E-06
sgeqrt Time (s)0.194980.167250.353542.3458624.34429134.03649
rWYQR ∥A−QR∥F\lVert A-QR\rVert_F1.70898E-023.21960E-028.55713E-023.93311E-01——
rWYQR ∥QTQ−I∥F\lVert Q^TQ-I\rVert_F2.04315E-023.78113E-029.95483E-024.41895E-01——
rWYQR Time (s)0.229670.220020.332851.24347——
mpWYQR ∥A−QR∥F\lVert A-QR\rVert_F5.87082E-035.98907E-035.99670E-035.83267E-034.18854E-032.92206E-03
mpWYQR ∥QTQ−I∥F\lVert Q^TQ-I\rVert_F7.68280E-037.94220E-037.92694E-037.79343E-036.08826E-035.12695E-03
mpWYQR Time (s)0.115870.208170.319961.171859.9871072.41314
mpBQR3 ∥A−QR∥F\lVert A-QR\rVert_F5.53513E-035.84412E-035.90515E-035.70679E-034.31061E-032.96021E-03
mpBQR3 ∥QTQ−I∥F\lVert Q^TQ-I\rVert_F7.08008E-037.59888E-037.70950E-037.72095E-036.06537E-035.05066E-03
mpBQR3 Time (s)0.076700.210810.566343.5987328.6452192.30898

Table 5.1. Performance and accuracy results for A∈Rm×nA\in\mathbb{R}^{m\times n}, where m=nm=n.

Now, we perform the same comparison using random tall-skinny matrices. Table 5.2 shows that the behavior of all routines using fp16 changes with tall-skinny matrices. Now, when m≤10000m\leq10000 or m≥330000m\geq330000, sgeqrt outperforms the other routines. This is because the MKL fp16 GEMM routine is optimized only for square matrices. Therefore, using fp16 does not provide the expected performance benefit. We observe that sgeqrt can be more than 1.5×1.5\times faster than mpWYQR, especially when mm is small. As mm increases, the speedup drops to around 1.06×1.06\times. In contrast, when 10000<m<33000010000<m<330000, mpWYQR achieves more than 5.8×5.8\times speedup over sgeqrt. The comparison between mpBQR3 and mpWYQR, however, remains similar to the square matrices case. mpWYQR outperforms mpBQR3 for all experiments, achieving up to 9×9\times speedup with at most 1.67×10−51.67\times10^{-5} difference in accuracy. Last but not least, we observe the effect of fp32 norm computation even for m=40000m=40000, when rWYQR fails due to overflow and mpWYQR continues.

Method(10000, 128)(20000, 128)(40000, 128)(100000, 128)(320000, 128)(330000, 128)
sgeqrt∥A−QR∥F\lVert A-QR\rVert_F2.76481E-072.98540E-073.59624E-075.89988E-071.89635E-061.96205E-06
∥QTQ−I∥F\lVert Q^{T}Q-I\rVert_F1.76102E-072.01938E-072.43083E-074.36624E-071.35620E-061.39062E-06
Time (s)0.040000.092500.080430.256040.199180.14789
rWYQR∥A−QR∥F\lVert A-QR\rVert_F6.62231E-022.82715E-01––––
∥QTQ−I∥F\lVert Q^{T}Q-I\rVert_F4.08630E-021.14807E-01––––
Time (s)0.064610.02027––––
mpWYQR∥A−QR∥F\lVert A-QR\rVert_F1.10340E-038.78811E-047.93457E-047.59125E-047.36237E-046.69003E-04
∥QTQ−I∥F\lVert Q^{T}Q-I\rVert_F1.82986E-041.45435E-049.25660E-057.43270E-055.67436E-057.03335E-05
Time (s)0.060490.015820.027710.057970.166210.15726
mpBQR3∥A−QR∥F\lVert A-QR\rVert_F9.64642E-047.63416E-046.63757E-046.51836E-046.09398E-046.52313E-04
∥QTQ−I∥F\lVert Q^{T}Q-I\rVert_F1.90377E-041.46985E-048.95858E-057.54595E-055.94854E-057.33137E-05
Time (s)0.062010.141740.173880.447920.829040.79343

Table 5.2. Performance and accuracy results for A∈Rm×nA \in\mathbb{R}^{m \times n} with m>n=128m > n = 128.

Special block matrix classes

We now run several numerical experiments to compare the performance and accuracy of the four routines using three matrix classes available in the BlockStab library [21]: glued, monomial, and piled. Each matrix class is created using dimensional inputs mm, pp, ss, where mm denotes the number of rows, pp denotes the number of block vectors, and ss denotes the number of columns in each block vector. We set m=100m = 100, p=10p = 10, and s=10s = 10 for glued matrices; m=1200m = 1200, p=120p = 120, s=2:2:12s = 2 : 2 : 12 for monomial matrices; and m=1000:1000:10000m = 1000 : 1000 : 10000, p=10p = 10, s=10s = 10 for piled matrices. We ran each experiment 5 times and present the average results in Figure 5.1–Figure 5.3.

Heatmaps showing loss of orthogonality, QR factorization error, and runtime for glued matrices across condition numbers and row counts

Figure 5.1. Loss of orthogonality (left), relative QR factorization error (middle), and runtime (right) for glued matrices with varying condition number and number of rows mm. From top to bottom, the rows correspond to sgeqrt, rWYQR, mpWYQR, and mpBQR3.

Loss of orthogonality, relative QR factorization error, and runtime heatmaps for piled matrices

Figure 5.3. Loss of orthogonality (left), relative QR factorization error (middle), and runtime (right) for piled matrices with varying condition number and number of rows mm. From top to bottom, the rows correspond to sgeqrt, rWYQR, mpWYQR, and mpBQR3.

We observe that mpWYQR and mpBQR3 have similar LOO, with mpWYQR yielding slightly worse LOO, especially when mm is small. However, this difference appears only in the fourth significant digit and is therefore not significant. The relative error behaves similarly, especially as the condition number increases, but as with the LOO, the difference is negligible. In contrast, mpWYQR is up to 18×18\times faster than mpBQR3 (Figure 5.2). Across all the figures, mpWYQR performs best when mm is moderately small (around 3000), regardless of the condition number, and relatively worse when mm is even smaller.

Heatmaps of loss of orthogonality, relative QR factorization error, and runtime

Figure 5.2. Loss of orthogonality (left), relative QR factorization error (middle), and runtime (right) for monomial matrices with varying block size ss and number of rows mm. From top to bottom, the rows correspond to sgeqrt, rWYQR, mpWYQR, and mpBQR3. The white areas appear when the result is NaN or Infinity.

As expected, sgeqrt yields the best LOO and relative error for the glued matrices in Figure 5.1. Although we cannot explain the scattered high-error yellow boxes in these two maps, the absolute differences are less than 10−610^{-6} and can be ignored. We also point out the effect of fp16 on timing by comparing the maps of rWYQR and mpWYQR. This effect becomes more visible as the system grows moderately large. In particular, when m≥8000m \ge8000, comparing the map of mpBQR3 with those of rWYQR and mpWYQR shows the impact of using fp16 in inner products.

Figure 5.2 most clearly shows why computing norms in fp32 matters. Once the system is sufficiently large, rWYQR fails to compute the QR decomposition due to overflow or underflow, which appears as white boxes in the map. In contrast, mpWYQR succeeds even when mm is very large and yields LOO and relative error similar to those of mpBQR3. This figure also shows the largest performance difference between mpBQR3 and mpWYQR, which occurs when the system is very large and ss is sufficiently small.

Figure 5.3 also shows a significant performance gain for mpWYQR over mpBQR3, with negligible changes in LOO and relative error. These results are consistent with our theory, which shows that the error bounds of mpBQR3 and mpWYQR differ only by a constant. However, since both algorithms heuristically have the same error bound and the differences in the results are negligible, we argue that our theory provides a worst-case bound, and that the constant difference does not appear in practice.

Conclusion

In this paper, we introduced a mixed-precision block Householder QR algorithm with WY representation, mpWYQR, and compared it with mpBQR3 introduced in [27]. We also compared it with the uniform fp16 variant of mpWYQR, namely rWYQR, to show the importance of using

fp32 accumulators in norm computations rather than using fp16 throughout the entire algorithm. In addition, we included sgeqrt as a control to show timing changes and compared it with the other algorithms. In all cases, mpBQR3 and mpWYQR behave similarly in terms of accuracy, while mpWYQR can provide significant speedup.

The accuracy of mpWYQR still depends on ulu_l, while the algorithm has fewer performance restrictions since it requires fewer precision conversions and performs more inner products in fp16, which increases the error bound by a constant. However, we showed that this constant does not significantly affect the relative error and loss of orthogonality compared with mpBQR3 in the numerical experiments, since both algorithms share the same heuristic bounds.

Our numerical experiments show that, on CPUs, the performance of our variants is currently limited by library support, since only GEMM is natively supported in fp16. With broader fp16 support in numerical libraries, our variants and fp16 algorithms in general can achieve better performance on CPUs. As future work, we plan to develop a GPU implementation of mpWYQR, which we anticipate will achieve comparable, if not better, performance while maintaining comparable accuracy.

Acknowledgments

Anthropic was used to structure the first draft of Sections 1-3. These sections were reviewed by all authors and substantially changed. No new ideas were contributed by Claude, and it was not used to generate or suggest a literature review or any references. All ideas in this paper belong to the authors, and we take full responsibility for the content. E.O. is funded by the German Research Foundation (DFG) through the research training group 2297 “MathCoRe”, Magdeburg.

References

References

  1. [1]E. Anderson, Z. Bai, C. Bischof, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, and D. Sorensen. LAPACK Users’ Guide. SIAM, Philadelphia, PA, third edition, 1999.DOI
  2. [2]C. Bischof and C. Van Loan. The WY representation for products of Householder matrices. SIAM J. Sci. Statist. Comput., 8(1):S2–S13, 1987. doi:10.1137/09080009.DOI
  3. [3]P. Blanchard, N. J. Higham, F. Lopez, T. Mary, and S. Pranesh. Mixed precision block fused multiply-add: Error analysis and application to GPU tensor cores. SIAM J. Sci. Comput., 42(3):C124–C141, 2020. doi:10.1137/19M1289546.DOI
  4. [4]E. Carson, N. J. Higham, and S. Pranesh. Three-precision GMRES-based iterative refinement for least squares problems. SIAM J. Sci. Comput., 42(6):A4063–A4083, 2020. doi:10.1137/20M1316822.DOI
  5. [5]K.-T. Chen, Y.-T. Hwang, and Y.-C. Liao. VLSI design of a high throughput hybrid precoding processor for wireless MIMO systems. IEEE Access, 7:85925–85936, 2019. doi:10.1109/ACCESS.2019.2923251.DOI
  6. [6]M. P. Connolly and N. J. Higham. Probabilistic rounding error analysis of Householder QR factorization. SIAM J. Matrix Anal. Appl., 44(3):1146–1163, 2023. doi:10.1137/22M1514817.
  7. [7]J. Demmel, L. Grigori, M. Hoemmen, and J. Langou. Communication-optimal parallel and sequential QR and LU factorizations. SIAM J. Sci. Comput., 34(1):A206–A239, 2012. doi:10.1137/080731992.DOI
  8. [8]A. Dmytryshyn, M. Fasi, N. J. Higham, and X. Liu. Mixed-precision algorithms for solving the Sylvester matrix equation. arXiv:2503.03456, 2025. doi:10.48550/arXiv.2503.03456.DOI
  9. [9]B. Gao, D. Kressner, and M. Shao. A mixed precision algorithm for the matrix square root. arXiv:2607.12430, 2026. doi:10.48550/arXiv.2607.12430.DOI
  10. [10]W. Gao, Y. Ma, and M. Shao. A mixed precision jacobi SVD algorithm. ACM Trans. Math. Software, 51(1):1–33, 2025. doi:10.1145/3721124.DOI
  11. [11]G. H. Golub and C. F. Van Loan. Matrix Computations. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, fourth edition, 2013.
  12. [12]A. Haidar, T. T. Dong, S. Tomov, P. Luszczek, and J. Dongarra. A framework for batched and GPU-resident factorization algorithms applied to block Householder transformations. In International Conference on High Performance Computing, pages 31–47. Springer, 2015.DOI
  13. [13]N. Halko, P.-G. Martinsson, and J. A. Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM Review, 53(2):217–288, 2011. doi:10.1137/090771806.DOI
  14. [14]N. J. Higham. Accuracy and Stability of Numerical Algorithms. Applied Mathematics. SIAM Publications, Philadelphia, second edition, 2002. doi:10.1137/1.9780898718027.DOI
  15. [15]N. J. Higham and T. Mary. Mixed precision algorithms in numerical linear algebra. Acta Numerica, 31:347–414, 2022. doi:10.1017/s0962492922000022.DOI
  16. [16]A. S. Householder. Unitary triangularization of a nonsymmetric matrix. Journal of the ACM, 5(4):339–342, 1958.DOI
  17. [17]IEEE Standard for Floating-Point Arithmetic, IEEE Std 754-2019 (Revision of IEEE 754-2008). The Institute of Electrical and Electronics Engineers, New York, USA, 2019. doi:10.1109/IEEESTD.2019.8766229.DOI
  18. [18]M. Köhler and P. Benner. Low precision Fortran – enabling low precision floating point arithmetic in modern Fortran. arXiv:2606.16709, 2026. doi:10.48550/arXiv.2606.16709.DOI
  19. [19]M. Köhler, E. Oktay, X. Liu, and P. Benner. Low precision Fortran implementation of reduced and mixed-precision block Householder QR factorization, Oct. 2026. doi:10.5281/zenodo.23555819.
  20. [20]Y. Leng, G. Zou, H. Wang, P. Wu, and S. Zhang. High performance householder QR factorization on emerging GPU architectures using tensor cores. IEEE Trans. Parallel Distrib. Syst., 36(3):422–436, 2025. doi:10.1109/TPDS.2024.3522776.
  21. [21]K. Lund, E. Oktay, E. Carson, and Y. Ma. BlockStab, 2024. URL: https://github.com/katlund/BlockStab.
  22. [22]W. J. Maddox, A. Potapczynski, and A. G. Wilson. Low-precision arithmetic for fast Gaussian processes. In Uncertainty in Artificial Intelligence, pages 1306–1316. PMLR, 2022.arxiv.org/abs/2207.06856
  23. [23]D. Rabinkin, W. Song, M. Vai, and H. Nguyen. Adaptive array beamforming with fixed-point arithmetic matrix inversion using Givens rotations. In Advanced Signal Processing Algorithms, Architectures, and Implementations XI, volume 4474 of Proceedings of SPIE, 2001. doi:10.1117/12.448661.DOI
  24. [24]F. Rotella and I. Zambettakis. Block Householder transformation for parallel QR factorization. Appl. Math. Lett., 12(4):29–34, 1999.DOI
  25. [25]R. Schreiber and C. Van Loan. A Storage-Efficient WY Representation for Products of Householder Transformations. SIAM J. Sci. Statist. Comput., 10(1):53–57, 1989. doi:10.1137/0910005.DOI
  26. [26]J. H. Wilkinson. Rounding Errors in Algebraic Processes. SIAM, second edition, 2023. doi:10.1137/1.9781611977523.DOI
  27. [27]L. M. Yang, A. Fox, and G. Sanders. Rounding error analysis of mixed precision block Householder QR algorithms. SIAM J. Sci. Comput., 43(3):A1723–A1753, 2021. doi:10.1137/19M1296367.DOI
  28. [28]A. Zhang, B. D. Verma, J. Van Lent, and G. Ballard. Efficient CP rounding using alternating least squares with QR decomposition. SIAM J. Matrix Anal. Appl., 47(2):544–563, 2026. doi:10.1137/25M1742333.

Paper details

vlnc:W_h6dsa6s5
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 11

downloads · 2

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude

View statement
Looking for related papers…
Contents