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 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 , 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 , the worst-case backward error is of order 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 , where and 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 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]
with denoting the working precision of the operation; in this paper or and or , depending on the precision used, and we particularly focus on the precision combination .
The standard product lemma [14 Lem. 3.1] expresses the accumulation of rounding errors in uniform precision as
where , , and ; 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 ,
The notation satisfies
where denotes a possibly different quantity of the same form as . We omit the prime in subsequent calculations, in accordance with the convention that each occurrence may have a different value. With , it follows that . Since , we obtain
Thus plays the same role for as does for . The bound (2.1) retains all orders of unit roundoff and holds under the assumption .
Define
If , Bernoulli’s inequality gives . Taking reciprocals therefore yields
where rightmost upper bound reduces to when . Furthermore, implies , so the preceding bound gives
Consequently,
The first-order estimate is useful only when , just as the first-order approximation requires in uniform precision. We will also use
where is the modest positive constant and .
Block Householder QR with WY representation
The classical Householder QR algorithm factorizes an matrix into an orthogonal matrix and an upper triangular matrix by successively applying Householder reflections. At each step , a Householder reflector zeros out the subdiagonal entries of the -th column of , where is the Householder vector and is the corresponding scalar. The reflector is then applied to the remaining columns of the matrix. After steps, the product 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 Householder reflectors as , where and are 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 . At a given block step, the next columns form a panel. The panel factorization constructs the corresponding 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: , , and block size .
Output: and panel WY factors , where .
for do
Factor the panel by Householder QR, storing the Householder vectors in and the corresponding scalars in
Form the WY factors and from so that the product of the panel reflectors is
if then
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 and then factorized by Householder QR to build the WY representation in precision . The resulting panel matrices, including the Householder basis and the WY factor, are subsequently cast back to so that the trailing matrix update can be performed by low-precision matrix–matrix operations with 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 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 , despite extensive use of inside each panel.
New Reduced/Mixed Precision Variants
Revising the strategy above, we first investigate whether Householder QR can run uniformly in without overflow or underflow while improving performance. We then introduce a mixed precision approach, mpWYQR, achieving accuracy in terms of residual and LOO, with substantially fewer 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, and , so that only and the small triangular factor need to be stored. We retain the more general 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 . 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 setting.
To compute , we first evaluate the squared norm of the tail, , and then form [11]. Thus, we avoid unnecessarily computing the intermediate quantity , saving one square-root operation and reducing the overflow and underflow risk. After implementing the revised approach, we first use throughout Algorithm 2.1, call it the rWYQR approach, and compare it with the geqrf routine in for fp16. Table 3.1 shows the effects of norm scaling on time, LOO, and residuals. The test matrices are generated with uniformly randomly distributed elements from the range . 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 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, , residual, , and runtime.
| Method | Time (s) | |||
| geqrf | ||||
| rWYQR | ||||
| geqrf | ||||
| rWYQR |
Table 3.1. Performance and accuracy results for for various 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 speedup for a matrix. When we increase the large dimension to , we still observe order error even with norm scaling, while still achieving more than 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 .
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 , we perform both in and use 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 . In the second configuration, denoted mpWYQR, we implement Algorithm 3.1 with , corresponding to the mixed-precision implementation presented in § 3.2.
Algorithm 3.1: Mixed-precision Householder reflector construction
Input:
Output: ,
\hfill norm in , result converted to
\hfill norm in , subtraction and division in
\hfill
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 and , computed using fp16 for the low-precision operations, against and computed in fp32. Although mpBQR3 gives more accurate and in most cases, the overall factorization errors remain similar. For instance, while the reported relative errors in for mpBQR3 and mpWYQR differ by 0.1135 for , their LOO and QR errors differ by at most , which is smaller than one fp16 unit roundoff, . We anticipate that the reason for this behavior is that, during the calculation of in line 3 of Algorithm 3.1, the inaccuracy from the computation of from the previous step can be subject to cancellation due to the inner product computation . This shows that using high precision for every inner product, as in mpBQR3, is unnecessary; instead, one can use to compute the norm, which can significantly improve performance. The importance of using 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 and , leading to highly inaccurate QR factors. The dashed entries in rWYQR show that the norm evaluations in can easily overflow for large problems.
| Method | Time (s) | |||||
| (4000, 4000) | rWYQR | 8.55713E-02 | 9.95483E-02 | 0.67257 | 0.03590 | 0.33285 |
| (4000, 4000) | mpWYQR | 5.99670E-03 | 7.92694E-03 | 0.63347 | 0.03217 | 0.31996 |
| (4000, 4000) | mpBQR3 | 5.90515E-03 | 7.70950E-03 | 0.51997 | 0.02832 | 0.56634 |
| (12000, 12000) | rWYQR | 5.42969E-01 | 6.17676E-01 | 0.81345 | 0.02097 | 1.60879 |
| (12000, 12000) | mpWYQR | 5.65338E-03 | 7.54547E-03 | 0.67193 | 0.01851 | 1.50179 |
| (12000, 12000) | mpBQR3 | 5.54276E-03 | 7.40814E-03 | 0.68853 | 0.01968 | 5.09183 |
| (36000, 36000) | rWYQR | – | – | – | – | – |
| (36000, 36000) | mpWYQR | 3.51143E-03 | 5.52368E-03 | 0.72925 | 0.01332 | 30.14354 |
| (36000, 36000) | mpBQR3 | 3.34358E-03 | 5.51224E-03 | 0.74434 | 0.01301 | 58.15787 |
| (42000, 42000) | rWYQR | – | – | – | – | – |
| (42000, 42000) | mpWYQR | 3.00980E-03 | 5.22614E-03 | 0.73835 | 0.01162 | 57.78656 |
| (42000, 42000) | mpBQR3 | 3.15475E-03 | 5.15747E-03 | 0.74534 | 0.01252 | 79.60925 |
Table 3.2. Performance and accuracy results for , where .
The numerical experiments show that the uniform implementation achieves lower accuracy than , indicating that norm evaluations in introduce rounding errors that degrade the quality of the Householder reflectors.
Error analysis in § 4 shows that computing the norm in rather than 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 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 for both norm evaluations. The remaining parts of the algorithm are carried out in , and the resulting LOO remains of order .
Numerical experiments show that the Householder reflector determines accuracy. In particular, if any precision 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 . This motivates a careful precision assignment: the norm computation in the reflector construction uses a accumulator, the resulting scalar is converted to , and the remaining reflector quantities are formed and stored in . The more computationally intensive operations, such as the matrix–matrix multiplications in the WY representation update, are then carried out in .
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 th reflector, with active vector length , each -norm requires high-precision additions and multiplications and one square root, followed by one scalar conversion to . Since the conversions occur in registers, they introduce no additional memory traffic or memory. Summed over all reflectors, the high-precision work is flops plus square roots and scalar conversions. This is lower order than the leading factorization cost . In the tall-skinny regime (), the relative high-precision work remains .
We now compare the computational and communication costs of mpBQR3 and mpWYQR. Let be the block size, assume for simplicity that , and let be the active panel height at block step . A key structural difference is that mpWYQR uses a geqrt-type blocked panel kernel in , whereas mpBQR3 uses a geqrf/HQR-type panel factorization and forms the WY representation in before casting it to . 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 high-precision flops at step , for a total of high-precision flops overall. Its trailing updates contain low-input block-FMA (bFMA) flops, whose accumulation is performed in . In contrast, mpWYQR restricts to norm computations, while the remaining, more computationally dominant operations are carried out in . 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 to .
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 entries. Since , the additional conversion traffic is 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 scalar register conversions, with no additional memory traffic. Overall, mpWYQR is cheaper in both computational and communication costs than mpBQR3; see Table 3.3.
| Algorithm | cost | /bFMA cost | Conversion traffic |
| mpBQR3 | bFMA | array entries | |
| mpWYQR | 0 array; register |
Table 3. Cost comparison of mpBQR3 and mpWYQR, where .
Error Analysis
Let with . The Householder QR factorization triangularizes by applying a sequence of Householder matrices. Given a nonzero vector , the Householder matrix (or Householder reflector) is of the form
which zeros out the elements of by columns. The Householder matrices are never formed explicitly in practice, because storage and computations are feasible by solely using the Householder vector .
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 be nonzero, with , and define
In floating-point arithmetic with and , the computed Householder vector and scaling factor produced by Algorithm 3.1 satisfy
In particular,
Consequently, when the corresponding are small, the first-order estimates are
Proof. For the input vector , the standard inner-product error expansion [14 sect. 3.1, eq. (3.2)] and the nonnegativity of the summands give
Let denote the norm of 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
Thus satisfies . Since the sign choice gives and prevents cancellation, we also have . For the subsequent subtraction, we have
It follows that
Combining the preceding bounds yields
In particular, .
To analyze the normalization step, define , the exact normalization of the computed vector, and . By (6), we have . Since , we have , and hence
Taking positive square roots shows that lies between and . Hence lies between and , while lies between and . For , combining this with (7) gives
Zero components of remain zero in . Repeating the norm analysis in (5) for gives
Then the low-precision divisions satisfy
Collecting these errors in yields
For , combining (8)–(10) and then using (7) gives
Since and zero components are preserved,
where .
For the final dot product, the low-precision analogue of (4) gives
Set . Since is diagonal, implies . Together with , the reverse triangle inequality therefore gives
Thus, using , we have
The final low-precision division and then give
Combining (9) and (11)–(13) gives
Since and , it follows that
Finally, taking Euclidean norms in the componentwise bound for and expanding as in § 2.1 gives the remaining statements. □
Lemma 4.1 moves the dimension-dependent errors in the two norm evaluations to , while the low-precision term proportional to remains in the bound for , since the inner product is still evaluated in . Next, we provide rounding error bounds for the application of a Householder matrix to a vector.
Lemma 4.2. Let define the exact Householder matrix associated with a nonzero as in Lemma 4.1, and let be the computed quantities produced by Algorithm 3.1. Let , and consider the computed application
where all arithmetic in the application is performed in . Then
where the all-orders bound is
When is small, this gives the first-order estimate
Proof. Set and separate the error in the stored reflector from the rounding error in its application as
We first bound using the quantities from the proof of Lemma 4.1. Define
Since , we have . By (11) and (13),
Moreover, and , so
To compare with , first note the division-error bounds in (10) and the bounds on in (12) give
where denote the diagonal entries of . For , we have . Combining this with (7) and (8) yields
Zero components of remain zero in , and hence
Using and , we obtain from (18)
We now hold and fixed and analyze their low-precision application to . For the dot product, we have
In particular, . The standard componentwise error bounds for the two multiplications and the final subtraction [14 sect. 2.2] give
Combining (20) and (21), and using
yields
Taking Euclidean norms and applying the Cauchy–Schwarz inequality gives
By (18), , and therefore
Combining (17), (19), and (22) gives , with defined in (15). For , set
Then . The identity , together with the preceding estimate, gives the required Frobenius-norm bound and proves (14). For , the computed result is zero and we take . Finally, when , expanding the 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 and consider Householder transformations
whose computed reflector quantities are produced by Algorithm 3.1. Let . Then the computed result satisfies
with the all-orders columnwise and normwise bounds
If is small, the corresponding first-order estimate is
and the same factor bounds .
Proof. For each column , Lemma 4.2 gives
Since every is orthogonal,
Setting 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 .
For the active column used to construct a reflector, we have , and the stored diagonal entry satisfies . Thus Lemma 4.3 yields the following QR backward-error result by the standard argument [14 Thm. 19.4].
Theorem 4.4. Let be the computed upper trapezoidal factor of obtained from the Householder reflector constructions and sequential applications analyzed above. Then there exists an orthogonal such that
where
If is small, the first-order estimate is
The matrix is given explicitly by , where is the exact Householder matrix associated with the th active column.
Finally, we present results concerning the error in the computed , the factorization residual, and the loss of orthogonality.
Theorem 4.5. Under the assumptions of Theorem 4.4, let be the result of applying the same computed reflector quantities to in the order used to form , and set . Then
Moreover,
and
If is small, the respective first-order estimates are
and
The orthogonal matrix is the one in Theorem 4.4.
Proof. Applying Lemma 4.3 to and transposing the result gives (25). Let
By Theorem 4.4 and (4.24),
Therefore,
which gives (26). Finally,
so
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 . 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 dependence is replaced by , up to constants and powers of the probability parameter [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
may be replaced, schematically, by terms of order . 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 , the panel QR factorization and WY representation are formed in , and the WY factors are cast back to so that the trailing updates can use low-precision matrix products with higher-precision accumulation. If is the block size and is the number of column blocks, their error bound for the computed thin orthogonal factor has the leading form
Since and , 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 more aggressively: only the two norm evaluations in the reflector construction are carried out in , while the remaining reflector construction, reflector application, and WY-style updates are governed by . Consequently, the deterministic bounds in Theorems 4.4 and 4.5 do not predict high-precision accuracy; they predict -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 , 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 .
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 with uniformly random elements in . All matrices are scaled from the right to prevent overflow and/or underflow. A fixed block size of is used throughout all experiments, and the precision pair 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, , residual, , and runtime.
Table 5.1 shows experiments on square random matrices with sizes ranging from to 45000. For small matrices (), 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 speedup over sgeqrt and more than 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 , whereas sgeqrt error is bounded by . Compared with mpBQR2, mpWYQR yields slightly less accurate results, again as expected. However this difference is between and , which can be neglected considering that both algorithms are using fp16 as the working precision and unit roundoff of fp16 is . 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 (, , , ), 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 | 7.92003E-07 | 9.82351E-07 | 1.27310E-06 | 1.86841E-06 | 3.42155E-06 | 5.54632E-06 |
| sgeqrt | 1.02469E-06 | 1.25968E-06 | 1.59754E-06 | 2.32236E-06 | 4.17879E-06 | 6.72147E-06 |
| sgeqrt Time (s) | 0.19498 | 0.16725 | 0.35354 | 2.34586 | 24.34429 | 134.03649 |
| rWYQR | 1.70898E-02 | 3.21960E-02 | 8.55713E-02 | 3.93311E-01 | — | — |
| rWYQR | 2.04315E-02 | 3.78113E-02 | 9.95483E-02 | 4.41895E-01 | — | — |
| rWYQR Time (s) | 0.22967 | 0.22002 | 0.33285 | 1.24347 | — | — |
| mpWYQR | 5.87082E-03 | 5.98907E-03 | 5.99670E-03 | 5.83267E-03 | 4.18854E-03 | 2.92206E-03 |
| mpWYQR | 7.68280E-03 | 7.94220E-03 | 7.92694E-03 | 7.79343E-03 | 6.08826E-03 | 5.12695E-03 |
| mpWYQR Time (s) | 0.11587 | 0.20817 | 0.31996 | 1.17185 | 9.98710 | 72.41314 |
| mpBQR3 | 5.53513E-03 | 5.84412E-03 | 5.90515E-03 | 5.70679E-03 | 4.31061E-03 | 2.96021E-03 |
| mpBQR3 | 7.08008E-03 | 7.59888E-03 | 7.70950E-03 | 7.72095E-03 | 6.06537E-03 | 5.05066E-03 |
| mpBQR3 Time (s) | 0.07670 | 0.21081 | 0.56634 | 3.59873 | 28.64521 | 92.30898 |
Table 5.1. Performance and accuracy results for , where .
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 or , 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 faster than mpWYQR, especially when is small. As increases, the speedup drops to around . In contrast, when , mpWYQR achieves more than 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 speedup with at most difference in accuracy. Last but not least, we observe the effect of fp32 norm computation even for , when rWYQR fails due to overflow and mpWYQR continues.
| Method | (10000, 128) | (20000, 128) | (40000, 128) | (100000, 128) | (320000, 128) | (330000, 128) | |
| sgeqrt | 2.76481E-07 | 2.98540E-07 | 3.59624E-07 | 5.89988E-07 | 1.89635E-06 | 1.96205E-06 | |
| 1.76102E-07 | 2.01938E-07 | 2.43083E-07 | 4.36624E-07 | 1.35620E-06 | 1.39062E-06 | ||
| Time (s) | 0.04000 | 0.09250 | 0.08043 | 0.25604 | 0.19918 | 0.14789 | |
| rWYQR | 6.62231E-02 | 2.82715E-01 | – | – | – | – | |
| 4.08630E-02 | 1.14807E-01 | – | – | – | – | ||
| Time (s) | 0.06461 | 0.02027 | – | – | – | – | |
| mpWYQR | 1.10340E-03 | 8.78811E-04 | 7.93457E-04 | 7.59125E-04 | 7.36237E-04 | 6.69003E-04 | |
| 1.82986E-04 | 1.45435E-04 | 9.25660E-05 | 7.43270E-05 | 5.67436E-05 | 7.03335E-05 | ||
| Time (s) | 0.06049 | 0.01582 | 0.02771 | 0.05797 | 0.16621 | 0.15726 | |
| mpBQR3 | 9.64642E-04 | 7.63416E-04 | 6.63757E-04 | 6.51836E-04 | 6.09398E-04 | 6.52313E-04 | |
| 1.90377E-04 | 1.46985E-04 | 8.95858E-05 | 7.54595E-05 | 5.94854E-05 | 7.33137E-05 | ||
| Time (s) | 0.06201 | 0.14174 | 0.17388 | 0.44792 | 0.82904 | 0.79343 |
Table 5.2. Performance and accuracy results for with .
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 , , , where denotes the number of rows, denotes the number of block vectors, and denotes the number of columns in each block vector. We set , , and for glued matrices; , , for monomial matrices; and , , for piled matrices. We ran each experiment 5 times and present the average results in Figure 5.1–Figure 5.3.

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 . From top to bottom, the rows correspond to sgeqrt, rWYQR, mpWYQR, and mpBQR3.

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 . 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 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 faster than mpBQR3 (Figure 5.2). Across all the figures, mpWYQR performs best when is moderately small (around 3000), regardless of the condition number, and relatively worse when is even smaller.

Figure 5.2. Loss of orthogonality (left), relative QR factorization error (middle), and runtime (right) for monomial matrices with varying block size and number of rows . 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 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 , 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 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 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 , 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]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]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]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]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]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]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]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]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]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]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]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]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]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]N. J. Higham. Accuracy and Stability of Numerical Algorithms. Applied Mathematics. SIAM Publications, Philadelphia, second edition, 2002. doi:10.1137/1.9780898718027.DOI
- [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]A. S. Householder. Unitary triangularization of a nonsymmetric matrix. Journal of the ACM, 5(4):339–342, 1958.DOI
- [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]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]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]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]K. Lund, E. Oktay, E. Carson, and Y. Ma. BlockStab, 2024. URL: https://github.com/katlund/BlockStab.
- [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]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]F. Rotella and I. Zambettakis. Block Householder transformation for parallel QR factorization. Appl. Math. Lett., 12(4):29–34, 1999.DOI
- [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]J. H. Wilkinson. Rounding Errors in Algebraic Processes. SIAM, second edition, 2023. doi:10.1137/1.9781611977523.DOI
- [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]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.