Skip to main content

xingo_statla/
cholesky.rs

1//! # Chapter 12.2 — Cholesky with rank-1 update and downdate
2//!
3//! ## Purpose
4//! A covariance, information or Gram matrix `A` changes by `± x xᵀ` — an
5//! observation enters or leaves a recursive least-squares fit, a Kalman
6//! filter absorbs a measurement, a Gaussian-process refit drops a point —
7//! and its upper Cholesky factor `R` (`RᵀR = A`) must follow in `O(n²)`
8//! instead of the `O(n³)` of a refactorization. [`Cholesky`] keeps `R`
9//! under `update` (`A + x xᵀ`) and `downdate` (`A − x xᵀ`), with solves,
10//! the whitening `R⁻ᵀ b` and the log-determinant.
11//!
12//! ## Notation
13//! `A ∈ T^{n×n}` symmetric positive definite (only its upper triangle is
14//! read); `R` upper triangular with `r_jj > 0`; `x ∈ T^n`; `u` the unit
15//! roundoff of `T`; `A_t` the matrix the sequence of operations defines.
16//! A rotation `G = (c, s)` acts as `(p, q) ↦ (c p + s q, c q − s p)`
17//! (Chapter 12.0.4).
18//!
19//! ## Algorithm F (factor)
20//! F1. \[Check.\] `A` square, its upper triangle finite, the options valid.
21//! F2. \[Factor.\] Copy the upper triangle into the lower triangle of a
22//!     block `W` (`w_ij = a_ji`, `i ≥ j`) and run `K::potrf` (Algorithm P of
23//!     Chapter 5.16): `W = L Lᵀ`; a nonpositive pivot at `j` is
24//!     [`StatlaError::NotPositiveDefinite`]` { column: j }`.
25//! F3. \[Pivot test.\] Reject column `j` unless `l_jj² > pivot_tol · a_jj`
26//!     (and `l_jj` is finite and positive, whatever the kernel).
27//! F4. \[Transpose.\] `R ← Lᵀ`, strict lower triangle zero.
28//!
29//! ## Algorithm U (update, `A + x xᵀ`; LINPACK `dchud`)
30//! U0. \[Check.\] `x.len() = n` and `x` finite — the only failures, checked
31//!     before any write (H3).
32//! U1. \[Loop.\] For `j = 0, …, n − 1`: `ξ ← x_j`; apply the rotations `G_0
33//!     … G_{j−1}` already found to the pairs `(r_ij, ξ)`, `i = 0, …, j − 1`,
34//!     in that order: `(r_ij, ξ) ← G_i (r_ij, ξ)`.
35//! U2. \[Rotate.\] Find `G_j` with `G_j (r_jj, ξ) = (ρ, 0)`, `ρ ≥ 0`
36//!     (Algorithm G of 12.0.4, the safe `hypot`); `r_jj ← ρ`.
37//! Cost `2n²` flops (`≈ 3n²` with the scaling of G2). Since `ρ ≥ r_jj >
38//! 0`, (H1) is kept.
39//!
40//! ## Algorithm C (downdate, `A − x xᵀ`; LINPACK `dchdd`, Saunders 1972)
41//! C0. \[Check.\] `x.len() = n`, `x` finite.
42//! C1. \[Solve.\] `Rᵀ a = x` (forward substitution).
43//! C2. \[Test.\] `α² ← 1 − ‖a‖²` (‖a‖ by Algorithm N); if `α²` is not
44//!     finite or `α² ≤ downdate_tol`, return
45//!     [`StatlaError::DowndateIndefinite`] — **before any change to `R`**
46//!     (H3 for free). (`RᵀR − xxᵀ = Rᵀ(I − aaᵀ)R` is positive definite iff
47//!     `‖a‖ < 1`.)
48//! C3. \[Rotations.\] `α ← √α²`; for `i = n − 1, …, 0`: `μ ← α + |a_i|`,
49//!     `α̂ ← α/μ`, `b ← a_i/μ`, `ν ← √(α̂² + b²)`, `c_i ← α̂/ν`, `s_i ← b/ν`,
50//!     `α ← μν`.
51//! C3′. \[Diagonal first.\] The new diagonal is `r_jj ← c_j r_jj` (step C4
52//!     at `i = j`, where `ξ = 0`). If one of them is not finite and
53//!     positive (only an underflow can do that), return
54//!     `DowndateIndefinite` with the margin of C2 — still before any
55//!     write. *An addition of this edition to LINPACK's algorithm.*
56//! C4. \[Apply.\] For each column `j`: `ξ ← 0`; for `i = j, …, 0`: `(r_ij,
57//!     ξ) ← (c_i r_ij − s_i ξ, c_i ξ + s_i r_ij)`.
58//! C5. \[Signs.\] Flip the rows with `r_ii < 0` (none, after C3′; kept as
59//!     the contract states it, so that (H1) does not rest on C3′ alone).
60//! Cost `≈ 3n²` flops plus the `n²` of C1. Backward stable in the mixed
61//! sense of Stewart (1979). The forward error against a refactorization
62//! grows like `κ₂(R̃) u` — the error of any algorithm, because two
63//! refactorizations of `A_t` perturbed at the level `u` already differ by
64//! that much (pilot s01, table A).
65//!
66//! ## Solves and the determinant
67//! `solve`: `Rᵀy = b` forward, then `Rx = y` backward (both
68//! column-oriented on `R`). `solve_upper_t`: the forward half only, `b ←
69//! R⁻ᵀb`, so `‖R⁻ᵀb‖² = bᵀA⁻¹b`. `log2_det_parts`: `det R = Π r_jj = m ·
70//! 2^e` with `m ∈ [1, 2)`, accumulated by splitting each `r_jj = f_j 2^{k_j}`
71//! with powers of two read off the `f64` bits (exact scalings), so it
72//! neither overflows nor underflows for any `n`; then `ln det A = 2(ln m +
73//! e ln 2)` in the caller's precision.
74//!
75//! ## Invariants
76//! (H1) `R` upper triangular (strict lower triangle exactly zero),
77//!      `r_jj > 0`, every entry finite — [`Cholesky::check_invariants`],
78//!      `debug_assert!` after each of F, U, C.
79//! (H2) `‖RᵀR − A_t‖_F ≤ c_H · n · u · ‖A_t‖_F` after any sequence; `c_H =
80//!      8` in the tests (`tests/cholesky.rs`, against `A_t` and `RᵀR` in
81//!      double-double; the norm along the path when downdates cancel more
82//!      than half of `A`).
83//! (H3) A failed `update`/`downdate` leaves `R` bit for bit unchanged:
84//!      U0 and C0–C3′ read `R` and write only local vectors.
85//!
86//! ## Acceptance (L3.2, S9 of D-0127) and what was measured
87//! In `f64` and `DoubleDouble`, `n ≤ 200`, `κ(A_t)` from `10` to `10¹²`
88//! (`tests/cholesky.rs`, proptests and fixed seeds):
89//! (i) `update∘downdate` and `downdate∘update` within `10 n u` of the
90//!     original factor (relative Frobenius);
91//! (ii) backward error (H2) `≤ c_H n u` at every `κ`;
92//! (iii) forward error against a refactorization of `A_t` `≤ 10⁻¹²` where
93//!      `κ(A_t) ≤ 10⁸`, and elsewhere `≤ 10×` the distance between two
94//!      refactorizations of `A_t` perturbed at the level `u`;
95//! (iv) a failed operation leaves the factor bit for bit unchanged.
96//!
97//! **What holds.** (i), (ii), (iv) per instance with wide margins
98//! (`upd∘dd`, `dd∘upd` `≤ 4.9 n u` at `n = 3`, `≤ 0.05 n u` for `n ≥ 50`).
99//! (iii) as worded does **not** hold per instance: the forward error of
100//! the downdate is governed by `1 − ‖a‖²`, not by `κ` alone — `n = 2`,
101//! `κ = 10⁶` gave `9.4·10⁻¹²`; at `κ = 10⁸`, `n = 100`, 10 of 200 seeds
102//! exceed `10⁻¹²`; the per-instance ratio to the distance between two
103//! refactorizations reaches 40–150 for `n ≤ 3`. The tests enforce what was
104//! measured to hold — per instance `fwd ≤ 8 κ u` (the first-order bound of
105//! any algorithm working from `R`), and the pilot's aggregate form (the
106//! maximum over 20 seeds at `n = 100, 200`: `≤ 10⁻¹²` where `κ ≤ 10⁶`, `≤
107//! 10×` the maximum distance everywhere) — and keep the literal criterion
108//! as an ignored test (question Q-L32-2 of task L3.2, settled this way by
109//! D-0132). The measured
110//! values are in `.claude/scratch/l32/l32-tables.md`; the example
111//! `accuracy` regenerates them.
112//!
113//! ## References
114//! LINPACK Users' Guide (1979), ch. 10 (`dchud`, `dchdd`); Saunders (1972);
115//! Stewart, J. IMA 23 (1979); Gill, Golub, Murray & Saunders, Math. Comp.
116//! 28 (1974); Higham (2002), Theorem 10.3 (backward error of Cholesky);
117//! pilot s01 (`.claude/scratch/s01/s01-pilot`). All cited from memory.
118
119use xingo_sparse::{DenseBlock, DenseError, DenseKernel, NaiveDense, Real};
120
121use crate::real::{is_exact_zero, le_exact, lt};
122use crate::small::{Rot, axpy_sub, check_finite, check_len, dot, givens, norm2};
123use crate::{MatMut, MatRef, StatlaError};
124
125/// Options of [`Cholesky`]: every threshold of chapter 12.2 lives here.
126#[derive(Clone, Copy, Debug, PartialEq)]
127pub struct CholOptions {
128    /// Step F3: a pivot `d_j` is rejected unless `d_j > pivot_tol · a_jj`
129    /// (default `0`: reject only nonpositive pivots, as LAPACK `potrf`).
130    pub pivot_tol: f64,
131    /// Step C2: the downdate is rejected unless `1 − ‖a‖² > downdate_tol`
132    /// (default `0`, LINPACK's test). A positive value refuses downdates
133    /// whose result is too ill conditioned to be trusted (forward error ≈
134    /// `u / margin`; pilot table A).
135    pub downdate_tol: f64,
136}
137
138impl Default for CholOptions {
139    fn default() -> Self {
140        Self {
141            pivot_tol: 0.0,
142            downdate_tol: 0.0,
143        }
144    }
145}
146
147impl CholOptions {
148    /// Both thresholds finite and nonnegative (a negative `downdate_tol`
149    /// would let C3 take the square root of a nonpositive `α²`).
150    fn validate(&self) -> Result<(), StatlaError> {
151        let ok = |v: f64| v.is_finite() && le_exact(0.0, v);
152        if !ok(self.pivot_tol) {
153            return Err(StatlaError::InvalidArgument {
154                what: "CholOptions::pivot_tol must be finite and >= 0",
155            });
156        }
157        if !ok(self.downdate_tol) {
158            return Err(StatlaError::InvalidArgument {
159                what: "CholOptions::downdate_tol must be finite and >= 0",
160            });
161        }
162        Ok(())
163    }
164}
165
166/// The upper Cholesky factor `R` of a symmetric positive definite `A =
167/// RᵀR`, kept up to date under `A ← A ± x xᵀ` (Chapter 12.2: Algorithms
168/// F, U, C).
169///
170/// ```
171/// use xingo_statla::{CholOptions, Cholesky, MatRef};
172/// // A = [[4, 2], [2, 3]] (upper triangle read).
173/// let a = [4.0, 0.0, 2.0, 3.0];
174/// let mut c = Cholesky::factor(MatRef::new(2, 2, 2, &a)?, &CholOptions::default())?;
175/// c.update(&[1.0, 1.0])?; // A + x xᵀ = [[5, 3], [3, 4]]
176/// let info = c.downdate(&[1.0, 1.0])?; // back to A
177/// assert!(info.margin > 0.0 && info.margin <= 1.0);
178/// let mut b = [6.0, 5.0]; // A · (1, 1)
179/// c.solve(&mut b)?;
180/// assert!((b[0] - 1.0).abs() < 1e-14 && (b[1] - 1.0).abs() < 1e-14);
181/// assert!(c.downdate(&[3.0, 0.0]).is_err()); // A − 9 e₀e₀ᵀ is indefinite
182/// # Ok::<(), xingo_statla::StatlaError>(())
183/// ```
184#[derive(Clone, Debug)]
185pub struct Cholesky<T: Real = f64, K: DenseKernel<T> = NaiveDense> {
186    r: DenseBlock<T>,
187    // Kept with the factor (the kernel it was built with); read again by
188    // the operations of v0.2 that refactor trailing blocks (S8).
189    #[allow(dead_code)]
190    kernel: K,
191    opts: CholOptions,
192}
193
194/// What a successful downdate saw.
195#[derive(Clone, Copy, Debug, PartialEq)]
196#[non_exhaustive]
197pub struct DowndateInfo {
198    /// `1 − ‖a‖²` of step C2, in `(downdate_tol, 1]`: near `0` means the
199    /// result is nearly singular and its forward error is large.
200    pub margin: f64,
201}
202
203impl<T: Real> Cholesky<T, NaiveDense> {
204    /// Factor the symmetric positive definite `A` (upper triangle read)
205    /// with the reference kernel.
206    ///
207    /// # Errors
208    /// [`StatlaError::InvalidArgument`] (not square, invalid options),
209    /// [`StatlaError::NonFinite`], [`StatlaError::NotPositiveDefinite`].
210    pub fn factor(a: MatRef<'_, T>, opts: &CholOptions) -> Result<Self, StatlaError> {
211        Self::factor_with(a, NaiveDense, opts)
212    }
213}
214
215impl<T: Real, K: DenseKernel<T>> Cholesky<T, K> {
216    /// As [`Cholesky::factor`] with the dense kernel `kernel`.
217    ///
218    /// # Errors
219    /// As [`Cholesky::factor`].
220    pub fn factor_with(
221        a: MatRef<'_, T>,
222        kernel: K,
223        opts: &CholOptions,
224    ) -> Result<Self, StatlaError> {
225        // F1.
226        opts.validate()?;
227        let n = a.rows();
228        if a.cols() != n {
229            return Err(StatlaError::InvalidArgument {
230                what: "Cholesky::factor: matrix not square",
231            });
232        }
233        let mut w = DenseBlock::zeros(n, n);
234        for j in 0..n {
235            let col = a.col(j).unwrap_or(&[]);
236            for (i, &v) in col.iter().enumerate().take(j + 1) {
237                if !v.is_finite() {
238                    return Err(StatlaError::NonFinite {
239                        what: "a",
240                        index: i + j * n,
241                    });
242                }
243                // F2: w_ji = a_ij for i ≤ j (lower triangle of W).
244                w.data[j + i * n] = v;
245            }
246        }
247        // F2.
248        kernel.potrf(&mut w).map_err(|e| match e {
249            DenseError::NotPositiveDefinite { position } => {
250                StatlaError::NotPositiveDefinite { column: position }
251            }
252            DenseError::Dimension => StatlaError::InvalidArgument {
253                what: "Cholesky::factor: the kernel rejected the dimensions",
254            },
255        })?;
256        // F3.
257        let tol = T::from_f64(opts.pivot_tol);
258        for j in 0..n {
259            let l = w.data[j + j * n];
260            let ajj = a.get(j, j).unwrap_or(T::ZERO);
261            if !l.is_finite() || !lt(T::ZERO, l) || le_exact(l * l, tol * ajj) {
262                return Err(StatlaError::NotPositiveDefinite { column: j });
263            }
264        }
265        // F4.
266        let mut r = DenseBlock::zeros(n, n);
267        for j in 0..n {
268            for i in 0..=j {
269                r.data[i + j * n] = w.data[j + i * n];
270            }
271        }
272        let c = Self {
273            r,
274            kernel,
275            opts: *opts,
276        };
277        debug_assert_eq!(c.check_invariants(), Ok(()), "(H1) after factor");
278        Ok(c)
279    }
280
281    /// Adopt an existing upper factor (for instance the `R` of a
282    /// [`crate::Qr`]: the Q-less QR of streaming regression *is* this type).
283    ///
284    /// # Errors
285    /// [`StatlaError::InvalidArgument`] if `r` is not square upper
286    /// triangular with positive diagonal (or the options are invalid);
287    /// [`StatlaError::NonFinite`].
288    pub fn from_upper(
289        r: DenseBlock<T>,
290        kernel: K,
291        opts: &CholOptions,
292    ) -> Result<Self, StatlaError> {
293        opts.validate()?;
294        let n = r.rows;
295        if r.cols != n || r.data.len() != n.saturating_mul(n) {
296            return Err(StatlaError::InvalidArgument {
297                what: "Cholesky::from_upper: not a square block",
298            });
299        }
300        check_finite("r", &r.data)?;
301        let c = Self {
302            r,
303            kernel,
304            opts: *opts,
305        };
306        c.check_invariants()
307            .map_err(|what| StatlaError::InvalidArgument { what })?;
308        Ok(c)
309    }
310
311    /// Order `n`.
312    #[must_use]
313    pub fn n(&self) -> usize {
314        self.r.rows
315    }
316
317    /// `R` (the strict lower triangle of the view is zero).
318    #[must_use]
319    pub fn upper(&self) -> MatRef<'_, T> {
320        MatRef::from_block(&self.r)
321    }
322
323    /// `R`, owned.
324    #[must_use]
325    pub fn into_upper(self) -> DenseBlock<T> {
326        self.r
327    }
328
329    /// `A ← A + x xᵀ` (Algorithm U).
330    ///
331    /// # Errors
332    /// [`StatlaError::Dimension`], [`StatlaError::NonFinite`]; the factor
333    /// is unchanged on error (H3).
334    pub fn update(&mut self, x: &[T]) -> Result<(), StatlaError> {
335        let n = self.n();
336        // U0.
337        check_len("x", n, x.len())?;
338        check_finite("x", x)?;
339        let mut rots = vec![Rot::IDENTITY; n];
340        let r = &mut self.r.data;
341        for j in 0..n {
342            // U1.
343            let mut xi = x[j];
344            let col = &mut r[j * n..(j + 1) * n];
345            for (rij, g) in col[..j].iter_mut().zip(&rots[..j]) {
346                let (p, q) = g.apply(*rij, xi);
347                *rij = p;
348                xi = q;
349            }
350            // U2.
351            let (g, rho) = givens(col[j], xi);
352            rots[j] = g;
353            col[j] = rho;
354        }
355        debug_assert_eq!(self.check_invariants(), Ok(()), "(H1) after update");
356        Ok(())
357    }
358
359    /// `A ← A − x xᵀ` (Algorithm C).
360    ///
361    /// # Errors
362    /// [`StatlaError::Dimension`], [`StatlaError::NonFinite`],
363    /// [`StatlaError::DowndateIndefinite`]; unchanged on error (H3).
364    pub fn downdate(&mut self, x: &[T]) -> Result<DowndateInfo, StatlaError> {
365        let n = self.n();
366        // C0.
367        check_len("x", n, x.len())?;
368        check_finite("x", x)?;
369        // C1.
370        let mut a = x.to_vec();
371        self.forward(&mut a);
372        // C2.
373        let nu = norm2(&a);
374        let alpha2 = T::ONE - nu * nu;
375        if !alpha2.is_finite() {
376            return Err(StatlaError::DowndateIndefinite {
377                margin: f64::NEG_INFINITY,
378            });
379        }
380        let margin = alpha2.to_f64();
381        if le_exact(alpha2, T::from_f64(self.opts.downdate_tol)) {
382            return Err(StatlaError::DowndateIndefinite { margin });
383        }
384        // C3.
385        let mut alpha = alpha2.sqrt();
386        let mut rots = vec![Rot::IDENTITY; n];
387        for i in (0..n).rev() {
388            let mu = alpha + a[i].abs();
389            let ah = alpha / mu;
390            let b = a[i] / mu;
391            let nu = (ah * ah + b * b).sqrt();
392            rots[i] = Rot {
393                c: ah / nu,
394                s: b / nu,
395            };
396            alpha = mu * nu;
397        }
398        // C3′.
399        for (j, g) in rots.iter().enumerate() {
400            let d = g.c * self.r.data[j + j * n];
401            if !d.is_finite() || !lt(T::ZERO, d) {
402                return Err(StatlaError::DowndateIndefinite { margin });
403            }
404        }
405        // C4.
406        let r = &mut self.r.data;
407        for j in 0..n {
408            let col = &mut r[j * n..(j + 1) * n];
409            let mut xi = T::ZERO;
410            for i in (0..=j).rev() {
411                let g = rots[i];
412                let rij = col[i];
413                col[i] = g.c * rij - g.s * xi;
414                xi = g.c * xi + g.s * rij;
415            }
416        }
417        // C5.
418        for i in 0..n {
419            if lt(self.r.data[i + i * n], T::ZERO) {
420                for j in i..n {
421                    self.r.data[i + j * n] = -self.r.data[i + j * n];
422                }
423            }
424        }
425        debug_assert_eq!(self.check_invariants(), Ok(()), "(H1) after downdate");
426        Ok(DowndateInfo { margin })
427    }
428
429    /// `b ← R⁻ᵀ b` without checks (`b.len() = n`).
430    fn forward(&self, b: &mut [T]) {
431        let n = self.n();
432        for j in 0..n {
433            let col = &self.r.data[(j * n)..=(j * n + j)];
434            let s = b[j] - dot(&col[..j], &b[..j]);
435            b[j] = s / col[j];
436        }
437    }
438
439    /// `b ← R⁻¹ b` without checks.
440    fn backward(&self, b: &mut [T]) {
441        let n = self.n();
442        for j in (0..n).rev() {
443            let col = &self.r.data[(j * n)..=(j * n + j)];
444            let xj = b[j] / col[j];
445            b[j] = xj;
446            axpy_sub(xj, &col[..j], &mut b[..j]);
447        }
448    }
449
450    /// `b ← A⁻¹ b`.
451    ///
452    /// # Errors
453    /// [`StatlaError::Dimension`].
454    pub fn solve(&self, b: &mut [T]) -> Result<(), StatlaError> {
455        check_len("b", self.n(), b.len())?;
456        self.forward(b);
457        self.backward(b);
458        Ok(())
459    }
460
461    /// `B ← A⁻¹ B` for a block of right-hand sides.
462    ///
463    /// # Errors
464    /// [`StatlaError::Dimension`].
465    pub fn solve_block(&self, mut b: MatMut<'_, T>) -> Result<(), StatlaError> {
466        let cols = b.as_ref().cols();
467        check_len("b (rows)", self.n(), b.as_ref().rows())?;
468        for j in 0..cols {
469            if let Some(col) = b.col_mut(j) {
470                self.forward(col);
471                self.backward(col);
472            }
473        }
474        Ok(())
475    }
476
477    /// `b ← R⁻ᵀ b` (whitening: `‖R⁻ᵀ b‖² = bᵀA⁻¹b`, a Mahalanobis
478    /// distance).
479    ///
480    /// # Errors
481    /// [`StatlaError::Dimension`].
482    pub fn solve_upper_t(&self, b: &mut [T]) -> Result<(), StatlaError> {
483        check_len("b", self.n(), b.len())?;
484        self.forward(b);
485        Ok(())
486    }
487
488    /// `ln det A = 2 Σ ln r_jj`, returned as `(m, e)` with `det R = Π r_jj
489    /// = m · 2^e` exactly split, `m ∈ [1, 2)` (`(1, 0)` for `n = 0`): no `ln`
490    /// in [`Real`], so the caller forms `ln det A = 2 (ln m + e ln 2)` in
491    /// its own precision (`log₂ det R = log₂ m + e`).
492    #[must_use]
493    pub fn log2_det_parts(&self) -> (T, i64) {
494        let n = self.n();
495        let two = T::from_f64(2.0);
496        let half = T::from_f64(0.5);
497        let mut m = T::ONE;
498        let mut e: i64 = 0;
499        for j in 0..n {
500            let d = self.r.data[j + j * n];
501            let (f, k) = split_pow2(d);
502            m *= f;
503            e += k;
504            while le_exact(two, m) {
505                m *= half;
506                e += 1;
507            }
508            while lt(m, T::ONE) && lt(T::ZERO, m) {
509                m *= two;
510                e -= 1;
511            }
512        }
513        (m, e)
514    }
515
516    /// Invariant (H1).
517    ///
518    /// # Errors
519    /// The text of the violated invariant.
520    pub fn check_invariants(&self) -> Result<(), &'static str> {
521        let n = self.r.rows;
522        if self.r.cols != n || self.r.data.len() != n * n {
523            return Err("(H1) R is not a consistent square block");
524        }
525        for j in 0..n {
526            for i in 0..n {
527                let v = self.r.data[i + j * n];
528                if !v.is_finite() {
529                    return Err("(H1) R has a non-finite entry");
530                }
531                if i > j && !is_exact_zero(v) {
532                    return Err("(H1) R is not upper triangular");
533                }
534                if i == j && !lt(T::ZERO, v) {
535                    return Err("(H1) R has a nonpositive diagonal entry");
536                }
537            }
538        }
539        Ok(())
540    }
541}
542
543/// `d = f · 2^k` with `2^k` the power of two of `d`'s `f64` value (exact
544/// scalings); `f ≈ [1, 2)` up to the rounding of `to_f64`, normalized by
545/// the caller.
546fn split_pow2<T: Real>(d: T) -> (T, i64) {
547    let bits = d.to_f64().to_bits();
548    let exp = i64::try_from((bits >> 52) & 0x7ff).unwrap_or(0);
549    if exp == 0 || exp == 0x7ff {
550        return (d, 0); // subnormal (normalized by the caller's loop) or not finite
551    }
552    let k = exp - 1023;
553    // 2^-k as f64: exact for k in −1022..=1023 (2^-1023 is subnormal but exact).
554    let inv = match u64::try_from(1023 - k) {
555        Ok(0) | Err(_) => f64::from_bits(1 << 51), // 2^-1023, subnormal and exact
556        Ok(b) => f64::from_bits(b << 52),
557    };
558    (d * T::from_f64(inv), k)
559}