xingo_statla/qr.rs
1//! # Chapter 12.3 — Thin QR with explicit `Q` and five updating operations
2//!
3//! ## Purpose
4//! A least-squares fit `min ‖Ax − b‖` whose design `A` gains or loses an
5//! observation (a row) or a regressor (a column), or changes by a rank-1
6//! term, should cost `O(mn)`, not the `O(mn²)` of refactorizing. [`Qr`]
7//! keeps the *thin* factorization `A = QR` — `Q ∈ T^{m×n}` with orthonormal
8//! columns, explicit; `R ∈ T^{n×n}` upper triangular with positive diagonal
9//! — through `insert_row`, `delete_row`, `insert_col`, `delete_col` and
10//! `rank1_update` (decision S8 of D-0127). The `Q`-less variant is
11//! [`Cholesky`] (`RᵀR = AᵀA`): [`Qr::to_cholesky`].
12//!
13//! ## Notation
14//! `A ∈ T^{m×n}`, `m ≥ n`, full column rank; `q_j` the columns of `Q`,
15//! `q_(i)ᵀ` its row `i`; `R̂`, `M` the bordered factors during an operation
16//! (`A = M R̂` throughout). A rotation `G = (c, s)` (Chapter 12.0.4)
17//! applied to rows `k, l` of `R̂` is always applied to columns `k, l` of `M`
18//! with the same `(c, s)`: then `M R̂` is unchanged, because `c q_k + s q_l`,
19//! `−s q_k + c q_l` against `c r_k + s r_l`, `−s r_k + c r_l` gives back
20//! `q_k r_kᵀ + q_l r_lᵀ`. `τ = rank_tol` resolved (see [`QrOptions`]); `η =
21//! reorth_eta`.
22//!
23//! ## Algorithm F (factor: Householder, GVL Algorithm 5.2.1)
24//! F1. \[Check.\] `m ≥ n`, `A` finite, options valid.
25//! F2. \[Reduce.\] For `k = 0, …, n − 1`: a reflector `H_k` (Algorithm H)
26//! maps `W[k.., k]` to `α_k e_0`; apply it to `W[k.., k+1..]`.
27//! F3. \[Form `Q`.\] `Q ← H_0 ⋯ H_{n−1} [I_n; 0]`, applied backwards (the
28//! reflector `H_k` touches columns `k..n` only).
29//! F4. \[Signs.\] Where `r_kk < 0`, negate row `k` of `R` and column `k` of
30//! `Q`.
31//! F5. \[Rank.\] If `r_kk ≤ τ ‖a_k‖`, [`StatlaError::RankDeficient`] at `k`.
32//!
33//! ## Algorithm I (insert row `wᵀ` before row `i`)
34//! I1. Check `|w| = n`, `i ≤ m`, `w` finite.
35//! I2. Border: `M = [Q with a zero row at i, e_i]`, `R̂ = [R; wᵀ]`.
36//! I3. For `j = 0, …, n − 1`: `G_j` with `G_j (r_jj, w_j) = (ρ, 0)`; rotate
37//! rows `j`, `n` of `R̂` (columns `j..`) and columns `j`, `n` of `M`.
38//! I4. Drop the last row of `R̂` (now zero) and the last column of `M`.
39//! Cost `3mn + 3n²/2` flops; nothing can fail after I1.
40//!
41//! ## Algorithm D (delete row `i`; requires `m > n`)
42//! D1. `z ← e_i`, orthogonalized against `Q` by Algorithm D of 12.0.4
43//! (DGKS, at most two passes); `ν = ‖z‖` (in exact arithmetic `ν² = 1 −
44//! ‖q_(i)‖²`). If `ν ≤ τ`, the remaining rows are rank deficient:
45//! `RankDeficient` (reported with the row index), nothing written.
46//! D2. Border: `M = [Q, z/ν]`, `R̂ = [R; 0]`, `w ← (q_(i); z_i/ν)` the row
47//! `i` of `M`.
48//! D3. For `k = n − 1, …, 0`: `G_k (w_k, w_{k+1}) = (·, 0)`; rotate rows `k,
49//! k+1` of `R̂` (columns `k..`; this fills `(k+1, k)` only) and columns
50//! `k, k+1` of `M`. Now `w = ±e_0` (so column 0 of `M` is `±e_i`), `R̂` is
51//! upper Hessenberg, its row 0 is the deleted row of `A`.
52//! D4. `R ← R̂[1.., ..]` (upper triangular), `Q ← M[rows ≠ i, 1..]`; signs as
53//! F4. Cost `≈ 5mn`.
54//!
55//! ## Algorithm C (insert column `c` before column `j`; requires `m > n`)
56//! C1. Check `|c| = m`, `j ≤ n`, `c` finite.
57//! C2. `h ← Qᵀc`, `z ← c − Qh` by Algorithm D of 12.0.4; `ρ = ‖z‖`; if `ρ ≤
58//! τ ‖c‖`, `RankDeficient` at `j`, nothing written.
59//! C3. Border: `M = [Q, z/ρ]`; `R̂ ∈ T^{(n+1)×(n+1)}` with the columns of `R`
60//! (and a zero last row) and the spike `(h; ρ)` at position `j`.
61//! C4. For `k = n, …, j + 1`: `G` with `G (r̂_{k−1,j}, r̂_{kj}) = (·, 0)`;
62//! rotate rows `k − 1, k` of `R̂` (columns `j+1..`) and columns `k − 1, k`
63//! of `M`. Signs as F4. Cost `≈ 4mn + 3n(n − j)`.
64//!
65//! ## Algorithm E (delete column `j`)
66//! E1. Remove column `j` of `R`: an `n × (n−1)` matrix, upper Hessenberg
67//! from column `j` on.
68//! E2. For `p = j, …, n − 2`: `G (r_pp, r_{p+1,p}) = (·, 0)`; rotate rows
69//! `p, p+1` (columns `p+1..`) and columns `p, p+1` of `Q`.
70//! E3. Drop the last row of `R` (zero) and the last column of `Q`; signs.
71//! Cost `6m(n − j)`; nothing can fail after the index check.
72//!
73//! ## Algorithm R (rank-1 update `A + u vᵀ`; Hammarling & Lucas §2.5)
74//! R1. Check `|u| = m`, `|v| = n`, finite.
75//! R2. `w ← Qᵀu`, `z ← u − Qw` (Algorithm D of 12.0.4), `ρ = ‖z‖`. If `ρ ≤
76//! τ ‖u‖`, `u` is in the range of `Q` to working precision: `ρ ← 0`, `z
77//! ← 0` (the border column then never mixes in: every rotation that
78//! touches it has `s = 0` exactly).
79//! R3. Work on copies: `M = [Q, z/ρ]`, `R̂ = [R; 0]`, `ŵ = (w; ρ)`.
80//! R4. For `k = n − 1, …, 0`: `G_k (ŵ_k, ŵ_{k+1}) = (·, 0)` on rows `k, k+1`
81//! of `R̂` and columns `k, k+1` of `M`: `ŵ = ‖ŵ‖e_0`, `R̂` upper
82//! Hessenberg.
83//! R5. `R̂_{0,:} ← R̂_{0,:} + ‖ŵ‖ vᵀ` (still Hessenberg).
84//! R6. For `k = 0, …, n − 1`: `G (r̂_kk, r̂_{k+1,k}) = (·, 0)` on rows `k, k+1`
85//! (columns `k+1..`) and columns `k, k+1` of `M`. The last row of `R̂` is
86//! now zero.
87//! R7. Signs; if some `r_kk ≤ τ (‖a_k‖ + |v_k| ‖u‖)` (the result lost
88//! rank; the scale is that of the column before any cancellation),
89//! `RankDeficient` at `k` and the copies are dropped; else commit `Q ←
90//! M[:, ..n]`, `R ← R̂[..n, :]`. Cost `≈ 10mn`.
91//!
92//! ## Least squares
93//! `y ← Qᵀb`, `x ← R⁻¹y` (back substitution), and the residual norm `‖b −
94//! Qy‖` (the residual is formed, not taken as `√(‖b‖² − ‖y‖²)`, which
95//! cancels).
96//!
97//! ## Invariants
98//! (Q1) `‖QᵀQ − I‖_F ≤ c_Q · m · u` — [`Qr::check_invariants`]`(c_Q)`;
99//! the DGKS step of D1, C2, R2 is what keeps it under deletions and
100//! nearly dependent insertions.
101//! (Q2) `R` upper triangular with `r_jj > 0` and finite (checked by
102//! `check_invariants`, and as a `debug_assert!` after every
103//! operation); `‖QR − A_t‖_F ≤ c_Q · m · u · ‖A_t‖_F` (tests, against
104//! `A_t` in double-double).
105//! (Q3) A failed operation leaves `Q` and `R` bit for bit unchanged: every
106//! failure is detected before the first write (I1, D1, C1–C2, E1) or
107//! on copies (R7).
108//!
109//! ## Acceptance (L3.2; the same as Chapter 12.2, plus Q1)
110//! `κ` here is `κ(A_tᵀA_t) = κ₂(A_t)²`, so that the bands of the
111//! criterion (iii) — `≤ 10⁻¹²` where `κ ≤ 10⁸`, `≤ 10×` the distance
112//! between two refactorizations elsewhere — mean the same conditioning of
113//! `R` as in Chapter 12.2. Tests in `tests/qr.rs`. Per instance: (Q1),
114//! (Q2) with `c_Q = 16`, `fwd ≤ 8 κ u`; in aggregate (20 seeds, `150 ×
115//! 100`): the ratified (iii) holds in full — `max fwd ≤ 4.6·10⁻¹⁵` where
116//! `κ ≤ 10⁸` and `≤ 1.3×` the distance between refactorizations. The
117//! literal per-instance (iii) fails on small matrices (ratio up to `3·10²`
118//! on `5 × 3`, where the refactorization is nearly exact): question
119//! Q-L32-2.
120//!
121//! ## References
122//! Golub & Van Loan (2013), §5.2 (Householder QR), §6.5.1–6.5.3 (updating
123//! the full QR); Hammarling & Lucas, MIMS EPrint 2008.111 (economy
124//! updates); Daniel, Gragg, Kaufman & Stewart, Math. Comp. 30 (1976)
125//! (Gram–Schmidt completion with reorthogonalization). Cited from memory.
126
127use xingo_sparse::{DenseBlock, DenseKernel, NaiveDense, Real};
128
129use crate::real::{is_exact_zero, le_exact, lt};
130use crate::small::{
131 apply_householder, axpy_sub, check_finite, check_len, dot, givens, householder, norm2,
132 orthogonalize,
133};
134use crate::{CholOptions, Cholesky, MatRef, StatlaError};
135
136/// Options of [`Qr`].
137#[derive(Clone, Copy, Debug, PartialEq)]
138pub struct QrOptions {
139 /// DGKS reorthogonalization: a second Gram–Schmidt pass runs when the
140 /// norm fell below `reorth_eta` times its value before the pass
141 /// (default `1/√2`, Daniel–Gragg–Kaufman–Stewart). Must be in `(0, 1]`.
142 pub reorth_eta: f64,
143 /// A new column (or a complement vector in `delete_row`) whose norm
144 /// after two passes is `≤ rank_tol · ‖column‖` is declared dependent.
145 /// **`0` (the default) means `n · ε_T`**, resolved at each operation
146 /// from the scalar `T` and the number of columns `n` of the result
147 /// (the default cannot know either; see the question Q-L32-1 of task
148 /// L3.2). Must be finite and `≥ 0`.
149 pub rank_tol: f64,
150}
151
152impl Default for QrOptions {
153 fn default() -> Self {
154 Self {
155 reorth_eta: core::f64::consts::FRAC_1_SQRT_2,
156 rank_tol: 0.0,
157 }
158 }
159}
160
161impl QrOptions {
162 fn validate(&self) -> Result<(), StatlaError> {
163 if !(self.reorth_eta.is_finite()
164 && lt(0.0, self.reorth_eta)
165 && le_exact(self.reorth_eta, 1.0))
166 {
167 return Err(StatlaError::InvalidArgument {
168 what: "QrOptions::reorth_eta must be in (0, 1]",
169 });
170 }
171 if !(self.rank_tol.is_finite() && le_exact(0.0, self.rank_tol)) {
172 return Err(StatlaError::InvalidArgument {
173 what: "QrOptions::rank_tol must be finite and >= 0",
174 });
175 }
176 Ok(())
177 }
178
179 /// `τ` for a result with `n` columns.
180 fn tau<T: Real>(&self, n: usize) -> T {
181 if is_exact_zero(self.rank_tol) {
182 #[allow(clippy::cast_precision_loss)] // a column count, far below 2^53
183 let nf = n.max(1) as f64;
184 T::EPSILON * T::from_f64(nf)
185 } else {
186 T::from_f64(self.rank_tol)
187 }
188 }
189}
190
191/// Thin QR `A = QR`, `Q ∈ R^{m×n}` explicit with orthonormal columns, `R ∈
192/// R^{n×n}` upper triangular with `r_jj > 0`, `m ≥ n`, full column rank
193/// (Chapter 12.3: Algorithms F, I, D, C, E, R).
194///
195/// ```
196/// use xingo_statla::{MatRef, Qr, QrOptions};
197/// // A = [1 0; 1 1; 1 2] (column-major), b = (1, 2, 4).
198/// let a = [1.0, 1.0, 1.0, 0.0, 1.0, 2.0];
199/// let mut f = Qr::factor(MatRef::new(3, 2, 3, &a)?, &QrOptions::default())?;
200/// let mut x = [0.0; 2];
201/// let res = f.solve_least_squares(&[1.0, 2.0, 4.0], &mut x)?;
202/// assert!((x[0] - 5.0 / 6.0).abs() < 1e-14 && (x[1] - 1.5).abs() < 1e-14);
203/// assert!((res - (1.0f64 / 6.0).sqrt()).abs() < 1e-14);
204/// f.insert_row(3, &[1.0, 3.0])?; // a fourth observation
205/// f.delete_row(0)?; // and the first leaves
206/// assert_eq!((f.nrows(), f.ncols()), (3, 2));
207/// assert!(f.check_invariants(16.0).is_ok());
208/// # Ok::<(), xingo_statla::StatlaError>(())
209/// ```
210#[derive(Clone, Debug)]
211pub struct Qr<T: Real = f64, K: DenseKernel<T> = NaiveDense> {
212 q: DenseBlock<T>,
213 r: DenseBlock<T>,
214 kernel: K,
215 opts: QrOptions,
216}
217
218impl<T: Real> Qr<T, NaiveDense> {
219 /// Householder QR of `A` (`m ≥ n`), `Q` formed explicitly.
220 ///
221 /// # Errors
222 /// [`StatlaError::InvalidArgument`] (`m < n`, invalid options),
223 /// [`StatlaError::NonFinite`], [`StatlaError::RankDeficient`].
224 pub fn factor(a: MatRef<'_, T>, opts: &QrOptions) -> Result<Self, StatlaError> {
225 Self::factor_with(a, NaiveDense, opts)
226 }
227}
228
229/// Where `r_kk < 0` for `k ≥ from`, negate row `k` of `r` and column `k`
230/// of `q` (step F4).
231fn fix_signs<T: Real>(q: &mut DenseBlock<T>, r: &mut DenseBlock<T>, from: usize) {
232 let (m, n) = (q.rows, r.cols);
233 for k in from..n.min(r.rows) {
234 if lt(r.data[k + k * r.rows], T::ZERO) {
235 for j in k..n {
236 r.data[k + j * r.rows] = -r.data[k + j * r.rows];
237 }
238 for v in &mut q.data[k * m..(k + 1) * m] {
239 *v = -*v;
240 }
241 }
242 }
243}
244
245/// `R̂[..n, ..]` of an `(n+1) × c` block, as an `n × c` block.
246fn drop_last_row<T: Real>(r: &DenseBlock<T>) -> DenseBlock<T> {
247 let (rows, cols) = (r.rows - 1, r.cols);
248 let mut out = DenseBlock::zeros(rows, cols);
249 for j in 0..cols {
250 out.data[j * rows..(j + 1) * rows].copy_from_slice(&r.data[j * r.rows..j * r.rows + rows]);
251 }
252 out
253}
254
255impl<T: Real, K: DenseKernel<T>> Qr<T, K> {
256 /// As [`Qr::factor`] with the dense kernel `kernel`.
257 ///
258 /// # Errors
259 /// As [`Qr::factor`].
260 pub fn factor_with(a: MatRef<'_, T>, kernel: K, opts: &QrOptions) -> Result<Self, StatlaError> {
261 // F1.
262 opts.validate()?;
263 let (m, n) = (a.rows(), a.cols());
264 if m < n {
265 return Err(StatlaError::InvalidArgument {
266 what: "Qr::factor: fewer rows than columns",
267 });
268 }
269 let mut w = a.to_block();
270 check_finite("a", &w.data)?;
271 let col_norms: Vec<T> = (0..n).map(|j| norm2(&w.data[j * m..(j + 1) * m])).collect();
272 // F2.
273 let mut taus = vec![T::ZERO; n];
274 for k in 0..n {
275 let (left, right) = w.data.split_at_mut((k + 1) * m);
276 let x = &mut left[k * m + k..];
277 taus[k] = householder(x);
278 let v = &x[1..];
279 for j in 0..n - k - 1 {
280 apply_householder(taus[k], v, &mut right[j * m + k..(j + 1) * m]);
281 }
282 }
283 let mut r = DenseBlock::zeros(n, n);
284 for j in 0..n {
285 for i in 0..=j {
286 r.data[i + j * n] = w.data[i + j * m];
287 }
288 }
289 // F3.
290 let mut q = DenseBlock::zeros(m, n);
291 for k in 0..n {
292 q.data[k + k * m] = T::ONE;
293 }
294 for k in (0..n).rev() {
295 let v = &w.data[k * m + k + 1..(k + 1) * m];
296 for j in k..n {
297 apply_householder(taus[k], v, &mut q.data[j * m + k..(j + 1) * m]);
298 }
299 }
300 // F4.
301 fix_signs(&mut q, &mut r, 0);
302 // F5.
303 let tau = opts.tau::<T>(n);
304 for k in 0..n {
305 if le_exact(r.data[k + k * n], tau * col_norms[k]) {
306 return Err(StatlaError::RankDeficient { column: k });
307 }
308 }
309 let f = Self {
310 q,
311 r,
312 kernel,
313 opts: *opts,
314 };
315 debug_assert_eq!(f.check_shape(), Ok(()), "(Q2) after factor");
316 Ok(f)
317 }
318
319 /// `m`.
320 #[must_use]
321 pub fn nrows(&self) -> usize {
322 self.q.rows
323 }
324
325 /// `n`.
326 #[must_use]
327 pub fn ncols(&self) -> usize {
328 self.r.cols
329 }
330
331 /// `Q`.
332 #[must_use]
333 pub fn q(&self) -> MatRef<'_, T> {
334 MatRef::from_block(&self.q)
335 }
336
337 /// `R`.
338 #[must_use]
339 pub fn r(&self) -> MatRef<'_, T> {
340 MatRef::from_block(&self.r)
341 }
342
343 /// Insert the row `w` (length `n`) before row `i` (`i = m` appends)
344 /// (Algorithm I).
345 ///
346 /// # Errors
347 /// [`StatlaError::Dimension`], [`StatlaError::InvalidArgument`],
348 /// [`StatlaError::NonFinite`]; unchanged on error (Q3).
349 pub fn insert_row(&mut self, i: usize, w: &[T]) -> Result<(), StatlaError> {
350 let (m, n) = (self.nrows(), self.ncols());
351 // I1.
352 check_len("w", n, w.len())?;
353 if i > m {
354 return Err(StatlaError::InvalidArgument {
355 what: "Qr::insert_row: row index > m",
356 });
357 }
358 check_finite("w", w)?;
359 // I2.
360 let m1 = m + 1;
361 let mut q = DenseBlock::zeros(m1, n);
362 for j in 0..n {
363 let src = &self.q.data[j * m..(j + 1) * m];
364 let dst = &mut q.data[j * m1..(j + 1) * m1];
365 dst[..i].copy_from_slice(&src[..i]);
366 dst[i + 1..].copy_from_slice(&src[i..]);
367 }
368 let mut e = vec![T::ZERO; m1];
369 e[i] = T::ONE;
370 let mut wr = w.to_vec();
371 // I3.
372 for j in 0..n {
373 let (g, rho) = givens(self.r.data[j + j * n], wr[j]);
374 self.r.data[j + j * n] = rho;
375 wr[j] = T::ZERO;
376 for l in j + 1..n {
377 let (p, s) = g.apply(self.r.data[j + l * n], wr[l]);
378 self.r.data[j + l * n] = p;
379 wr[l] = s;
380 }
381 for (x, y) in q.data[j * m1..(j + 1) * m1].iter_mut().zip(e.iter_mut()) {
382 let (p, s) = g.apply(*x, *y);
383 *x = p;
384 *y = s;
385 }
386 }
387 // I4.
388 self.q = q;
389 debug_assert_eq!(self.check_shape(), Ok(()), "(Q2) after insert_row");
390 Ok(())
391 }
392
393 /// Delete row `i` (requires `m > n`) (Algorithm D).
394 ///
395 /// # Errors
396 /// [`StatlaError::InvalidArgument`], [`StatlaError::RankDeficient`]
397 /// (with `column = i`: the rows left are rank deficient); unchanged on
398 /// error (Q3).
399 pub fn delete_row(&mut self, i: usize) -> Result<(), StatlaError> {
400 let (m, n) = (self.nrows(), self.ncols());
401 if m <= n {
402 return Err(StatlaError::InvalidArgument {
403 what: "Qr::delete_row: requires m > n",
404 });
405 }
406 if i >= m {
407 return Err(StatlaError::InvalidArgument {
408 what: "Qr::delete_row: row index >= m",
409 });
410 }
411 // D1.
412 let mut z = vec![T::ZERO; m];
413 z[i] = T::ONE;
414 let mut h = vec![T::ZERO; n];
415 let (nu, _) = orthogonalize(&self.q, &mut z, &mut h, T::from_f64(self.opts.reorth_eta));
416 if le_exact(nu, self.opts.tau::<T>(n)) {
417 return Err(StatlaError::RankDeficient { column: i });
418 }
419 // D2.
420 let n1 = n + 1;
421 let mut mq = DenseBlock::zeros(m, n1);
422 mq.data[..m * n].copy_from_slice(&self.q.data);
423 for (d, &s) in mq.data[m * n..].iter_mut().zip(&z) {
424 *d = s / nu;
425 }
426 let mut rh = DenseBlock::zeros(n1, n);
427 for j in 0..n {
428 rh.data[j * n1..j * n1 + n].copy_from_slice(&self.r.data[j * n..(j + 1) * n]);
429 }
430 let mut w: Vec<T> = (0..n1).map(|k| mq.data[i + k * m]).collect();
431 // D3.
432 for k in (0..n).rev() {
433 let (g, rho) = givens(w[k], w[k + 1]);
434 w[k] = rho;
435 w[k + 1] = T::ZERO;
436 g.rotate_rows(&mut rh, k, k + 1, k);
437 g.rotate_cols(&mut mq.data, m, k, k + 1);
438 }
439 // D4.
440 let mut r = DenseBlock::zeros(n, n);
441 for j in 0..n {
442 for p in 0..=j {
443 r.data[p + j * n] = rh.data[p + 1 + j * n1];
444 }
445 }
446 let m0 = m - 1;
447 let mut q = DenseBlock::zeros(m0, n);
448 for j in 0..n {
449 let src = &mq.data[(j + 1) * m..(j + 2) * m];
450 let dst = &mut q.data[j * m0..(j + 1) * m0];
451 dst[..i].copy_from_slice(&src[..i]);
452 dst[i..].copy_from_slice(&src[i + 1..]);
453 }
454 fix_signs(&mut q, &mut r, 0);
455 self.q = q;
456 self.r = r;
457 debug_assert_eq!(self.check_shape(), Ok(()), "(Q2) after delete_row");
458 Ok(())
459 }
460
461 /// Insert the column `c` (length `m`) before column `j` (requires `m >
462 /// n`) (Algorithm C).
463 ///
464 /// # Errors
465 /// [`StatlaError::Dimension`], [`StatlaError::InvalidArgument`],
466 /// [`StatlaError::NonFinite`], [`StatlaError::RankDeficient`];
467 /// unchanged on error.
468 pub fn insert_col(&mut self, j: usize, c: &[T]) -> Result<(), StatlaError> {
469 let (m, n) = (self.nrows(), self.ncols());
470 // C1.
471 check_len("c", m, c.len())?;
472 if m <= n {
473 return Err(StatlaError::InvalidArgument {
474 what: "Qr::insert_col: requires m > n",
475 });
476 }
477 if j > n {
478 return Err(StatlaError::InvalidArgument {
479 what: "Qr::insert_col: column index > n",
480 });
481 }
482 check_finite("c", c)?;
483 // C2.
484 let cn = norm2(c);
485 let mut z = c.to_vec();
486 let mut h = vec![T::ZERO; n];
487 let (rho, _) = orthogonalize(&self.q, &mut z, &mut h, T::from_f64(self.opts.reorth_eta));
488 if le_exact(rho, self.opts.tau::<T>(n + 1) * cn) {
489 return Err(StatlaError::RankDeficient { column: j });
490 }
491 // C3.
492 let n1 = n + 1;
493 let mut mq = DenseBlock::zeros(m, n1);
494 mq.data[..m * n].copy_from_slice(&self.q.data);
495 for (d, &s) in mq.data[m * n..].iter_mut().zip(&z) {
496 *d = s / rho;
497 }
498 let mut rh = DenseBlock::zeros(n1, n1);
499 for p in 0..n1 {
500 let dst = &mut rh.data[p * n1..p * n1 + n];
501 match p.cmp(&j) {
502 core::cmp::Ordering::Less => {
503 dst.copy_from_slice(&self.r.data[p * n..(p + 1) * n]);
504 }
505 core::cmp::Ordering::Equal => {
506 dst.copy_from_slice(&h);
507 rh.data[n + p * n1] = rho;
508 }
509 core::cmp::Ordering::Greater => {
510 dst.copy_from_slice(&self.r.data[(p - 1) * n..p * n]);
511 }
512 }
513 }
514 // C4.
515 for k in (j + 1..=n).rev() {
516 let (g, top) = givens(rh.data[k - 1 + j * n1], rh.data[k + j * n1]);
517 rh.data[k - 1 + j * n1] = top;
518 rh.data[k + j * n1] = T::ZERO;
519 g.rotate_rows(&mut rh, k - 1, k, j + 1);
520 g.rotate_cols(&mut mq.data, m, k - 1, k);
521 }
522 fix_signs(&mut mq, &mut rh, j);
523 self.q = mq;
524 self.r = rh;
525 debug_assert_eq!(self.check_shape(), Ok(()), "(Q2) after insert_col");
526 Ok(())
527 }
528
529 /// Delete column `j` (Algorithm E).
530 ///
531 /// # Errors
532 /// [`StatlaError::InvalidArgument`].
533 pub fn delete_col(&mut self, j: usize) -> Result<(), StatlaError> {
534 let (m, n) = (self.nrows(), self.ncols());
535 if j >= n {
536 return Err(StatlaError::InvalidArgument {
537 what: "Qr::delete_col: column index >= n",
538 });
539 }
540 // E1.
541 let mut rh = DenseBlock::zeros(n, n - 1);
542 for p in 0..n - 1 {
543 let src = if p < j { p } else { p + 1 };
544 rh.data[p * n..(p + 1) * n].copy_from_slice(&self.r.data[src * n..(src + 1) * n]);
545 }
546 // E2.
547 for p in j..n - 1 {
548 let (g, top) = givens(rh.data[p + p * n], rh.data[p + 1 + p * n]);
549 rh.data[p + p * n] = top;
550 rh.data[p + 1 + p * n] = T::ZERO;
551 g.rotate_rows(&mut rh, p, p + 1, p + 1);
552 g.rotate_cols(&mut self.q.data, m, p, p + 1);
553 }
554 // E3.
555 let r = drop_last_row(&rh);
556 self.q.data.truncate(m * (n - 1));
557 self.q.cols = n - 1;
558 self.r = r;
559 fix_signs(&mut self.q, &mut self.r, j);
560 debug_assert_eq!(self.check_shape(), Ok(()), "(Q2) after delete_col");
561 Ok(())
562 }
563
564 /// `A ← A + u vᵀ` (`u` of length `m`, `v` of length `n`) (Algorithm
565 /// R).
566 ///
567 /// # Errors
568 /// [`StatlaError::Dimension`], [`StatlaError::NonFinite`],
569 /// [`StatlaError::RankDeficient`] (the result lost rank); unchanged on
570 /// error.
571 pub fn rank1_update(&mut self, u: &[T], v: &[T]) -> Result<(), StatlaError> {
572 let (m, n) = (self.nrows(), self.ncols());
573 // R1.
574 check_len("u", m, u.len())?;
575 check_len("v", n, v.len())?;
576 check_finite("u", u)?;
577 check_finite("v", v)?;
578 let tau = self.opts.tau::<T>(n);
579 // R2.
580 let un = norm2(u);
581 let mut z = u.to_vec();
582 let mut w = vec![T::ZERO; n];
583 let (mut rho, _) =
584 orthogonalize(&self.q, &mut z, &mut w, T::from_f64(self.opts.reorth_eta));
585 if le_exact(rho, tau * un) {
586 rho = T::ZERO;
587 }
588 // R3.
589 let n1 = n + 1;
590 let mut mq = DenseBlock::zeros(m, n1);
591 mq.data[..m * n].copy_from_slice(&self.q.data);
592 if !is_exact_zero(rho) {
593 for (d, &s) in mq.data[m * n..].iter_mut().zip(&z) {
594 *d = s / rho;
595 }
596 }
597 let mut rh = DenseBlock::zeros(n1, n);
598 for j in 0..n {
599 rh.data[j * n1..j * n1 + n].copy_from_slice(&self.r.data[j * n..(j + 1) * n]);
600 }
601 let mut wh = w;
602 wh.push(rho);
603 // R4.
604 for k in (0..n).rev() {
605 let (g, top) = givens(wh[k], wh[k + 1]);
606 wh[k] = top;
607 wh[k + 1] = T::ZERO;
608 g.rotate_rows(&mut rh, k, k + 1, k);
609 g.rotate_cols(&mut mq.data, m, k, k + 1);
610 }
611 // R5.
612 let t = wh.first().copied().unwrap_or(T::ZERO);
613 for (j, &vj) in v.iter().enumerate() {
614 rh.data[j * n1] += t * vj;
615 }
616 // R6.
617 for k in 0..n {
618 let (g, top) = givens(rh.data[k + k * n1], rh.data[k + 1 + k * n1]);
619 rh.data[k + k * n1] = top;
620 rh.data[k + 1 + k * n1] = T::ZERO;
621 g.rotate_rows(&mut rh, k, k + 1, k + 1);
622 g.rotate_cols(&mut mq.data, m, k, k + 1);
623 }
624 // R7.
625 let mut r = drop_last_row(&rh);
626 mq.data.truncate(m * n);
627 mq.cols = n;
628 fix_signs(&mut mq, &mut r, 0);
629 for k in 0..n {
630 // The scale of the new column a_k + v_k u, bounded before any
631 // cancellation: ‖a_k‖ + |v_k| ‖u‖ (a relative test against the
632 // new column's own norm would accept the rounding residue of a
633 // cancelled column).
634 let cn = norm2(&self.r.data[(k * n)..=(k * n + k)]) + v[k].abs() * un;
635 if le_exact(r.data[k + k * n], tau * cn) {
636 return Err(StatlaError::RankDeficient { column: k });
637 }
638 }
639 self.q = mq;
640 self.r = r;
641 debug_assert_eq!(self.check_shape(), Ok(()), "(Q2) after rank1_update");
642 Ok(())
643 }
644
645 /// `x = argmin ‖A x − b‖` (`x ← R⁻¹ Qᵀ b`); returns `‖b − Q Qᵀ b‖`,
646 /// the residual norm.
647 ///
648 /// # Errors
649 /// [`StatlaError::Dimension`].
650 pub fn solve_least_squares(&self, b: &[T], x: &mut [T]) -> Result<T, StatlaError> {
651 let (m, n) = (self.nrows(), self.ncols());
652 check_len("b", m, b.len())?;
653 check_len("x", n, x.len())?;
654 let mut res = b.to_vec();
655 for j in 0..n {
656 let qj = &self.q.data[j * m..(j + 1) * m];
657 x[j] = dot(qj, b);
658 }
659 for j in 0..n {
660 axpy_sub(x[j], &self.q.data[j * m..(j + 1) * m], &mut res);
661 }
662 for j in (0..n).rev() {
663 let col = &self.r.data[(j * n)..=(j * n + j)];
664 let xj = x[j] / col[j];
665 x[j] = xj;
666 axpy_sub(xj, &col[..j], &mut x[..j]);
667 }
668 Ok(norm2(&res))
669 }
670
671 /// The Q-less view: a [`Cholesky`] of `AᵀA` holding a copy of `R`
672 /// (with the default [`CholOptions`]).
673 ///
674 /// # Errors
675 /// As [`Cholesky::from_upper`].
676 pub fn to_cholesky(&self) -> Result<Cholesky<T, K>, StatlaError>
677 where
678 K: Clone,
679 {
680 Cholesky::from_upper(self.r.clone(), self.kernel.clone(), &CholOptions::default())
681 }
682
683 /// The shape part of (Q2): consistent blocks, `R` upper triangular with
684 /// finite entries and positive diagonal, `Q` finite. `O(mn)`.
685 fn check_shape(&self) -> Result<(), &'static str> {
686 let (m, n) = (self.q.rows, self.r.cols);
687 if self.r.rows != n
688 || self.q.cols != n
689 || self.q.data.len() != m * n
690 || self.r.data.len() != n * n
691 {
692 return Err("(Q2) Q and R are not consistent blocks");
693 }
694 if m < n {
695 return Err("(Q2) fewer rows than columns");
696 }
697 if self.q.data.iter().any(|v| !v.is_finite()) {
698 return Err("(Q2) Q has a non-finite entry");
699 }
700 for j in 0..n {
701 for i in 0..n {
702 let v = self.r.data[i + j * n];
703 if !v.is_finite() {
704 return Err("(Q2) R has a non-finite entry");
705 }
706 if i > j && !is_exact_zero(v) {
707 return Err("(Q2) R is not upper triangular");
708 }
709 if i == j && !lt(T::ZERO, v) {
710 return Err("(Q2) R has a nonpositive diagonal entry");
711 }
712 }
713 }
714 Ok(())
715 }
716
717 /// Invariants (Q1) and the shape part of (Q2), with `c_Q` given:
718 /// `‖QᵀQ − I‖_F ≤ c_Q · m · u` (computed in `T`, `O(mn²)`).
719 ///
720 /// # Errors
721 /// The text of the violated invariant.
722 pub fn check_invariants(&self, c_q: f64) -> Result<(), &'static str> {
723 self.check_shape()?;
724 let (m, n) = (self.q.rows, self.q.cols);
725 let mut s = T::ZERO;
726 for j in 0..n {
727 let qj = &self.q.data[j * m..(j + 1) * m];
728 for i in 0..n {
729 let mut d = dot(&self.q.data[i * m..(i + 1) * m], qj);
730 if i == j {
731 d -= T::ONE;
732 }
733 s += d * d;
734 }
735 }
736 #[allow(clippy::cast_precision_loss)] // a row count, far below 2^53
737 let bound = T::from_f64(c_q * m.max(1) as f64) * T::EPSILON * T::from_f64(0.5);
738 if !s.is_finite() || !le_exact(s.sqrt(), bound) {
739 return Err("(Q1) Q has lost orthogonality");
740 }
741 Ok(())
742 }
743}