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}