Numerical Linear Algebra
where the algebra stops being the arithmetic
Series

Gram–Schmidt — the series

7 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. for each previous column i, subtract the projection of column j onto qᵢclassicalr[i][j] = qᵢ · a[j] ↑ the ORIGINAL columnv = v − r[i][j] · qᵢthe three worst |qᵢ · qⱼ|:columns 7 and 8: 1columns 6 and 8: 0.13columns 6 and 7: 0.13modifiedr[i][j] = qᵢ · v ↑ what is LEFT of itv = v − r[i][j] · qᵢthe three worst |qᵢ · qⱼ|:columns 1 and 8: 4.4·10⁻⁷columns 2 and 8: 2.7·10⁻⁷columns 3 and 8: 2.4·10⁻⁸The two R factors agree to 1.2·10⁻⁶ relative. The two Q factors do not.the 8×8 Hilbert matrixone word, eight orders

    Two Gram–Schmidts

    One argument changes. Classical Gram–Schmidt projects the original column onto each previous direction; modified projects what is left of it. In exact arithmetic the coefficients are identical. In floating point they differ by eight orders of magnitude in the thing that matters.

    part 2 · orthogonality
  2. 10²10⁴10⁶10⁸10¹⁰10¹²10¹⁴10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹condition number κ(A)‖x̂ − x‖ / ‖x‖modified, through Qᵀbclassical, either route‖QᵀQ − I‖, modifiedHouseholdermodified, on [A b]κ²uκuforward error at κ = 10⁸Householder4·10⁻⁹modified, through Qᵀb0.13modified, on [A b]2.7·10⁻¹⁰classical840×8, three seeds, against an exact rational solveQ is not orthogonal; x is right

    The right-hand side as one more column

    Modified Gram–Schmidt's Q is 4.3·10⁻⁹ from orthogonal at κ = 10⁸, and a least-squares solve that multiplies b by it is wrong by 0.13. Hand the same routine b as an extra column instead and the answer is right to 2.7·10⁻¹⁰ — closer than Householder's 4.0·10⁻⁹. Classical Gram–Schmidt gains nothing from the same trick, to the last bit.

    part 3 · orthogonality
  3. 10¹10³10⁵10⁷10⁹10¹¹10¹³10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹condition number κ(A)‖QᵀQ − I‖classical once, Householdermodified once, Householderclassical twice, Householderclassical twice, Cholesky QRκ²uκuat κ = 10⁸classical once, Householder0.0042modified once, Householder5.7·10⁻⁹classical twice, Householder3.1·10⁻¹⁵classical twice, Cholesky QR10⁻¹⁵64×16 in blocks of 4, three seedsHouseholder inside does not help between

    A stable block is not a stable basis

    Block Gram–Schmidt orthogonalises twice over — between blocks, and inside each one. Householder inside the blocks does not stop the classical between-block step losing orthogonality like κ², 4.2·10⁻³ at κ = 4.3·10⁷, and a second pass does not stop Cholesky QR inside the blocks breaking down at κ = 10⁸. Each level fails only on ill-conditioning placed at its own level, and one variant holds 3·10⁻¹⁵ on every placement.

    part 4 · orthogonality
  4. three seeds, medianblock MGS, Qᵀb, κ 10⁸0.23block MGS, b as a block1.1·10⁻⁹Householder2.8·10⁻⁹10²10⁴10⁶10⁸10¹⁰10¹²10⁻¹⁶10⁻¹²10⁻⁸10⁻⁴110⁴10⁸κ(A)relative error of xblock MGS, Qᵀbblock CGS, either routeblock MGS, b as a blockHouseholderthe same Q in both block MGS routesonly the order in which b meets it differs

    What the appended block inherits

    Modified Gram–Schmidt on [A b] solves least squares as well as Householder, although its Q is not orthogonal. A block code appends b as one more block. Block modified Gram–Schmidt inherits the rescue at every placement of the ill-conditioning: at κ = 10⁸ the appended block gives 6.9·10⁻¹⁰ where the same Q through Qᵀb gives 8.9·10⁻³. Block classical Gram–Schmidt gets the same wrong answer both ways, to the last bit. And the variant whose Q is orthogonal to 10⁻¹⁵ — two passes with Cholesky QR inside — is a hundred thousand times worse than Householder when the ill-conditioning is inside the blocks, because its R is wrong.

    part 5 · orthogonality
  5. κ = 10⁸, acrossQᵀb ÷ appended, ρ = 01.3·10⁷Qᵀb ÷ appended, ρ = 10.6710⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1relative residual ρforward error010⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1block MGS, Qᵀbblock MGS, appendedHouseholderdotted: κ squared times u times ρthe residual brings every route to the same term

    The residual the appended block cannot remove

    Appending b as one more block made block modified Gram–Schmidt solve least squares as well as Householder, ten million times better than the same Q through Qᵀb at κ = 10⁸ — on problems with no residual. Give b a component outside the range and every stable route's error rises with it, while Qᵀb's, already at κ²u, does not move. The appended block's advantage then falls as one over the residual: 5,400 at a relative residual of 10⁻⁴, 54 at a per cent, none at one. It never falls behind Householder by more than a factor of four. What the residual decides is whether the extra block is worth its synchronisations, and the answer is yes up to a residual of about a per cent.

    part 6 · orthogonality
  6. a generic tall matrixHouseholder: aimed over median8b appended: aimed over median11column MGS: aimed over median1110⁻⁴10⁻³10⁻²10⁻¹1error ÷ κ²uρthe boundHouseholderb appendedcolumn MGSdots: random directions · bar: aimed · ring: the fixed directionaiming closes a factor of seven

    The worst residual belongs to the route

    Every stable least-squares route's error rises with the residual at about a fiftieth of the bound κ²uρ, and the question left open was whether a residual aimed at the weak directions closes the gap. It can be aimed exactly: the map from residual to error is, on these problems, one direction and rounding. Aimed, Householder's constant rises from a median of 0.014 to 0.11 — √(m − n) = 6.9 times a typical direction, at 32, 64 and 128 rows to three figures — and stops a factor of nine short of the bound. The direction is each route's own: aimed at one, another route draws a fifth of its worst. And aimed at the appended block, the one-per-cent rule that made it worth its extra block falls to half a per cent, with the block twelve times behind Householder on the same data.

    part 7 · orthogonality
  7. 0.000.050.100.15aimed error ÷ κ²uρill-conditioning spread through the columnsill-conditioning between column blocksHouseholder, sequential0.113tree of two leaves0.090tree of four leaves0.130Householder, sequential0.014tree of two leaves0.042tree of four leaves0.031bars: aimed constantsame order, different directions

    A tree leaks along its leaves

    A stable least-squares route's error, for a fixed factorisation, is a linear map from the residual with one dominant direction, and each route leaks along its own. A tree of Householder factorisations — the shape a distributed code factorises in — was expected to have a direction of its own too, with b appended at every leaf inheriting Householder's accuracy there. Measured at κ = 10⁸ on two placements of the ill-conditioning, a tree's map has one direction like every route's, and its aimed constant is of Householder's order: within a fifth of it when the ill-conditioning is spread, two to three times it when it sits between column blocks. Its direction is its own — at a cosine of 0.40 to 0.58 from the sequential route's, 0.13 to 0.18 between blocks — and the split of the rows decides it. Appending b at the leaves changes nothing: the same constant to five figures, the same direction to ten.

    part 8 · orthogonality

All series