Skip to main content

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}