Skip to main content

Module cholesky

Module cholesky 

Source
Expand description

§Chapter 12.2 — Cholesky with rank-1 update and downdate

§Purpose

A covariance, information or Gram matrix A changes by ± x xᵀ — an observation enters or leaves a recursive least-squares fit, a Kalman filter absorbs a measurement, a Gaussian-process refit drops a point — and its upper Cholesky factor R (RᵀR = A) must follow in O(n²) instead of the O(n³) of a refactorization. Cholesky keeps R under update (A + x xᵀ) and downdate (A − x xᵀ), with solves, the whitening R⁻ᵀ b and the log-determinant.

§Notation

A ∈ T^{n×n} symmetric positive definite (only its upper triangle is read); R upper triangular with r_jj > 0; x ∈ T^n; u the unit roundoff of T; A_t the matrix the sequence of operations defines. A rotation G = (c, s) acts as (p, q) ↦ (c p + s q, c q − s p) (Chapter 12.0.4).

§Algorithm F (factor)

F1. [Check.] A square, its upper triangle finite, the options valid. F2. [Factor.] Copy the upper triangle into the lower triangle of a block W (w_ij = a_ji, i ≥ j) and run K::potrf (Algorithm P of Chapter 5.16): W = L Lᵀ; a nonpositive pivot at j is StatlaError::NotPositiveDefinite { column: j }. F3. [Pivot test.] Reject column j unless l_jj² > pivot_tol · a_jj (and l_jj is finite and positive, whatever the kernel). F4. [Transpose.] R ← Lᵀ, strict lower triangle zero.

§Algorithm U (update, A + x xᵀ; LINPACK dchud)

U0. [Check.] x.len() = n and x finite — the only failures, checked before any write (H3). U1. [Loop.] For j = 0, …, n − 1: ξ ← x_j; apply the rotations G_0 … G_{j−1} already found to the pairs (r_ij, ξ), i = 0, …, j − 1, in that order: (r_ij, ξ) ← G_i (r_ij, ξ). U2. [Rotate.] Find G_j with G_j (r_jj, ξ) = (ρ, 0), ρ ≥ 0 (Algorithm G of 12.0.4, the safe hypot); r_jj ← ρ. Cost 2n² flops (≈ 3n² with the scaling of G2). Since ρ ≥ r_jj > 0, (H1) is kept.

§Algorithm C (downdate, A − x xᵀ; LINPACK dchdd, Saunders 1972)

C0. [Check.] x.len() = n, x finite. C1. [Solve.] Rᵀ a = x (forward substitution). C2. [Test.] α² ← 1 − ‖a‖² (‖a‖ by Algorithm N); if α² is not finite or α² ≤ downdate_tol, return StatlaError::DowndateIndefinite — before any change to R (H3 for free). (RᵀR − xxᵀ = Rᵀ(I − aaᵀ)R is positive definite iff ‖a‖ < 1.) C3. [Rotations.] α ← √α²; for i = n − 1, …, 0: μ ← α + |a_i|, α̂ ← α/μ, b ← a_i/μ, ν ← √(α̂² + b²), c_i ← α̂/ν, s_i ← b/ν, α ← μν. C3′. [Diagonal first.] The new diagonal is r_jj ← c_j r_jj (step C4 at i = j, where ξ = 0). If one of them is not finite and positive (only an underflow can do that), return DowndateIndefinite with the margin of C2 — still before any write. An addition of this edition to LINPACK’s algorithm. C4. [Apply.] For each column j: ξ ← 0; for i = j, …, 0: (r_ij, ξ) ← (c_i r_ij − s_i ξ, c_i ξ + s_i r_ij). C5. [Signs.] Flip the rows with r_ii < 0 (none, after C3′; kept as the contract states it, so that (H1) does not rest on C3′ alone). Cost ≈ 3n² flops plus the n² of C1. Backward stable in the mixed sense of Stewart (1979). The forward error against a refactorization grows like κ₂(R̃) u — the error of any algorithm, because two refactorizations of A_t perturbed at the level u already differ by that much (pilot s01, table A).

§Solves and the determinant

solve: Rᵀy = b forward, then Rx = y backward (both column-oriented on R). solve_upper_t: the forward half only, b ← R⁻ᵀb, so ‖R⁻ᵀb‖² = bᵀA⁻¹b. log2_det_parts: det R = Π r_jj = m · 2^e with m ∈ [1, 2), accumulated by splitting each r_jj = f_j 2^{k_j} with powers of two read off the f64 bits (exact scalings), so it neither overflows nor underflows for any n; then ln det A = 2(ln m + e ln 2) in the caller’s precision.

§Invariants

(H1) R upper triangular (strict lower triangle exactly zero), r_jj > 0, every entry finite — Cholesky::check_invariants, debug_assert! after each of F, U, C. (H2) ‖RᵀR − A_t‖_F ≤ c_H · n · u · ‖A_t‖_F after any sequence; c_H = 8 in the tests (tests/cholesky.rs, against A_t and RᵀR in double-double; the norm along the path when downdates cancel more than half of A). (H3) A failed update/downdate leaves R bit for bit unchanged: U0 and C0–C3′ read R and write only local vectors.

§Acceptance (L3.2, S9 of D-0127) and what was measured

In f64 and DoubleDouble, n ≤ 200, κ(A_t) from 10 to 10¹² (tests/cholesky.rs, proptests and fixed seeds): (i) update∘downdate and downdate∘update within 10 n u of the original factor (relative Frobenius); (ii) backward error (H2) ≤ c_H n u at every κ; (iii) forward error against a refactorization of A_t ≤ 10⁻¹² where κ(A_t) ≤ 10⁸, and elsewhere ≤ 10× the distance between two refactorizations of A_t perturbed at the level u; (iv) a failed operation leaves the factor bit for bit unchanged.

What holds. (i), (ii), (iv) per instance with wide margins (upd∘dd, dd∘upd ≤ 4.9 n u at n = 3, ≤ 0.05 n u for n ≥ 50). (iii) as worded does not hold per instance: the forward error of the downdate is governed by 1 − ‖a‖², not by κ alone — n = 2, κ = 10⁶ gave 9.4·10⁻¹²; at κ = 10⁸, n = 100, 10 of 200 seeds exceed 10⁻¹²; the per-instance ratio to the distance between two refactorizations reaches 40–150 for n ≤ 3. The tests enforce what was measured to hold — per instance fwd ≤ 8 κ u (the first-order bound of any algorithm working from R), and the pilot’s aggregate form (the maximum over 20 seeds at n = 100, 200: ≤ 10⁻¹² where κ ≤ 10⁶, ≤ 10× the maximum distance everywhere) — and keep the literal criterion as an ignored test (question Q-L32-2 of task L3.2, settled this way by D-0132). The measured values are in .claude/scratch/l32/l32-tables.md; the example accuracy regenerates them.

§References

LINPACK Users’ Guide (1979), ch. 10 (dchud, dchdd); Saunders (1972); Stewart, J. IMA 23 (1979); Gill, Golub, Murray & Saunders, Math. Comp. 28 (1974); Higham (2002), Theorem 10.3 (backward error of Cholesky); pilot s01 (.claude/scratch/s01/s01-pilot). All cited from memory.

Structs§

CholOptions
Options of Cholesky: every threshold of chapter 12.2 lives here.
Cholesky
The upper Cholesky factor R of a symmetric positive definite A = RᵀR, kept up to date under A ← A ± x xᵀ (Chapter 12.2: Algorithms F, U, C).
DowndateInfo
What a successful downdate saw.

Functions§

split_pow2 🔒
d = f · 2^k with 2^k the power of two of d’s f64 value (exact scalings); f ≈ [1, 2) up to the rounding of to_f64, normalized by the caller.