Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Row ordering — where it appears

The order in which the equations of a least-squares problem are presented to a factorisation. It changes nothing in exact arithmetic, and under Householder QR it decides which rows carry the rounding: rows of very different scale belong in decreasing order of size.

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

0246810121410⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹10⁴10⁷10¹⁰log₁₀ τ — the weight on the constraintrelative error against the exact answerτ = 1/√uGram–Schmidtnormal equationsHouseholder QRthe ceiling is the method'sHouseholder, τ = 10¹⁴4.8·10⁻¹⁵normal equations14Gram–Schmidt4.9·10¹⁰1/√u6.7·10⁷a constraint is a weight at infinityand the solver decides how far infinity is

A constraint is a weight at infinity

Stack an equality constraint on top of a least-squares problem with a large weight and the answer approaches the constrained one like 1/τ². The limit is takeable to any accuracy — and how far it can be taken is a property of the solver, not of the problem. One of them stops at the square root of the precision, and one of them does not stop.

leastsquares · Constrained least-squares heavy row first1 − h at 4³⁰7.4·10⁻¹⁸κ(A) at 4³⁰3.1·10⁸complement's error2.1·10⁻¹⁶110³10⁶10⁹10¹²10¹⁵10¹⁸10⁻¹⁷10⁻¹⁵10⁻¹³10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹weight on the rowrelative error of 1 − h1 − ‖R⁻ᵀa‖²1 − ‖row of Q₁‖²‖row of Q₂‖²κ(A)·uthe rows are the same in every positiononly the order the factorisation meets them changes

The weight the factor met first

The route to one minus a leverage through the orthogonal factor was said to lose a digit for every decade of the condition number, whatever else it does. Put a weight on one row and it does not. With the heavy row first, the complement keeps every digit at κ(A) = 2.5·10⁹ while both subtractions return nothing. With the same row last it loses digits as the row's scale grows. And two heavy rows that leave κ(A) at 3.1 still lose six digits when the light rows come first. The law was about the order the factor met the rows, and the condition number had been standing in for it.

leastsquares · Leverage

Named alongside it

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

Condition numberExact ground truthMethod of weightingQR factorisationBackward stabilityCatastrophic cancellationEquality constrained least-squaresHouseholderHouseholder reflectionLeast-squaresLeverageNormal equations

All concepts