Skip to content

Givens and Householder explorer

A Givens rotation or a Householder reflector is built from one column of the matrix, the pivot column xx, so that it puts xx on the first axis. Every other column of the rows it touches is then carried along: the same operator is applied to it, and it rotates or reflects without landing on any axis. The figures in Givens and Householder in pictures show only the pivot column. Here you can move both.

The operator is computed the way MTL5 computes it, in the number format you choose. Each multiply, add, divide and square root is rounded to the format, so the operator you see is the one a factorization in that format would apply. The arrows’ hollow rings show where an exact operator would put each vector.

Operator
Number format

How r is formed
Vectors (rounded to the format)
x
y

Drag the arrow tips. ● computed image of x, ○ where an exact operator puts it; ● and ○ the same for y. Ticks on the axes mark the format's values when they are few enough to draw.

The pivot column lands on the axis; the carried one is only moved. The operator is chosen for xx, so xx ends at (∥x∥,0)(\lVert x \rVert, 0) up to rounding. yy turns through the same angle, or flips across the same mirror, and keeps its length only as well as the operator is orthogonal. The tables report that as (∥y′∥−∥y∥)/∥y∥(\lVert y' \rVert - \lVert y \rVert) / \lVert y \rVert, in units of the format’s unit roundoff uu at 1.

A rounded operator is not orthogonal. For a rotation, c2+s2−1c^2 + s^2 - 1 is the stretch it applies to every vector. In fp8 E4M3 at the starting position, x=(2.5,1.5)x = (2.5, 1.5), rr rounds to 2.75 against an exact 2.92, so c=a/rc = a/r rounds to 0.9375 and c2+s2−1=0.20c^2 + s^2 - 1 = 0.20. The reflector for the same xx in the same format has ∥HTH−I∥=0.025\lVert H^TH - I \rVert = 0.025.

Squaring overflows before the answer does. MTL5’s GMRES forms r=a2+b2r = \sqrt{a^2 + b^2} without scaling. In binary16, set x=(300,200)x = (300, 200) (view ±400): a2=90000a^2 = 90000 is beyond the largest binary16 value, 65504, so r=∞r = \infty, c=s=0c = s = 0, and the “rotation” is the zero matrix. Both columns vanish. Choose scaled by max(|a|, |b|) first and the same xx gives r=360.75r = 360.75. In fp8 E4M3, which saturates instead of overflowing, x=(20,15)x = (20, 15) gives r=22r = 22 against an exact 25. The scaled form is the one lapy2 and MTL5’s householder() use.

Squaring underflows too. In binary16, set x=(0.0001,0.0001)x = (0.0001, 0.0001): both squares are below the smallest subnormal, the sum is zero, and the unscaled rotation is the identity. The scaled one rotates correctly.

The reflector can decline. MTL5’s householder() returns the identity when bb is below half an ulp of aa, and when the computed reflector would be further from orthogonal than leaving xx alone. In fp8 E4M3, x=(4,0.25)x = (4, 0.25) takes the first exit, while the rotation still turns by s=0.0625s = 0.0625. The readout names the test that fired.

The entry that should be zero. Applying the computed operator to xx leaves a small second component. Factorizations do not use it: MTL5’s GMRES writes rr and an exact 0, and qr_factor stores the reflector’s vector below the diagonal in its place. The rest of the row pair, the carried columns, gets no such repair.

Posit precision tapers. posit<16,2> has 11 fraction bits for magnitudes between 1/16 and 16, and fewer further out: 9 near 2000. Move yy far from the origin (view ±4000) and compare its error with binary16’s, whose relative precision is the same across its normal range.

The page holds every value as a JavaScript double and rounds each operation’s result once to the chosen format. For formats of 16 bits or fewer, that gives the correctly rounded result: rounding twice is harmless when the wider format has at least 2p+22p + 2 significand bits, and a double has 53. Posits are rounded in their encoding, as the posit standard requires: never to zero, and values beyond the largest posit go to it.

The arithmetic is in docs-site/src/components/gh/. It is checked by npm test in docs-site/ against test vectors that tools/givens_householder_svg.py computes in exact rational arithmetic, the same code that draws the figures. The vectors cover rounding, square roots, both forms of the rotation, the reflector and eight steps of the drift figure, in ten formats.

The operation sequences follow MTL5:

  • Rotation, from include/mtl/operation/givens.hpp: r=a⋅a+b⋅br = \sqrt{a \cdot a + b \cdot b}, c=a/rc = a/r, s=b/rs = b/r, and G(u,w)=(cu+sw,  cw−su)G(u, w) = (c u + s w,\; c w - s u). The scaled variant divides aa and bb by max⁡(∣a∣,∣b∣)\max(\lvert a \rvert, \lvert b \rvert) before squaring.
  • Reflector, from include/mtl/operation/householder.hpp, for n=2n = 2: scale by max⁡(∣a∣,∣b∣)\max(\lvert a \rvert, \lvert b \rvert); Parlett’s v0=−σ/(x0+∥x∥)v_0 = -\sigma / (x_0 + \lVert x \rVert) for x0>0x_0 > 0; τ=−v0/∥x∥\tau = -v_0 / \lVert x \rVert; v=(1,x1/v0)v = (1, x_1 / v_0); and the identity fallbacks described above. It is applied as y−τv(vTy)y - \tau v (v^T y).