Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Orthogonality loss — where it appears

The growth of the norm of QᵀQ − I in a basis that should be orthonormal, which is the quantity separating algorithms that share an algebra.

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

10²10³10⁴10⁵10⁶10⁷10⁸10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²condition number‖QᵀQ − I‖one passsweeptwicetreewhat the second pass removesfitted slope, one pass2fitted slope, two passes0.96rounds, two passes6rounds, the sweep24one pass squares the condition numberand two do not

Doing it twice

Cholesky QR squares the condition number — a fitted slope of 1.95 in κ against the Householder sweep's 1.00. Run the identical routine a second time on the Q it returned and the slope is 0.93, the orthogonality is at or below the sweep's at every κ, and the price is one more all-reduce.

cost · communication 10²10⁴10⁶10⁸10¹⁰0285684112140168196224condition numberstepsnormal equationsbidiagonalisationone sequence, two costssteps at κ = 10², both16at κ = 10⁶, ratio1.1at κ = 10¹⁰, ratio1.9the same iterates in the algebraand twice the work at κ = 10¹⁰

One sequence and two recurrences

CGLS and LSQR compute the same iterates — the minimiser over a space is unique, so there is nothing to choose between them in the algebra. At κ = 10⁶ they cost 42 steps and 47. At κ = 10¹⁰ they cost 110 and 209, across four seeds, and the quantity that separates them is the orthogonality of a basis neither of them keeps.

iterative · krylov

Named alongside it

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

Normal equationsUnit roundoffAll reduceBackward stabilityCglsCholesky qrCommunication avoidingCondition numberForward errorGolub kahan bidiagonalisationGram matrixKrylov subspace

All concepts