Skip to content

Householder reflector forms

householder, apply_householder_left, apply_householder_right, qr_factor and lq_factor can build and apply a Householder reflector in either of two forms. Both produce a valid factorization with the same signs, and they produce different bits. The second form is opt-in, for callers that need to reproduce a hand-written textbook QR or LQ exactly.

From 5.22.0 the default reflects onto LAPACK’s sign, −sign(x₀)·‖x‖, where it used to reflect onto +‖x‖ for x₀ > 0 (#672). See The sign of R below for what changed and how to get the old non-negative diagonal back.

#include <mtl/operation/qr.hpp>
mtl::qr_factor(A, tau); // default: LAPACK form
mtl::qr_factor(A, tau, mtl::tag::textbook_reflector{}); // opt-in: textbook form

A reflector H = I − τ·v·vᵀ maps a column x onto a multiple of e₁. The algebra fixes H up to a sign, and leaves open how v is scaled and how the sums are formed. MTL5’s default follows LAPACK’s dlarfg, and the textbook (Golub & Van Loan §5.1) makes different choices:

default (LAPACK form)textbook form
‖x‖x scaled by an exact 2⁻ᵉ, 2ᵉ ≤ max|xᵢ| < 2ᵉ⁺¹, before squaringΣxᵢ², unscaled, from zero, ascending i
vnormalized, v(0) = 1not normalized: v = x, v(0) = x₀ − α
reflected ontoα = −sign(x₀)·‖x‖, so v₀ = x₀ − αα = −sign(x₀)·‖x‖
scalarτ = −v₀/α = 1 + |x₀|/‖x‖vᵀv, summed from zero
column updateA(i,j) -= τ·v(i)·wf = (2·s)/vᵀv, then A(i,j) -= f·v(i)
R’s diagonal−sign(x₀)·‖x‖, the reflector’s β, stored; x₀ when τ = 0 (the tail is already zero, H = I)−sign(x₀)·‖x‖: α, stored

In both, sign(0) = +1. Each column is rounded through a different sequence of operations, so R differs in the last bits. Q·R = A and Q is orthogonal either way.

That doesn’t matter to most callers. It matters to a caller whose results are pinned to the textbook form. branes-ai/cortex is porting a multi-state-constraint Kalman filter (MSCKF) to MTL5 and requires every stage to reproduce the pre-port output (#559). It uses the textbook form twice: a QR that keeps only R, for the square-root covariance, and a projection onto the left null space of the feature Jacobian, built from three reflectors applied across [H_f | H_x | r]. A prototype on the default form measured:

  • in the stage benchmarks, 10 of 117 outputs moved. The null-space projection changed at O(1), because a different reflector sign gives a different, equally valid basis;
  • on EuRoC V2_03, 1 of 16,265 update decisions flipped, and the trajectory diverged from there (ATE 0.269 → 0.289 m).

That prototype predates 5.22.0, when the default reflected onto the opposite sign. The two forms now agree on the sign, but they still round differently, so the tag is still what reproduces the textbook bits.

This is the same situation as summation order in Cholesky, and it has the same kind of remedy: a tag that selects the other form.

namespace mtl::tag { struct textbook_reflector {}; } // <mtl/tag/reflector_form.hpp>
callformLAPACK
householder(x)default; returns {v, τ} with v(0) = 1—
householder_reflector(x)default; returns {v, τ, β}, H x = β e₁—
householder(x, tag::textbook_reflector{})textbook; returns {v, vtv, alpha}—
apply_householder_left(A, v, τ, row, col)default—
apply_householder_left(A, v, vtv, row, col, tag::textbook_reflector{})textbook—
qr_factor(A, tau)defaultgeqrf when MTL5_HAS_LAPACK and A is a float/double dense matrix
qr_factor(A, tau, tag::textbook_reflector{})textbooknever
apply_householder_right(A, v, τ, row, col)default—
apply_householder_right(A, v, vtv, row, col, tag::textbook_reflector{})textbook—
lq_factor(A, tau)default—
lq_factor(A, tau, tag::textbook_reflector{})textbook—

The tagged householder returns a textbook_reflection<T>, which supports structured bindings:

auto [v, vtv, alpha] = mtl::householder(x, mtl::tag::textbook_reflector{});

householder_reflector(x) returns the β that the default reflector maps x onto, alongside v and τ. householder(x) is a wrapper over it that returns {v, τ}, so existing two-name structured bindings keep compiling. When τ = 0 (H = I), β is x₀.

The default qr_factor, lq_factor and hessenberg_factor, and the tridiagonalization in eigen_symmetric, store β as the pivot: R(k,k), L(k,k), or the subdiagonal entry. They apply the reflector to the trailing columns (or rows) only. That is what LAPACK’s xGEQR2, xGELQ2, xGEHD2 and xSYTD2 do with dlarfg’s β, and what the textbook form does with α.

Until #678 the default applied the reflector to the pivot column as well, which recomputed the pivot as x₀ − τ(vᵀx). In floating point that only adds a rounding. In fixed point the products v(i)·x(i) of a column near the type’s resolution round to zero, so the pivot came out 0 although β is representable, and qr_solve divided by it. The decompositions study found this in fixpnt<16,8> and fixpnt<32,16> (stillwater-sc/mp-numerics#20). Q depends only on v and τ, so it is unchanged. In float and double the pivots, and what is computed from them, move by a rounding.

A column is skipped when !(norm > 0): it is zero, or it contains a NaN. The tagged householder then returns vtv = 0, and the tagged apply_householder_left and apply_householder_right do nothing when !(vtv > 0), which also covers a vᵀv that underflows. These are the tests a hand-written loop uses, so NaN handling matches too: a NaN column is left as it is, not propagated through a reflector.

A column that is zero below the pivot is not skipped. If x = (x₀, 0, …, 0) with x₀ > 0, the textbook reflector is H = I − 2e₁e₁ᵀ, which maps x₀ to −x₀. The default returns τ = 0 there and leaves the column alone.

For each column k it computes the textbook reflector of A(k:m−1, k), skips the column if the reflector says so, applies it to columns k+1 onward, and writes R(k,k) = α. So R, on and above the diagonal, is bit-identical to a hand-written textbook QR, including its signs.

Below the diagonal and in tau it stores the same reflector in MTL5’s packed form: v/v(0), with τ = 2·v(0)²/vᵀv. v(0) = x₀ − α can’t be zero, because α has the opposite sign to x₀, so |v(0)| = |x₀| + ‖x‖. Because of this, qr_extract_Q and qr_solve work on the result unchanged. The Q they produce agrees with the textbook Q to rounding, not to the bit, since the packed form is a rescaling of v. A caller that needs Q, or Qᵀb, bit for bit should apply the reflectors with the tagged apply_householder_left as the original code does.

A skipped column gets τ = 0 and keeps its entries, like the default’s identity reflection.

apply_householder_right(A, v, vtv, row, col, tag) is the row mirror of the left update. It computes A := A·H for rows row onward and columns col .. col+v.size()−1. Each row i is updated as

s = Σ_j A(i, col+j)·v(j) from zero, ascending j
f = (2·s)/vᵀv
A(i, col+j) -= f·v(j)

For a real reflector H = Hᵀ, so there is no conjugate to place, unlike the default’s complex path.

lq_factor(A, tau, tag) is the row mirror of the tagged qr_factor. For each row k it computes the textbook reflector of A(k, k:n−1), skips the row if the reflector says so, applies it on the right to rows k+1 onward, and writes L(k,k) = α. So L, on and below the diagonal, is bit-identical to a hand-written textbook LQ. Above the diagonal and in tau the reflector is stored in the packed form, as in QR, so lq_extract_Q works on the result unchanged, with Q matching the textbook Q to rounding. lq_factor has no LAPACK path in either form.

  • Real element types only. The textbook form has no single complex counterpart, so the tagged overloads static_assert on a complex type.
  • No scaling. The squares are formed as a hand-written loop forms them, so in double entries above about 1e154 overflow and entries below about 1e−154 underflow. The default’s scaling avoids both. That’s the cost of reproducing the loop.
  • QR and LQ only. The Hessenberg reduction, the eigensolvers and the SVD use the default form only.
  • No accumulator. The point of the tag is a fixed order of operations, so the tagged overloads don’t take an Accumulator.

If the code being ported looks like this:

for (k = 0; k < std::min(m, n); ++k) {
double norm = 0;
for (i = k; i < m; ++i) norm += A[i][k] * A[i][k];
norm = std::sqrt(norm);
if (!(norm > 0)) continue;
double alpha = A[k][k] >= 0 ? -norm : norm;
for (i = k; i < m; ++i) v[i] = A[i][k];
v[k] -= alpha;
double vtv = 0;
for (i = k; i < m; ++i) vtv += v[i] * v[i];
if (!(vtv > 0)) continue;
for (j = k + 1; j < n; ++j) {
double s = 0;
for (i = k; i < m; ++i) s += v[i] * A[i][j];
double f = (2 * s) / vtv;
for (i = k; i < m; ++i) A[i][j] -= f * v[i];
}
A[k][k] = alpha;
for (i = k + 1; i < m; ++i) A[i][k] = 0;
}

then this is its MTL5 equivalent, bit for bit on and above the diagonal:

mtl::vec::dense_vector<double> tau;
mtl::qr_factor(A, tau, mtl::tag::textbook_reflector{});
auto R = mtl::qr_extract_R(A); // exact zeros below the diagonal

A null-space projection, or anything else that applies reflectors to a matrix of its own, uses the two lower-level calls:

using mtl::tag::textbook_reflector;
auto [v, vtv, alpha] = mtl::householder(col, textbook_reflector{});
mtl::apply_householder_left(M, v, vtv, row, 0, textbook_reflector{});

As with Cholesky, the bits match only if FP contraction is the same in both codebases. With FMA available a compiler may fuse s += v*a or a -= f*v, and it decides per loop. MTL5’s tests compile with -ffp-contract=off when they compare bits; see condition 2 in the Cholesky page.

situationuse
Results must match an existing textbook-form implementationtag::textbook_reflector
Results must match LAPACK’s geqrf, signs includedthe default
Code relies on the non-negative diagonal MTL5 gave before 5.22.0the default, then qr_normalize_signs or lq_normalize_signs
Columns may be very large or very small in magnitudethe default, which scales
Complex matricesthe default
You need the same bits in LAPACK and non-LAPACK buildstag::textbook_reflector, because it never dispatches
Nothing is pinnedthe default
mtl::vec::dense_vector<double> x{3.0, 4.0};
auto [v, tau] = mtl::householder(x); // H*x = -5 e1
// v == {1, 0.5}, tau == 1.6
auto [w, vtv, alpha] = mtl::householder(x, mtl::tag::textbook_reflector{});
// alpha == -5, w == {8, 4}, vtv == 80: H*x = -5 e1

Both reflections are exact here, and both reflect onto −5. Before 5.22.0 the default reflected this x onto +5, with Parlett’s v₀ = −σ/(x₀ + ‖x‖) for x₀ > 0. That made R’s diagonal non-negative, but for a small tail v₀ is small and v(1) ≈ −2x₀/x(1) is large. In a tapered or fixed-point type, v and 1 + v² then land where the type has few bits, and the reflector lost orthogonality: the Givens and Householder study measured 8.0×10⁵ ε for posit<64,2> and 512 ε for posit<32,2>, against 4.1 and 3.8 ε with LAPACK’s sign. With LAPACK’s sign every |v(i)| ≤ 1.

So from 5.22.0 a QR has R(k,k) < 0 wherever the pivot entry x₀ was ≥ 0, as LAPACK’s geqrf has. The generic path and the geqrf path of a LAPACK build now agree, diagonal signs included; before, they disagreed wherever x₀ > 0. A caller that uses only Q·R, R·Rᵀ, or the span of Q’s columns won’t notice. A caller that reads the sign of R’s diagonal, or compares Q or R entrywise, will. To get the old convention back, normalize the explicit factors:

mtl::qr_factor(A, tau);
auto Q = mtl::qr_extract_Q(A, tau);
auto R = mtl::qr_extract_R(A);
mtl::qr_normalize_signs(Q, R); // R(k,k) >= 0; Q*R unchanged

lq_normalize_signs(L, Q) does the same for an LQ. For a full-rank A the normalized factorization is the unique one with a positive diagonal. The values match the pre-5.22.0 default to rounding, not to the bit. The packed factor can’t store a negated column of Q, so the helpers work on the extracted Q and R (or L and Q).

A = | 0 1 1 | textbook R = | 0 1 1 | tau = (0, 2, 2)
| 0 2 3 | | 0 −2 −3 |
| 0 0 4 | | 0 0 −4 |

Column 0 is zero, so it is skipped. Column 1 is zero below its pivot, and the reflector I − 2e₁e₁ᵀ flips row 1. Column 2’s remaining entry 4 is reflected onto −4. The default leaves this matrix as it is, with τ = (0, 0, 0).

tests/unit/operation/test_householder_textbook.cpp compares bits (==) against serial reference loops written as above:

  • the tagged householder equals the reference on double, float and a class-typed scalar, for x₀ positive, negative and zero, and for a tail of zeros;
  • zero and NaN columns are skipped, and applying a skipped reflector leaves A untouched;
  • the tagged apply_householder_left equals the reference update with row and column offsets, on all three types, for a 40 × 85 [H_f | H_x | r] shape, and for a 300 × 2000 matrix that splits across a pool of 4 threads;
  • the tagged apply_householder_right equals the reference update with row and column offsets, on all three types, and for a 2000 × 300 matrix that splits across the pool;
  • the tagged qr_factor’s R equals the reference R for shapes from 1 × 1 to 81 × 81, plus 256 × 200, on all three types, and the tagged lq_factor’s L equals the reference L for the transposed shapes, plus 200 × 256;
  • the matrix above gives exactly the R and τ shown, and its transpose gives the transposed L under lq_factor;
  • qr_extract_Q and qr_solve work on the tagged result: Q·R reproduces A and Q is orthogonal to 1e−13, and a square system solves to 1e−11. lq_extract_Q works on the tagged LQ the same way: L·Q reproduces A to 1e−13;
  • qr_solve skips a column that the tagged qr_factor skipped for a NaN below the diagonal, and returns a finite solution of the system that was factored. Before #560’s review fix, qr_solve applied the τ = 0 reflector anyway and 0·NaN made the whole solution NaN;
  • the default and the textbook form produce different R, and different L, for the same matrix, though from 5.22.0 with the same signs.

The target is compiled with -ffp-contract=off. As a teeth check, five patched copies of the headers each fail the tests that should notice:

mutationfails
the update sums s in descending ithe apply_householder_left and qr_factor comparisons
the norm sums x² in descending ithe householder and qr_factor comparisons
qr_factor keeps the column’s own diagonal instead of writing αthe qr_factor comparison, the exact 3 × 3 case, and Q·R = A
the right update sums s in descending jthe apply_householder_right and lq_factor comparisons
lq_factor keeps the row’s own diagonal instead of writing αthe lq_factor comparison, and L·Q = A

(2·(s/vᵀv) in place of (2·s)/vᵀv is not a useful mutation: multiplying by 2 is exact, so the two round identically.)