Skip to main content

xingo_sparse/
dense.rs

1//! # Chapter 5.16 — Dense kernels for supernodal blocks
2//!
3//! *New with task L1.5 (PLAN.md trilha L; the contract's §5.8, decision
4//! Q4).*
5//!
6//! ## Purpose
7//! A supernodal factorization (L1.6, `SupernodalLdl`) spends its time in a
8//! handful of dense operations on the blocks of `L`: factorize a diagonal
9//! block, solve the block below it against that factor, and subtract the
10//! products into the blocks of the ancestors. [`DenseKernel`] names them
11//! with their BLAS/LAPACK names (`potrf`, `sytrf`, `trsm`, `gemm`, `syrk`)
12//! so a backend can be swapped without touching the sparse code:
13//! [`NaiveDense`] — straightforward loops, generic in `T`, always available,
14//! the oracle of the others — and `FaerDense` (feature `faer`), faer's
15//! optimized `f64` kernels. A scalar type other than `f64` (the
16//! double-double of `xingo-extprec`) uses [`NaiveDense`].
17//!
18//! ## Notation
19//! A [`DenseBlock`] `A` is `rows × cols`, column-major: `a_ij =
20//! data[i + j·rows]`. Square blocks are read and written **in their lower
21//! triangle only** (the strict upper triangle is left untouched), like
22//! LAPACK with `uplo = 'L'`. For [`DenseKernel::sytrf`], `P A Pᵀ = L B Lᵀ`
23//! with `P` a permutation ([`Perm`], `fwd[k]` = the original index placed
24//! `k`-th), `L` unit lower triangular and `B` block diagonal with `1×1`
25//! and `2×2` blocks; `α = (1 + √17)/8 ≈ 0.6404` is Bunch & Kaufman's
26//! constant, which minimizes the bound on element growth.
27//!
28//! ## Algorithm P (`potrf`, Cholesky by columns)
29//! For `j = 0, …, n − 1`: `d ← a_jj − Σ_{k<j} l_jk²`; if `d ≤ 0` (or not
30//! finite) fail with [`DenseError::NotPositiveDefinite`] at `j`;
31//! `l_jj ← √d`; for `i > j`, `l_ij ← (a_ij − Σ_{k<j} l_ik l_jk) / l_jj`.
32//!
33//! ## Algorithm B (`sytrf`, Bunch–Kaufman partial pivoting)
34//! On a working copy `W` of the symmetric matrix, `k ← 0`; while `k < n`:
35//! B1. `λ ← max_{i>k} |w_ik|`, `r` its first row index. If `λ = 0`, the
36//!     column is already eliminated: a `1×1` pivot `w_kk` (possibly zero).
37//! B2. Else if `|w_kk| ≥ α λ`: `1×1` pivot at `k`.
38//! B3. Else `σ ← max_{i≥k, i≠r} |w_ir|`: if `|w_kk| σ ≥ α λ²`, `1×1` at
39//!     `k`; else if `|w_rr| ≥ α σ`, swap `r` into position `k` and take a
40//!     `1×1` pivot; else swap `r` into position `k + 1` and take the `2×2`
41//!     pivot `E = W[k..k+2, k..k+2]`.
42//! B4. A swap exchanges rows and columns of `W`, the rows of the computed
43//!     columns of `L`, and the entries of `P`.
44//! B5. Eliminate: `1×1` — `l_ik ← w_ik / w_kk` and `W ← W − l d lᵀ` on the
45//!     trailing block; `2×2` — `[l_ik, l_i,k+1] ← [w_ik, w_i,k+1] E⁻¹` and
46//!     `W ← W − [w_k w_k+1] E⁻¹ [w_k w_k+1]ᵀ`; advance `k` by 1 or 2.
47//! Output in `A`: `B`'s diagonal on the diagonal, the off-diagonal of each
48//! `2×2` block at `(k + 1, k)` (where `L` has an implicit zero), `L` below;
49//! `pivot_2x2[k] = pivot_2x2[k + 1] = true` for a `2×2` block. The inertia
50//! is that of `B` (Sylvester; Chapter 5.14, step K4).
51//!
52//! ## Algorithms T, G, S (`trsm_lower`, `gemm_sub`, `syrk_sub`)
53//! `trsm_lower(L, B, false)`: `B ← L⁻¹ B` by forward substitution, column
54//! by column of `B`; `trsm_lower(L, B, true)`: `B ← B L⁻ᵀ`, i.e. the rows
55//! of `B` solved against `L` (the "solve the block below the diagonal"
56//! step of a left-looking Cholesky). `L` is non-unit lower triangular (the
57//! output of `potrf`). `gemm_sub(A, B, C)`: `C ← C − A Bᵀ`. `syrk_sub(A,
58//! C)`: `C ← C − A Aᵀ` on the lower triangle of `C`. Sums run over `k` in
59//! increasing order.
60//!
61//! *Loop order of [`NaiveDense`] (task L1.6b).* The first edition summed
62//! each entry of the result in place (`c_ij ← c_ij − Σ_k a_ik b_jk`), which
63//! reads `A` across its rows — a stride of `rows` between consecutive `k`
64//! — and made `SupernodalLdl<f64, NaiveDense>` 14× slower than faer's
65//! kernels on dfl001 (D-0099). The kernels now run their innermost loop
66//! down one column (contiguous: an `axpy` on the column of `C` with the
67//! column `k` of `A` scaled by `b_jk`), in blocks of [`GEMM_BLOCK_ROWS`]
68//! rows and [`GEMM_BLOCK_K`] columns of `A` so that the block of `A` in
69//! use stays in cache while every column of `C` passes over it. No SIMD
70//! and no `unsafe`: plain slices, which the compiler vectorizes. The
71//! additions still run over `k` in increasing order, so the result is
72//! deterministic; its rounding differs from the first edition's (the sum
73//! is accumulated into `c_ij` instead of formed apart and subtracted once).
74//!
75//! ## Invariants
76//! (D1) After `potrf`, `L Lᵀ = A` (lower triangle) to working precision.
77//! (D2) After `sytrf`, `P A Pᵀ = L B Lᵀ` to working precision, `B` has
78//!      only `1×1` and `2×2` blocks, every `2×2` block has a negative
79//!      determinant or is indefinite-safe (`|e_21| ≥ λ > 0`), and the
80//!      returned inertia sums to `n`. Checked by the tests against the
81//!      reconstruction and against `NaiveDense` vs `FaerDense`.
82//! (D3) Every kernel leaves the strict upper triangle of a square block
83//!      untouched.
84//!
85//! ## References
86//! Bunch & Kaufman, "Some stable methods for calculating inertia and
87//! solving symmetric linear systems", Math. Comp. 31, 1977; Golub & Van
88//! Loan, *Matrix Computations*, 4th ed. 2013, §4.2 and §4.4; Higham,
89//! *Accuracy and Stability of Numerical Algorithms*, 2nd ed. 2002, ch.
90//! 10–11; LAPACK `dpotrf`/`dsytrf`/`dtrsm`/`dgemm`/`dsyrk` (interfaces,
91//! read); faer 0.24.4 `linalg::{cholesky, triangular_solve, matmul}` (the
92//! API, read, not copied).
93
94use crate::kkt::count_inertia;
95use crate::real::{Real, is_exact_zero, le, lt};
96use crate::{DenseError, Inertia, Perm};
97
98/// A column-major dense block: `a_ij = data[i + j·rows]`.
99#[derive(Clone, Debug, PartialEq)]
100pub struct DenseBlock<T: Real = f64> {
101    /// Number of rows.
102    pub rows: usize,
103    /// Number of columns.
104    pub cols: usize,
105    /// The entries, column by column (`rows · cols` of them).
106    pub data: Vec<T>,
107}
108
109impl<T: Real> DenseBlock<T> {
110    /// The `rows × cols` zero block.
111    pub fn zeros(rows: usize, cols: usize) -> Self {
112        Self {
113            rows,
114            cols,
115            data: vec![T::ZERO; rows * cols],
116        }
117    }
118
119    /// Entry `(i, j)`.
120    #[inline]
121    pub fn get(&self, i: usize, j: usize) -> T {
122        self.data[i + j * self.rows]
123    }
124
125    /// Sets entry `(i, j)`.
126    #[inline]
127    pub fn set(&mut self, i: usize, j: usize, v: T) {
128        self.data[i + j * self.rows] = v;
129    }
130
131    fn is_consistent(&self) -> bool {
132        self.data.len() == self.rows * self.cols
133    }
134
135    fn square(&self) -> Result<usize, DenseError> {
136        if self.is_consistent() && self.rows == self.cols {
137            Ok(self.rows)
138        } else {
139            Err(DenseError::Dimension)
140        }
141    }
142}
143
144/// The kernels a supernodal factorization needs (BLAS-3 names kept for
145/// recognizability). Square blocks are read and written in their lower
146/// triangle (invariant (D3)).
147pub trait DenseKernel<T: Real> {
148    /// In-place Cholesky `A = L Lᵀ` of a square block (Algorithm P).
149    fn potrf(&self, a: &mut DenseBlock<T>) -> Result<(), DenseError>;
150
151    /// In-place `P A Pᵀ = L B Lᵀ` with `1×1`/`2×2` pivots (Bunch–Kaufman,
152    /// Algorithm B); returns the inertia and writes the permutation into
153    /// `perm` and the `2×2` marks into `pivot_2x2` (both resized to `n`).
154    fn sytrf(
155        &self,
156        a: &mut DenseBlock<T>,
157        perm: &mut Perm,
158        pivot_2x2: &mut Vec<bool>,
159    ) -> Result<Inertia, DenseError>;
160
161    /// `B ← B L⁻ᵀ` (`transpose = true`) or `B ← L⁻¹ B` (`false`), `L`
162    /// square, non-unit lower triangular.
163    ///
164    /// # Panics
165    /// If the dimensions do not agree.
166    fn trsm_lower(&self, l: &DenseBlock<T>, b: &mut DenseBlock<T>, transpose: bool);
167
168    /// `C ← C − A Bᵀ`.
169    ///
170    /// # Panics
171    /// If the dimensions do not agree.
172    fn gemm_sub(&self, a: &DenseBlock<T>, b: &DenseBlock<T>, c: &mut DenseBlock<T>);
173
174    /// `C ← C − A Aᵀ`, lower triangle of `C`.
175    ///
176    /// # Panics
177    /// If the dimensions do not agree.
178    fn syrk_sub(&self, a: &DenseBlock<T>, c: &mut DenseBlock<T>);
179
180    /// A short name for logs and tables.
181    fn name(&self) -> &'static str;
182}
183
184/// Reference kernels: straightforward loops, always available, the oracle
185/// of the others in tests.
186///
187/// ```
188/// use xingo_sparse::{DenseBlock, DenseKernel, NaiveDense};
189/// let mut a = DenseBlock { rows: 2, cols: 2, data: vec![4.0, 2.0, 0.0, 5.0] };
190/// NaiveDense.potrf(&mut a).unwrap();
191/// assert_eq!((a.get(0, 0), a.get(1, 0), a.get(1, 1)), (2.0, 1.0, 2.0));
192/// ```
193#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
194pub struct NaiveDense;
195
196/// Rows of `C` and `A` handled per block in [`NaiveDense::gemm_sub`] and
197/// [`NaiveDense::syrk_sub`] (a cache-blocking size, not a numerical
198/// threshold): `GEMM_BLOCK_ROWS × GEMM_BLOCK_K` entries of `A` — 128 KiB
199/// in `f64` — stay in cache while the columns of `C` pass over them.
200pub const GEMM_BLOCK_ROWS: usize = 256;
201/// Columns of `A` (the summation index `k`) per block; see
202/// [`GEMM_BLOCK_ROWS`].
203pub const GEMM_BLOCK_K: usize = 64;
204
205/// Bunch & Kaufman's `α = (1 + √17)/8` (a constant of Algorithm B, not a
206/// tuning knob: it minimizes the growth bound).
207fn bk_alpha<T: Real>() -> T {
208    (T::ONE + T::from_f64(17.0).sqrt()) / T::from_f64(8.0)
209}
210
211impl<T: Real> DenseKernel<T> for NaiveDense {
212    fn potrf(&self, a: &mut DenseBlock<T>) -> Result<(), DenseError> {
213        let n = a.square()?;
214        for j in 0..n {
215            let d = a.get(j, j) - (0..j).map(|k| a.get(j, k) * a.get(j, k)).sum::<T>();
216            if !d.is_finite() || le(d, T::ZERO, T::ZERO) {
217                return Err(DenseError::NotPositiveDefinite { position: j });
218            }
219            let ljj = d.sqrt();
220            a.set(j, j, ljj);
221            for i in j + 1..n {
222                let s = a.get(i, j) - (0..j).map(|k| a.get(i, k) * a.get(j, k)).sum::<T>();
223                a.set(i, j, s / ljj);
224            }
225        }
226        Ok(())
227    }
228
229    #[allow(clippy::too_many_lines)] // Algorithm B, steps B1–B5 in one place
230    fn sytrf(
231        &self,
232        a: &mut DenseBlock<T>,
233        perm: &mut Perm,
234        pivot_2x2: &mut Vec<bool>,
235    ) -> Result<Inertia, DenseError> {
236        let n = a.square()?;
237        let alpha = bk_alpha::<T>();
238        // The working copy W (full, symmetric) and the factor L.
239        let mut w = vec![T::ZERO; n * n];
240        for j in 0..n {
241            for i in j..n {
242                w[i + j * n] = a.get(i, j);
243                w[j + i * n] = a.get(i, j);
244            }
245        }
246        let mut l = vec![T::ZERO; n * n];
247        let mut fwd: Vec<usize> = (0..n).collect();
248        let mut two = vec![false; n];
249        // `first[k]`: a 2×2 block starts at k.
250        let mut first = vec![false; n];
251        let mut diag = vec![T::ZERO; n];
252        let mut off = vec![T::ZERO; n];
253        let swap = |w: &mut [T], l: &mut [T], fwd: &mut [usize], k: usize, r: usize| {
254            if k == r {
255                return;
256            }
257            for c in 0..n {
258                w.swap(k + c * n, r + c * n);
259            }
260            for c in 0..n {
261                w.swap(c + k * n, c + r * n);
262            }
263            for c in 0..k {
264                l.swap(k + c * n, r + c * n);
265            }
266            fwd.swap(k, r);
267        };
268        let mut k = 0;
269        while k < n {
270            // B1.
271            let mut lambda = T::ZERO;
272            let mut r = k;
273            for i in k + 1..n {
274                if lt(lambda, w[i + k * n].abs()) {
275                    lambda = w[i + k * n].abs();
276                    r = i;
277                }
278            }
279            let akk = w[k + k * n].abs();
280            let size = if is_exact_zero(lambda) || !lt(akk, alpha * lambda) {
281                1 // B1, B2
282            } else {
283                // B3.
284                let mut sigma = T::ZERO;
285                for i in k..n {
286                    if i != r {
287                        sigma = sigma.max(w[i + r * n].abs());
288                    }
289                }
290                if !lt(akk * sigma, alpha * lambda * lambda) {
291                    1
292                } else if !lt(w[r + r * n].abs(), alpha * sigma) {
293                    swap(&mut w, &mut l, &mut fwd, k, r);
294                    1
295                } else {
296                    swap(&mut w, &mut l, &mut fwd, k + 1, r);
297                    2
298                }
299            };
300            // B5.
301            if size == 1 {
302                let d = w[k + k * n];
303                diag[k] = d;
304                l[k + k * n] = T::ONE;
305                if !is_exact_zero(d) {
306                    for i in k + 1..n {
307                        l[i + k * n] = w[i + k * n] / d;
308                    }
309                    for j in k + 1..n {
310                        let ljd = l[j + k * n] * d;
311                        for i in j..n {
312                            let v = w[i + j * n] - l[i + k * n] * ljd;
313                            w[i + j * n] = v;
314                            w[j + i * n] = v;
315                        }
316                    }
317                }
318                k += 1;
319            } else {
320                let (e11, e21, e22) = (w[k + k * n], w[k + 1 + k * n], w[k + 1 + (k + 1) * n]);
321                let det = e11 * e22 - e21 * e21;
322                diag[k] = e11;
323                diag[k + 1] = e22;
324                off[k] = e21;
325                two[k] = true;
326                two[k + 1] = true;
327                first[k] = true;
328                l[k + k * n] = T::ONE;
329                l[k + 1 + (k + 1) * n] = T::ONE;
330                for i in k + 2..n {
331                    let (x, y) = (w[i + k * n], w[i + (k + 1) * n]);
332                    // [x y] E⁻¹, E⁻¹ = [e22 −e21; −e21 e11] / det.
333                    l[i + k * n] = (x * e22 - y * e21) / det;
334                    l[i + (k + 1) * n] = (y * e11 - x * e21) / det;
335                }
336                for j in k + 2..n {
337                    let (xj, yj) = (w[j + k * n], w[j + (k + 1) * n]);
338                    for i in j..n {
339                        let v = w[i + j * n] - (l[i + k * n] * xj + l[i + (k + 1) * n] * yj);
340                        w[i + j * n] = v;
341                        w[j + i * n] = v;
342                    }
343                }
344                k += 2;
345            }
346        }
347        // Output.
348        for j in 0..n {
349            a.set(j, j, diag[j]);
350            for i in j + 1..n {
351                let v = if first[j] && i == j + 1 {
352                    off[j]
353                } else {
354                    l[i + j * n]
355                };
356                a.set(i, j, v);
357            }
358        }
359        *perm = Perm::from_fwd(fwd.into_iter().map(crate::perm::idx32).collect())
360            .map_err(|_| DenseError::Dimension)?;
361        pivot_2x2.clear();
362        pivot_2x2.extend_from_slice(&two);
363        Ok(block_inertia(a, pivot_2x2))
364    }
365
366    fn trsm_lower(&self, l: &DenseBlock<T>, b: &mut DenseBlock<T>, transpose: bool) {
367        let n = l.square().expect("trsm_lower: L must be square");
368        assert!(b.is_consistent(), "trsm_lower: B is inconsistent");
369        let rows = b.rows;
370        if transpose {
371            // X Lᵀ = B: row i of X solves L xᵢ = bᵢ (forward substitution),
372            // all rows at once, column by column of B: column j of X is
373            // (b_j − Σ_{k<j} l_jk x_k) / l_jj — contiguous axpys.
374            assert_eq!(b.cols, n, "trsm_lower: B must have n columns");
375            for j in 0..n {
376                let (done, rest) = b.data.split_at_mut(j * rows);
377                let xj = &mut rest[..rows];
378                for k in 0..j {
379                    let t = l.get(j, k);
380                    for (x, &y) in xj.iter_mut().zip(&done[k * rows..(k + 1) * rows]) {
381                        *x -= y * t;
382                    }
383                }
384                let d = l.get(j, j);
385                for x in xj {
386                    *x = *x / d;
387                }
388            }
389        } else {
390            // L X = B, column c of B: right-looking forward substitution,
391            // the update of the rows below k contiguous.
392            assert_eq!(rows, n, "trsm_lower: B must have n rows");
393            for c in 0..b.cols {
394                let col = &mut b.data[c * n..(c + 1) * n];
395                for k in 0..n {
396                    let x = col[k] / l.get(k, k);
397                    col[k] = x;
398                    let (_, below) = col.split_at_mut(k + 1);
399                    for (y, &lik) in below.iter_mut().zip(&l.data[k + 1 + k * n..(k + 1) * n]) {
400                        *y -= lik * x;
401                    }
402                }
403            }
404        }
405    }
406
407    fn gemm_sub(&self, a: &DenseBlock<T>, b: &DenseBlock<T>, c: &mut DenseBlock<T>) {
408        assert!(
409            a.is_consistent()
410                && b.is_consistent()
411                && c.is_consistent()
412                && a.cols == b.cols
413                && c.rows == a.rows
414                && c.cols == b.rows,
415            "gemm_sub: dimensions do not agree"
416        );
417        let (rows, kk) = (a.rows, a.cols);
418        let mut i0 = 0;
419        while i0 < rows {
420            let i1 = (i0 + GEMM_BLOCK_ROWS).min(rows);
421            let mut k0 = 0;
422            while k0 < kk {
423                let k1 = (k0 + GEMM_BLOCK_K).min(kk);
424                for j in 0..c.cols {
425                    let cj = &mut c.data[j * rows + i0..j * rows + i1];
426                    for k in k0..k1 {
427                        let t = b.data[j + k * b.rows];
428                        let ak = &a.data[k * rows + i0..k * rows + i1];
429                        for (x, &av) in cj.iter_mut().zip(ak) {
430                            *x -= av * t;
431                        }
432                    }
433                }
434                k0 = k1;
435            }
436            i0 = i1;
437        }
438    }
439
440    fn syrk_sub(&self, a: &DenseBlock<T>, c: &mut DenseBlock<T>) {
441        let n = c.square().expect("syrk_sub: C must be square");
442        assert!(
443            a.is_consistent() && a.rows == n,
444            "syrk_sub: dimensions do not agree"
445        );
446        let kk = a.cols;
447        let mut k0 = 0;
448        while k0 < kk {
449            let k1 = (k0 + GEMM_BLOCK_K).min(kk);
450            for j in 0..n {
451                let cj = &mut c.data[j * n + j..(j + 1) * n];
452                for k in k0..k1 {
453                    let t = a.data[j + k * n];
454                    let ak = &a.data[k * n + j..(k + 1) * n];
455                    for (x, &av) in cj.iter_mut().zip(ak) {
456                        *x -= av * t;
457                    }
458                }
459            }
460            k0 = k1;
461        }
462    }
463
464    fn name(&self) -> &'static str {
465        "naive"
466    }
467}
468
469/// The inertia of the block diagonal `B` stored by `sytrf`.
470fn block_inertia<T: Real>(a: &DenseBlock<T>, pivot_2x2: &[bool]) -> Inertia {
471    let n = a.rows;
472    let mut ones = Vec::new();
473    let mut twos = Vec::new();
474    let mut k = 0;
475    while k < n {
476        if pivot_2x2[k] && k + 1 < n {
477            twos.push((a.get(k, k), a.get(k + 1, k), a.get(k + 1, k + 1)));
478            k += 2;
479        } else {
480            ones.push(a.get(k, k));
481            k += 1;
482        }
483    }
484    count_inertia(ones.into_iter(), twos.into_iter())
485}
486
487/// faer's dense kernels (`f64` only in v0.1; extended types use
488/// [`NaiveDense`]). `sytrf` uses faer's Bunch–Kaufman with partial
489/// pivoting, whose pivot choices may differ from [`NaiveDense`]'s in ties:
490/// both satisfy (D2).
491#[cfg(feature = "faer")]
492#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
493pub struct FaerDense;
494
495#[cfg(feature = "faer")]
496mod faer_impl {
497    use faer::dyn_stack::{MemBuffer, MemStack};
498    use faer::linalg::cholesky::lblt::factor::{LbltParams, PivotingStrategy};
499    use faer::linalg::cholesky::llt::factor::LltRegularization;
500    use faer::linalg::matmul::triangular::BlockStructure;
501    use faer::{Accum, ColMut, MatMut, MatRef, Par, Spec};
502
503    use super::{DenseBlock, DenseError, DenseKernel, FaerDense, Inertia, Perm, block_inertia};
504    use crate::real::is_exact_zero;
505
506    fn view(a: &DenseBlock<f64>) -> MatRef<'_, f64> {
507        MatRef::from_column_major_slice(&a.data, a.rows, a.cols)
508    }
509
510    fn view_mut(a: &mut DenseBlock<f64>) -> MatMut<'_, f64> {
511        MatMut::from_column_major_slice_mut(&mut a.data, a.rows, a.cols)
512    }
513
514    impl DenseKernel<f64> for FaerDense {
515        fn potrf(&self, a: &mut DenseBlock<f64>) -> Result<(), DenseError> {
516            let n = a.square()?;
517            let params = Spec::default();
518            let mut buf = MemBuffer::new(
519                faer::linalg::cholesky::llt::factor::cholesky_in_place_scratch::<f64>(
520                    n,
521                    Par::Seq,
522                    params,
523                ),
524            );
525            faer::linalg::cholesky::llt::factor::cholesky_in_place(
526                view_mut(a),
527                LltRegularization::default(),
528                Par::Seq,
529                MemStack::new(&mut buf),
530                params,
531            )
532            .map(|_| ())
533            .map_err(|e| match e {
534                faer::linalg::cholesky::llt::factor::LltError::NonPositivePivot { index } => {
535                    DenseError::NotPositiveDefinite { position: index }
536                }
537            })
538        }
539
540        fn sytrf(
541            &self,
542            a: &mut DenseBlock<f64>,
543            perm: &mut Perm,
544            pivot_2x2: &mut Vec<bool>,
545        ) -> Result<Inertia, DenseError> {
546            let n = a.square()?;
547            let mut params: Spec<LbltParams, f64> = Spec::default();
548            params.config.pivoting = PivotingStrategy::Partial;
549            let mut subdiag = vec![0.0_f64; n];
550            let mut fwd = vec![0_usize; n];
551            let mut inv = vec![0_usize; n];
552            let mut buf = MemBuffer::new(
553                faer::linalg::cholesky::lblt::factor::cholesky_in_place_scratch::<usize, f64>(
554                    n,
555                    Par::Seq,
556                    params,
557                ),
558            );
559            faer::linalg::cholesky::lblt::factor::cholesky_in_place(
560                view_mut(a),
561                ColMut::from_slice_mut(&mut subdiag).as_diagonal_mut(),
562                &mut fwd,
563                &mut inv,
564                Par::Seq,
565                MemStack::new(&mut buf),
566                params,
567            );
568            pivot_2x2.clear();
569            pivot_2x2.resize(n, false);
570            let mut k = 0;
571            while k < n {
572                if k + 1 < n && !is_exact_zero(subdiag[k]) {
573                    a.set(k + 1, k, subdiag[k]);
574                    pivot_2x2[k] = true;
575                    pivot_2x2[k + 1] = true;
576                    k += 2;
577                } else {
578                    k += 1;
579                }
580            }
581            *perm = Perm::from_fwd(fwd.into_iter().map(crate::perm::idx32).collect())
582                .map_err(|_| DenseError::Dimension)?;
583            Ok(block_inertia(a, pivot_2x2))
584        }
585
586        fn trsm_lower(&self, l: &DenseBlock<f64>, b: &mut DenseBlock<f64>, transpose: bool) {
587            let n = l.square().expect("trsm_lower: L must be square");
588            if transpose {
589                assert_eq!(b.cols, n, "trsm_lower: B must have n columns");
590                // X Lᵀ = B  ⇔  L Xᵀ = Bᵀ.
591                faer::linalg::triangular_solve::solve_lower_triangular_in_place(
592                    view(l),
593                    view_mut(b).transpose_mut(),
594                    Par::Seq,
595                );
596            } else {
597                assert_eq!(b.rows, n, "trsm_lower: B must have n rows");
598                faer::linalg::triangular_solve::solve_lower_triangular_in_place(
599                    view(l),
600                    view_mut(b),
601                    Par::Seq,
602                );
603            }
604        }
605
606        fn gemm_sub(&self, a: &DenseBlock<f64>, b: &DenseBlock<f64>, c: &mut DenseBlock<f64>) {
607            assert!(
608                a.cols == b.cols && c.rows == a.rows && c.cols == b.rows,
609                "gemm_sub: dimensions do not agree"
610            );
611            faer::linalg::matmul::matmul(
612                view_mut(c),
613                Accum::Add,
614                view(a),
615                view(b).transpose(),
616                -1.0,
617                Par::Seq,
618            );
619        }
620
621        fn syrk_sub(&self, a: &DenseBlock<f64>, c: &mut DenseBlock<f64>) {
622            let n = c.square().expect("syrk_sub: C must be square");
623            assert_eq!(a.rows, n, "syrk_sub: dimensions do not agree");
624            faer::linalg::matmul::triangular::matmul(
625                view_mut(c),
626                BlockStructure::TriangularLower,
627                Accum::Add,
628                view(a),
629                BlockStructure::Rectangular,
630                view(a).transpose(),
631                BlockStructure::Rectangular,
632                -1.0,
633                Par::Seq,
634            );
635        }
636
637        fn name(&self) -> &'static str {
638            "faer"
639        }
640    }
641}
642
643#[cfg(test)]
644mod tests {
645    use super::*;
646    use crate::real::approx_eq;
647    use proptest::prelude::*;
648
649    /// A deterministic pseudo-random block (xorshift).
650    fn block(rows: usize, cols: usize, seed: u64) -> DenseBlock {
651        let mut s = seed | 1;
652        let data = (0..rows * cols)
653            .map(|_| {
654                s ^= s << 13;
655                s ^= s >> 7;
656                s ^= s << 17;
657                #[allow(clippy::cast_precision_loss)]
658                let u = (s >> 11) as f64 / (1_u64 << 53) as f64;
659                2.0 * u - 1.0
660            })
661            .collect();
662        DenseBlock { rows, cols, data }
663    }
664
665    /// A symmetric block: `M + Mᵀ` (indefinite in general), or
666    /// `M Mᵀ + n I` (positive definite).
667    fn symmetric(n: usize, seed: u64, spd: bool) -> DenseBlock {
668        let m = block(n, n, seed);
669        let mut a = DenseBlock::zeros(n, n);
670        for j in 0..n {
671            for i in 0..n {
672                #[allow(clippy::cast_precision_loss)]
673                let v = if spd {
674                    (0..n).map(|k| m.get(i, k) * m.get(j, k)).sum::<f64>()
675                        + if i == j { n as f64 } else { 0.0 }
676                } else {
677                    m.get(i, j) + m.get(j, i)
678                };
679                a.set(i, j, v);
680            }
681        }
682        a
683    }
684
685    fn close(x: &DenseBlock, y: &DenseBlock, lower_only: bool) -> bool {
686        (0..x.cols).all(|j| {
687            (if lower_only { j } else { 0 }..x.rows)
688                .all(|i| approx_eq(x.get(i, j), y.get(i, j), 1e-10))
689        })
690    }
691
692    /// `‖P A Pᵀ − L B Lᵀ‖_max` from the output of `sytrf`.
693    fn sytrf_error(a0: &DenseBlock, f: &DenseBlock, perm: &Perm, two: &[bool]) -> f64 {
694        let n = a0.rows;
695        let mut l = DenseBlock::zeros(n, n);
696        let mut b = DenseBlock::zeros(n, n);
697        let mut k = 0;
698        while k < n {
699            if two[k] {
700                b.set(k, k, f.get(k, k));
701                b.set(k + 1, k + 1, f.get(k + 1, k + 1));
702                b.set(k + 1, k, f.get(k + 1, k));
703                b.set(k, k + 1, f.get(k + 1, k));
704                l.set(k, k, 1.0);
705                l.set(k + 1, k + 1, 1.0);
706                for i in k + 2..n {
707                    l.set(i, k, f.get(i, k));
708                    l.set(i, k + 1, f.get(i, k + 1));
709                }
710                k += 2;
711            } else {
712                b.set(k, k, f.get(k, k));
713                l.set(k, k, 1.0);
714                for i in k + 1..n {
715                    l.set(i, k, f.get(i, k));
716                }
717                k += 1;
718            }
719        }
720        let mut err = 0.0_f64;
721        for i in 0..n {
722            for j in 0..=i {
723                let mut s = 0.0;
724                for p in 0..n {
725                    for q in 0..n {
726                        s += l.get(i, p) * b.get(p, q) * l.get(j, q);
727                    }
728                }
729                let (pi, pj) = (perm.fwd[i] as usize, perm.fwd[j] as usize);
730                let aij = if pi >= pj {
731                    a0.get(pi, pj)
732                } else {
733                    a0.get(pj, pi)
734                };
735                err = err.max((s - aij).abs());
736            }
737        }
738        err
739    }
740
741    #[test]
742    fn potrf_rejects_indefinite_blocks() {
743        let mut a = DenseBlock {
744            rows: 2,
745            cols: 2,
746            data: vec![1.0, 2.0, 0.0, 1.0],
747        };
748        assert_eq!(
749            NaiveDense.potrf(&mut a.clone()),
750            Err(DenseError::NotPositiveDefinite { position: 1 })
751        );
752        #[cfg(feature = "faer")]
753        assert_eq!(
754            FaerDense.potrf(&mut a),
755            Err(DenseError::NotPositiveDefinite { position: 1 })
756        );
757        let mut r = DenseBlock::<f64>::zeros(2, 3);
758        assert_eq!(NaiveDense.potrf(&mut r), Err(DenseError::Dimension));
759        let mut p = Perm::identity(0);
760        let mut t = Vec::new();
761        assert_eq!(
762            NaiveDense.sytrf(&mut r, &mut p, &mut t),
763            Err(DenseError::Dimension)
764        );
765        a.data.pop();
766        assert_eq!(NaiveDense.potrf(&mut a), Err(DenseError::Dimension));
767    }
768
769    #[test]
770    fn sytrf_finds_2x2_pivots_and_inertia() {
771        // [0 1; 1 0]: no 1×1 pivot is acceptable.
772        let mut a = DenseBlock {
773            rows: 2,
774            cols: 2,
775            data: vec![0.0, 1.0, 0.0, 0.0],
776        };
777        let mut p = Perm::identity(0);
778        let mut two = Vec::new();
779        let s = NaiveDense.sytrf(&mut a, &mut p, &mut two).unwrap();
780        assert_eq!(
781            s,
782            Inertia {
783                positive: 1,
784                negative: 1,
785                zero: 0
786            }
787        );
788        assert_eq!(two, vec![true, true]);
789        // A singular block has a zero pivot.
790        let mut z = DenseBlock {
791            rows: 2,
792            cols: 2,
793            data: vec![1.0, 0.0, 0.0, 0.0],
794        };
795        let s = NaiveDense.sytrf(&mut z, &mut p, &mut two).unwrap();
796        assert_eq!(s.zero, 1);
797    }
798
799    proptest! {
800        #![proptest_config(ProptestConfig::with_cases(48))]
801        /// (D1), (D2) and NaiveDense vs FaerDense: equal to working
802        /// precision (factors of potrf, trsm, gemm, syrk entry by entry;
803        /// sytrf by reconstruction and identical inertia).
804        #[test]
805        fn kernels_agree(n in 1_usize..24, k in 1_usize..9, seed in any::<u64>()) {
806            // potrf.
807            let spd = symmetric(n, seed, true);
808            let mut x = spd.clone();
809            NaiveDense.potrf(&mut x).unwrap();
810            let mut llt = DenseBlock::zeros(n, n);
811            for j in 0..n {
812                for i in j..n {
813                    llt.set(i, j, (0..=j).map(|p| x.get(i, p) * x.get(j, p)).sum());
814                }
815            }
816            prop_assert!(close(&llt, &spd, true));
817            // sytrf on an indefinite block.
818            let ind = symmetric(n, seed ^ 0x9e37, false);
819            let mut f = ind.clone();
820            let mut p = Perm::identity(0);
821            let mut two = Vec::new();
822            let s = NaiveDense.sytrf(&mut f, &mut p, &mut two).unwrap();
823            prop_assert_eq!(s.positive + s.negative + s.zero, n);
824            prop_assert!(sytrf_error(&ind, &f, &p, &two) <= 1e-9);
825            // trsm, gemm, syrk.
826            let b = block(k, n, seed ^ 0x7);
827            let mut t1 = b.clone();
828            NaiveDense.trsm_lower(&x, &mut t1, true);
829            let b2 = block(n, k, seed ^ 0xb);
830            let mut t2 = b2.clone();
831            NaiveDense.trsm_lower(&x, &mut t2, false);
832            let a3 = block(k, n, seed ^ 0xd);
833            let mut c3 = block(k, k, seed ^ 0x11);
834            let c3_0 = c3.clone();
835            NaiveDense.gemm_sub(&a3, &b, &mut c3);
836            for i in 0..k {
837                for j in 0..k {
838                    let v: f64 = c3_0.get(i, j) - (0..n).map(|p| a3.get(i, p) * b.get(j, p)).sum::<f64>();
839                    prop_assert!(approx_eq(v, c3.get(i, j), 1e-12));
840                }
841            }
842            let mut c4 = symmetric(k, seed ^ 0x13, false);
843            let c4_0 = c4.clone();
844            NaiveDense.syrk_sub(&a3, &mut c4);
845            #[cfg(feature = "faer")]
846            {
847                let mut y = spd.clone();
848                FaerDense.potrf(&mut y).unwrap();
849                prop_assert!(close(&x, &y, true));
850                let mut g = ind.clone();
851                let mut q = Perm::identity(0);
852                let mut two_f = Vec::new();
853                let sf = FaerDense.sytrf(&mut g, &mut q, &mut two_f).unwrap();
854                prop_assert_eq!(s, sf);
855                prop_assert!(sytrf_error(&ind, &g, &q, &two_f) <= 1e-9);
856                let mut u1 = b.clone();
857                FaerDense.trsm_lower(&x, &mut u1, true);
858                prop_assert!(close(&t1, &u1, false));
859                let mut u2 = b2.clone();
860                FaerDense.trsm_lower(&x, &mut u2, false);
861                prop_assert!(close(&t2, &u2, false));
862                let mut d3 = c3_0.clone();
863                FaerDense.gemm_sub(&a3, &b, &mut d3);
864                prop_assert!(close(&c3, &d3, false));
865                let mut d4 = c4_0.clone();
866                FaerDense.syrk_sub(&a3, &mut d4);
867                prop_assert!(close(&c4, &d4, true));
868                // (D3): the strict upper triangle is untouched.
869                prop_assert!((0..k).all(|j| (0..j).all(|i| approx_eq(d4.get(i, j), c4_0.get(i, j), 0.0))));
870            }
871            prop_assert!((0..k).all(|j| (0..j).all(|i| approx_eq(c4.get(i, j), c4_0.get(i, j), 0.0))));
872            // trsm really solved: t1 Lᵀ = b.
873            for i in 0..k {
874                for j in 0..n {
875                    let v: f64 = (0..=j).map(|p| t1.get(i, p) * x.get(j, p)).sum();
876                    prop_assert!(approx_eq(v, b.get(i, j), 1e-9));
877                }
878            }
879        }
880    }
881}