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§
- Chol
Options - Options of
Cholesky: every threshold of chapter 12.2 lives here. - Cholesky
- The upper Cholesky factor
Rof a symmetric positive definiteA = RᵀR, kept up to date underA ← A ± x xᵀ(Chapter 12.2: Algorithms F, U, C). - Downdate
Info - What a successful downdate saw.
Functions§
- split_
pow2 🔒 d = f · 2^kwith2^kthe power of two ofd’sf64value (exact scalings);f ≈ [1, 2)up to the rounding ofto_f64, normalized by the caller.