Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Cholesky QR — where it appears

A QR factorisation computed by forming the Gram matrix AᵀA, taking its Cholesky factor R, and setting Q = AR⁻¹. It needs only a matrix product and a small factorisation, which makes it cheap to communicate, and it squares the condition number of A in the orthogonality of Q.

Named by 3 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⁹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.

orthogonality · Gram–Schmidt 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.

orthogonality · Gram–Schmidt

Named alongside it

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

Condition numberReorthogonalisationBackward stabilityBlock methodsCommunication-avoidingGram–SchmidtHouseholder reflectionLoss of orthogonalityAll reduceBlocked algorithmExact ground truthGram matrix

All concepts