Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Seminormal equations — where it appears

Solving least squares with the triangular factor R of a QR factorisation but without its orthogonal factor, by two triangular solves on the normal equations. It saves storing Q and squares the condition number in the solve, which one step of refinement from the rows' own residual repairs.

Named by 3 essays across one field — each of them below, with the objects they name alongside it.

10²10³10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹steps takenlargest relative error in a coefficientcarried factorrecomputedcarried + one correction+ a second correctionHouseholder QR, same rowsdrift of the factorafter 2875 stepsκ(A) of the window2·10⁴carried factor2.8·10⁻⁸recomputed5.8·10⁻⁹carried + one correction7.1·10⁻¹³+ a second correction3.7·10⁻¹²Householder QR, same rows1.1·10⁻¹²measured against the coefficients in exact rationalsthe refresh repairs the factor, not the answer

The repair the drift did not need

A sliding window's carried Cholesky factor drifts 3.9·10⁻¹⁴ from its data, and multiplying by κ(AᵀA) predicts eight lost digits in the coefficients, a stream conditioned at 10¹² losing the answer, and a periodic refresh of the factor as the default repair. Measured against coefficients computed exactly in rationals, all three come out differently. On a stream made ill-conditioned by scaling, the conditioning never reaches the coefficients. On a collinear stream, a freshly recomputed factor is as wrong as the drifted one. And one correction from the window's own rows reaches Householder's accuracy for a fraction of a refresh's cost.

sequence · Sequence stability noise none, mediansthe answer's step0fresh start, corrected6.2·10⁻⁹carried start, corrected1.3·10⁻¹¹0200400600800100010⁻¹²10⁻¹⁰10⁻⁸steps along the streamlargest relative coefficient errorfresh solve, one correctioncarried answer, one correctionfresh solve, two correctionsHouseholder on the rowseach correction contracts its start by the same factorthe nearer start wins

The answer the last window left

A sliding window that corrects its least-squares answer at every step could start each correction from the previous step's corrected answer instead of from a fresh solve: the two windows share all but one row. On a stream with any noise in it, that start is three orders worse. The window's exact answer moves by 0.79 of itself in one step at κ(A) = 3·10⁶, a fresh seminormal solve is wrong by only 1.8·10⁻⁴, and one correction contracts either start by the same factor — so the fresh start ends at 2.2·10⁻⁸ and the carried one at 3.7·10⁻⁵. Only on data that agree exactly does carrying win.

sequence · Sequence stability 10³10⁴10⁵10⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1κ(A), median over the windowsrelative error, mediansingle's unit roundoff × κdouble's × κsingle residualsingle sum, double residualdoublenoise 1, every step corrected against all 24 rowsthe residual sets the floor

The sum can be single, the residual cannot

A sliding least-squares window's correction has to read every row, so the cheaper correction proposed instead was one whose residual is formed in single precision and summed in double. It was predicted to cost little at κ(A) = 3·10⁴ and a great deal at 3·10⁶. It costs seven to eight decades at both: the window ends at 3.7·10⁻² instead of 3.3·10⁻⁹ at the worse conditioning and at 3.1·10⁻⁴ instead of 2.2·10⁻¹² at the better. The single residual's error is a fixed fraction of single precision's unit roundoff times κ(A), at every noise level, because its rounding reaches the answer through the rows themselves and is amplified once, not squared. The other half of the correction behaves the other way: summing the rows weighted by a double residual in single is free when the data fit exactly and costs in proportion to the residual otherwise, two decades for every decade of κ.

sequence · Sequence stability

Named alongside it

The objects these essays reach for when they reach for this one.

Exact ground truthIterative refinementLow-rank updateBackward errorCholesky factorisationCondition squaringRecursive least squaresComponentwise condition numberCondition numberLeast squaresMixed-precisionUnit roundoff

All concepts