Skip to main content

xingo_extprec/
dense.rs

1//! # Chapter 11.7 — `DdDense`: the dense kernel of `xingo-sparse` in double-double
2//!
3//! ## Purpose
4//! `xingo_sparse::SupernodalLdl<T, K>` spends its time in the dense
5//! operations of a `DenseKernel<T>` (Chapter 5.16 of `xingo-sparse`). For
6//! `T = DoubleDouble` the only kernel so far was the generic
7//! `NaiveDense`, one scalar double-double operation at a time. [`DdDense`]
8//! is the same kernel with its inner loop — the column update of
9//! Chapter 11.5, step B3 — on vector registers (Chapter 11.6). It returns
10//! **the bits of `NaiveDense`**, so a factorization does not change when
11//! the kernel is swapped; only its speed does.
12//!
13//! ## Notation
14//! As in Chapter 5.16: a `DenseBlock` `A` is `rows × cols`, column-major;
15//! square blocks are read and written in their lower triangle. `c ← c ⊖ a
16//! ⊗ t` is the column update of Chapter 11.5 (`c`, `a` columns of equal
17//! length, `t` a double-double), `⊘` the division D2 of Chapter 11.2.
18//!
19//! ## Algorithm K (the five operations)
20//! K1. \[`gemm_sub`: `C ← C − A Bᵀ`.\] Step B3 of Chapter 11.5 with `t(j,
21//!     l) = b_jl`, in its blocks: for each entry, `l` increasing.
22//! K2. \[`syrk_sub`: `C ← C − A Aᵀ`, lower triangle.\] For `l` in blocks of
23//!     `BLOCK_K`, for each column `j` of `C`: the column update of the
24//!     rows `i ≥ j` with `a = A[j.., l]` and `t = a_jl`.
25//! K3. \[`trsm_lower`, `B ← B L⁻ᵀ`.\] For `j = 0, …, n − 1`: for `l < j`,
26//!     the column update of column `j` of `B` with `a` = column `l` of `B`
27//!     (already solved) and `t = l_jl`; then `b_ij ← b_ij ⊘ l_jj`.
28//! K4. \[`trsm_lower`, `B ← L⁻¹ B`.\] For each column `c` of `B`, for `l =
29//!     0, …, n − 1`: `x ← b_lc ⊘ l_ll`, `b_lc ← x`, then the column update
30//!     of the rows below `l` with `a = L[l + 1.., l]` and `t = x`.
31//! K5. \[`potrf`, left-looking (Algorithm P of Chapter 5.16 since
32//!     `xingo-sparse` 0.4.0).\] For `j = 0, …, n − 1`: for `k < j`, the
33//!     column update of the rows `i ≥ j` of column `j` with `a = L[j..,
34//!     k]` and `t = l_jk`; then the pivot test and `l_jj ← √a_jj` of
35//!     `NaiveDense`, and `l_ij ← a_ij ⊘ l_jj` for `i > j`.
36//! K6. \[`sytrf`.\] That of `NaiveDense`, unchanged: its eliminations
37//!     update a full working copy row and column at once, and the block
38//!     factorization is not where the supernodal factorization spends its
39//!     time.
40//!
41//! K7. \[`solve_unit_lower`, Algorithm V of Chapter 5.16.\] For `j = 0,
42//!     …, n_c − 1`: the column update of `y[o..]` with `a = L[o.., j]` and
43//!     `t = y_j`.
44//! K8. \[`solve_unit_lower_t`, Algorithm W.\] For `j = n_c − 1, …, 0`:
45//!     `y_j ← y_j ⊖ (D(L[o..n_c, j], y[o..n_c]) ⊕ D(L[n_c.., j],
46//!     y[n_c..]))`, with `D` the kernel `dot4` of Chapter 11.5 (step B4)
47//!     on SIMD registers (step W2 of Chapter 11.6).
48//! K9. \[`solve_min_rows`.\] [`SOLVE_MIN_ROWS`]: the supernodes of
49//!     `SupernodalLdl` with at least that many rows are solved through
50//!     K7–K8 (step S0′ of Chapter 5.17), the others by the generic loops.
51//!     A cost switch (invariant (D5) of Chapter 5.16): the bits are the
52//!     same either way.
53//!
54//! *Task L1.8.* Until `xingo-sparse` 0.3.x the generic `potrf` summed each
55//! entry along a row of `L` (`Σ_k l_ik l_jk`, left to right, subtracted
56//! once), which lanes would reorder, so it was `NaiveDense`'s here too;
57//! 0.4.0 subtracts term by term down a column, the statement of K1–K4, and
58//! K5 vectorizes it with the same bits.
59//!
60//! K1–K5, K7 are the loops of `NaiveDense` (Chapter 5.16, "Loop order"), which
61//! compute each entry as `x ← x − a · t` with the same operands in the
62//! same order; the column update is that statement for a whole column, and
63//! it is bit for bit the scalar one (invariant K1 of Chapter 11.5). The
64//! product is `a ⊗ t` with the entry of the column first: the
65//! double-double product M2 is not commutative in its last bits, so the
66//! order of the operands is part of the definition.
67//!
68//! ## What the contract said
69//! The approved contract describes `DdDense` as "`potrf`, `sytrf` and the
70//! triangular solves are those of `NaiveDense`; `gemm_sub` and `syrk_sub`
71//! go through `kernels::gemm_sub`". Two differences, neither visible in a
72//! result: the triangular solves also use the vectorized column update
73//! (their results are still `NaiveDense`'s, bit for bit), because the
74//! supernodal factorization calls `trsm_lower` once per panel; and
75//! `gemm_sub`/`syrk_sub` go through the column update of
76//! `kernels::gemm_sub` rather than through that function, whose `B` is
77//! `k × n` where the trait's is `n × k` (transposed).
78//!
79//! ## Invariants
80//! (X1) *Same bits.* Every operation of [`DdDense`] leaves in its output
81//!      block the bits `NaiveDense` would (NaN payloads aside, invariant K1
82//!      of Chapter 11.5). Tested entry by entry on random blocks, and on
83//!      whole factorizations in `tests/sparse_dd.rs`.
84//! (X2) (D3) of Chapter 5.16: the strict upper triangle of a square block
85//!      is untouched.
86//! (X3) *Same bits in the solve* (task L1.8): K7–K8 return the bits of the
87//!      provided `solve_unit_lower`, `solve_unit_lower_t` of
88//!      `DenseKernel` — (D4) of Chapter 5.16 — so `SupernodalLdl` solves to
89//!      the same bits with `DdDense` as with `NaiveDense`, whatever
90//!      [`SOLVE_MIN_ROWS`] is. Tested on blocks and on whole solves in
91//!      `tests/sparse_dd.rs`.
92//!
93//! ## References
94//! Chapter 5.16 of `xingo-sparse` (`DenseKernel`, `NaiveDense`: the loop
95//! order and the cache blocks); Chapters 11.5 and 11.6.
96
97use xingo_sparse::{DenseBlock, DenseError, DenseKernel, Inertia, NaiveDense, Perm};
98
99use crate::dd::DoubleDouble;
100use crate::kernels::reference::Reference;
101use crate::kernels::{BLOCK_K, ColumnUpdate, dispatch, gemm_blocked};
102
103/// The dense kernel of `xingo-sparse` for double-double blocks, with the
104/// results of `NaiveDense` bit for bit (Chapter 11.7): `gemm_sub`,
105/// `syrk_sub` and the triangular solves run the column update of
106/// [`crate::kernels::gemm_sub`] on SIMD registers (feature `simd`), and
107/// so does `potrf` (left-looking since `xingo-sparse` 0.4.0); `sytrf` is
108/// that of `NaiveDense`. With it
109/// `SupernodalLdl<DoubleDouble, DdDense>` spends its time in SIMD.
110///
111/// ```
112/// use xingo_extprec::{DdDense, DoubleDouble};
113/// use xingo_sparse::{DenseBlock, DenseKernel, NaiveDense};
114/// let third = DoubleDouble::ONE / 3.0;
115/// let a = DenseBlock { rows: 2, cols: 1, data: vec![third, DoubleDouble::ONE] };
116/// let mut c = DenseBlock { rows: 2, cols: 2, data: vec![DoubleDouble::ONE; 4] };
117/// let mut d = c.clone();
118/// DdDense.syrk_sub(&a, &mut c);
119/// NaiveDense.syrk_sub(&a, &mut d);
120/// assert_eq!(c, d);
121/// ```
122#[derive(Clone, Copy, Debug, Default)]
123pub struct DdDense;
124
125/// `rows · cols` entries.
126fn is_consistent(a: &DenseBlock<DoubleDouble>) -> bool {
127    a.data.len() == a.rows * a.cols
128}
129
130/// The order of a consistent square block.
131fn square(a: &DenseBlock<DoubleDouble>) -> Option<usize> {
132    (is_consistent(a) && a.rows == a.cols).then_some(a.rows)
133}
134
135/// Step K2.
136#[inline(always)] // into `pulp`'s `vectorize` (Chapter 11.6)
137#[allow(clippy::inline_always)]
138fn syrk<U: ColumnUpdate>(
139    update: U,
140    n: usize,
141    a: &DenseBlock<DoubleDouble>,
142    c: &mut DenseBlock<DoubleDouble>,
143) {
144    let kk = a.cols;
145    let mut l0 = 0;
146    while l0 < kk {
147        let l1 = (l0 + BLOCK_K).min(kk);
148        for j in 0..n {
149            let cj = &mut c.data[j * n + j..(j + 1) * n];
150            for l in l0..l1 {
151                update.column_sub(cj, &a.data[l * n + j..(l + 1) * n], a.data[j + l * n]);
152            }
153        }
154        l0 = l1;
155    }
156}
157
158/// Step K3.
159#[inline(always)] // into `pulp`'s `vectorize` (Chapter 11.6)
160#[allow(clippy::inline_always)]
161fn trsm_transposed<U: ColumnUpdate>(
162    update: U,
163    n: usize,
164    l: &DenseBlock<DoubleDouble>,
165    b: &mut DenseBlock<DoubleDouble>,
166) {
167    let rows = b.rows;
168    for j in 0..n {
169        let (done, rest) = b.data.split_at_mut(j * rows);
170        let xj = &mut rest[..rows];
171        for k in 0..j {
172            update.column_sub(xj, &done[k * rows..(k + 1) * rows], l.get(j, k));
173        }
174        let d = l.get(j, j);
175        for x in xj {
176            *x /= d;
177        }
178    }
179}
180
181/// Step K5 (the error of a non-positive pivot is `NaiveDense`'s).
182#[inline(always)] // into `pulp`'s `vectorize` (Chapter 11.6)
183#[allow(clippy::inline_always)]
184fn potrf_columns<U: ColumnUpdate>(
185    update: U,
186    n: usize,
187    a: &mut DenseBlock<DoubleDouble>,
188) -> Result<(), DenseError> {
189    for j in 0..n {
190        let (done, rest) = a.data.split_at_mut(j * n);
191        let cj = &mut rest[j..n];
192        for k in 0..j {
193            update.column_sub(cj, &done[j + k * n..(k + 1) * n], done[j + k * n]);
194        }
195        let d = cj[0];
196        if !d.is_finite() || d <= DoubleDouble::ZERO {
197            return Err(DenseError::NotPositiveDefinite { position: j });
198        }
199        let ljj = d.sqrt();
200        cj[0] = ljj;
201        for x in &mut cj[1..] {
202            *x /= ljj;
203        }
204    }
205    Ok(())
206}
207
208/// Step K9: the smallest supernode block, in rows, that the solves of
209/// `SupernodalLdl<DoubleDouble, DdDense>` send through K7–K8 (a cost
210/// switch). Measured in task L1.8 with `dd_bench ldl` (NEON, Apple M2):
211/// `1`, `8` and `32` within the noise of each other on the four systems
212/// (2-D grid simplicial and forced supernodal, 3-D grid, dense 200), all
213/// 1.3–1.8× faster than the generic loops; `8` keeps the gather out of
214/// the smallest blocks.
215const SOLVE_MIN_ROWS: usize = 8;
216
217/// `o = j + 1 + [skip_j]` of Algorithms V and W of Chapter 5.16.
218#[inline(always)]
219#[allow(clippy::inline_always)]
220fn solve_offset(skip: &[bool], j: usize) -> usize {
221    j + 1 + usize::from(skip.get(j).copied().unwrap_or(false))
222}
223
224/// The argument checks of K7–K8 (those of the provided methods).
225fn check_solve(l: &DenseBlock<DoubleDouble>, skip: &[bool], y: &[DoubleDouble]) {
226    assert!(
227        is_consistent(l)
228            && l.rows >= l.cols
229            && y.len() == l.rows
230            && (skip.is_empty() || skip.len() == l.cols),
231        "solve_unit_lower: dimensions do not agree"
232    );
233}
234
235/// Step K7.
236#[inline(always)] // into `pulp`'s `vectorize` (Chapter 11.6)
237#[allow(clippy::inline_always)]
238fn solve_forward<U: ColumnUpdate>(
239    update: U,
240    l: &DenseBlock<DoubleDouble>,
241    skip: &[bool],
242    y: &mut [DoubleDouble],
243) {
244    let nr = l.rows;
245    for j in 0..l.cols {
246        let o = solve_offset(skip, j);
247        let t = y[j];
248        update.column_sub(&mut y[o..], &l.data[j * nr + o..(j + 1) * nr], t);
249    }
250}
251
252/// Step K8, with the kernel `dot` of step B4.
253#[inline(always)] // into `pulp`'s `vectorize` (Chapter 11.6)
254#[allow(clippy::inline_always)]
255fn solve_backward(
256    l: &DenseBlock<DoubleDouble>,
257    skip: &[bool],
258    y: &mut [DoubleDouble],
259    dot: impl Fn(&[DoubleDouble], &[DoubleDouble]) -> DoubleDouble,
260) {
261    let (nr, nc) = (l.rows, l.cols);
262    for j in (0..nc).rev() {
263        let o = solve_offset(skip, j);
264        let col = &l.data[j * nr..(j + 1) * nr];
265        let a = dot(&col[o..nc], &y[o..nc]);
266        let b = dot(&col[nc..], &y[nc..]);
267        y[j] -= a + b;
268    }
269}
270
271/// Step K4.
272#[inline(always)] // into `pulp`'s `vectorize` (Chapter 11.6)
273#[allow(clippy::inline_always)]
274fn trsm_plain<U: ColumnUpdate>(
275    update: U,
276    n: usize,
277    l: &DenseBlock<DoubleDouble>,
278    b: &mut DenseBlock<DoubleDouble>,
279) {
280    for col in b.data.chunks_exact_mut(n.max(1)).take(b.cols) {
281        for k in 0..n {
282            let x = col[k] / l.get(k, k);
283            col[k] = x;
284            update.column_sub(&mut col[k + 1..], &l.data[k + 1 + k * n..(k + 1) * n], x);
285        }
286    }
287}
288
289impl DenseKernel<DoubleDouble> for DdDense {
290    fn potrf(&self, a: &mut DenseBlock<DoubleDouble>) -> Result<(), DenseError> {
291        let Some(n) = square(a) else {
292            return Err(DenseError::Dimension);
293        };
294        dispatch!(|lanes| potrf_columns(lanes, n, a));
295        potrf_columns(Reference, n, a)
296    }
297
298    fn sytrf(
299        &self,
300        a: &mut DenseBlock<DoubleDouble>,
301        perm: &mut Perm,
302        pivot_2x2: &mut Vec<bool>,
303    ) -> Result<Inertia, DenseError> {
304        NaiveDense.sytrf(a, perm, pivot_2x2)
305    }
306
307    fn trsm_lower(
308        &self,
309        l: &DenseBlock<DoubleDouble>,
310        b: &mut DenseBlock<DoubleDouble>,
311        transpose: bool,
312    ) {
313        let n = square(l).expect("trsm_lower: L must be square");
314        assert!(is_consistent(b), "trsm_lower: B is inconsistent");
315        if transpose {
316            assert_eq!(b.cols, n, "trsm_lower: B must have n columns");
317            dispatch!(|lanes| trsm_transposed(lanes, n, l, b));
318            trsm_transposed(Reference, n, l, b);
319        } else {
320            assert_eq!(b.rows, n, "trsm_lower: B must have n rows");
321            dispatch!(|lanes| trsm_plain(lanes, n, l, b));
322            trsm_plain(Reference, n, l, b);
323        }
324    }
325
326    fn gemm_sub(
327        &self,
328        a: &DenseBlock<DoubleDouble>,
329        b: &DenseBlock<DoubleDouble>,
330        c: &mut DenseBlock<DoubleDouble>,
331    ) {
332        assert!(
333            is_consistent(a)
334                && is_consistent(b)
335                && is_consistent(c)
336                && a.cols == b.cols
337                && c.rows == a.rows
338                && c.cols == b.rows,
339            "gemm_sub: dimensions do not agree"
340        );
341        let (m, k, n) = (a.rows, a.cols, b.rows);
342        dispatch!(
343            |lanes| gemm_blocked(lanes, m, k, &a.data, &mut c.data, |j, l| b.data[j + l * n])
344        );
345        gemm_blocked(Reference, m, k, &a.data, &mut c.data, |j, l| {
346            b.data[j + l * n]
347        });
348    }
349
350    fn syrk_sub(&self, a: &DenseBlock<DoubleDouble>, c: &mut DenseBlock<DoubleDouble>) {
351        let n = square(c).expect("syrk_sub: C must be square");
352        assert!(
353            is_consistent(a) && a.rows == n,
354            "syrk_sub: dimensions do not agree"
355        );
356        dispatch!(|lanes| syrk(lanes, n, a, c));
357        syrk(Reference, n, a, c);
358    }
359
360    fn name(&self) -> &'static str {
361        "dd"
362    }
363
364    fn solve_min_rows(&self) -> usize {
365        SOLVE_MIN_ROWS
366    }
367
368    fn solve_unit_lower(
369        &self,
370        l: &DenseBlock<DoubleDouble>,
371        skip: &[bool],
372        y: &mut [DoubleDouble],
373    ) {
374        check_solve(l, skip, y);
375        dispatch!(|lanes| solve_forward(lanes, l, skip, y));
376        solve_forward(Reference, l, skip, y);
377    }
378
379    fn solve_unit_lower_t(
380        &self,
381        l: &DenseBlock<DoubleDouble>,
382        skip: &[bool],
383        y: &mut [DoubleDouble],
384    ) {
385        check_solve(l, skip, y);
386        dispatch!(|lanes| solve_backward(l, skip, y, |a, b| crate::simd::dot4(lanes, a, b)));
387        solve_backward(l, skip, y, crate::kernels::reference::dot4);
388    }
389}