Skip to content

QR and least squares across number systems

mp-numerics#14, part 1 of 6, in the series that stillwater-sc/mtl5#666 tracks. The operator study (#13, ../givens_householder/) measured one Givens rotation or one Householder reflector at a time. This one measures the factorizations built from them. It factors the same matrices in each number type by QR and solves the same least-squares problems by QR and by the normal equations. It then asks where each type stops being usable, and whether the method or the type decides that.

Part 1 covers the hardware IEEE types, posits and fixed point, 12 types in all. Part 2 adds the cfloat matrix, lns, takum, dd and qd. The later parts cover Hessenberg and Schur, the SVD, banded and sparse inputs, and the findings note for the MTL5 docs.

Terminal window
cmake --build build --target decompositions_study
./build/benchmarks/linalg/decompositions/decompositions_study results/
python3 benchmarks/linalg/decompositions/summarize.py results/
python3 benchmarks/linalg/decompositions/plot.py results/ figures/
  • Options: --quick runs a small sample. --family ieee,posit,fixpnt picks families; all of them run by default.
  • Run time: the full run takes about 11 minutes on one core. Most of it is the exact measurement and the qd condition numbers at n = 16 and 32 × 16.
  • Sidecars: each CSV has a .sysinfo sidecar, as in #13. It records the platform, the compiler, the sample counts, and the commits of mp-numerics, MTL5 and Universal, read when CMake configures.
  • Determinism: the committed results were made with GCC 15 on x86-64. The --quick CSVs are byte-identical between GCC 15 and Clang 21 there. A compiler that fuses a·b + c into an FMA (Clang on AArch64) changes the roundings, and with them the last digits.
  • Dependencies: plot.py needs matplotlib; summarize.py needs only the standard library.

Every matrix is generated in qd (212 bits) and rounded once into each type, so all twelve types factor the same matrices. Each error is measured against the matrix the type actually stores, not the qd original. Rounding into a narrow type can change the condition number a lot: Hilbert 8 × 8 has κ = 1.5×10¹⁰ in qd, 1.2×10⁷ once stored as posit<16,2>, and 9.6×10³ as fixpnt<16,8>. So the CSVs carry both the generated κ and kappa_stored, the stored matrix’s condition number computed in qd.

classAκ
randsvdU Σ Vᵀ, with U and V random orthogonal and σᵢ = κ^(−i/(n−1))10⁰ to 10²⁴ by decades; a type stops 4 decades past 1/ε
gradedU Σ: orthonormal columns scaled from 1 down to 1/κas randsvd
kahanU K, with K = diag(sⁱ)(I − c N), s = sin θ, c = cos θ, N the strictly upper ones; R is K up to signsθ = 1.2, 0.8, 0.4, 0.2
hilbert1/(i + j + 1)fixed by the size
  • Random orthogonal factors: Q of a matrix of uniforms in [−1, 1), with R’s diagonal made positive so that the distribution doesn’t depend on the signs qr_factor picks.
  • Seeds: inputs come from std::mt19937_64, seeded with an FNV-1a hash of the class, the size, the parameter and the sample index, as in #13. The seed doesn’t depend on the type, so every type sees the same matrices.
  • Samples: eight per (class, size, parameter); Hilbert has one.
  • Rounding into a type: a qd value is rounded by summing its two leading limbs in the type. That can round twice, but nothing depends on it, because every error is measured against the stored value.

QR runs on square 8 × 8 and 16 × 16 matrices. Least squares runs on 16 × 8 and 32 × 16. Each least-squares problem has a right-hand side b = A x for a random unit x (zero residual), and one with a residual r orthogonal to range(A), where ‖r‖ = ‖A x‖ (large, θ = 45°).

QRwhat it is
householder_mtl5mtl::qr_factor, dlarfg’s sign and power-of-two scaling (MTL5 5.22.0); Q from qr_extract_Q
householder_betathe same reflectors, but R(j,j) is set to the reflector’s β, as dgeqr2 does, instead of recomputed; sw::mp_numerics::qr_factor_stored_beta, the remedy tested (see Findings)
householder_textbookmtl::qr_factor(A, tau, tag::textbook_reflector): v = x − αe₁, unscaled and unnormalized
givens_mtl5sw::mp_numerics::givens_qr, column by column and bottom up, with rotations from MTL5’s mtl::math::givens_rotation
least squareswhat it is
qr_householdermtl::qr_factor, then mtl::qr_solve
qr_householder_betaqr_factor_stored_beta, then mtl::qr_solve
qr_givenssw::mp_numerics::givens_qr_solve: Qᵀb by the same rotations, then back substitution
normal_equationsAᵀA and Aᵀb formed in the type, then mtl::cholesky_factor and mtl::cholesky_solve

MTL5 has no Givens QR. givens_qr takes its rotations from MTL5, so a difference from householder_mtl5 comes from the method, not the rotation.

columnmeaning
bwd‖A − QR‖_F / ‖A‖_F
bwd_colmaxⱼ ‖(A − QR) eⱼ‖ / ‖A eⱼ‖, the columnwise backward error that Householder QR is proved to bound (Higham, Accuracy and Stability, Thm. 19.4)
orth‖QᵀQ − I‖_F
fwd‖x − x_ref‖ / ‖x_ref‖, where x_ref is the least-squares solution of the stored problem, by Householder QR in qd
q_identitysamples where Q came back exactly I
skippedsamples where some reflector was the identity (τ = 0), leaving its column as it was
nonfinitesamples with an infinity or NaN in the result
thrownsamples where the type threw. Here that means a fixed-point division by zero (see Findings)
breakdownnormal equations: Cholesky found AᵀA not positive definite in the type
singularthe stored A is rank deficient in qd, so the problem has no unique solution. All methods skip it

bwd, bwd_col and orth are formed exactly. Q, R and A are read out as Shewchuk expansions (exact.hpp), every entry of A − QR and QᵀQ − I is summed exactly, and the result is rounded once to double. The rows give the maximum and the median over the samples, and the tables quote them in units of the type’s epsilon().

familytypes
IEEEfloat, double, long double (x87 80-bit here)
positposit<8,2>, posit<16,2>, posit<32,2>, posit<64,2>, posit<16,1>
fixpntfixpnt<16,8> and fixpnt<32,16>, each modulo and saturating

fixpnt is built with FIXPNT_THROW_ARITHMETIC_EXCEPTION. Universal’s default is to print fixpnt_divide_by_zero and return maxpos (saturating) or 0 (modulo), which no later test can tell from a result.

Every method is backward stable at every κ. At n = 16, the worst columnwise backward error is 5.5 to 8.8 ε, and the orthogonality of Q is 11 to 17 ε. Householder with dlarfg’s sign is the tightest of the four, and the textbook reflector and Givens follow within a factor of two.

Least squares then splits on the method:

  • Zero residual:
    • QR stays accurate to about κ ≈ 1/ε: 10¹⁵ in double, 10¹⁹ in long double, at 32 × 16.
    • The normal equations stop at about √(1/ε) (10⁷ in double), because forming AᵀA squares κ. Past that, Cholesky breaks down.
  • 45° residual: every method stops near √(1/ε), QR included (10⁸ in double). QR’s error has a κ²ε·tan θ term of its own, so with a large residual the orthogonal method buys almost nothing over the normal equations. This is the classical result (Golub & Van Loan §5.3.8), reproduced in each type.

Posits: normwise stable, but not columnwise on graded columns

Section titled “Posits: normwise stable, but not columnwise on graded columns”

On randsvd matrices, QR in posits behaves like IEEE. In posit<16,2> through posit<64,2>, householder_mtl5 and givens_mtl5 stay within about 7 ε columnwise and 17 ε in orthogonality at every κ.

On graded matrices, where the columns span 1 down to 1/κ, the columnwise backward error grows with κ in every posit. Orthogonality is unaffected:

posit<64,2>, householder_mtl5, n = 16κ = 10⁴10⁸10¹²10¹⁶10²⁰
columnwise backward error16 ε237 ε2.6×10³ ε1.7×10⁴ ε1.6×10⁵ ε
(double at the same κ)4.1 ε3.8 ε5.7 ε5.1 ε
  • Rate: the error grows by about 10× every four decades of κ, which is κ^(1/4). That is a posit’s taper. With es = 2, a posit loses one fraction bit for every factor of 16 its magnitude moves away from 1, which is 3.3 bits per factor of 10⁴. A column of size 1/κ is held to fewer bits than ε counts, and its backward error grows to match.
  • Normwise: the backward error on the same matrices is 3.1 ε. The loss is confined to the small columns, which a normwise measure weighs by their size.
  • Givens shows the same growth (2.7×10⁵ ε at 10²⁰). This is the type, not the method.

So in a posit, Householder QR keeps its normwise guarantee but not the columnwise one that IEEE gives it. The columnwise guarantee is the one that makes it insensitive to column scaling. If an application’s columns differ greatly in scale, equilibrating them before factoring keeps the posit near 1, where it has its bits.

The textbook reflector loses orthogonality in tapered types

Section titled “The textbook reflector loses orthogonality in tapered types”

householder_textbook forms v = x − αe₁ and vᵀv unscaled. In posits that costs orthogonality even on well-conditioned randsvd matrices: 353 ε in posit<16,2>, 1.1×10⁵ ε in posit<32,2>, and 3.3×10⁹ ε in posit<64,2>, where dlarfg’s form stays at 10 to 11 ε. #13 measured this one reflector at a time. Here it carries into the factorization: on graded matrices the textbook form’s columnwise error reaches 1.1×10¹⁰ ε in posit<64,2>. In IEEE the two forms are within a factor of two.

Fixed point: MTL5’s qr_factor gives exact-zero pivots

Section titled “Fixed point: MTL5’s qr_factor gives exact-zero pivots”

In fixpnt<16,8> and fixpnt<32,16>, qr_solve after qr_factor divides by zero, while the same problems with β stored, or by Givens, never do:

typeqr_householderqr_householder_betaqr_givens
fixpnt<16,8>72 of 404 problems00
fixpnt<32,16>12 of 558 problems00

The cause is in qr_factor. It applies column j’s reflector to column j as well, so R(j,j) is recomputed as x₀ − τ(vᵀx) instead of being set to the β the reflector was built for. LAPACK’s dgeqr2 stores β and applies H to columns j+1 onward only, and so does MTL5’s own textbook path.

  • Why fixed point: its resolution is absolute. When a column has shrunk to a few ulps, the products v(i)·x(i) round to 0, so x₀ − τ(vᵀx) is 0 although β = ‖x‖ is representable.
  • Minimal case: x = (0, u, u, u, u) with u = 2⁻⁸ gives R(0,0) = 0, where β = −2u (test_householder_qr).
  • In floating point the recomputation only adds rounding.
  • What storing β changes: householder_beta and qr_householder_beta store it. That removes every zero pivot, and where fixed point gives a usable answer at all, it changes nothing material. Filed as mtl5#678.

Universal’s fixpnt hides the symptom by default. A division by zero prints fixpnt_divide_by_zero and returns maxpos (saturating) or 0 (modulo). In this study’s first run that showed up as a forward error of 426 that looked like a result. The study defines FIXPNT_THROW_ARITHMETIC_EXCEPTION to count such cases instead. Integer, einteger, erational and edecimal share the default; filed as universal#1894.

Apart from the zero pivots, fixed point is limited by its absolute resolution, not by the method:

  • Reach of QR least squares: κ ≈ 1 in fixpnt<16,8> and about 10² to 10³ in fixpnt<32,16>.
  • Rank: the graded and Kahan matrices often lose rank outright when rounded in. Their small entries fall below resolution, and kappa_stored turns infinite.
  • Modulo and saturating give identical QR results, and identical least-squares results except in three fixpnt<16,8> rows with a 45° residual. There the forward error is already above 1, an intermediate leaves the range, and wrapping and saturating part ways. Every other failure is at the bottom of the range.

Neither method dominates. In most types their least-squares reach (randsvd) is within a decade of each other. These differ by two decades or more:

  • float: Givens reaches 10⁵, against Householder’s 10⁷, at both sizes.
  • posit<16,2> at 16 × 8: Givens reaches 10³ and Householder 10. At 32 × 16 the gap is one decade.
  • posit<16,1> at 16 × 8: the reverse: Householder reaches 10³ and Givens 10.
  • fixpnt<32,16> at 32 × 16: Householder reaches 10³ and Givens 10.

With eight samples per point, one bad sample decides a type’s reach, so differences of a decade are within the noise. The two 16-bit posits pointing opposite ways at the same size suggests the same for some of these. Part 5 tests Givens where it should win: banded and sparse inputs, whose zeros it keeps.

Rounding into the type changes the problem

Section titled “Rounding into the type changes the problem”

The Hilbert and Kahan rows show how much the stored matrix differs from the qd one:

matrixκ in qdκ stored in posit<16,2>in fixpnt<16,8>
Hilbert 16 × 86.5×10⁸8×10⁴7.2×10²
Kahan 16 × 8, θ = 0.21.6×10⁷5×10⁴singular

A narrow type can’t hold an ill-conditioned matrix at all. What it factors is a better-conditioned neighbour, or a singular one. That is why every least-squares error here is measured against the stored problem, and why the tables give its κ.

QR columnwise backward error

Least-squares forward error

Generated by summarize.py from the committed results. A least-squares “reach” is the largest stored κ up to which every sample’s forward error is at most 10%, scanning up from κ = 1. A type that is never that accurate shows none.

QR, n = 8: worst columnwise backward error / orthogonality (eps)

Section titled “QR, n = 8: worst columnwise backward error / orthogonality (eps)”
typehouseholder_mtl5householder_betahouseholder_textbookgivens_mtl5
float5.05 / 6.943.94 / 6.946.17 / 8.594.93 / 9.02
double4.39 / 7.664.39 / 7.667.33 / 9.094.52 / 9.97
long double4.78 / 7.094.78 / 7.096.62 / 9.424.45 / 9.76
posit<8,2>9.94 / 8.349.94 / 8.34321 / 3.78e+0313.1 / 12
posit<16,2>68.4 / 7.5268.4 / 7.52798 / 64160.5 / 8.95
posit<32,2>1.7e+03 / 7.361.7e+03 / 7.361.9e+05 / 9.4e+041.45e+03 / 10.2
posit<64,2>2.0e+05 / 82.0e+05 / 84.7e+09 / 1.6e+091.8e+05 / 9.85
posit<16,1>4.79e+03 / 8.384.79e+03 / 8.387.4e+07 / 7.5e+044.18e+03 / 9.21
fixpnt<16,8,mod>341 / 16.9341 / 16.9627 / 2.28e+03440 / 14.3
fixpnt<16,8,sat>341 / 16.9341 / 16.9627 / 2.28e+03440 / 14.3
fixpnt<32,16,mod>8.4e+04 / 14.58.4e+04 / 14.51.3e+05 / 3.2e+051.7e+05 / 14.1
fixpnt<32,16,sat>8.4e+04 / 14.58.4e+04 / 14.51.3e+05 / 3.2e+051.7e+05 / 14.1

QR, n = 16: worst columnwise backward error / orthogonality (eps)

Section titled “QR, n = 16: worst columnwise backward error / orthogonality (eps)”
typehouseholder_mtl5householder_betahouseholder_textbookgivens_mtl5
float5.81 / 11.85.81 / 11.87.94 / 15.88.13 / 16.8
double5.73 / 115.73 / 117.19 / 15.46.29 / 16.3
long double5.45 / 10.85.45 / 10.88.84 / 15.67.75 / 17.1
posit<8,2>17.7 / 1517.7 / 154.79e+03 / 2.6e+0533.9 / 27.6
posit<16,2>121 / 10.3121 / 10.31.41e+03 / 3.5e+03105 / 15.4
posit<32,2>2.17e+03 / 11.12.17e+03 / 11.13.9e+05 / 7.8e+051.68e+03 / 16.2
posit<64,2>3.1e+05 / 11.43.1e+05 / 11.41.1e+10 / 1.2e+102.7e+05 / 16.7
posit<16,1>1.1e+04 / 14.21.1e+04 / 14.24.0e+07 / 8.1e+049.21e+03 / 17
fixpnt<16,8,mod>506 / 34.7448 / 34.73.1e+03 / 4.69e+031.31e+03 / 36.3
fixpnt<16,8,sat>506 / 34.7448 / 34.73.1e+03 / 4.69e+031.31e+03 / 36.3
fixpnt<32,16,mod>1.5e+05 / 36.21.1e+05 / 36.23.5e+05 / 6.0e+054.5e+05 / 38
fixpnt<32,16,sat>1.5e+05 / 36.21.1e+05 / 36.23.5e+05 / 6.0e+054.5e+05 / 38

Least squares, 16 x 8, zero residual: largest kappa with forward error <= 10%

Section titled “Least squares, 16 x 8, zero residual: largest kappa with forward error <= 10%”
type1/epsqr_householderqr_householder_betaqr_givensnormal_equations
float8.4e+061e71e71e51e3
double4.5e+151e141e141e141e7
long double9.2e+181e181e181e171e9
posit<8,2>8.0e+00nonenonenonenone
posit<16,2>2.0e+031e11e11e310
posit<32,2>1.3e+081e81e81e71e3
posit<64,2>5.8e+171e171e171e171e8
posit<16,1>4.1e+031e31e31e11e1
fixpnt<16,8,mod>2.6e+021.011.011.011.01
fixpnt<16,8,sat>2.6e+021.011.011.011.01
fixpnt<32,16,mod>6.6e+041e21e21e21e1
fixpnt<32,16,sat>6.6e+041e21e21e21e1

Least squares, 16 x 8, large residual: largest kappa with forward error <= 10%

Section titled “Least squares, 16 x 8, large residual: largest kappa with forward error <= 10%”
type1/epsqr_householderqr_householder_betaqr_givensnormal_equations
float8.4e+061e31e31e31e3
double4.5e+151e81e81e81e7
long double9.2e+181e91e91e91e9
posit<8,2>8.0e+00nonenonenonenone
posit<16,2>2.0e+0310101010
posit<32,2>1.3e+081e41e41e41e3
posit<64,2>5.8e+171e91e91e91e8
posit<16,1>4.1e+031e11e11e11e1
fixpnt<16,8,mod>2.6e+021.011.011.011.01
fixpnt<16,8,sat>2.6e+021.011.011.011.01
fixpnt<32,16,mod>6.6e+041e11e11e11e1
fixpnt<32,16,sat>6.6e+041e11e11e11e1

Least squares, 16 x 8, hilbert: forward error

Section titled “Least squares, 16 x 8, hilbert: forward error”
typekappa storedqr_householderqr_householder_betaqr_givensnormal_equations
float3.9e+080.670.6721 breakdown
double6.5e+082.5e-092.5e-096.8e-091 breakdown
long double6.5e+081.4e-121.4e-124.4e-120.0099
posit<8,2>3.4e+020.590.711.61 breakdown
posit<16,2>8e+041.31.30.761 breakdown
posit<32,2>6.6e+080.140.140.00991 breakdown
posit<64,2>6.5e+086e-116e-111.2e-100.17
posit<16,1>8e+040.730.731.41 breakdown
fixpnt<16,8,mod>7.2e+021 thrown1.91.81 breakdown
fixpnt<16,8,sat>7.2e+021 thrown1.91.81 breakdown
fixpnt<32,16,mod>2.2e+051.30.991.71 breakdown
fixpnt<32,16,sat>2.2e+051.30.991.71 breakdown

Least squares, 16 x 8, kahan: forward error

Section titled “Least squares, 16 x 8, kahan: forward error”
typekappa storedqr_householderqr_householder_betaqr_givensnormal_equations
float1.6e+070.220.220.248 breakdown
double1.6e+072.7e-102.7e-104.6e-100.0088
long double1.6e+072.9e-132.9e-132.8e-138e-06
posit<8,2>8.4e+65singularsingularsingularsingular
posit<16,2>5e+043.93.91.48 breakdown
posit<32,2>1.6e+070.00250.00250.0175 breakdown
posit<64,2>1.6e+071.7e-121.7e-123.9e-126.9e-05
posit<16,1>7.7e+041.71.71.48 breakdown
fixpnt<16,8,mod>6.9e+65singularsingularsingularsingular
fixpnt<16,8,sat>6.9e+65singularsingularsingularsingular
fixpnt<32,16,mod>2.3e+0521.91.98 breakdown
fixpnt<32,16,sat>2.3e+0521.91.98 breakdown

Least squares, 32 x 16, zero residual: largest kappa with forward error <= 10%

Section titled “Least squares, 32 x 16, zero residual: largest kappa with forward error <= 10%”
type1/epsqr_householderqr_householder_betaqr_givensnormal_equations
float8.4e+061e71e71e51e3
double4.5e+151e151e151e151e7
long double9.2e+181e191e191e181e9
posit<8,2>8.0e+00nonenonenonenone
posit<16,2>2.0e+031e21e21e310
posit<32,2>1.3e+081e81e81e81e3
posit<64,2>5.8e+171e161e161e171e8
posit<16,1>4.1e+031e31e31e310
fixpnt<16,8,mod>2.6e+021.011.011.011.01
fixpnt<16,8,sat>2.6e+021.011.011.011.01
fixpnt<32,16,mod>6.6e+041e31e31e11e1
fixpnt<32,16,sat>6.6e+041e31e31e11e1

Least squares, 32 x 16, large residual: largest kappa with forward error <= 10%

Section titled “Least squares, 32 x 16, large residual: largest kappa with forward error <= 10%”
type1/epsqr_householderqr_householder_betaqr_givensnormal_equations
float8.4e+061e31e31e31e3
double4.5e+151e81e81e81e7
long double9.2e+181e91e91e91e9
posit<8,2>8.0e+00nonenonenonenone
posit<16,2>2.0e+0310101010
posit<32,2>1.3e+081e41e41e41e3
posit<64,2>5.8e+171e91e91e91e8
posit<16,1>4.1e+0310101010
fixpnt<16,8,mod>2.6e+021.011.011.011.01
fixpnt<16,8,sat>2.6e+021.011.011.011.01
fixpnt<32,16,mod>6.6e+041e11e11e11e1
fixpnt<32,16,sat>6.6e+041e11e11e11e1

Least squares, 32 x 16, hilbert: forward error

Section titled “Least squares, 32 x 16, hilbert: forward error”
typekappa storedqr_householderqr_householder_betaqr_givensnormal_equations
float8.1e+080.70.71.41 breakdown
double2.4e+170.470.470.31 breakdown
long double1.6e+190.0290.0290.0561 breakdown
posit<8,2>4e+026.72.22.71 breakdown
posit<16,2>7.6e+041.31.31.51 breakdown
posit<32,2>4.6e+090.630.630.351 breakdown
posit<64,2>8.9e+180.0360.0360.231 breakdown
posit<16,1>7.6e+040.610.651.21 breakdown
fixpnt<16,8,mod>6.5e+021 thrown2.62.51 breakdown
fixpnt<16,8,sat>6.5e+021 thrown2.62.51 breakdown
fixpnt<32,16,mod>1.5e+051.51.221 breakdown
fixpnt<32,16,sat>1.5e+051.51.221 breakdown

Least squares, 32 x 16, kahan: forward error

Section titled “Least squares, 32 x 16, kahan: forward error”
typekappa storedqr_householderqr_householder_betaqr_givensnormal_equations
float8.3e+65singularsingularsingularsingular
double2.2e+150.0410.0410.068 breakdown
long double2.2e+151.1e-051.1e-051.9e-056 breakdown
posit<8,2>2.4e+66singularsingularsingularsingular
posit<16,2>1.6e+66singularsingularsingularsingular
posit<32,2>8.6e+091 non-finite1 non-finite5.4e+048 breakdown
posit<64,2>2.2e+150.000290.000290.000328 breakdown
posit<16,1>1.7e+66singularsingularsingularsingular
fixpnt<16,8,mod>2e+66singularsingularsingularsingular
fixpnt<16,8,sat>2e+66singularsingularsingularsingular
fixpnt<32,16,mod>1.6e+66singularsingularsingularsingular
fixpnt<32,16,sat>1.6e+66singularsingularsingularsingular