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 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⁹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

Named alongside it

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

Communication avoidingCondition numberReorthogonalisationAll reduceBackward stabilityBlock methodsBlocked algorithmGram matrixGram–SchmidtHouseholder reflectionKrylov subspaceLoss of orthogonality

All concepts