Skip to main content

Module qr

Module qr 

Source
Expand description

§Chapter 12.3 — Thin QR with explicit Q and five updating operations

§Purpose

A least-squares fit min ‖Ax − b‖ whose design A gains or loses an observation (a row) or a regressor (a column), or changes by a rank-1 term, should cost O(mn), not the O(mn²) of refactorizing. Qr keeps the thin factorization A = QR — Q ∈ T^{m×n} with orthonormal columns, explicit; R ∈ T^{n×n} upper triangular with positive diagonal — through insert_row, delete_row, insert_col, delete_col and rank1_update (decision S8 of D-0127). The Q-less variant is Cholesky (RᵀR = AᵀA): Qr::to_cholesky.

§Notation

A ∈ T^{m×n}, m ≥ n, full column rank; q_j the columns of Q, q_(i)ᵀ its row i; R̂, M the bordered factors during an operation (A = M R̂ throughout). A rotation G = (c, s) (Chapter 12.0.4) applied to rows k, l of R̂ is always applied to columns k, l of M with the same (c, s): then M R̂ is unchanged, because c q_k + s q_l, −s q_k + c q_l against c r_k + s r_l, −s r_k + c r_l gives back q_k r_kᵀ + q_l r_lᵀ. τ = rank_tol resolved (see QrOptions); η = reorth_eta.

§Algorithm F (factor: Householder, GVL Algorithm 5.2.1)

F1. [Check.] m ≥ n, A finite, options valid. F2. [Reduce.] For k = 0, …, n − 1: a reflector H_k (Algorithm H) maps W[k.., k] to α_k e_0; apply it to W[k.., k+1..]. F3. [Form Q.] Q ← H_0 ⋯ H_{n−1} [I_n; 0], applied backwards (the reflector H_k touches columns k..n only). F4. [Signs.] Where r_kk < 0, negate row k of R and column k of Q. F5. [Rank.] If r_kk ≤ τ ‖a_k‖, StatlaError::RankDeficient at k.

§Algorithm I (insert row wᵀ before row i)

I1. Check |w| = n, i ≤ m, w finite. I2. Border: M = [Q with a zero row at i, e_i], R̂ = [R; wᵀ]. I3. For j = 0, …, n − 1: G_j with G_j (r_jj, w_j) = (ρ, 0); rotate rows j, n of R̂ (columns j..) and columns j, n of M. I4. Drop the last row of R̂ (now zero) and the last column of M. Cost 3mn + 3n²/2 flops; nothing can fail after I1.

§Algorithm D (delete row i; requires m > n)

D1. z ← e_i, orthogonalized against Q by Algorithm D of 12.0.4 (DGKS, at most two passes); ν = ‖z‖ (in exact arithmetic ν² = 1 − ‖q_(i)‖²). If ν ≤ τ, the remaining rows are rank deficient: RankDeficient (reported with the row index), nothing written. D2. Border: M = [Q, z/ν], R̂ = [R; 0], w ← (q_(i); z_i/ν) the row i of M. D3. For k = n − 1, …, 0: G_k (w_k, w_{k+1}) = (·, 0); rotate rows k, k+1 of R̂ (columns k..; this fills (k+1, k) only) and columns k, k+1 of M. Now w = ±e_0 (so column 0 of M is ±e_i), R̂ is upper Hessenberg, its row 0 is the deleted row of A. D4. R ← R̂[1.., ..] (upper triangular), Q ← M[rows ≠ i, 1..]; signs as F4. Cost ≈ 5mn.

§Algorithm C (insert column c before column j; requires m > n)

C1. Check |c| = m, j ≤ n, c finite. C2. h ← Qᵀc, z ← c − Qh by Algorithm D of 12.0.4; ρ = ‖z‖; if ρ ≤ τ ‖c‖, RankDeficient at j, nothing written. C3. Border: M = [Q, z/ρ]; R̂ ∈ T^{(n+1)×(n+1)} with the columns of R (and a zero last row) and the spike (h; ρ) at position j. C4. For k = n, …, j + 1: G with G (r̂_{k−1,j}, r̂_{kj}) = (·, 0); rotate rows k − 1, k of R̂ (columns j+1..) and columns k − 1, k of M. Signs as F4. Cost ≈ 4mn + 3n(n − j).

§Algorithm E (delete column j)

E1. Remove column j of R: an n × (n−1) matrix, upper Hessenberg from column j on. E2. For p = j, …, n − 2: G (r_pp, r_{p+1,p}) = (·, 0); rotate rows p, p+1 (columns p+1..) and columns p, p+1 of Q. E3. Drop the last row of R (zero) and the last column of Q; signs. Cost 6m(n − j); nothing can fail after the index check.

§Algorithm R (rank-1 update A + u vᵀ; Hammarling & Lucas §2.5)

R1. Check |u| = m, |v| = n, finite. R2. w ← Qᵀu, z ← u − Qw (Algorithm D of 12.0.4), ρ = ‖z‖. If ρ ≤ τ ‖u‖, u is in the range of Q to working precision: ρ ← 0, z ← 0 (the border column then never mixes in: every rotation that touches it has s = 0 exactly). R3. Work on copies: M = [Q, z/ρ], R̂ = [R; 0], ŵ = (w; ρ). R4. For k = n − 1, …, 0: G_k (ŵ_k, ŵ_{k+1}) = (·, 0) on rows k, k+1 of R̂ and columns k, k+1 of M: ŵ = ‖ŵ‖e_0, R̂ upper Hessenberg. R5. R̂_{0,:} ← R̂_{0,:} + ‖ŵ‖ vᵀ (still Hessenberg). R6. For k = 0, …, n − 1: G (r̂_kk, r̂_{k+1,k}) = (·, 0) on rows k, k+1 (columns k+1..) and columns k, k+1 of M. The last row of R̂ is now zero. R7. Signs; if some r_kk ≤ τ (‖a_k‖ + |v_k| ‖u‖) (the result lost rank; the scale is that of the column before any cancellation), RankDeficient at k and the copies are dropped; else commit Q ← M[:, ..n], R ← R̂[..n, :]. Cost ≈ 10mn.

§Least squares

y ← Qᵀb, x ← R⁻¹y (back substitution), and the residual norm ‖b − Qy‖ (the residual is formed, not taken as √(‖b‖² − ‖y‖²), which cancels).

§Invariants

(Q1) ‖QᵀQ − I‖_F ≤ c_Q · m · u — Qr::check_invariants(c_Q); the DGKS step of D1, C2, R2 is what keeps it under deletions and nearly dependent insertions. (Q2) R upper triangular with r_jj > 0 and finite (checked by check_invariants, and as a debug_assert! after every operation); ‖QR − A_t‖_F ≤ c_Q · m · u · ‖A_t‖_F (tests, against A_t in double-double). (Q3) A failed operation leaves Q and R bit for bit unchanged: every failure is detected before the first write (I1, D1, C1–C2, E1) or on copies (R7).

§Acceptance (L3.2; the same as Chapter 12.2, plus Q1)

κ here is κ(A_tᵀA_t) = κ₂(A_t)², so that the bands of the criterion (iii) — ≤ 10⁻¹² where κ ≤ 10⁸, ≤ 10× the distance between two refactorizations elsewhere — mean the same conditioning of R as in Chapter 12.2. Tests in tests/qr.rs. Per instance: (Q1), (Q2) with c_Q = 16, fwd ≤ 8 κ u; in aggregate (20 seeds, 150 × 100): the ratified (iii) holds in full — max fwd ≤ 4.6·10⁻¹⁵ where κ ≤ 10⁸ and ≤ 1.3× the distance between refactorizations. The literal per-instance (iii) fails on small matrices (ratio up to 3·10² on 5 × 3, where the refactorization is nearly exact): question Q-L32-2.

§References

Golub & Van Loan (2013), §5.2 (Householder QR), §6.5.1–6.5.3 (updating the full QR); Hammarling & Lucas, MIMS EPrint 2008.111 (economy updates); Daniel, Gragg, Kaufman & Stewart, Math. Comp. 30 (1976) (Gram–Schmidt completion with reorthogonalization). Cited from memory.

Structs§

Qr
Thin QR A = QR, Q ∈ R^{m×n} explicit with orthonormal columns, R ∈ R^{n×n} upper triangular with r_jj > 0, m ≥ n, full column rank (Chapter 12.3: Algorithms F, I, D, C, E, R).
QrOptions
Options of Qr.

Functions§

drop_last_row 🔒
R̂[..n, ..] of an (n+1) × c block, as an n × c block.
fix_signs 🔒
Where r_kk < 0 for k ≥ from, negate row k of r and column k of q (step F4).